4 ms·

Why is a Fibonacci sequence used as a benchmark for an argument for concurrent programming? The Fibonacci sequence is a recursive algorithm that inherently has

by gvb 15y ago

Why is a Fibonacci sequence used as a benchmark for an argument for concurrent programming? The Fibonacci sequence is a recursive algorithm that inherently has dependencies on previous calculations that prevent effective concurrent execution. The Fibonacci algorithm executed concurrently is going to spend an inordinate amount of time creating tasks that do a trivial calculation (add two numbers together). If you want to benchmark concurrency, at least pick an benchmark algorithm that exercises concurrency. The FFT comes to mind, but there are probably lots of better examples (that is a challenge to HNers ;-).

bunderbunder 15y ago
I think that's where the "well-executed trolling" comment comes in. He essentially whipped everyone into a tizzy by complaining that a framework for helping to get better performance out of I/O-bound web services by handling I/O calls asynchronously doesn't work so well if you take a CPU-bound monkey wrench and jam it directly into the gearbox. I suspect that it worked so well because the idea of using Fib to talk about performance is kind of built into the collective programmer unconscious. The whys, hows, and whats of using Fib to talk about performance are somewhat less well-entrenched, though. So there's room to trip people up by getting them to go, "Yeah, this sounds interesting, and I recognize all the words so it probably isn't technobabble!"
nightski 15y ago
You are talking about parallelism. Concurrency is demonstrated just fine by the example, as it is being executed on a web server on every request.
lobster_johnson 15y ago
He was not benchmarking concurrency, he was pointing out that Node is single-threaded system that essentially implements the old-style cooperative multitasking, where a single task will block everything else. He could have used sleep() and it would have illustrated the same point (and more elegantly, since half of the responses miss the point entirely and focus on the Fibonacci part). Node developers probably don't do a lot of computationally complex stuff, but when they do, they have to think about the concurrency problem. Even something as trivial as sorting a large list or parsing a huge chunk of JSON is going to stop all other requests from executing.
- gvb 15y ago
  But he isn't benchmarking web server concurrency because he is doing a single curl $ time curl http://localhost:8000 165580141 real 0m0.016s user 0m0.007s sys 0m0.005s So he is running the Fibonacci (40) once with the web server. The only concurrency / parallelism that is happening is in the recursive Fibonacci algorithm. I stand by my contention that the Fibonacci algorithm is a very poor test of concurrency / parallelism. I stand by my contention that he should have implemented an algorithm that could be solved in concurrent pieces and then benchmarked node.js against his favorite language. If the algorithm cannot be parallelized effectively, it doesn't matter how many tasks you spawn to solve it (cooperative or otherwise), the algorithm's dependencies will cause all the tasks to block and effectively serialize their execution.
  - lobster_johnson 15y ago
    I'm referring to the original post (http://teddziuba.com/2011/10/node-js-is-cancer.html http://teddziuba.com/2011/10/node-js-is-cancer.html), which did test concurrency. The Haskell guy missed the point entirely and seems to have given up after Haskell is shown to memoize his function.

by gvb 15y ago

bunderbunder 15y ago

I think that's where the "well-executed trolling" comment comes in. He essentially whipped everyone into a tizzy by complaining that a framework for helping to get better performance out of I/O-bound web services by handling I/O calls asynchronously doesn't work so well if you take a CPU-bound monkey wrench and jam it directly into the gearbox. I suspect that it worked so well because the idea of using Fib to talk about performance is kind of built into the collective programmer unconscious. The whys, hows, and whats of using Fib to talk about performance are somewhat less well-entrenched, though. So there's room to trip people up by getting them to go, "Yeah, this sounds interesting, and I recognize all the words so it probably isn't technobabble!"

nightski 15y ago

You are talking about parallelism. Concurrency is demonstrated just fine by the example, as it is being executed on a web server on every request.

lobster_johnson 15y ago

He was not benchmarking concurrency, he was pointing out that Node is single-threaded system that essentially implements the old-style cooperative multitasking, where a single task will block everything else. He could have used sleep() and it would have illustrated the same point (and more elegantly, since half of the responses miss the point entirely and focus on the Fibonacci part). Node developers probably don't do a lot of computationally complex stuff, but when they do, they have to think about the concurrency problem. Even something as trivial as sorting a large list or parsing a huge chunk of JSON is going to stop all other requests from executing.

gvb 15y ago
But he isn't benchmarking web server concurrency because he is doing a single curl $ time curl http://localhost:8000 165580141 real 0m0.016s user 0m0.007s sys 0m0.005s So he is running the Fibonacci (40) once with the web server. The only concurrency / parallelism that is happening is in the recursive Fibonacci algorithm. I stand by my contention that the Fibonacci algorithm is a very poor test of concurrency / parallelism. I stand by my contention that he should have implemented an algorithm that could be solved in concurrent pieces and then benchmarked node.js against his favorite language. If the algorithm cannot be parallelized effectively, it doesn't matter how many tasks you spawn to solve it (cooperative or otherwise), the algorithm's dependencies will cause all the tasks to block and effectively serialize their execution.
- lobster_johnson 15y ago
  I'm referring to the original post (http://teddziuba.com/2011/10/node-js-is-cancer.html http://teddziuba.com/2011/10/node-js-is-cancer.html), which did test concurrency. The Haskell guy missed the point entirely and seems to have given up after Haskell is shown to memoize his function.