Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Node-fib: Fast non-blocking fibonacci server

github.com

Post reply on HN
Print view View original

81–90 of 124 posts

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

#81

Post by bunderbunder »

rbranson wrote: post #11
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...

Would be cheating, man. Micro-benchmarking is all about using fictitious tests to show off fake performance in blog posts.

Or, for that matter, using fictitious tests to show of fake lack-of-performance in blog posts.

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

#82

Post by tzs »

tlrobinson wrote: post #25
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.

That's actually pretty good. Double precision floating point (IEEE format, anyway), can represent all positive integers up to 9007199254740990, which takes you up to Fib(78), so the fact that you can get up to Fib(76) means you are getting close to the top. Good enough for most work.

After 9007199254740990, double precision only represents even integers. Fib(79) is odd, so can't be represented. Fib(80) would be representable though, as will be every other Fibonacci number for a while. Then comes a range where only multiples of 4 can be represented, and then a range with multiple of 8, and so on, so while there will be representable Fibonacci numbers in those ranges, more and more will be omitted.

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

#83

Post by burgerbrain »

DrHankPym wrote: post #79
burgerbrain wrote: post #67

Earlier quoted context omitted.

The issue is what happens when you write that CPU intensive task. If you do it in idiomatic Go, that same server will keep on responding to other requests in the meantime. With Node.js, that is not the case. You have to do things like, well, what this article does, to get it to work.

I'm still not getting it. Go might be able to handle an extra request or two for high CPU intensive tasks, but it will inevitably suffer the same consequence of locking all it's processes given enough requests. Still doing anything that is CPU intense on that layer is stupid in the first place.

A so called 'goroutine' locking up will not lock up the rest of that server. Other pages will still be served by that server. This has nothing to do with the efficiency of the underlying language, it has to do with Go doing cooperative multitasking transparently. It might as well be a separate process (in fact, for all you really know it could be).

The code seen here does cooperative multitasking explicitly. It is essentially explicitly specifying places where rescheduling can take place. The result is the same but with this Node code you are getting your hands far more dirty.

The point of the Cancer article is that since it (allegedly) is not made explicitly clear what is going on, programmers can deal far more damage to themselves than they would with other schemes.

I really don't know how to explain it any better than that.

PS: "cpu intensive" is relative. The fib example is a deliberate exaggeration of what you'd see in reality, to make the point trivial to observe.

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

#85

Post by logancapaldo »

Wilfred wrote: post #68
bascule wrote: post #32

Earlier quoted context omitted.

If I try to ask for a large number (say 1 million) I run out of RAM: $ node app.js FATAL ERROR: CALL_AND_RETRY_2 Allocation failed - process out of memory Somehow you're using O(n) RAM to do the calculation. Seems bad bro. This code is the epitome of roflscale

That's a consequence of memoisation. It scales better than the original code though. Still, the original point (node is cooperatively multitasked) was clear. Anything beyond that and I just want to reach for better Fibonacci algorithms.

And this is why, any cache without an eviction policy and/or size limitation is bad (and memoization _is_ a cache). I shudder every time I see a "magical" memoization function whose interface is just

   memo function-to-memoize

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

#86

Post by lamby »

fendrak wrote: post #29

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.

Perhaps if enough alternative implementations are submitted to HN it will drown out the silence on the actual issue that was raised.

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

#87

Post by mappu »

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...

By using a field extension over √5, you can evaluate this exactly without rounding or resorting to floating point.

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

#88

Post by marshray »

jerf wrote: post #17
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…

Yes, you too can by required by the compiler to implement cooperative multitasking by hand. In 2011. Yes. It is an answer to the criticism made, and I acknowledge that. But it is not a very good answer to the objection. The better answer is "don't do that in Node.js", which is still not all that great (it's really easy to accidentally write something that blocks badly), but is better.

Yes. It is an answer to the criticism made, and I acknowledge that.

It's an answer that says: "You're using the wrong tool for the job."

Which is particularly weird given that Fibonoacci itself is probably the most overused example of algorithm-to-promote-paradigm in computer science. Except it's for a different paradigm: recursion, not asynchronous IO.

Still, it's interesting in a recursive sort of way.

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

#90

Post by freshhawk »

InclinedPlane wrote: post #53
vogonj wrote: post #24

Earlier quoted context omitted.

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 pitch…

Personally I've never seen node.js pitched as a solution for newbies or sub-par coders toiling away in the enterprise trenches. I've always seen it marketed as a useful tool for people who know WTF they're doing.

Really? I've almost never seen node.js pitched to anyone other than newbies (although not in the enterprise trenches for sure).

Rarely the pitch involves being able to share libraries between the server side and browser side (wonderful benefit of node.js)

Most of the time it's being sold as "you already know javascript" or "it's super fast, because non-blocking is magic sauce!"

I haven't used Node.js for anything serious but the hype and especially the discussion around the now infamous node is cancer post sure makes it seem like Biilmann was correct when he said "For better or worse, Node is like the PHP of concurrency and ever so often worse is better"

Even if that's not true, if that demographic is the dominant users of and contributors to Node then that's what Node will become.

Post reply on HN