Nice to see the different implementations side-by-side. I do believe however that this is mainly a benchmark of startup time and initial JIT of the CRT/runtime/virtual machine/execution environment.
If you remove that time from the equation, I expect that the execution time will not differ a lot from each other.
Of all the benchmarks out there this is actually reasonable (though obviously limited). It runs the same thing in different languages and the processing time is long enough for VM startup not to matter.
Also the performance shows the bytecode languages C# and Java to do fairly well compared to C and GO.
That has mostly to do with the fact that the code isn't manipulating objects at all. As soon as you're starting pointer chasing in languages where almost everything is an object like javascript performance will suffer.
I thought so as well, and benchmarked the Julia version inside the REPL (after calling the function once to make sure JIT compilation was done), and the difference was insignificant (maybe 1 to 5 percent - basically same order of magnitude as the measurement error, ie usual run time fluctuations). So Julia runtime was still a bit less than 2x the C/C++ runtime (but faster than C/C++ without the -O3 switch).
This shouldn't be surprising though. The point of Julia is that compilation time stays relatively constant while runtimes can grow enormous very easily. Normally with microbenchmarks you run multiple times to get rid of compilation time because microbenchmarks run in <1 second so compile time matters. But this show that, in any case where the user does begin to care about speed, that compilation time is really minimal. The only place where it truly matters in practice is in the REPL: it can cause a bit of lag which can get annoying but it's a tradeoff.
I'd be interested to see how Elixir does with an OTP-optimised redo. Probably still not great, but I feel like the example isn't playing to its strengths.
Otp won't help. The benchmark itself is too synthetic to really matter as an analog for real world use cases where you would deploy elixir (or go or swift for that matter if we're being honest). Elixir cares about developer ease, high up time, lots of connections (network I/o). Do you need these things? Then you shouldn't care about the benchmark.
What is OTP? Fibonacci optimised by memorising already calculated values is linear time and constant time if you use the analytical formular for it. But then it stops being an interesting micro benchmark (as is pointed out on the website).
OTP allows for work to be distributed across cores and get a speedup in some way proportional to that. It wouldn't be a fair comparison though, exactly like memoisation or constexpr.
It's also an option that isn't unique to Elixir. Go is the obvious other candidate where the programming language helps, but all of the languages have support for parallelism.
That's obviously a better choice if you actually want Fibonacci numbers, but it defeats the point of a benchmark if you implement a completely different algorithm in one of the languages.
As for me, these benchmarks are strange because there are solutions that are not omptimized -- in node.js implementation the memoized approach has been used (which outperforms the recursion), but in Java solution (as an example) -- the recursive approach has been implemented.
I think the intent is that the main implementations are those in files like `[Ff]ib.*`. There are additional memoized implementations for some languages, but presumably these are only used in the "Optimized code that breaks the benchmark" section.
You can't really compute it in constant time since the number of bits in the nth Fibonacci number is O(n), so you need to take at least that long just to write the result out.
Computing with Binet's formula is also rather tricky. You just need to round φ^n/√5, but how many bits of √5 do you need to use?
Languages without tail recursion will perform worse. Memoization is borderline cheating, because it's a different implementation.
Fib is the poster boy for tail recursion but the reason for that is that recursion to implement fib is simply a bad choice. It's cute but that's about it. If the point is to measure function call overhead, then measure _that_?
The benchmark includes a C++ constexpr version, at https://github.com/drujensen/fib/blob/master/fib-constexpr.c... , with timing numbers under the section "Optimized code that breaks the benchmark" and the comment "all benchmarks will have some caveat."
Somewhat off topic, but I love the fact that the first post regarding compile-time Fibonacci in C++ was submitted in 2000, another user expanded on the original in 2008, and now it's being usefully referenced in 2018.
I stumbled across Everything2 recently, but in many ways it strikes me as a tiny bit of the golden age of the internet, unexpectedly preserved.
It can be a gateway for learning interesting things about the mechanics of a language, its compilation, and in turn how to make similar cases in other languages faster/cleaner/more-secure. e.g. why is nim so fast in this case? Is it tail call optimisation, not doing overflow checks, static inlining, or something else? Nim compiles to c to it is especially odd.
Why would languages without tail recursion optimisation perform worse when all languages use the naive implementation? It's not tail recursive, so it shouldn't make a difference, right?
But recursive Fibonacci isn't tail recursive. The final function call is to `+` (addition), which means that the two recursive calls must each be put on the stack and later returned so the sum can be computed. Tail recursion requires that there is no final operation other than exactly a single recursive call.
What’s the point of even mentioning the memoized versions? OF COURSE the naive recursive version is slow and it’s very easy to write something much faster in any language whatsoever.
I couldn't find a list of the hardware used in the benchmarks, so comparing is difficult, though before testing, I'd lean towards agreeing with you. Luajit is often on par with C, D or Go.
However, as C was one of the faster, I'll use it as a comparison.
fib.c, compiled with 03: 10.49user 0.28system 0:11.62elapsed
#include <stdio.h>
long fib(long n) {
if (n <= 1) return 1;
return fib(n - 1) + fib(n - 2);
}
int main(void) {
printf("%li\n", fib(46));
return 0;
}
Lua:
function fib(n)
if n <= 1 then
return 1
else
return fib(n - 1) + fib(n - 2)
end
end
print(fib(46))
Luajit: 48.66user 0.11system 0:52.95elapsed
Lua 5.3: 717.21user 8.40system 14:19.47elapsed
As Luajit was so much slower than C for this, which can be somewhat surprising.
Luajit would probably beat Ruby, for it's interpreted crown, but without optimisation, it won't beat the big boys.
I would say, that Lua isn't a good fit for solving this kind of problem, with these constraints, because every function call requires a hash lookup, which is irritating.
Of course, you could use Luajit's FFI to use C's implementation, which would be somewhat faster. Or expose the C implementation as a Lua library.
However, Lua is probably also a really good fit for memoization, and other techniques like that.
local nums = {}
local fib
fib = function(n)
if n <= 1 then
return 1
else
if nums[n] then
return nums[n]
else
nums[n] = fib(n - 1) + fib(n - 2)
return nums[n]
end
end
end
print(fib(46))
This is a fairly naive implementation, but has the same final result as the previous examples... And 'time' is unable to measure how fast it is (Both Luajit and Lua5.3). For all intents and purposes, it's instant.
During the my last technical interview, they asked my to write a fibonacci implementation in golang, i wrote the code, then they asked me to test it for like fb(180), i was surprised how slow it, then i was asked to come up with an optimisation in order to make it fast,
i come exactly with same fib-mem.go provided in this benchmark,
i was hired !
Or you write an iterative version of it that will not only be the simplest solution, it will be fast enough to compute fib(10000). There are constant time ones IIRC, but if someone comes up with such a solution in an interview without knowing it from before, they are probably over qualified for any job that uses the Fibonacci sequence as an interview question.
I guess if the point is to optimize fibonacci then wouldn't the smartest move be to use the closed form solution where Fib(n) is the closest integer to phi^n / sqrt(5), where phi = (1 + sqrt(5))/2?
This is one of the examples in the beginning of SICP, if I remember correctly.
The identity involves going through real numbers to get the integer result, and if you're using floating point or fixed point calculations, you need a good amount of accuracy to get the correct integer out, which also won't be the fastest thing. Using https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form you can get a different way to calculate Fibonacci numbers recursively, which involves far fewer computations.
Fundamentally, the thing to do is to understand the N-th Fibonacci number as a + b, where φ^N = a + b * φ, where a and b are natural numbers and φ^2 = φ + 1.
It's not important to understand phi as a floating point value; we can just work in the abstract arithmetic where we've added to the natural numbers a new entity phi defined to satisfy φ^2 = φ + 1 (just like complex numbers are the abstract arithmetic where we've added to ordinary arithmetic an i defined to satisfy i^2 = -1).
Call these Fomplex numbers; a Fomplex number a + b * φ amounts to just a pair of natural numbers, and it's easy enough to add and multiply them with natural number arithmetic. To calculate the N-th Fibonacci number, just calculate φ^N and add together its coefficients, as noted. As for how to efficiently calculate φ^N, use the usual addition chain approach to exponentiation (e.g., "repeated squaring"), thus getting a result in Θ(log N) many additions and multiplications.
This is incidentally the same as the matrix approach, essentially, but perhaps a cleaner perspective on it; at any rate, it is a way of thinking which will serve as a useful tool in your back pocket for other general problems about linear recurrences.
How neat! Among its properties not the least interesting is that it has finally convinced me that the initial condition f(0) = f(1) = 1 is not arbitrary but perfectly natural.
Ah, but actually that part is still a little arbitrary. This technique is fully general; variants describe ANY linear recurrence with ANY initial values. In particular, the Nth value of the Fibonacci-type sequence with 0th value x and 1th value y is xa + yb where a + bϕ = ϕ^N. I just happen to have chosen the weights x and y to both be 1 in that discussion.
It would be interesting to include skip[1] as it has language level memoization. There was a recent HN discussion about the language [2]. I do not think that the naive recursive Fibonacci is a useful benchmark in any way though, it's a way too pessimized implementation.
> It's available in Haskell as a first class citizen.
Not really. Haskell's laziness makes it easier to write functions that are memoized, but it does not automagically memoize functions. And how could it without incurring a non-trivial runtime space/time cost?
Haskell's purity is what makes it easier to write libraries that facilitate building memoized versions of functions in a transparent way (and that are obviously correct). For instance, I usually reach for [data-memocombinators][0], which happens to have a fibonacci example at the top of the docs:
import qualified Data.MemoCombinators as Memo
fib = Memo.integral fib'
where
fib' 0 = 0
fib' 1 = 1
fib' x = fib (x-1) + fib (x-2)
[0]: http://hackage.haskell.org/package/data-memocombinators-0.5.1/docs/Data-MemoCombinators.html
But is there any reason the Haskell compiler couldn't decide to memoize a function call itself if it determined that it would speed things up? To me that sounds hard for the compiler to do heuristically but a Haskell compiler should still have more scope to do optimizations like that than a C compiler has.
Why do we need language level memorization again? In python memoizing a function is just one line `@lru_cache()` I can't see why this needs an improvement by adding yet another thing to the core language.
Just adding a @lru_cache() to a python isn't guaranteed to be correct; for example, if you're reading from an API the response could change between calls.
Skip tracks side effects, and will either (a) memoize automatically a pure function or (b) recognize that a function is impure and avoid the memoization.
Some time ago, facebook introduced a javascript compiler which pre-compiled intermediate values. I think the point was to extend the spirit to the backend apps. If memoization is first class, implementing pre-compilation should be a blast
> I do not think that the naive recursive Fibonacci is a useful benchmark in any way though, it's a way too pessimized implementation.
probably, but I would still like to see more benchmarks that use recursion. It's a fundamental technique from functional programming and so few benchmarks bother with it at all.
I think Rust also does not have tail call optimisation. Nim and Crystal I'd heard why relying on underlying compilers, and could sometimes fail to get it (perhaps more than you'd expect using a compiler more "directly"?).
So... before looking at the code, I compared the elapsed time between the fib.rs program compiled with `rustc -O` and `rustc -O -C lto`. This yielded, interestingly, a ~500ms difference: ~6.45s vs ~6.95s (with LTO winning).
Then I looked at the code, and it began to make no sense. Then I looked at the assembly, and it made even less sense: the main function, fib::fib, which is where the vast majority of the time is spent, is identical, except for addresses.
I was starting to think, well, this might be related to instruction-cache lines... and it looks like it's not that:
$ perf stat ./fib-lto
2971215073
Performance counter stats for './fib':
6474.410894 task-clock (msec) # 1.000 CPUs utilized
17 context-switches # 0.003 K/sec
0 cpu-migrations # 0.000 K/sec
112 page-faults # 0.017 K/sec
22,607,598,238 cycles # 3.492 GHz
55,325,512,417 instructions # 2.45 insn per cycle
13,021,149,180 branches # 2011.171 M/sec
76,737,179 branch-misses # 0.59% of all branches
6.474991613 seconds time elapsed
6.474816000 seconds user
0.000000000 seconds sys
$ perf stat ./fib
2971215073
Performance counter stats for './fib':
6956.534790 task-clock (msec) # 1.000 CPUs utilized
11 context-switches # 0.002 K/sec
0 cpu-migrations # 0.000 K/sec
113 page-faults # 0.016 K/sec
24,290,924,647 cycles # 3.492 GHz
55,325,864,841 instructions # 2.28 insn per cycle
13,021,213,404 branches # 1871.796 M/sec
84,392,454 branch-misses # 0.65% of all branches
6.957260487 seconds time elapsed
6.956974000 seconds user
0.000000000 seconds sys
I didn't know an address difference of 0x30 could influence the number of branch misses so much.
Interestingly, the C and C++ versions have different performance for the same reason: they produce the exact same machine code, at different addresses. Thus one runs faster than the other. Edit: actually, there isn't a difference in branch-misses for those... only in cycles, which is even more intriguing.
Another interesting fact: valgrind's branch simulator doesn't show a difference in branch mispredictions between both (it also shows a misprediction rate much larger than reality, it's likely based on an old model Edit: valgrind manual says: Cachegrind simulates branch predictors intended to be typical of mainstream desktop/server processors of around 2004.).
More edit: I hacked a linker script to place the fib function from the C++ implementation at a fixed address, and tried different addresses, with interesting results:
0x10000: 5.117084095 seconds time elapsed, 17,866,364,962 cycles
0x10010: 5.206242916 seconds time elapsed, 18,090,712,907 cycles
0x10020: 6.096635146 seconds time elapsed, 21,285,484,583 cycles
0x10030: 4.955020420 seconds time elapsed, 17,297,162,836 cycles
0x10040: 5.146043048 seconds time elapsed, 17,954,722,919 cycles
0x10050: 5.252477508 seconds time elapsed, 18,335,804,193 cycles
0x10060: 6.100806292 seconds time elapsed, 21,300,089,284 cycles
0x10070: 4.936397948 seconds time elapsed, 17,216,051,020 cycles
Even more edit: I vaguely remember there was someone doing some analysis (with performance counters) of some similar performance difference depending where the function was located, that was on HN a few months ago, but I can't find it anymore.
Essentially, some of the loop heuristics work on a 32-byte window, not a 16-byte window. An interesting statistic would be to find where all the loops are in the code as relative offsets, and find how these shift based on starting alignment.
Edit: It's interesting to note that there's only one recursive call to the function, not two (you get two calls if you compile with -O1). It's also interesting to note that -Os generates an even smaller version with only one recursion, but that ends up slower (~6.5s).
The compiler has determined that the second call `fib(n - 2)` is "almost" tail-recursive (there is probably a better term for this), and so was able to convert that call into the loop you see at 10081 to 10095. This loop repeatedly calls the `fib(n - 1)` part.
In other words, the function was transformed from:
uint64_t fib2(uint64_t n) {
if (n <= 1) return 1;
uint64_t sum = 1;
for (; n > 1; n -= 2) {
sum += fib2(n - 1);
}
return sum;
}
Unfortunately, the result isn't too great as the initial part of the function is pretty heavy, and this bottlenecks computation. It would be better to inline some copies of fib into itself which might even allow some small amount of CSE, but importantly would reduce the number of calls.
The alignment you show is "special" (fast) because it's the point at which the top of the main loop (10081) is near the start of a 32-byte region, which allows multiple uops to be efficiently dispatched after jumping there.
It looks like gcc is going backwards on this one (at least in performance, the gcc-8 code is smaller): gcc-8, which generates the compact code you show, is the slowest of all the versions I tested (at -O3). Here's what I got:
gcc 4.8: 4.1 s
gcc 4.9: 4.3 s
gcc 5.5: 4.3 s
gcc 7.3: 4.8 s
gcc 8.1: 6.6 s
The difference between the compilers isn't just alignment: gcc-8 is generating very different code than the others, which are generally generating a large fib function with several calls of fib inlined into it, so there are many fewer calls (around 300k calls for gcc 4.8 through 7, but around 3 million for gcc 8).
Many versions of GCC do, including the version of 5.5 I tested above, but the mitigation optional (enabled by specific command line arguments) and off by default, so they don't impact this test.
I was intrigued to learn more about the winning language Nim to see how it beats C/C++, so I did a web search and was confounded to see Nim compiles to C/C++! What gives? Starting to doubt the methodology somewhat, though it was an interesting read.
Where did you hear that? 3 hasn’t even been competitive vs 2 until very recently.
Reasons for the switch have always been better Unicode handling and not being left behind as the community matches on (and soon lack of security updates to 2).
Sorry, but this is not how you do numeric benchmarks. Most real programs that deal with numbers also manipulate data structures and call many standard library methods. If those things are slow, your app is slow. This benchmark doesn't demonstrate anything that would translate into real-life performance.
It's definitely not a realistic measure of overall language performance, but I think it certainly has value if taken with the right caveats. It's probably a reasonably good measure of function call overhead in different languages, and I think it's good for getting a better intuition about the order of magnitude difference to expect from, say, C vs JS (~3x slower than C in simple cases) vs Python (~100x slower than C).
> It's probably a reasonably good measure of function call overhead in different languages
It's actually not. Fibonacci has a near-tail call in it that can convert some of the recursion into a loop. Furthermore, the runtime is dominated by useless recomputation that can be handled by memoization. So the distinction between languages is going to be dominated by their ability to do some moderately complex optimizations rather than by any intrinsic performance characteristics of their implementation.
Moreover, because the code is so small, there is likely to be major side effects as a result of effectively random differences--consider the effects of the code placement that cause a spurious difference between C and C++ kernels of about 20%. The JS version is going to get hit with a deoptimization at the very end (it might not impact performance) because the final result does not fit in an int32_t, and suddenly fib is no longer a well-typed function.
Microbenchmarking is _hard_, and it is all too easy for the microbenchmark to cease measuring the things that you want to measure.
But each has to return to the original caller because a summation still has to happen. The actual tail call is to the +/2 function.
F(N) can't complete until F(N-1) and F(N-2) have completed so it can sum up the values. If you pass the earlier computation, F(N-1), down to F(N-2) as a second parameter, you could get a tail call on the last part.
fib(0, Val) -> Val + 1;
fib(1, Val) -> Val + 1;
fib(N, Val) ->
T = fib(N-1,Val),
fib(N-2,T).
(I think I wrote that correctly, can't test here.)
But that's a non-obvious tranformation. I really would like to see the compiler that recognized that this was a valid (computational) equivalent to the original.
Any matrix implementation (with fast exponentiation) is going to be much faster, even in a "slow" language. For instance, in ruby, `Matrix[[1,1],[1,0]] * * 46` is instantaneous (real time: 0.000131s).
We have to go up to the ten million'th term to get something that is not instantaneous (0.486s) for a result which has 2089876 digits.
Are you sure `Matrix[[1,1],[1,0]] * * 46` isn't optimized into a constant value by the bytecode compiler? Idk Ruby much, but it seems like a possiblity.
Using generators in Python you can do this much much faster :D.
#!/usr/bin/env python
"""
Calculate fibonacci numbers using a generator
Usage: fibonacci.py [options] <N>
Arguments:
<N> Print all Fibonacci numbers up to <N>-th
Options:
-h, --help This help
"""
from docopt import docopt
def fibonacci():
"""generate fibonacci numbers"""
a, b = 0, 1
while 1:
yield a
a, b = b, a + b
if __name__ == '__main__':
try:
args = docopt(__doc__)
fib = fibonacci()
for i in range(int(args["<N>"])):
print fib.next()
except ValueError:
print "You must specify valid integer"
except KeyboardInterrupt:
print "Good-bye"
I'm perfectly aware it's meant to be recursive, but it's also a completely pointless test. It's not tail recursive, so you are measuring function call overhead in various languages. But various languages have options to perform much faster anyway, but solution is of course going to be language specific.
169 comments
[ 2.6 ms ] story [ 211 ms ] threadIf you remove that time from the equation, I expect that the execution time will not differ a lot from each other.
Also the performance shows the bytecode languages C# and Java to do fairly well compared to C and GO.
It's also an option that isn't unique to Elixir. Go is the obvious other candidate where the programming language helps, but all of the languages have support for parallelism.
I made a PR to fix that: https://github.com/drujensen/fib/pull/33
http://raganwald.com/2015/12/20/an-es6-program-to-compute-fi...
It is based on a Ruby implementation:
http://raganwald.com/2008/12/12/fibonacci.html
https://artofproblemsolving.com/wiki/index.php?title=Binet%2...
Computing with Binet's formula is also rather tricky. You just need to round φ^n/√5, but how many bits of √5 do you need to use?
http://raganwald.com/2013/03/26/the-interview.html
http://sarabander.github.io/sicp/html/1_002e2.xhtml (Ctrl-F "We can also formulate an iterative process for computing the Fibonacci numbers.")
Here's a Python implementation:
With that, fib(100000) takes half a second to compute on my machine.Languages without tail recursion will perform worse. Memoization is borderline cheating, because it's a different implementation.
Fib is the poster boy for tail recursion but the reason for that is that recursion to implement fib is simply a bad choice. It's cute but that's about it. If the point is to measure function call overhead, then measure _that_?
https://everything2.com/title/C%252B%252B%253A+computing+Fib...
I stumbled across Everything2 recently, but in many ways it strikes me as a tiny bit of the golden age of the internet, unexpectedly preserved.
But recursive Fibonacci isn't tail recursive. The final function call is to `+` (addition), which means that the two recursive calls must each be put on the stack and later returned so the sum can be computed. Tail recursion requires that there is no final operation other than exactly a single recursive call.
https://paste.pound-python.org/show/m403qNkpS5I8dnYjJGJq/
I wanna see the compiler that gets that.
But I suppose it's more accurate to describe it as the poster boy example for changing an implementation to make it tail recurse.
However, as C was one of the faster, I'll use it as a comparison.
fib.c, compiled with 03: 10.49user 0.28system 0:11.62elapsed
Lua: Luajit: 48.66user 0.11system 0:52.95elapsedLua 5.3: 717.21user 8.40system 14:19.47elapsed
As Luajit was so much slower than C for this, which can be somewhat surprising.
Luajit would probably beat Ruby, for it's interpreted crown, but without optimisation, it won't beat the big boys.
I would say, that Lua isn't a good fit for solving this kind of problem, with these constraints, because every function call requires a hash lookup, which is irritating.
Of course, you could use Luajit's FFI to use C's implementation, which would be somewhat faster. Or expose the C implementation as a Lua library.
However, Lua is probably also a really good fit for memoization, and other techniques like that.
This is a fairly naive implementation, but has the same final result as the previous examples... And 'time' is unable to measure how fast it is (Both Luajit and Lua5.3). For all intents and purposes, it's instant.This is one of the examples in the beginning of SICP, if I remember correctly.
It's not important to understand phi as a floating point value; we can just work in the abstract arithmetic where we've added to the natural numbers a new entity phi defined to satisfy φ^2 = φ + 1 (just like complex numbers are the abstract arithmetic where we've added to ordinary arithmetic an i defined to satisfy i^2 = -1).
Call these Fomplex numbers; a Fomplex number a + b * φ amounts to just a pair of natural numbers, and it's easy enough to add and multiply them with natural number arithmetic. To calculate the N-th Fibonacci number, just calculate φ^N and add together its coefficients, as noted. As for how to efficiently calculate φ^N, use the usual addition chain approach to exponentiation (e.g., "repeated squaring"), thus getting a result in Θ(log N) many additions and multiplications.
This is incidentally the same as the matrix approach, essentially, but perhaps a cleaner perspective on it; at any rate, it is a way of thinking which will serve as a useful tool in your back pocket for other general problems about linear recurrences.
[1] http://www.skiplang.com/ [2] https://news.ycombinator.com/item?id=18077612
This benchmark explicitly targets popular languages, and it happens to include no pure functional languages.
Not really. Haskell's laziness makes it easier to write functions that are memoized, but it does not automagically memoize functions. And how could it without incurring a non-trivial runtime space/time cost?
Haskell's purity is what makes it easier to write libraries that facilitate building memoized versions of functions in a transparent way (and that are obviously correct). For instance, I usually reach for [data-memocombinators][0], which happens to have a fibonacci example at the top of the docs:
Skip tracks side effects, and will either (a) memoize automatically a pure function or (b) recognize that a function is impure and avoid the memoization.
probably, but I would still like to see more benchmarks that use recursion. It's a fundamental technique from functional programming and so few benchmarks bother with it at all.
- remove the memoized versions (obviously it's faster)
- show the executed instructions for each language of the main loop (which would be a nice exercise with all the vms and dynamic languages)
Then I looked at the code, and it began to make no sense. Then I looked at the assembly, and it made even less sense: the main function, fib::fib, which is where the vast majority of the time is spent, is identical, except for addresses.
I was starting to think, well, this might be related to instruction-cache lines... and it looks like it's not that:
I didn't know an address difference of 0x30 could influence the number of branch misses so much.Another interesting fact: valgrind's branch simulator doesn't show a difference in branch mispredictions between both (it also shows a misprediction rate much larger than reality, it's likely based on an old model Edit: valgrind manual says: Cachegrind simulates branch predictors intended to be typical of mainstream desktop/server processors of around 2004.).
More edit: I hacked a linker script to place the fib function from the C++ implementation at a fixed address, and tried different addresses, with interesting results:
Even more edit: I vaguely remember there was someone doing some analysis (with performance counters) of some similar performance difference depending where the function was located, that was on HN a few months ago, but I can't find it anymore.Essentially, some of the loop heuristics work on a 32-byte window, not a 16-byte window. An interesting statistic would be to find where all the loops are in the code as relative offsets, and find how these shift based on starting alignment.
FWIW, this is what the function looks like at 0x10070:
Edit: It's interesting to note that there's only one recursive call to the function, not two (you get two calls if you compile with -O1). It's also interesting to note that -Os generates an even smaller version with only one recursion, but that ends up slower (~6.5s).In other words, the function was transformed from:
into the equivalent of: Unfortunately, the result isn't too great as the initial part of the function is pretty heavy, and this bottlenecks computation. It would be better to inline some copies of fib into itself which might even allow some small amount of CSE, but importantly would reduce the number of calls.The alignment you show is "special" (fast) because it's the point at which the top of the main loop (10081) is near the start of a 32-byte region, which allows multiple uops to be efficiently dispatched after jumping there.
Tail call optimization is only marginally relevant here, since the tail call is the addition, not one of the recursions.
† not to be confused with the typical C long int type.
Reasons for the switch have always been better Unicode handling and not being left behind as the community matches on (and soon lack of security updates to 2).
It's actually not. Fibonacci has a near-tail call in it that can convert some of the recursion into a loop. Furthermore, the runtime is dominated by useless recomputation that can be handled by memoization. So the distinction between languages is going to be dominated by their ability to do some moderately complex optimizations rather than by any intrinsic performance characteristics of their implementation.
Moreover, because the code is so small, there is likely to be major side effects as a result of effectively random differences--consider the effects of the code placement that cause a spurious difference between C and C++ kernels of about 20%. The JS version is going to get hit with a deoptimization at the very end (it might not impact performance) because the final result does not fit in an int32_t, and suddenly fib is no longer a well-typed function.
Microbenchmarking is _hard_, and it is all too easy for the microbenchmark to cease measuring the things that you want to measure.
F(N) can't complete until F(N-1) and F(N-2) have completed so it can sum up the values. If you pass the earlier computation, F(N-1), down to F(N-2) as a second parameter, you could get a tail call on the last part.
(I think I wrote that correctly, can't test here.)But that's a non-obvious tranformation. I really would like to see the compiler that recognized that this was a valid (computational) equivalent to the original.
And this idiom is recognized by both gcc and llvm. In fact. llvm has a test that specifically makes sure fib is transformed as thus: https://github.com/llvm-mirror/llvm/blob/30fa583f8430bfc7935...
We have to go up to the ten million'th term to get something that is not instantaneous (0.486s) for a result which has 2089876 digits.
λ: fibs = 1 : 1 : zipWith (+) fibs (tail fibs) λ: last $ take 47 fibs 2971215073
[0]: https://wiki.haskell.org/The_Fibonacci_sequence#Canonical_zi...
let fibs = 0 : 1 : zipWith (+) fibs (tail fibs) in fibs !! 47
Shorter but less readable:
fix (scanl (+) 0 . (1:)) !! 47