Ask HN: Why is this Racket code so fast? | Hacker News Reader

Ask HN: Why is this Racket code so fast?

30 pointsexdsq27 comments

I was completing some of the Project Euler problems in Racket and usually see the Fibonacci sequence take a couple seconds to generate. While showing my wife I tried a number greater than 4,000,000 and it was instant, so I tried again and again and again, up to a 1,000,000 digit number that took 70 seconds. 10^10000 is still around 100ms.

Can anyone explain how this code is so quick? Running it on a Mac M1 Pro (2021).

https://github.com/Mithaecus/cp-project-euler/blob/main/answers/0002.rkt

https://github.com/Mithaecus/cp-project-euler/blob/main/answers/_solution.rkt

View on HN

  lim = 10**1000000
  a, b = 1, 2
  acc = 0
  while a < lim:
      if not a & 1:
          acc += a
      a, b = b, (a + b)
  print("done", flush=True)
  print(acc)

For a baseline this trivial python implementation does it in 34 ms for 10^10000 and 2m55 for 10^1,000,000 on a ryzen 5. Because the fibonacci sequence is increasing roughly exponentially, the iteration count scales roughly linearly to the number of digits. Then it just goes down to the number crunching speed of the bignum implementation? (Calculating the exponent also takes multiple seconds, as well formatting the number to a string takes around 10 seconds as well.)

Thanks for the comparison :) I'm plotting the racket implementation over input size to see how it performs over input size - it feels slightly more sharply curved than linear but you may very well be correct!

If you benchmark the solution, remember to do it in the terminal using the command line version `racket`.

With default settings DrRacket will add extra debug code to the program, which will slow it down.

racket/stream is lazy, so you only ever generate values when they're directly asked for, and in this case they get discarded almost immediately. This means that the two sequences (fibonacci-sequence and even-fibonacci-sequence) use very little memory at any one point in time. If you switched from a lazy stream approach to a naive approach generating every single Fibonacci number below the threshold and then filtering and then summing, you'd see much worse performance. By using a lazy stream approach you end up with something that should be roughly comparable to this C-ish pseudocode, but still has the appearance of the functional map/filter/reduce style:

  threshold = whatever;
  accum = 0;
  for (a = 0, b = 0; a <= threshold; a, b = b, a + b) { // parallel assignment invalid in C, thus pseudocode
    if (a % 2 == 0) accum += a;
  }
  return accum;

Untested, so assuming no errors in my pseudocode. Note how this only ever has two values of the Fibonacci sequence in memory at any one point in time. The lazy stream version should be equivalent to this since it's only when you actually ask for an element of the even Fibonacci numbers that anything should be generated at all from either sequence.

Also, there is a shortcut to generate only the even Fibonacci numbers. Should reduce your execution time by a bit. Since the even Fibonacci numbers are every 3rd entry, this means you can cut out 2/3rds of the generated values and the conditional checking if a value is even or not.

I guess I'm surprised at the speed of lazy streams then - usually I just pre-generate the fib sequence if I need it and then filter/aggregate as you mention. Probably slightly embarrassing I've only just discovered their power after several years working in software development :)

This is basically the way that Haskell and other lazy languages work, but also generators in Python and other languages. They're often implemented using something like coroutines or closures in languages that aren't lazy (by default), or perhaps with classes and objects.

