Node-fib: Fast non-blocking fibonacci server
github.com
github.com
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.
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.
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".
"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.
I still think you may not understand what modern schedulers end up doing here.
Node isn't a bad technology and I don't hate it. Well, I personally hate working in the event-loop paradigm (due to abundant experience) but that's no discredit to Node, which simply is what it is. The hype is toxic. The hype is basically full of flat-out lies. It teaches people that the state-of-the-art as of 1990 or so is the state of the art today. The hype claims Node is blazing a new path in the field of concurrency, when in fact it's traveling a 4-lane highway with fast food and hotels, while putting blindfolds on its partisans to hide them from the fact they're actually smack dab in the middle of civilization.
CPU is finite. RAM is finite. The kernel has limits on things like sockets.
(Erlang is super-neat, and Go goes a long way in the same direction. But I rather imagine the original poster meant that people should use CGI)
Of course the real issue is that you should choose a better implementation of the algorithm.
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.
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.
NodeJS is no magic bullet, those who treat it as such should be extremely wary. It is, however, rather nice to work with.
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.
Preemptive multitasking solves that problem, but if mixed with lots of shared mutable state, it reintroduces much worse problems of non-determinism and unreproducible bugs.
The golden path involves preemptive multitasking with little-to-no shared state. That way you get to have your cake (determinism) and eat it too (no blocking problems/starvation).
These newfangled non-blocking designs are seemingly much better for everyday tasks.
And saying that an async IO server is a bad choice for computational things is, well, a well-known tradeoff that 99% of apps don't have to worry about.
When was the last time someone complained that their webservers were CPU bound? Its always the DB that is the bottleneck...
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.
also, the joyent node.js homepage itself claims, as a business advantage:
"• Huge JavaScript developer pool at the ready for faster development"
my point isn't that you shouldn't build up buzz. it's that, when buzz exists around something, your job as a platform implementor includes making people aware of the things your product can't do well, and pitfalls the end-user might run into.
saying "well, it's their own fault for not being clueful enough to know what they were doing wrong, this technology is for pro hackers only!" is developer-hostile.
Or in other words,
a) what did they do wrong?
b) What do you think would be the best way to "spin" a new platform like that without either being cluelessly elitist or giving the unwashed masses false hope?
that said, my ideal pitch page would contain something to the effect of: "extensive standard library, including robust facilities for concurrent/non-blocking I/O". nothing marketing-y about non-blocking I/O or a given programming model making a language intrinsically "fast" or scalable, like nodejs.org's:
"This is in contrast to today's more common concurrency model where OS threads are employed. Thread-based networking is relatively inefficient and very difficult to use. [...] Almost no function in Node directly performs I/O, so the process never blocks. Because nothing blocks, less-than-expert programmers are able to develop fast systems."
in addition, node.js is in a little bit of a weird position of introducing a whole new language environment for an existing programming language, since node.js is effectively the vanguard of server-side/concurrent Javascript: I'd hope for an official series of tutorials designed to introduce the nonprogrammer, or "Web app-only programmer" of Javascript, to concurrent programming in the large.
that said, the node community might already be doing things like this which aren't obvious to the layman, and if so, good on them. good concurrent programmers are hard to find, and anything that encourages people to learn how to do concurrency well is a good thing.
Or at least that line of thought makes sense to me.
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.
I find the notion of sharing libraries between the client and server kind of odd, in that people who talk about the "open web" think it's a desirable quality.
it allows you to rev a protocol faster, but at the cost of not being forced to have a point of reference that isn't also intrinsically tied to one implementation of the protocol, which seems a very un-open thing to do to me.
</derail>
Things like form validation, user input normalization, navigation options. There are ton of small data manipulation functions that you either have to maintain in both javascript and your server side language and cause some weird bugs when one version doesn't behave exactly the same as the other or else you need to make a bunch of unnecessary ajax calls just to avoid reimplementing things in js.
There is much deeper integration you could do but I think we're on the same page as to why that's a bad idea.
http://teddziuba.com/2010/10/taco-bell-programming.html
http://teddziuba.com/2011/02/the-case-against-queues.html
http://teddziuba.com/2011/03/osx-unsuitable-web-development....
http://teddziuba.com/2008/09/a-web-os-are-you-dense.html
if I had to sum up his philosophy in three sentences, here they are:
your job is software engineering. every bit of fancy shiny stuff that you add onto your software is another thing that can break. the most important decision you need to make in your job is determining when your tools are good enough and don't need further elaboration -- at a certain point you need to stop jerking off about your toolchain, and just ship your project.
If you try the well reasoned analysis, you get passed over. It turns out that no-one pays attention unless there is a fight happening (c.f. tech crunch's reporting style)
'If the truths are sufficiently impalatable, our audience is psychically incapable of accepting them and we will be written off as totally unrealistic, hopelessly idealistic, dangerously revolutionary, foolishly gullible or what have you.'
The morale is - everyone admonishes a flame, but nothing else gathers posts quite like it. If you think something is terrible, holding back will get you nowhere.
I don't see how Node.js isn't a valid tool. Async can be a bit of an over-optimization, but you don't have to use it (even in Node), as Ted's naive Fib server shows. And Javascript is ugly as sin. But so's PHP, the language behind Wikipedia, and you have to use JS (or something like Coffee-script) anyway.
I don't know enough about Node to really judge it, but there's nothing I've heard in this whole flame-war that really rules it out.
$ node app.js
FATAL ERROR: CALL_AND_RETRY_2 Allocation failed - process out of memory
This code is the epitome of roflscale
Still, the original point (node is cooperatively multitasked) was clear. Anything beyond that and I just want to reach for better Fibonacci algorithms.
memo function-to-memoizeIf 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.
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 :)
The best way to get information on Usenet is not to ask a
question, but to post the wrong information.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.
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.
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.
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
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.
Still doing anything that is CPU intense on that layer is stupid in the first place.
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.
But he wanted us to go back to CGI folks...
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 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-...
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 :)
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...
Math.round(Math.pow((1 + Math.sqrt(5))/2, n) / Math.sqrt(5))
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.
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
In [5]: float(_)
Out[5]: 308061521170129.0
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.
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.
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.
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.
function fib(n)
{
var phi = (Math.sqrt(5) + 1)/2
return Math.floor( Math.pow(phi, n)/Math.sqrt(5)+0.5)
}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.
$ time curl localhost:3000/1000000
curl: (52) Empty reply from server
real 1m0.392s
user 0m0.006s
sys 0m0.004s
$ node app.js
FATAL ERROR: CALL_AND_RETRY_2 Allocation failed - process out of memoryYou can up the limit by starting node with --max-old-space-size=<size in MB>
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.
Trying to nail a hammer with a drilling machine, is not to take yo anywhere.
Peace.
- Node sucks;
- No it doesn't * 2;
- Use Haskell;
- (others) ?
This one however has made me laugh as well :)
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.
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.
fibonacci(40,function(f) {
console.log(f);
});