11 ms·
Node-fib: Fast non-blocking fibonacci server
- raganwald 15y agoNote to self: Starting immediately, all raganwald projects will have a “Is it any good?” section in the readme, and the answer shall be “yes."
- DrHankPym 15y agoWow, this really made me laugh.
- AlexC04 15y agoMe too. I was rolling my eyes this morning at all the he said she said stuff. It's been a pretty standard example of "hacker news eating its own tail" today. - Node sucks; - No it doesn't * 2; - Use Haskell; - (others) ? This one however has made me laugh as well :)
- jrussbowman 15y agohilarious
- callahad 15y agoI 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#%_thm_1.13 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html... https://secure.wikimedia.org/wikipedia/en/wiki/Fibonacci_number#Relation_to_the_golden_ratio https://secure.wikimedia.org/wikipedia/en/wiki/Fibonacci_num...
- rbranson 15y agoWould be cheating, man. Micro-benchmarking is all about using fictitious tests to show off fake performance in blog posts.
- bunderbunder 15y agoOr, for that matter, using fictitious tests to show of fake lack-of-performance in blog posts.
- cperciva 15y agoWhy would you want to use that formula? The doubling identities are faster and avoid floating-point arithmetic.
- raganwald 15y agoTo 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 story is that an abrasive blog post asserted that Node.js was a terrible platform for certain types of problems, and this algorithm was given as an example. The author here is simply showing that with care, Node.js will not be the problem. For shits and giggles, here’s another Fib algorithm, chosen strictly for the pleasure of implementing it: https://github.com/raganwald/homoiconic/blob/master/2008-12-12/fibonacci.md https://github.com/raganwald/homoiconic/blob/master/2008-12-...
- foca 15y agoThe 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 :)
- robinhouston 15y agoIt’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-numbers-using-binet’s-formula/ http://bosker.wordpress.com/2011/07/27/computing-fibonacci-n...
- tlrobinson 15y agoI 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.
- tzs 15y agoThat'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.
- jules 15y agoThat 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 http://en.wikipedia.org/wiki/Power_iteration
- mappu 15y agoBy using a field extension over √5, you can evaluate this exactly without rounding or resorting to floating point.
- euyyn 15y agoI think that's a very sharp observation. I tried it, but in order to exponentiate the vectors (instead of floating point numbers) I end up with the original matrix algorithm (pre-eigenvalues)...
- nateberkopec 15y agoBREAKING: glenjamin cures cancer.
- wavephorm 15y agoNow I just need an async ajax library, so I can do: fibonacci(40,function(f) { console.log(f); });
- glenjamin 15y agoAuthor 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 locking.
- ovi256 15y agoI think it'a a valuable tutorial to show node.js idioms. It's pretty easy to read, but I for one would struggle to write it as concisely.
- jerf 15y agoYes, 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.
- philjackson 15y ago"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 comments like "which is still not all that great".
- Detrus 15y agoToo bad the code is so nasty
- mattlong 15y agoHow so? IMHO, it's an elegant demonstration of the async module.
- deleted 15y ago[deleted]
- wmf 15y agoCheck out the Cilk version, which is not only concurrent but parallel as well: http://myxman.org/dp/node/182 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.
- scooty-puff 15y agohttp://hpaste.org/52108 http://hpaste.org/52108
- scooty-puff 15y agohttp://hpaste.org/52109 http://hpaste.org/52109, in case one prefers to be more explicit.
- Detrus 15y agoBut is the async module itself elegant? I guess it's relative, it's even less elegant not to use the module. The async module is still a hack, the cleanest one Node has. I think the whole discussion about "cancer" wouldn't have happened if the V8 team added continuations by now. They mentioned that they will so we might be cleaning up big chunks of code. It's funny how a tech can get so popular with these big warts. Probably because people use it in a very limited way, no one writes CPU intensive code because you rarely need it for serving sites and data. Then the clumsy callbacks aren't so bad.
- ovi256 15y agoI'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 the first one are served from its cache in the test the author uses as example. This still doesn't highlight any strength of node.js IMO, asides from the easy shared memoization. It could be translated to Tornado-web, an async Python framework, almost literally.
- prosa 15y agoIt does in fact share memoization. Easy shared state is a key strength of the single-threaded model. :) Re: Node.js, you're right. The core of the debate is whether the single-threaded, evented model is a legitimate theoretical approach to concurrency. That programming style is the same across Node.js, Tornado-web, EventMachine, etc. It translates literally to Tornado-web because the idioms are the same.
- masklinn 15y ago> 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.
- SamReidHughes 15y agoBinet's formula doesn't run in O(1) if you want an exact answer. Using a + b * sqrt(5) representations or floating point with sufficient precision, you can get O(n log n 2^O(log* n)) time (quoting Wikipedia's Furer's algorithm page here). Which beats O(n log n log log n) time, if you were wondering. If something beats that for computing Fibonacci numbers, that'd be pretty cool.
- rkalla 15y agoAs 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 node as a result of the whole fiasco. Thanks Ted :)
- knieveltech 15y agoAahz's law The best way to get information on Usenet is not to ask a question, but to post the wrong information.
- Udo 15y agoasync is not part of the node.js core - it's an external module.
- bascule 15y agoHmmm... $ 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
- flexd 15y ago32bit 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=<size in MB>
- bascule 15y agoFibonacci isn't a kind of problem that should be bounded on RAM though. Something is fundamentally broken with the way this is implemented.
- glenjamin 15y agoYou can probably get it work by asking it for increasingly large numbers to break up the calculation into stages. v8's current GC implementation has a hard memory limit of 1GB which is uppable to 1.7GB on 64bit systems. There's a new GC implementation in the works which is supposed to be able to beat this. The memory usage is due to the overhead of nextTick creating a new stack each time, and the interpreter keeping track of where the callbacks need to lead. Splitting the calculation up into batches could be incorporated into the algorithm quite simply by adding an additional task to async.series which called fib(i) for i to n with a step of 10 when n is > 100. Obviously there are much more efficient and effective ways of calculating the fibonacci sequence, but I quite like the recursive algorithm for its clearness and its amenability to memoisation.
- fendrak 15y agoIs 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.
- lamby 15y agoPerhaps if enough alternative implementations are submitted to HN it will drown out the silence on the actual issue that was raised.
- willvarfar 15y agoTed-gate was advocating a return to CGI instead...
- wpeterson 15y agoThe only difference in this implementation is that it uses memory-based caching (memoization) to compute given value once and then serve the cached copy. Of course this is fast for 1000 iterations, since the effective cost is zero from the second request. People really are misunderstanding the critique of fibbonacci as representing any CPU intensive task. TLDR; All the author did here was remove the CPU intensity by caching the calculation
- Sidnicious 15y agoIt also uses process.nextTick aggressively (for each recursive call) so that the server can take other requests in the middle of computing a big sum.
- DrHankPym 15y agoI'm actually very confused by his criticism. You can write a CPU intensive task in any language, and you'll have the same problem. Or is that the point? Some people believe Node.js will magically make all processing computations = 0? I'm all for discouraging the rumor that Node.js will solve every problem, but don't call it Cancer.
- burgerbrain 15y agoThe 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.
- DrHankPym 15y agoI'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.
- carllerche 15y agoInstead 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.
- glenjamin 15y agoNow there's an idea! That could be rather fun...
- InclinedPlane 15y agofunction fib(n) { var phi = (Math.sqrt(5) + 1)/2 return Math.floor( Math.pow(phi, n)/Math.sqrt(5)+0.5) }
- adgar 15y agoAnyone know offhand what the minimum value of n is for which this fails due to floating point inaccuracies?
- InclinedPlane 15y agoJavascript 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.
- mark242 15y agoNote to Ted: next time, just use sleep().
- glenjamin 15y agoTo which the response is the same: simply don't block the event loop and use setTimeout. The whole cancer thing is based on the premise that blocking the event loop is unavoidable. I'm attempting to say that it isn't. Jerf's points about how it can happen accidentally are perfectly valid, it's up to the developer not to do something stupid and to actually have decent tests and benchmarks in place - as it would be with any approach. Its certainly true that significantly poor performance in code which doesn't release the loop will degrade a single-threaded event loop far more than a threaded approach.
- ldh 15y agoDoesn't that kind of take the wind out of Node's sails as far as its claims of being easier for dummies to write non-blocking code, if you have to do all the usual due diligence anyway? I'm genuinely curious as someone who's only familiarity with Node is hype and through hearing the adjective "evented" thrown around with wild abandon lately.
- mark242 15y agoCPU speed and bus speed is finite on the machine you're running on. Using setTimeout to poll the results of some thread you've spawned to run a calculation is _worse_ performance than just blocking in the first place, because now when you try to profile your application (how does one do that in node.js, anyways?) you're going to be looking at a million setTimeout closed loops. Here's Ted's entire point: "The point is that the HTTP server isn't the same entity doing the application work." ..which has basically been true ever since mod_jk was created.
- SaltwaterC 15y agoThe point is moot. HTTP is just the transport protocol in this case. Doesn't have to say that it has to be the front end service that talks to the end user web browser. The OP of the "cancer" article made up that shit. I can bind the listener of a node service to an UNIX Domain Socket and talk HTTP over that socket with a front end web server, instead of plain TCP (reduces the IPC latency). It is IPC between distinct components. It delegates the dynamic page generation to another service. It is a text interface, although sometimes, well, most of the times, the binary protocols outperform the text based protocols therefore the theory is crap. Isn't this "UNIX way" enough for some people? Forget the part that says: any IPC adds extra latency to the request - response paradigm aka the opposite of the stuff a web stack should do. Can you tell me at least one example from the myriad xGI protocols for interfacing a web server with an application server that actually brings any benefit over having plain HTTP/1.1 and a reverse proxy? Does it help to have yet another protocol for doing basically the same task: IPC between a couple of servers? Any xGI client (aka web server) is basically a reverse proxy for an IPC protocol. Does it say somewhere, carved in stone, that this protocol must be other than HTTP? I think that most people that spend the time engineering yet another xGI solution simply don't see the forest for the trees. PS: nobody stops anybody to drop a scgi.js or fastcgi.js module for node.js if that keeps people warm at night. But maybe I'm one of those tired of this shit: engineering yet another xGI protocol for every programming language that floats around the web. NIH syndrome, I'd say. At least HTTP is ubiquitous, while most servers already HAVE a reverse proxy handler.
- tedjdziuba 15y agoI've just submitted a pull request that I think really enhances this app. https://github.com/glenjamin/node-fib/pull/5/files https://github.com/glenjamin/node-fib/pull/5/files
- wippler 15y agowow.. this is incredibly juvenile. you should need to appreciate other people's opinions too apart from yours
- pabloPXL 15y agotoo much boilerplate :) https://gist.github.com/1258982 https://gist.github.com/1258982
- pabloPXL 15y agolol ted is really mad :D https://github.com/teddziuba/node-fib https://github.com/teddziuba/node-fib
- ww520 15y agoI'm actually quite impression with the 5000 requests/second ab result. I can't get more than 1000 requests/second on my pony laptop. What hardware are you using?
- justin_vanw 15y agoI think this proves Ted's point. Look at that code. It is ugly as sin. Since I'm not an expert at node.js, I can't follow what is going on at all. Plus, this is memoizing. That is just cheating, it doesn't matter how you implement the algorithm if it memoizes. If the creator of this github repo is to be believed, implementing a 3 line algorithm in node, you must use 20 lines of intricate, ugly code. If that is the case, node.js IS cancer.
- robinduckett 15y agoNode.js can be done in different ways to this, the fact is, that this code works asynchronously, and this is how Node does async.
- jrockway 15y agoThis is the wrong approach. The right approach is to write your computationally-intensive code so that it runs in another process, and then to talk to that process over the network. Network servers must only talk to the network.
- prodigal_erik 15y agoIf I have unused capacity, I can afford simpler threaded code. If I'm overloaded, I need some other platform for the real work. It sounds interesting but unless I need to write my own software load balancer, I'm not sure what node (as implemented today) is appropriate for doing.
- Nemmie 15y agoI lolled (at work).
- amit_heroic 15y agoAny tool in the wrong hands, is dangerous. So anyone trying to prove that fib makes node slow, is stupid. Node.js was made to make memory requests unblocking; not to generate the fib series for you. Trying to nail a hammer with a drilling machine, is not to take yo anywhere. Peace.