Node-fib: Fast non-blocking fibonacci server • Hacker News Board

Re: Node-fib: Fast non-blocking fibonacci server

#21

Post by bascule » Mon, Oct 03, 2011, 7:22 PM UTC

Hmmm...

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

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

This actually crashes the server because it runs out of memory:

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

Re: Node-fib: Fast non-blocking fibonacci server

#22

Post by robinhouston » Mon, Oct 03, 2011, 7:27 PM UTC

callahad wrote: post #5

I wonder why I don't often see folks directly computing Fib(n) using the equation given in SICP exercise 1.13: Fib(n) = round(φ^n / sqrt(5)), where φ = (1 + sqrt(5)) / 2. Cites: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html... https://secure.wikimedia.org/wikipedia/en/wiki/Fibonacci_num...

It’s tangential to this thread, but since it’s a topic close to my heart:

If you just implement this formula using doubles then it only gives the correct answer for input values up to about 70. Yes it’s pretty fast, but a static table of the first 70 Fibonacci numbers would be even faster. If you’re only interested in the first few dozen Fibonacci numbers then it doesn’t really matter what algorithm you use, as long as it isn’t naive recursion.

If you want to get correct answers for larger Fibonacci numbers, you need to work harder to use this equation. You need some sort of multiple-precision floating point arithmetic library, for example.

And once you’ve done that, the resulting algorithm is quite a lot slower than the best integer methods.

I wrote a big blog post about this back in July: http://bosker.wordpress.com/2011/07/27/computing-fibonacci-n...

Re: Node-fib: Fast non-blocking fibonacci server

#23

Post by knieveltech » Mon, Oct 03, 2011, 7:30 PM UTC

rkalla wrote: post #20

As much as this whole Ted-gate thing has turned into a amped up argument of sorts, there has been a significant amount of knowledge for everyone shaken out of the trees about node.js as a result. Take for example this implementation, how many people getting started with node knew about async or memoization? Could be just me, but I learned a lot about what not to do and how to do certain things more efficiently with n…

Aahz's law

   The best way to get information on Usenet is not to ask a
   question, but to post the wrong information.

Re: Node-fib: Fast non-blocking fibonacci server

#24

Post by vogonj » Mon, Oct 03, 2011, 7:30 PM UTC

glenjamin wrote: post #8

Author here, didn't really expect this to get picked up anywhere but since it has I'd like to point out the idea was to demonstrate that computationally expensive algorithms can be split across multiple iterations of the event loop to avoid blocking it. In this case concurrent requests take advantage of each others' memoisation, which would be somewhat trickier to do with threads as you'd probably need to worry about…

you realize that you're just making Ted's point for him from the opposite direction, right?

his point, when you look behind the trolling, is that node.js is not magical special sauce and that shitty coders who write poorly-scaling code will be shitty coders who write poorly-scaling code no matter what technology they use -- the "cancerous" properties of node arise simply because of the amount of groupthink that pitches the Next Big Thing as intrinsically better than everything that came before it.

Re: Node-fib: Fast non-blocking fibonacci server

#25

Post by tlrobinson » Mon, Oct 03, 2011, 7:30 PM UTC

callahad wrote: post #5

I wonder why I don't often see folks directly computing Fib(n) using the equation given in SICP exercise 1.13: Fib(n) = round(φ^n / sqrt(5)), where φ = (1 + sqrt(5)) / 2. Cites: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html... https://secure.wikimedia.org/wikipedia/en/wiki/Fibonacci_num...

I just tried this:

    Math.round(Math.pow((1 + Math.sqrt(5))/2, n) / Math.sqrt(5))

But it starts returning incorrect results at fib(76), presumably due to floating point calculations lacking enough precision.

Re: Node-fib: Fast non-blocking fibonacci server

#26

Post by jules » Mon, Oct 03, 2011, 7:32 PM UTC

callahad wrote: post #5

I wonder why I don't often see folks directly computing Fib(n) using the equation given in SICP exercise 1.13: Fib(n) = round(φ^n / sqrt(5)), where φ = (1 + sqrt(5)) / 2. Cites: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html... https://secure.wikimedia.org/wikipedia/en/wiki/Fibonacci_num...

That formula fails for fib(71) with double precision floating point arithmetic:

    In [1]: def fib(n):
       ...:     a,b = 0,1
       ...:     for i in range(0,n): a,b = b,a+b
       ...:     return a
       ...: 

    In [2]: def fib2(n):
       ...:     phi = (1+sqrt(5))/2
       ...:     return round(phi**n / sqrt(5))
       ...: 

    In [3]: fib2(71)
    Out[3]: 308061521170130.0

    In [4]: fib(71)
    Out[4]: 308061521170129L

And it's not that the latter is not exactly representable as a floating point number:

    In [5]: float(_)
    Out[5]: 308061521170129.0

So you'd have to use bigger precision numbers. How many digits are you going to use? You have to use enough not to produce a wrong result and not too many to slow down the algorithm. I bet that the resulting algorithm is slower than the standard [1 1; 1 0]^n matrix exponentiation. Note that your formula comes from the eigenvalue expansion of this matrix exponentiation, which -- despite what you might hear from undergraduate linear algebra courses -- is not a good method for matrix exponentiation. On the contrary, finding eigenvalues is done by a process analogous to matrix exponentiation: http://en.wikipedia.org/wiki/Power_iteration

Re: Node-fib: Fast non-blocking fibonacci server

#27

Post by flexd » Mon, Oct 03, 2011, 7:32 PM UTC

bascule wrote: post #21

Hmmm... $ time curl localhost:3000/1000000 curl: (52) Empty reply from server real 1m0.392s user 0m0.006s sys 0m0.004s This actually crashes the server because it runs out of memory: $ node app.js FATAL ERROR: CALL_AND_RETRY_2 Allocation failed - process out of memory

32bit or 62bit node? If 64bit did you specify it can use more ram than the 1.7GB that's the default setting?

You can up the limit by starting node with --max-old-space-size=

Re: Node-fib: Fast non-blocking fibonacci server

#28

Post by wmf » Mon, Oct 03, 2011, 7:33 PM UTC

mattlong wrote: post #12

Detrus wrote: post #9

Too bad the code is so nasty

How so? IMHO, it's an elegant demonstration of the async module.

Check out the Cilk version, which is not only concurrent but parallel as well: http://myxman.org/dp/node/182

I agree with jerf that either you shouldn't have to worry about splitting your computation at all or at least you should have syntactic sugar for it. The Node solution has much more noise than code.

Re: Node-fib: Fast non-blocking fibonacci server

#29

Post by fendrak » Mon, Oct 03, 2011, 7:35 PM UTC

Is it just me, or have all these implementations of fast Fibonacci servers missed the original intent of the 'Cancer' article? As I read it, it was more of a commentary on giving novice concurrent programmers enough rope to hang themselves than on the capabilities of Node itself.

Re: Node-fib: Fast non-blocking fibonacci server

#30

Post by bascule » Mon, Oct 03, 2011, 7:40 PM UTC

flexd wrote: post #27

bascule wrote: post #21

Hmmm... $ time curl localhost:3000/1000000 curl: (52) Empty reply from server real 1m0.392s user 0m0.006s sys 0m0.004s This actually crashes the server because it runs out of memory: $ node app.js FATAL ERROR: CALL_AND_RETRY_2 Allocation failed - process out of memory

32bit or 62bit node? If 64bit did you specify it can use more ram than the 1.7GB that's the default setting? You can up the limit by starting node with --max-old-space-size=

Fibonacci isn't a kind of problem that should be bounded on RAM though. Something is fundamentally broken with the way this is implemented.