2018-10-23
Scheme 9 from Empty Space used to be one of the slower Scheme systems. Changing this has been on my to-do list for a long time. In the past months, I finally found the resources to work on it.
The result is called Scheme 9 from Empty Space, Reimagined. Here is a summary of its performance.
Here is a quick summary of the benchmark results, normalized to various systems. A result to the left of the 1× column is faster than the "normal" system and a result to the right is 2×, 3×, etc slower. A result in the middle of the 0.× column would be about twice as fast as the "normal" system.
A description of the benchmarks can be found below.
| 0.× | 1× | 2× | 3× | 4× | 5× | >6× | |
| ACK | -----CM--- | R--------O | ---------- | ---------- | ---------- | ---------- | |
| ARRAY1 | -------C-M | R--------- | -------O-- | ---------- | ---------- | ---------- | |
| BLANK | ---------C | RO-------- | ---------- | ---------- | ---------- | ---------- | --- M 18.0× |
| BOYER | ---------C | R--------M | ---------- | ---------- | ----O----- | ---------- | |
| CAT | -------C-- | R-----M--- | ---------- | --------O- | ---------- | ---------- | |
| COMP | ------C--- | R--------- | ---------- | -MO------- | ---------- | ---------- | |
| CPSTAK | -------M-- | R--------C | ---------- | O--------- | ---------- | ---------- | |
| CTAK | --CO----M- | R--------- | ---------- | ---------- | ---------- | ---------- | |
| FFT | CM-------- | R-O------- | ---------- | ---------- | ---------- | ---------- | |
| FIB | ---CM----- | R--------O | ---------- | ---------- | ---------- | ---------- | |
| GCTEST | ----MC---- | R--------- | ---------- | ---------- | -------O-- | ---------- | |
| LTAK | ---------- | R-C------- | ---M------ | ---------- | ---------- | ---------O | |
| STRING | -----C---M | RO-------- | ---------- | ---------- | ---------- | ---------- | |
| TAK | ----C--M-- | R--------- | -O-------- | ---------- | ---------- | ---------- |
| 0.× | 1× | 2× | 3× | |
| ACK | -----R---- | O--------- | ---------- | ---------- |
| ARRAY1 | ----R----- | O--------- | ---------- | ---------- |
| BLANK | ---------- | OR-------- | ---------- | ---------- |
| BOYER | --R------- | O--------- | ---------- | ---------- |
| CAT | ---R------ | O--------- | ---------- | ---------- |
| COMP | -----R---- | O--------- | ---------- | ---------- |
| CPSTAK | ---R------ | O--------- | ---------- | ---------- |
| CTAK | ---------- | O--------- | ---------- | --------R- |
| FFT | --------R- | O--------- | ---------- | ---------- |
| FIB | -----R---- | O--------- | ---------- | ---------- |
| GCTEST | --R------- | O--------- | ---------- | ---------- |
| LTAK | -R-------- | O--------- | ---------- | ---------- |
| STRING | ---------R | O--------- | ---------- | ---------- |
| TAK | -----R---- | O--------- | ---------- | ---------- |
| 0.× | 1× | 2× | >3× | |
| ACK | ---------- | M------R-- | ---------- | |
| ARRAY1 | ---------- | MR-------- | ---------- | |
| BLANK | R--------- | M--------- | ---------- | |
| BOYER | -----R---- | M--------- | ---------- | |
| CAT | ------R--- | M--------- | ---------- | |
| COMP | -----R---- | M--------- | ---------- | |
| CPSTAK | ---------- | M---R----- | ---------- | |
| CTAK | ---------- | M-R------- | ---------- | |
| FFT | ---------- | M--------- | ---------- | --- R 9.0× |
| FIB | ---------- | M--------- | -----R---- | |
| GCTEST | ---------- | M--------- | ---R------ | |
| LTAK | ----R----- | M--------- | ---------- | |
| STRING | ---------- | MR-------- | ---------- | |
| TAK | ---------- | M---R----- | ---------- |
| 0.× | 1× | 2× | 3× | >4× | |
| ACK | ---------- | C--------- | --R------- | ---------- | |
| ARRAY1 | ---------- | C----R---- | ---------- | ---------- | |
| BLANK | ---------- | CR-------- | ---------- | ---------- | |
| BOYER | ---------- | CR-------- | ---------- | ---------- | |
| CAT | ---------- | C---R----- | ---------- | ---------- | |
| COMP | ---------- | C------R-- | ---------- | ---------- | |
| CPSTAK | -----R---- | C--------- | ---------- | ---------- | |
| CTAK | ---------- | C--------- | ---------- | ---------- | --- R 5.5× |
| FFT | ---------- | C--------- | ---------- | ---------- | --- R 25.0× |
| FIB | ---------- | C--------- | ---------- | --------R- | |
| GCTEST | ---------- | C--------- | R--------- | ---------- | |
| LTAK | ---------R | C--------- | ---------- | ---------- | |
| STRING | ---------- | C--------- | --R------- | ---------- | |
| TAK | ---------- | C--------- | -------R-- | ---------- |
Of course, the usual caveats regarding benchmarks apply. I have run the test three times and taken the mean. The test hardware was a Dell E6410 with a Core i5 CPU running at 750MHz. Feel free to download the benchmark scripts and programs (scmbench.tgz) to conduct your own experiments.
C=5.88s M=7.53s R=12.94s O=24.92s
Compute the Ackermann function (ack 3 8). Measures
recursion, tail recursion, and integer computations. S9R
is much faster than the old S9 here, but not really in the league
of Chicken or MIT Scheme, most probably due to the numeric part.
C=6.14s M=8.64s R=9.38s O=25.61s
Create and fill 2-dimensional arrays of various sizes. Measures vector creation and mutation. S9R is almost as fast as MIT Scheme here, but much slower than Chicken. Again, this is most probably due to the integer computations involved.
C=0.01s O=0.01s R=0.01s M=0.18s
Load a blank file. Measures start-up speed. No big differences here, except for MIT Scheme which takes its time. Note that both S9 versions run with a minimal image, which includes just the R4RS procedures. With a full image (including all extensions), S9R takes 0.02 seconds.
C=12.08s R=13.13s M=24.90s O=57.72s
Logic programming benchmark. Measures typical list operations and control constructs. When no numeric computations are involved, S9 Reimagined is about as fast as Chicken and almost twice as fast as MIT Scheme.
C=10.15s R=14.43s M=23.40s O=54.45s
Copy a file 512KB file character by character. Measures character-based I/O. Even here S9R is quite a bit faster than MIT Scheme and reaches 2/3 of the speed of Chicken.
C=1.52s R=2.52s M=5.49s O=5.56s
Compile 300K bytes (14250 lines) of Scheme code. Measures compilation speed. To be honest, the S9R compiler is not that fast with a full image, because the reader will slow down when the symbol table fills up (where 3.5 would be a more realistic value). Not bad, though! And: Kudos to the Chicken folks: almost 10k lines per second is impressive!
M=2.79s R=3.78s C=6.98s O=11.38s
Takeuchi function using continuation passing, (tak 18 12 6).
Measures tail calls. S9R does not look too shabby here.
C=0.89s O=1.24s M=4.02s R=4.86s
Takeuchi function using call-with-current-continuation,
(tak 18 12 6). Measures continuations. In fact S9R
performs a bit worse than displayed here, depending on the size of the
runtime stack, which is copies each time a continuations is
captured or called. Don't use continuations in S9 unless you
have to!
Note: the original S9 is much faster, but its implementation of continuations is limited.
Note 2: when using S9R's catch/throw
mechanism instead of call/cc, the CTAK benchmark takes
only 0.45 seconds.
C=0.67s M=1.74s R=15.77s O=19.36s
Fast Fourier transform. Measures real number performance. Don't do your number crunching in Scheme 9, obviously. (That being said, I use it for basic statistics and curve fitting, where it works fine.)
C=3.80s M=5.96s R=14.83s O=27.96s
Compute the Fibonacci function (fib 30). Measures (fat)
recursion and integer computation. It's the numeric stuff that slows
down S9 again.
M=3.19s C=3.76s R=7.36s O=34.32s
Garbage collector stress test. Allocates a very deep (1e6) list structure. Great improvement over the original S9. GC performance is really okay in S9R. Again, it's the numbers that drag it down.
R=7.92s C=9.07s M=18.09s O=46.84s
Takeuchi function using lists as numbers, (tak 18 12 6).
Measures recursion and tail recursion. With the numbers out of the way,
S9R looks pretty good! Almost 6× faster than the old
implementation.
C=0.65s M=1.39s R=1.42s O=1.62s
Concatenate and decompose strings. In fact, this is a garbage collector test more than a string operation test. No big differences here, only Chicken Scheme likes to show off.
C=1.05s M=1.98s R=2.83s O=6.19s
Compute the Takeuchi function (tak 18 12 6). Measures
recursion, tail recursion, and integer computation. Interestingly,
S9R is almost in the same ballpark as MIT Scheme here.