glenjamin/node-fib

Fast non-blocking fibonacci server

node-fib

A little express server that gives you back whatever fibonacci number you ask for

Coming here from Hacker News?

Hello there! You've stumbled across a short script I wrote to see how effective a non-blocking implementation would be for the famous NodeJS cancer also known as calculating the fibonacci sequence recursively.

They key differences from the original algorithm are that process.nextTick is used agressively (probably too agressively), so ensure that the main event loop is not blocked. In addition, memoisation is used which is shared across concurrent and subsequent requests without having to worry about locking.

Obviously there are other algorithms to calculate the nth term of the fibonacci sequence, many of which will be more effective than this one (although I do like how easy it is to memoise this). Some people have already mentioned a few of these in the issues section. As this is a toy rather than a real project I'm unlikely to implement these improvements unless they sound particularly fun or I have some time to kill on a train.

I would encourage anyone with suggestions of improvements to have a go at them yourself, especially if you're not familiar with NodeJS - you may even like it. I would also encourage any similar implementations in non-reactor frameworks as a comparison of the relative merits and disadvantages of event loops vs threads.

Usage

node app.js &
curl localhost:3000/40

Replace 40 with whatever fibonacci number you want

Why?

To point out that implementation of whatever you're doing is far more important than which framework you're using, or whether you're using threads or an event loop to handle concurrency.

Is it any good?

Yes.

> ab -n 10000 -c 50 'http://127.0.0.1:3000/100'
This is ApacheBench, Version 2.3 <$Revision: 655654 $>
Copyright 1996 Adam Twiss, Zeus Technology Ltd, http://www.zeustech.net/
Licensed to The Apache Software Foundation, http://www.apache.org/

Benchmarking 127.0.0.1 (be patient)
Completed 1000 requests
Completed 2000 requests
Completed 3000 requests
Completed 4000 requests
Completed 5000 requests
Completed 6000 requests
Completed 7000 requests
Completed 8000 requests
Completed 9000 requests
Completed 10000 requests
Finished 10000 requests


Server Software:
Server Hostname:        127.0.0.1
Server Port:            3000

Document Path:          /100
Document Length:        21 bytes

Concurrency Level:      50
Time taken for tests:   2.114 seconds
Complete requests:      10000
Failed requests:        0
Write errors:           0
Total transferred:      1420000 bytes
HTML transferred:       210000 bytes
Requests per second:    4731.49 [#/sec] (mean)
Time per request:       10.568 [ms] (mean)
Time per request:       0.211 [ms] (mean, across all concurrent requests)
Transfer rate:          656.12 [Kbytes/sec] received

Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        0    0   0.3      0       5
Processing:     2   10   3.0     10      28
Waiting:        2   10   3.0     10      28
Total:          3   10   3.0     10      28

Percentage of the requests served within a certain time (ms)
  50%     10
  66%     11
  75%     12
  80%     13
  90%     14
  95%     15
  98%     18
  99%     20
 100%     28 (longest request)

Related

Derivative project in python-twisted: https://github.com/zed/txfib

node-fib's Issues

Cannot calculate 1,000,000th Fibonacci number

This crashes node-fib:

$ time curl localhost:3000/1000000
curl: (52) Empty reply from server

real    1m0.392s
user 0m0.006s
sys 0m0.004s

It appears it ran out of memory:

$ node app.js 
FATAL ERROR: CALL_AND_RETRY_2 Allocation failed - process out of memory

Memoize results in an LRU cache

For optimum performance, the server should use node-lru-cache to memoize the results of each calculation in a lru cache. (npm install lru-cache is a pretty well tested O(1) implementation.)

Should use closed-form fibonacci function

It would be much more performant to calculate the fibonacci number like so:

function fib (n) {
  var a=1
    , b=0
  while (0 > n--) {
    var c = b
    b = b + a
    a = c
  }
  return b
}

Perhaps it might make sense to add this as a separate endpoint?

fewer dependencies

Perhaps some code like this with fewer dependencies (and less memory used) could work.
For 1000000 it returns Infinity, for 1000 it returns 2.686381002448534e+208 in 0.071s

function fibonacci(nfib, cb) {
  function fib(n1, n2, n, cb) {
    if(n > nfib) return cb(n2)
    process.nextTick(function() { fib(n2, n1 + n2, n + 1, cb) })
  }
  switch(nfib) {
    case 1: cb(0); break
    case 2: cb(1); break
    default: fib(0, 1, 3, cb)
  }
}

// usage example
// first arg is fibonacci number, 1-based
fibonacci(3, function(res) { console.log('fibonacci number is ', res) })

Get a clue by actually understanding the OPs point

Missing LICENSE.txt?

...a permissive license, I hope?

Improve ten-fold by knowing math

O(log n)

phi = (1 + Math.sqrt(5)) / 2
fibonacci = (n) -> Math.floor(Math.pow(phi, n) / Math.sqrt(5) + 1/2)
fibonacci(10) # => 55