Writing fast arithmetic code on IronScheme

As some may have noticed, I have started actively working on IronScheme again. After a year of fiddling with other shit like microcontrollers and other hardware-related program, the itch for ‘bare-metal’ knowledge has finally subsided enough to let IronScheme take preference.

Also, the IronScheme source code is now under a BSD license. The DLR goodies stays on MSPL however, as moving it to the new Apache license DLR would be too much effort. Now for the rest of the post.

So the general feeling is that most ‘dynamic’ languages are pretty poor with number crunching. This is true, as code is mostly generic and have no static typing. The same goes for IronScheme, but you can make code (read hotspots) behave much better with only a little extra effort.

Let’s take the naive Fibonacci algorithm to use for this example.

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 2)) (fib (- n 1)))))

The main problem here is the usage of generic math operators. They are generally slow, as they cover the entire number hierarchy of Scheme. This can be improved by using the fixnum specific procedures.

(define fibf (lambda (n)
  (if (fx<? n 2)
      n
      (fx+ (fibf (fx- n 1)) (fibf (fx- n 2))))))

While the above run significantly faster (about 5 times faster), there is still quite a bit of overhead due to boxing of value types, and overflow checks. This can now be improved by using a statically typed variant of lambda called typed-lambda, and by using some ‘unsafe’ operators provided by IronScheme.

(define fibt (typed-lambda (n) ((Int32) Int32)
  (if ($fx<? n 2)
      n
      ($fx+ (fibt ($fx- n 1)) (fibt ($fx- n 2))))))

The above only requires minor changes again, that could be easily made transparent with a macro or 2. The result is a very fast procedure that runs optimally on .NET (when compared to the same code generated by the C# compiler). My tests show it running almost 13 times faster than the fixnum version and subsequently around 60 times faster than the original generic approach.

Here are timings for all of the above:

isc fibs.sps
Statistics for '(fib 35)':
  Real Time:  8357ms
  CPU Time:   8344ms
  User Time:  8344ms
  GC's:       0
Statistics for '(fibf 35)':
  Real Time:  1826ms
  CPU Time:   1828ms
  User Time:  1828ms
  GC's:       0
Statistics for '(fibt 35)':
  Real Time:  147ms
  CPU Time:   141ms
  User Time:  141ms
  GC's:       0 

Update:

On the same PC, IronPython 2.6 takes 3150ms for a naive fib.