JS Fibonacci Benchmarks
Just some comparisons of various programming techniques for computing the nth Fibonacci number
Requires node.js >= v7.0.0 (currently the nightly build) since that is the first version that supports tail-call optimization
Versions less than that will still run; however, the V8 engine won't optimize the tail-call recursion and you probably won't see an improvement for tailcall
Running
- (Optional) Install node.js >= v7.0.0 (At the time of this writing is a nightly build. The one that I used was
v7.0.0-nightly201608173177b99737
. It can be installed using nvm withNVM_NODEJS_ORG_MIRROR=https://nodejs.org/download/nightly nvm install v7.0.0-nightly201608173177b99737
) npm install
- (Optional)
npm test
ORnode --harmony test.js
to confirm that all fibs work npm start
ORnode --harmony run.js [FIB_NUMBER]
Implementations
iterative
: An iterative approach that you probably learned in a CS class after they told you the naive recursive approach was garbageiterativees6
: An iterative approach with an in-place swap using ES6 array destructuring assignment just to see if there were any optimizations for the swap (spoiler: there aren't)recursive
: The naive approach that y'all used when you were learning recursiontailcall
: A version that you may have seen in a functional programming class that uses a smarter recursion that can be optimized by some compilers/interpreters (in our case the V8 engine)memoized
: The first dynamic programming algorithm you were probably introduced to using a cache of previously computed steps to prevent duplicate workcomposed
: A simple memoization wrapper that wraps the naive recursive approach because higher-order functions are the bestclosedform
: The closed form function of the infinite series (Floating point precision is only precise enough to compute up to the 75th Fibonacci number)lookup
: Arguably the best implementation because it's just a lookup table/array and isO(1)
time and space (The nativeNumber
type in Javascript is only big enough to hold up to the 79th Fibonacci number which is reasonable to store in a table/array)
Results
These are the results that I got on my Macbook
$ node --harmony run.js 32
iterative x 763,905 ops/sec ±0.91% (84 runs sampled)
iterativees6 x 112,614 ops/sec ±1.16% (89 runs sampled)
recursive x 4.96 ops/sec ±6.74% (16 runs sampled)
composed x 1,031,719 ops/sec ±1.60% (82 runs sampled)
tailcall x 1,016,012 ops/sec ±1.04% (86 runs sampled)
memoized x 507,615 ops/sec ±1.05% (85 runs sampled)
closedform x 4,603,626 ops/sec ±1.15% (83 runs sampled)
lookup x 6,155,979 ops/sec ±0.96% (87 runs sampled)
Fastest is lookup
Obviously, the fastest was going to be lookup
, but what surprised me was that composed
was the third fastest—twice as fast as memoization
. Both use a similar strategy of caching previously computed values, but composed doing so in an outer, memoization function rather than directly in the main Fibonacci function. Another surprise to me was that tailcall
was nearly as fast as composed
—taking fourth place ahead of both iterative solutions.
Further Reading
Apparently I wasn't the first to get bored one day and test this stuff. @ericelliott did a similar thing with ES6 generators, and @devlucky wrote about the classic example (recursive/iterative/memoization) in more depth.