Posted by: leppie | December 2, 2010

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.


Responses

  1. Its nice that you started hacking again. Are you planning to convert the ironscheme solution to VS 2010?

    • Thanks :)

      I will convert to VS2010 once SP1 is out. It has a showstopper bug that has been fixed, but not released.

  2. Cool! By the way, have you seen common-lisp way to type code?

    (defun fib (n)
    (declare (fixnum n))
    (if (< n 2) n
    (+ (fib (- n 2))
    (fib (- n 1)))))

    And kind of type-inferrer will automatically found all he can.
    However, cl-spec says, that implementation may ignore declares.
    But cleverest common-lisp-compiler SBCL produces ultra-optimal code with right declarations, sometimes compared even with C.

  3. Glad to see work starting on this again.

    I’m fascinated by Clojure (and lisp/scheme in general), but I don’t have the time to get to know the Java libraries to make use of it. My day job is C#, so if I can use IronScheme with the .Net libraries I’ll be very happy!


Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: