Ask HN: Why is this Racket code so fast?
5 comments
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)
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.
With default settings DrRacket will add extra debug code to the program, which will slow it down.
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 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.
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 :)
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:
You can compile it first with:
racket make filename.rkt
racket filename.rktI don't believe Racket uses Memoization automatically. You can certainly use it easily enough but that's a user decision.
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:
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.
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;
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:
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
> (let ((fib (new-fib-sequence))
(loop repeat 3 do (print (funcall fib))))
0
1
1
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:
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
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)
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)
Gotcha! Thanks for all your informed answers.
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