But the question is: will it recurse? Part 1: fibonacci(40) | Hacker News Reader

But the question is: will it recurse? Part 1: fibonacci(40)

saltwaterc.eu

22 pointstitel17 comments

Recur is to make a recursive call. Recurse is to curse again.

Thanks. Missed that one. My "3rd party" language support is not perfect.

Don't want to get into the language shootouts here. But this seems like a horrible way to compare language performance.

There are many more interesting real-life programs tested on computer language shootout website.

In particular, you can't compare C and JVM performance on programs that run for such a short time. The JVM time will be dominated by the time to start up the the JVM and to do the first JIT optimization. I think it is very likely that for a larger fibonnaci number, the JVM performance will come asymptotically close to optimized C's.

This may be the subject for a part 2. Aka more intensive testing for the implementations that actually perform. And other recursive algorithms (such as the classic factorial). I didn't test the language (implementation!) performance, but the recursion and how the various implementations can actually handle the bad recursion algo.

A proper testing suite that tests various aspects of a specific runtime takes time. I am aware of that, but I am not aware of any test suite that does this.

Okay, I don't get this. I thought the original node.js article was using a terrible implementation of Fibonacci precisely because it was stupidly slow.

Why are people writing articles looking at how fast different languages / implementations are at running this terrible code? Does that give us any useful information whatsoever?

There isn't an original article. In fact, my article isn't something to give the node.js police ideas on how to "fix" various stuff. This is about how various runtimes handle bad recursion. In fact, V8 isn't stupidly slow compared to PHP, CPython, and the de facto Ruby implementation.

If you aren't writing recursive code, then the valuable information for you is NULL. Otherwise, it may give you some food for though.

I do write recursive code. However, I certainly do my best not to write bad recursive code...

In fact it is good recursive code, mathematically speaking. It's just that some compilers are bad at it aka doing brute force instead of tail recursion. The main selling point of these "interpreted" languages is the programmer productivity. Now why the hell one would have to write more complicated algorithms just to go around the compiler? C does this just fine. The 0.6 seconds to 5 minutes difference for the same simple algorithm shows that something is fundamentally broken.

Try using compiler optimisations...

Good catch.

fib|⇒ gcc -O4 fib.c -o fib fib|⇒ time ./fib ./fib 0.65s user 0.01s system 100% cpu 0.657 total fib|⇒ gcc -O3 fib.c -o fib fib|⇒ time ./fib ./fib 0.66s user 0.00s system 100% cpu 0.657 total fib|⇒ gcc -O2 fib.c -o fib fib|⇒ time ./fib ./fib 1.54s user 0.00s system 100% cpu 1.535 total fib|⇒ gcc -O1 fib.c -o fib fib|⇒ time ./fib ./fib 0.00s user 0.00s system 0% cpu 0.001 total

For some reason, it hates the O1 flag. Printing the result brings it close to the result without the optimization.

O1 probably sees you don't use the result or have side effects in fibonacci(40) and optimizes the call away...

One of the reasons I get why people advise against certain levels of optimization without understanding its implications. As I write few lines of C code, usually I don't bother with deep understanding of all the concepts of compiler optimization.

I just took a look at the output of gcc on -O1,-O2,-O3,and -Os (using the -S flag to output assembler.) It appears that with -O1 or -Os enabled, gcc turns the double recursion into single recursion. This makes the algorithm scale O(n) instead of O(fib(n)); i.e. much much faster. (Weirdly, -O2 and -O3 look to be double-recursing, but I didn't check closely. May be that gcc's smarter than me.)

It _also_ notices you're not using the result of fibonacci(40) and that it's a pure function, so it skips it. If you look at any optimized main function it's pretty much "set return code to 0 and get out of here."

To avoid this problem I've changed main to "return fibonacci(40)".

Now optimization becomes interesting. At -O3 main becomes 4 calls to fib(36), fib(35), fib(38), and fib(37). Crazy huh? It looks like it's unrolled fib(40) a few steps! At -Os I lost track of what's going on, but it starts with a call to fib(38) too. -O1 plays it pretty straight, and is what I'd recommend looking at for readable assembly.

-O2 and -O3 are easily the fastest. Something very clever is going on there.

    real	0m0.075s
    user	0m0.073s
    sys	0m0.001s

Moral of the story? Use -S! :)

Wow meaningless article. Try tail recursion, and a functional language - although that won't be able to help you with your terminal banality...

Can you post something that actually means something?

"sucks" "suckier" sucks that hard " "makes me laugh so hard up to the point of bursting into tears"

In these sorts of posts, I tend to find that flavor comments like the above:

a) add nothing of value to the post

b) are likely to provoke hostile responses (or turn people off from responding), actively detracting value from the conversation surrounding the post.

Thank you, though, for taking the time to write up your benchmarks.

Buzz marketing. These days nobody gives some attention to a purely technical article without any incentives. Seriously, on HN usually it matters who wrote the article, not the factual contents of it.

Reply on news.ycombinator.com