For instance, in Common Lisp you might do something like this (I'm too rusty on Racket to write it up properly) as a kind of poor man's generator/iterator/stream:

  (defun new-fib-sequence ()
    (let ((a 0) (b 1))
      (lambda ()
        (shiftf a b (+ a b))))) ;; CL detail, permits parallel assignment and returns the value of the first item *before* assignment

(untested, should work) and then you can repeatedly use apply or funcall (so not as clean as Scheme or Racket as lisp-1s) to generate the sequence)

  > (let ((fib (new-fib-sequence))
    (loop repeat 3 do (print (funcall fib))))
  0
  1
  1

racket/stream just gives you all this without the manual elements that I'm doing here. There are libraries in CL that give you all of this, too, but I figured an illustration of what's happening behind the scenes would be useful.

I appreciate it, thanks!

NP. By the way, for grins I altered my program to generate only even Fibonacci numbers. I was seeing approximately 30% improvements, though I think you will see bigger improvements as you get to much larger numbers than I was testing on (on a cheap VPS box with 1 core and 4GB of RAM so I didn't really feel like stressing it too much because it was slow enough already).

The changed recurrence relation is:

  EF(N) = Nth Even Fibonacci Numbers

  EF(N) = 4 * EF(N-1) + EF(N)
  EF(0) = 0, EF(1) = 2

This skips the generation of odd Fibonacci numbers and removes the need for the filtering step (if even then add to accumulator), but it adds in the multiplication which seems to reduce some of the potential performance gains. Once you get to the point that you're dealing with big numbers, addition becomes very expensive and, depending on how multiplication is implemented, you ought to get a larger performance boost as you get to very large numbers.

Multiplication is more efficient than addition? That’s surprising! I assumed multiplication would be built at least partially from addition when you’re at the lowest levels of the stack

Well, in this case because we also eliminate several additions. For each even Fibonacci number you have to perform multiple additions in the naive approach (generate all, filter):

  F(0) = 0
  F(1) = 1
  F(2) = 1 + 0
  F(3) = 1 + 1 = 2 (2 additions to get here)
  F(4) = 2 + 1 = 3
  F(5) = 3 + 2 = 5
  F(6) = 5 + 3 = 8 (3 more additions to get here, and 3 for each subsequent one)

With the faster version you have one multiplication and one addition (2 operations) versus 3 additions. The 3 additions naive version also has a branch that has been eliminated by just generating the even elements.

  EF(0) = 0
  EF(1) = 2
  EF(2) = 4 * 2 + 0 = 8 (1 mul, 1 add)
  EF(3) = 4 * 8 + 2 = 34 (1 mul, 1 add)

This is why I was getting about a 30% improvement in performance, it's performing one less op (the branch itself isn't too expensive in comparison so with large numbers it's a minor cost).

Gotcha! Thanks for all your informed answers.

10^10000 is a large number, but it is surpassed only by the 47,852th Fibonacci number -- a small number of iterations for a computer.

I often suppose as a rule of thumb that a C program can perform ~10 million for-loop additions per second (assuming the accumulator fits in a register). So to do 500,000 bignum additions/second, each bignum addition would only require on average the time of 20 normal additions+iterations.

Also note that the functions provided are all tail recursive. Racket performs tail-call optimizations which would make these similarly performant to a for loop.

I think the trick here is tail recursion optimization and comparing with other recursive solutions in languages that don’t have that

Doesn't Racket run on Chez Scheme now? I'd read up on that. It's a famously performance-oriented Scheme implementation.

Thanks! Whatever this is far faster than I've seen in other non-compiled languages. If it holds up like this I might actually use it for small projects in the future!

If it’s running in Chez, it’s probably compiled: chez, sbcl and other lisps often compile everything before executing it.

> Chez Scheme compiles source forms as it sees them to machine code before evaluating them, i.e., "just in time."

https://cisco.github.io/ChezScheme/csug9.5/use.html

There is no such thing as a “compiled language”: some languages are implemented as compilers and some as interpreters, but nothing prevents writing a compiler for most languages.

While this is technically true, it's possible for a language to be so mismatched to the underlying architecture, and so difficult to reason about, that the "compiled" version is not much better than an interpreter bundled with the source code.

Chez is comparable to v8 in speed

OP could port the code to Node.js to see if that holds.

Racket compiles the program to machine code before it is run.

I believe racket/stream uses memoization. So it should be as fast as any memoized fibbonaci function.

I'll have to test this because it's much faster than I remember Python achieving with memoization.

Presumably python is 10-100 times slower than compiled machine code, so that's not too surprising?

I'm not running compiled code, am I? If I just run 'racket ./filename.rkt' it's interpreted? This is why I'm so amazed - it's uncompiled code running at speeds I'd expect from C, not an 'academic' Lisp.

Edit: I see someone else describes how it compiles JIT so I see your point. Slightly less magic than I thought :)

In that case the file is first compiled then run.

You can compile it first with:

    racket make filename.rkt

And then run it:

     racket filename.rkt

I don't believe Racket uses Memoization automatically. You can certainly use it easily enough but that's a user decision.

Reply on news.ycombinator.com