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.

- S9R's strength is symbolic computation. It is in the same ballpark as Chicken Scheme here and almost twice as fast as MIT Scheme.
- S9R's weakness is numeric computation. Integer computations are half as fast as Chicken or MIT Scheme's and real number computations are easily slower by an order of magnitude.
- Continuations work properly in all cases now, but are expensive due to the lack of CPS conversion.

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.

**R**= Scheme 9 from Empty Space, Reimagined, 2018-10-22**O**= Scheme 9 from Empty Space, Old version, 2018-08-23**M**= MIT Scheme 9.2, 2014-05-17**C**= Chicken Scheme 4.13.0, 2017-12-11

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.