[HN Gopher] Ask HN: Why is this Racket code so fast?
___________________________________________________________________
Ask HN: Why is this Racket code so fast?
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
Author : exdsq
Score : 16 points
Date : 2022-04-03 17:06 UTC (5 hours ago)
| whateveracct wrote:
| Doesn't Racket run on Chez Scheme now? I'd read up on that. It's
| a famously performance-oriented Scheme implementation.
| exdsq wrote:
| 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!
| fiddlerwoaroof wrote:
| If it's running in Chez, it's probably compiled: chez, sbcl
| and other lisps often compile everything before executing it.
| fiddlerwoaroof wrote:
| > 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.
| rurban wrote:
| Chez is comparable to v8 in speed
| eurasiantiger wrote:
| OP could port the code to Node.js to see if that holds.
| pubby wrote:
| I believe racket/stream uses memoization. So it should be as fast
| as any memoized fibbonaci function.
| rajandatta wrote:
| I don't believe Racket uses Memoization automatically. You can
| certainly use it easily enough but that's a user decision.
| exdsq wrote:
| I'll have to test this because it's much faster than I remember
| Python achieving with memoization.
| sgtnoodle wrote:
| Presumably python is 10-100 times slower than compiled
| machine code, so that's not too surprising?
| exdsq wrote:
| 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 :)
| Jtsummers wrote:
| 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.
| exdsq wrote:
| 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 :)
| Jtsummers wrote:
| 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.
| exdsq wrote:
| I appreciate it, thanks!
| km6GEwiQqsyEKQH wrote:
| 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.)
| exdsq wrote:
| 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!
___________________________________________________________________
(page generated 2022-04-03 23:02 UTC)