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

http://www.saltwaterc.eu/but-the-question-is-will-it-recurse-part-1-fibonacci40.html

by titel • 15 years ago

22 17 15 years ago

saltwaterc.eu

Jabbles• 15 years ago

Try using compiler optimisations...

SaltwaterC8• 15 years ago

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.

aklein• 15 years ago

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

mtklein• 15 years ago

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! :)

rauljara• 15 years ago

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

SaltwaterC8• 15 years ago

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.

maxs• 15 years ago

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.

SaltwaterC8• 15 years ago

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.

colomon2• 15 years ago

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?

SaltwaterC8• 15 years ago

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.

colomon2• 15 years ago

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

Locke1689• 15 years ago

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

SaltwaterC8• 15 years ago

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

throwaway1415• 15 years ago

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

SaltwaterC8• 15 years ago

Can you post something that actually means something?

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

Related Stories