Making uLisp run faster – any suggestions?


#1

I’ve been thinking about ways of making the uLisp interpreter run faster.

uLisp’s code is very compact, and on most platforms it takes up a small fraction of the available program memory. For example:

Platform Usage
Arduino Zero (ATSAMD21) 28%
Adafruit Feather M4 (ATSAMD51) 13%
Adafruit ItsyBitsy nRF52840 12%

This offers the possibility of improving uLisp’s performance by taking advantage of the large amount of spare program memory. Ideally this should be done without requiring extra RAM, or totally rewriting the code.

One idea is to unwind loops where possible.

Done anyone have any other suggestions?


#2

You may try to find out (or measure) where (in which functions) the program stays for long times and which part of the program is called most, there may be profiling tools helping in this question.
These may be the places where optimizations have a large effect.
I think gcc has some features doing this, but I have no experience in using them. (GPROF and GCOV may help, but I read about it in a rather old book; there may be better / more modern helpers available).


#3

I actually think that “speeding up” is not aaaaall that important.

Kindly permit me a “philosophical” observation: everything you usually do on a machine demands “memory”. The “scarce” memory is the RAM, the “available” memory is the flash. If you could somehow “shift” the “memory burden” from the RAM into the flash, you will have freed more of the most precious resource. “How can one do that?” - Yeah, there are different ways, and this time I do not mean “virtual memory”. Rather, I mean “TYPICAL” operations. “Things a user would do”: compute mean and standard deviation of a range, compute calendar dates, etc.

Philosophically, “programming” is itself a “problem”. The most “typical” style of computation still takes place as in the 1940s: people sum up columns of numbers, compute interest, etc. For this, they use not the Manchester Mark I, but… Microsoft Excel or LibreOffice Calc or whatever. Every time you have to “enter into a loop” or a recursion - you “wager” whether you will actually come out of it. “Columns of numbers” seem, on the other hand, for about a century to “be the thing that people compute on”. Columns are “safe”. Programmers are focused on VARIABLES, and then they put lipstick on the pig by using “objects” and “functions” and whatnot. But “common people” use “something that works on columns of numbers”. (I have devised a system which I call 1V0 (I have been working on it like obsessed for the last month) which operates just on that - the “number column in memory” is quasi its prime target of operations.)

So where “copious” space is available, I advise creating and using “libraries of functions”, and perhaps even letting the user pick which to include at compile time.

Operations I am using in my system - I refer to memory ranges, but here I shall call them simply “lists” are e.g.:

  • add two lists, number by number;

  • divide two lists, without getting hysteric about division by zero and just giving 0 as return;

  • fill a list from a value on in steps with a value;

  • compute mean and standard deviation on a list;

  • I actually put a look-up-function in there to say “at what standard deviation a certain probability should be covered” and vice versa;

  • take the square root of a list;

  • divide a list by a number;

  • return the list with an area “zeroed”;

  • etc.

My system allows up to 63 functions total, and yes, 1V0 operates ONLY AND EXCLUSIVELY on numbers, whereas uLisp faces no such constraints.

I know that most of these suggestions are laughably easy to implement with a simple map or a simple apply. But AMATEURS (School kids? Their teachers? Their parents?) actually HATE the “fancy stuff to begin with”.

WHAT to implement? - Just google “the 100 most useful Excel functions”, you will find several works on that.

Of course, this will totally “blow up” the language reference, and hence I suggest not actually making these part of “core” uLisp, but making them part of “libraries”. @johnsondavies of course has already made MANY libraries available, particularly considering physical I/O and sensor reading, and whatnot. But I am having another “basic” view: I simply think the Arduino DUE or the BBC micro could be a very nice bookkeeping machine if properly configured.

What I thus propose for a basic design idea is to make to the user the following possible:

(fn … (f3 (f2 (f1 SOME-LIST)) …)

where these functions are aimed at fulfilling many of the most common tasks a user would normally perform.

It DOES require some design though, mind you. For instance, what do you do when you really compute mean and standard deviation of a list? Do you return just these two values? Is only one value returned, depending on the function? Is the original list to be returned, with these two values at the front?

Another question is, “how do you return MULTIPLE values”, and here, I actually have another “non-standard” proposal: “multiple-value-bind”, for instance, is ABSOLUTE TRASH for the novice. Seriously?! These people are afraid to even CALL a function, and you want them to handle its multiple values? - My “terrible” proposal is thus another: set certain pre-defined global variables to certain values.

In essence, the basic idea of my proposal is to let the user come as far as possible using one or two lists as arguments to a series of “stacked operations”, and to set, where necessary, certain (automatically generated?) global variables to certain values. The aim of the effort is to avoid any fancy “map apply …”, and to avoid looping.

If none of these ideas sound convincing, then the “easiest space-waster”, by the way, is a look-up-table. (Particularly as used in statistics for standard deviation and probability coverage.)


#4

A post was split to a new topic: Book about writing a Lisp interpreter


#5

@Aeneas I think what you’re describing is a library manager for uLisp, along the lines of Zach Beane’s Quicklisp for Common Lisp. To quote his summary:

Quicklisp is a library manager for Common Lisp. It works with your existing Common Lisp implementation to download, install, and load any of over 1,500 libraries with a few simple commands.

Since a uLisp implementation doesn’t necessarily have access to the Internet, perhaps the equivalent would be a library of packages on an SD card from which you could load what you needed on demand.

In fact the existing require function in uLisp could perhaps be extended to also work from an SD card.

The next question is how the library is compiled, but that could be a gradual process with users requesting useful functions, or contributing functions.

Have I understood you correctly?


#6

Good suggestion - thanks. David


#7

extending ([require) to work with files stored on a sdcard]

I’m not sure that this would be necessary, because we can simply load files containing Lisp code with a (load “filename”). This uLisp function is described in another thread and it works very well (-> ‘Loading and saving uLisp functions to a sdcard’), I use it often. A function to save all defined symbols is also available. This two functions can be defined in the lisp-library, so they are available at system-start.
So we “just” need the uLisp files and the user can copy them to a sdcard. We may create a storage (like the lisp-library) to make the files available and users can upload new code. A naming convention may be useful.


#8

I think this is something the compiler should deal with.
You may try setting the compiler optimization to higher levels (-O3) to make uLisp run faster. I think you’ll find these settings in the board.txt or platform.txt arduino files (arduino-xx/hardware/…).
For Teensy-4.1 this is available at the arduino ide, the difference between “Smallest Code” and “Fastest” is quite significant: (tak 18 12 6) needed between 430 to 550 milli seconds depending on this setting.
In general I wouldn’t care too much about uLisp speed, because

  • for most application it is fast enough
  • you’re supporting many different platforms; if the choosen platform is too slow for your project, use a faster one ;-)
  • of cause there are situations optimizations are necessary: my esp32 with 4MB workspace-size is one example, where I optimized some code (newsymbol(), don’t call gc() in repl (), optimized compactimage ()), I think this was useful because the code was optimized to platforms with tiny amount of RAM.
    Anyway I tried changing newsymbol () to return just a new symbol in any cases; the speed up for (tak 18 12 6) was just a few milli seconds (less than 1% for this example)…

I think one starting point for optimization are the loops going though the WORKSPACE_SIZE; only iterating about the used cells is needed in many cases (you may need some pointers to track usage).