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

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

#41

Post by masklinn » Mon, Oct 03, 2011, 7:58 PM UTC

glenjamin wrote: post #40

jerf wrote: post #17

Earlier quoted context omitted.

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.

Well the other option for computationally expensive code is to use some sort of worker that runs a sufficiently fast language. JavaScript on v8 is actually one of the fastest interpreted languages available, so unless you really need to drop down into C or similar, splitting across the event loop or using another node child process is not an unreasonable way to approach CPU heavy calculations.

> Well the other option for computationally expensive code is to use some sort of worker that runs a sufficiently fast language.

Which only helps if you know your code is going to be slow. If you somehow implemented an algorithm with a quadratic complexity and did not test for sufficiently large input, you might not realize what's going to happen before it hits production.

> JavaScript on v8 is actually one of the fastest interpreted languages available

1. Nobody is denying that.

2. The issue is with the behavior of evented systems in general and node in particular in case of in-request CPU-bound code paths, namely that the whole server blocks killing concurrency and basically DOSing the instance.

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

#42

Post by foca » Mon, Oct 03, 2011, 7:58 PM UTC

raganwald wrote: post #19

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

To answer your (possible rhetorical) question literally, the requirement here isn’t that it generate Fibonacci numbers efficiently, it’s that it implement the recursive algorithm efficiently. It’s true that another algorithm will be much faster, but that deprives us of the opportunity to discuss how this implementation of the recursive algorithm delivers much higher performance than a naïve implementation. The back s…

The specific point is that the evented model is not designed as a "one size fits all" solution. It's great for certain scenarios, not very good for certain others.

Basically, the original blog post tries to get to this, remarking on node.js is sold as if it was the silver bullet of web servers, that will scale to anything for anything you .

Of course, you can try to adapt most problems into something that would work in an evented model, but you have to know VERY WELL what you're doing.

IMO the solution is simple: polyglotism. Have parts of your app in node. Other parts in python. Others in ruby. Whatever works best for each specific small part :)

Node is not useless, but it's definitely not my choice to program everything and anything. Same thing with, for example, Rails :)

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

#43

Post by InclinedPlane » Mon, Oct 03, 2011, 7:59 PM UTC

  function fib(n)
  {
	var phi = (Math.sqrt(5) + 1)/2
	return Math.floor( Math.pow(phi, n)/Math.sqrt(5)+0.5)
  }

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

#44

Post by adgar » Mon, Oct 03, 2011, 8:00 PM UTC

InclinedPlane wrote: post #43

function fib(n) { var phi = (Math.sqrt(5) + 1)/2 return Math.floor( Math.pow(phi, n)/Math.sqrt(5)+0.5) }

Anyone know offhand what the minimum value of n is for which this fails due to floating point inaccuracies?

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

#45

Post by InclinedPlane » Mon, Oct 03, 2011, 8:04 PM UTC

adgar wrote: post #44

InclinedPlane wrote: post #43

function fib(n) { var phi = (Math.sqrt(5) + 1)/2 return Math.floor( Math.pow(phi, n)/Math.sqrt(5)+0.5) }

Anyone know offhand what the minimum value of n is for which this fails due to floating point inaccuracies?

Javascript doesn't have more than one number data type. This algorithm may fail earlier due to loss of precision from the way JS does exponentiation or sqrt or some such but even a purely additive method will fail due to floating point inaccuracies as well.

Edit: On an in-browser test with Chrome I get accurate values up to 75 with the closed form function and accurate values up to n=78 for the recursive / additive function.

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

#46

Post by glenjamin » Mon, Oct 03, 2011, 8:05 PM UTC

carllerche wrote: post #35

Instead of memoizing in the server you could memoize in the browser and use socket.io to ask connected browsers if they have a memoized value for a given fib number. That would get you around the limitations that bascule mentioned.

Now there's an idea! That could be rather fun...

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

#47

Post by jerf » Mon, Oct 03, 2011, 8:07 PM UTC

philjackson wrote: post #36

jerf wrote: post #17

Earlier quoted context omitted.

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.

"it's really easy to accidentally write something that blocks badly" What is this nonsense? Isn't it time we knock this one on the head? Let me let you into a secret: If you write CPU intensive enough code in any framework you can eventually block all further requests. This whole debate was based on FUD and a complete misunderstanding of what node is all about. Read the previous posts and don't post generic, bullshit…

"If you write CPU intensive enough code in any framework you can eventually block all further requests."

"Intensive enough" is a vague and fuzzy term which you can hide too much behind. So let me put it this way: Go grab Yaws, the Erlang web framework. Write a web page that goes into an infinite loop. Write some other web pages that work normally. Observe that visiting the infinite-loop web page once does not cause the rest of the web server to stop serving. Yaws may time it out eventually, too, not clear from a quick look at the docs. In fact it will only marginally decrease performance, even on single core machines.

Yes, if you bash on that page often enough you will eventually degrade service to an unacceptable level. But you will not bring down the whole server, or even that OS process, and it will take substantially more than one hit per process or one hit per core.

Now, go grab Node, and write a web page that goes into an infinite loop. You just brought that OS process down, from the user's point of view.

Node is qualitatively much easier to lock up an OS process with than Erlang. Or Haskell, or Go, or anything else with a modern task scheduler, which is an ever-increasing number of language platforms.

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

#48

Post by jcdavis » Mon, Oct 03, 2011, 8:08 PM UTC

bascule wrote: post #30

flexd wrote: post #27

Earlier quoted context omitted.

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.

Sure it is. Stack space isn't free

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

#49

Post by glenjamin » Mon, Oct 03, 2011, 8:10 PM UTC

masklinn wrote: post #41

glenjamin wrote: post #40

Earlier quoted context omitted.

Well the other option for computationally expensive code is to use some sort of worker that runs a sufficiently fast language. JavaScript on v8 is actually one of the fastest interpreted languages available, so unless you really need to drop down into C or similar, splitting across the event loop or using another node child process is not an unreasonable way to approach CPU heavy calculations.

> Well the other option for computationally expensive code is to use some sort of worker that runs a sufficiently fast language. Which only helps if you know your code is going to be slow. If you somehow implemented an algorithm with a quadratic complexity and did not test for sufficiently large input, you might not realize what's going to happen before it hits production. > JavaScript on v8 is actually one of the fa…

I can't disagree with any of these points.

NodeJS is no magic bullet, those who treat it as such should be extremely wary. It is, however, rather nice to work with.

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

#50

Post by masklinn » Mon, Oct 03, 2011, 8:13 PM UTC

ovi256 wrote: post #10

I'd like to point out that this uses important improvements over the naive Ziuba's strawman version: memoization and callbacks using the event loop. The callbacks improve concurrency, allowing a single process/thread to multitask requests, and memoization reduces total time spent per request. Actually, if the async lib memoization facility shares values between requests, which seems quite sure to me, all requests but…

> I'd like to point out that this uses important improvements over the naive Ziuba's strawman version

The Ziuba version was not "a strawman", it was an example used to trivially generate high in-request CPU load and demonstrate the misbehavior of evented system under this condition.

If you want to compute fibonacci fast, just use Binet's Fibonacci formula, it runs in O(1), then your only issue is that you're going to overflow very fast on doubles (not sure you'll even reach fib 1500). Using decimal, you can probably go higher before reaching your limits (though you'll run out of display space long before that if you print all digits): Python's decimal.Decimal reaches ~fib 4000000000 before an overflow error.