Recursive fibonacci benchmark using top languages on GitHub(github.com)
github.com
Recursive fibonacci benchmark using top languages on GitHub
https://github.com/drujensen/fib
169 comments
Breaking benchmarks... Is that like the time I fiddled with the corresponding C program trying to get it to run at least in the same ballpark as the Rust version? That was until I determined that the Rust optimizer noted that the results of the 'meat' of the test were never used so it just optimized the whole thing away. :) (I thought it was a little disingenuous for the Rust folks to use this as an example of how performant Rust was.)
I used to benchmark using fibonacci, but the recursive method is just awful because it does a lot of function calls and you're essentially benchmarking that. Then I switched to finding primes using the Sieve of Sundaram. It uses arrays, hashes/maps/dicts and two loops. Also wastes a lot of memory if you don't split your search domain into ranges. The surprise was that Go and D (in that order) turned out to be faster than Rust mainly due to Rust's HashMap SipHash algorithm. I gave up trying to use other hash libraries (SeaHash specifically) that are not part of the standard lib, because it was quite frustrating compared to D.
> gave up trying to use other hash libraries
fwiw a Rust k-nucleotide program using indexmap:
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
fwiw a Rust k-nucleotide program using indexmap:
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
> really don't think comparing them from a performance benchmark makes much sense
No, it really doesn't — but if you provide times we all know that's exactly what people will do.
That's why the same comparison was removed from the benchmarks game and replaced with tasks that were still toy but more than a dozen lines.
> adding all of your change requests
These are the programs that were replaced:
https://salsa.debian.org/benchmarksgame-team/archive-alioth-...
https://salsa.debian.org/benchmarksgame-team/archive-alioth-...
No, it really doesn't — but if you provide times we all know that's exactly what people will do.
That's why the same comparison was removed from the benchmarks game and replaced with tasks that were still toy but more than a dozen lines.
> adding all of your change requests
These are the programs that were replaced:
https://salsa.debian.org/benchmarksgame-team/archive-alioth-...
https://salsa.debian.org/benchmarksgame-team/archive-alioth-...
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:
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
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:
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
An Intel engineer gave a presentation at the 2016 LLVM Developers' Meeting that gives some insight: http://llvm.org/devmtg/2016-11/Slides/Ansari-Code-Alignment.... (for the slides).
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.
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.
Thanks. This looks familiar, but I thought I had seen something similar in a blog form. Edit: Found it! https://dendibakh.github.io/blog/2018/01/18/Code_alignment_i... https://news.ycombinator.com/item?id=16198171
FWIW, this is what the function looks like at 0x10070:
FWIW, this is what the function looks like at 0x10070:
0000000000010070 <_Z3fibl>:
10070: 48 83 ff 01 cmp $0x1,%rdi
10074: 7e 32 jle 100a8 <_Z3fibl+0x38>
10076: 55 push %rbp
10077: 31 ed xor %ebp,%ebp
10079: 53 push %rbx
1007a: 48 89 fb mov %rdi,%rbx
1007d: 48 83 ec 08 sub $0x8,%rsp
10081: 48 8d 7b ff lea -0x1(%rbx),%rdi
10085: 48 83 eb 02 sub $0x2,%rbx
10089: e8 e2 ff ff ff callq 10070 <_Z3fibl>
1008e: 48 01 c5 add %rax,%rbp
10091: 48 83 fb 01 cmp $0x1,%rbx
10095: 7f ea jg 10081 <_Z3fibl+0x11>
10097: 48 83 c4 08 add $0x8,%rsp
1009b: 48 8d 45 01 lea 0x1(%rbp),%rax
1009f: 5b pop %rbx
100a0: 5d pop %rbp
100a1: c3 retq
100a2: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)
100a8: b8 01 00 00 00 mov $0x1,%eax
100ad: c3 retq
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:
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.
In other words, the function was transformed from:
uint64_t fib(uint64_t n) {
if (n <= 1) return 1;
return fib(n - 1) + fib(n - 2);
}
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;
}
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
Doesnt gcc8 include spectre mitigations?
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.
The owner of this repo has no idea it’s trending on HN. This issue gave me a good laugh: https://github.com/drujensen/fib/issues/51
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.
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.
Fibonacci (as implemented here) shouldn't be aided by any TCO. The execution trace will be something like:
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.
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.
F(N) -- F(N-2) ...
|
F(N-1) -- F(N-3) ...
|
F(N-2) -- F(N-4) ...
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).
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.
But it is aided by tail-call optimization. Suppose you have a function as follows:
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...
int foo(int x) {
if (test(x)) return C;
return evaluate(x) + foo(adjust(x));
}
int foo(int x) {
int accum = C;
for ( ; !test(x); x = adjust(x)) {
accum += evaluate(x);
}
return accum;
}
int fib(int x) {
int accum = 1;
for (; x > 1; x -= 2) {
accum += fib(x - 1);
}
return accum;
}
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...
yup, this was my original goal.
its exactly how you do a benchmark of recursive Fibonacci performance, which is what it is called.
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.
Probably more about the difference between "echo" and "std::cout << ... << std::endl;" than the recursive function call.
I would be very very surprised if printing "2971215073" accounted for more than 1 second of runtime.
std::endl flushes which isn't cheap, you're generally better off simply steaming in a newline.
Don't see the point really.
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_?
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_?
> Fib is the poster boy for tail recursion
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.
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.
some compilers can rearrange it to be tail recursive automatically
Pretend you're a compiler, what changes would you make to this to make it tail recursive:
fib(0) -> 1;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).
Fun challenge.
https://paste.pound-python.org/show/m403qNkpS5I8dnYjJGJq/
I wanna see the compiler that gets that.
https://paste.pound-python.org/show/m403qNkpS5I8dnYjJGJq/
I wanna see the compiler that gets that.
Which compilers can rearrange fib, with two recursive calls, into being tail recursive?
Any LLVM-based compiler. GCC.
If it knows it's a pure function, it's possible. It'd have to be a very specific optimization pass though.
But that doesn't make it "poster boy" material, in my opinion.
I called it that because I've seen fib be the go-to example of so many introductions to functional programming.
But I suppose it's more accurate to describe it as the poster boy example for changing an implementation to make it tail recurse.
But I suppose it's more accurate to describe it as the poster boy example for changing an implementation to make it tail recurse.
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?
You're right that tail recursion doesn't help - the final operation is the addition, not a recursive call.
Just to underline the futility of this, if you are clever you can let the compiler do it.
https://everything2.com/title/C%252B%252B%253A+computing+Fib...
https://everything2.com/title/C%252B%252B%253A+computing+Fib...
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.
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 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.
[1] http://www.skiplang.com/ [2] https://news.ycombinator.com/item?id=18077612
[1] http://www.skiplang.com/ [2] https://news.ycombinator.com/item?id=18077612
Memoization isn't a new thing. It's available in Haskell as a first class citizen.
This benchmark explicitly targets popular languages, and it happens to include no pure functional languages.
This benchmark explicitly targets popular languages, and it happens to include no pure functional languages.
> 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:
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.htmlBut 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.
Haskell is call-by-need so you get guarantees you wouldn't otherwise. It's not the same as memoization but it gives you what you want in any case.
> 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.
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.
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.
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
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 !
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.
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.
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.
So you didn't write the non-recursive version?
Yeah that fib-mem.go is just weird. It's almost a WTF.
fib(180) without caching would take billions of years to complete, so "slow" is an understatement.
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.
Billions of years is a gross understatement.
cause o^2n?
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.
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.
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.
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.
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.
Java needs warmup time though to optimize, and the configuration of the vm can have a heavy inpact on performance as well
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.
Startup time of most VMs is in miliseconds. For VM stuff that includes compilation all times are 10s+.
SBCL on my 2012 Mac mini:
rjmacmini:~$ sbcl
This is SBCL 1.4.2, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.
SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
* (defun fib (n)
(declare (fixnum n)
(optimize (speed 3) (debug 0) (safety 0)))
(if (<= n 1)
1
(the fixnum
(+ (fib (- n 1))
(fib (- n 2))))))
FIB
* (time (fib 46))
Evaluation took:
14.957 seconds of real time
14.947616 seconds of total run time (14.934818 user, 0.012798 system)
99.94% CPU
38,799,794,836 processor cycles
0 bytes consed
2971215073
* (SAVE-LISP-AND-DIE "/tmp/fiblisp" :toplevel (lambda (&rest args) (print (fib 46))) :executable t)
; in: SAVE-LISP-AND-DIE "/tmp/fiblisp"
; (LAMBDA (&REST ARGS) (PRINT (FIB 46)))
;
; caught STYLE-WARNING:
; The variable ARGS is defined but never used.
;
; compilation unit finished
; caught 1 STYLE-WARNING condition
[undoing binding stack and other enclosing state... done]
[defragmenting immobile space... 643+15263+734+344+25029+16756 objects... done]
[saving current Lisp image into /tmp/fiblisp:
writing 0 bytes from the read-only space at 0x20000000
writing 848 bytes from the static space at 0x20100000
writing 1863680 bytes from the immobile space at 0x20300000
writing 11472480 bytes from the immobile space at 0x21b00000
writing 26542080 bytes from the dynamic space at 0x1000000000
done]
rjmacmini:~$ time /tmp/fiblisp
2971215073
real 0m14.785s
user 0m14.755s
sys 0m0.020s
rjmacmini:~$I don't think adding debug/safety 0 are really worth it. In this:
(declaim (optimize speed)
(ftype (function (fixnum) fixnum) fib))
(defun fib (n)
(if (<= n 1)
1
(+ (fib (- n 1))
(fib (- n 2)))))
(print (fib 46))
Generally depends on the implementation and the default behavior.
But anyway, it's a good point.
But anyway, it's a good point.
They should
- 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)
- 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)
Re. Go.
I've turned this code into a Go benchmark and run it with both the default cmd/compile (1.11) and gccgo (8.2.0).
Here is the gist, please tell me if I screwed up somewhere: https://gist.github.com/ainar-g/1bd363d41c441d9ebf05c0c0b9f2....
EDIT: After some disassembly and experimenting, it seems like what we see here is some clever unrolling and memoisation. If I change 46 from a constant to a variable, it becomes twice as slow. Plus there is this in disasm:
I've turned this code into a Go benchmark and run it with both the default cmd/compile (1.11) and gccgo (8.2.0).
cmd/compile:
BenchmarkFib-4 1 16530409619 ns/op
PASS
ok command-line-arguments 16.533s
gccgo:
BenchmarkFib-4 2 776368644 ns/op
PASS
ok command-line-arguments 2.381s
Here is the gist, please tell me if I screwed up somewhere: https://gist.github.com/ainar-g/1bd363d41c441d9ebf05c0c0b9f2....
EDIT: After some disassembly and experimenting, it seems like what we see here is some clever unrolling and memoisation. If I change 46 from a constant to a variable, it becomes twice as slow. Plus there is this in disasm:
/tmp/go/fibbench_test.go:13
return fib(n-1) + fib(n-2)
30b9: e8 72 ff ff ff callq 3030 <command_line_arguments.fib>
30be: bf 25 00 00 00 mov $0x25,%edi
30c3: e8 68 ff ff ff callq 3030 <command_line_arguments.fib>
30c8: bf 24 00 00 00 mov $0x24,%edi
30cd: e8 5e ff ff ff callq 3030 <command_line_arguments.fib>
30d2: bf 23 00 00 00 mov $0x23,%edi
...
Microbenchmarks like this can be difficult to perform in practice, as gccgo can perform optimizations on pure functions that prevent Go's benchmarks from actually fully repeating a test. Also, this is a special case in which gccgo shines, specifically because it is completely cpu-bound. Generally, there isn't nearly as much of a performance difference.
[deleted]
[deleted]
SBCL on my AMD FX(tm)-8350 Eight-Core Processor:
~$ sbcl
This is SBCL 1.4.11, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.
SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
* (defun fibonacci-tail-recursive ( n &optional (a 1) (b 1))
(declare (optimize (speed 3) (safety 0) (debug 0))
(type fixnum n a b))
(if (< n 1)
a
(fibonacci-tail-recursive (- n 1) b (+ a b))))
FIBONACCI-TAIL-RECURSIVE
* (time (fibonacci-tail-recursive 46))
Evaluation took:
0.000 seconds of real time
0.000001 seconds of total run time (0.000001 user, 0.000000 system)
100.00% CPU
2,513 processor cycles
0 bytes consed
2971215073
*Different machine and superior algorithm, where are you aiming with this?
It's true, I only read recursive Fibonacci. Now I see my mistake.
That being said, this one [0] gives correct results and runs slightly faster :)
[0] https://gist.github.com/codr4life/59f2c02403b27d551e706f673b...
[0] https://gist.github.com/codr4life/59f2c02403b27d551e706f673b...
Because Fortran was listed as x.xxx, I figured I'd try it.
Taking the minimum of 100 runs of gcc/gfortran, 200 runs of g++, and 4 runs of Julia 1.1-dev:
gcc: 3.4866
g++: 3.4428
gfortran: 3.4953
Julia: 8.0378
I was doing other things while the benchmarks ran, which added noise. For the first run of g++, the mean was slightly higher than C's mean, while the standard deviation was much higher than C or Fortran's. So I reran it for C++, and then decided to just report the minimums for everything instead, because the minimum is probably the least biased measure.
So long as there are no allocations that occasionally get cleaned up by a garbage collector. If there were, the GC cost should get amortized over all the runs that contributed to it. We don't have to worry about this here.
While the C and C++ assembly for the fib function was the same, Fortran's was different.
Julia's assembly was extremely brief in comparison, because it doesn't have any recursion optimizations -- it is just the check and then two calls to itself.
gcc: 3.4866
g++: 3.4428
gfortran: 3.4953
Julia: 8.0378
I was doing other things while the benchmarks ran, which added noise. For the first run of g++, the mean was slightly higher than C's mean, while the standard deviation was much higher than C or Fortran's. So I reran it for C++, and then decided to just report the minimums for everything instead, because the minimum is probably the least biased measure.
So long as there are no allocations that occasionally get cleaned up by a garbage collector. If there were, the GC cost should get amortized over all the runs that contributed to it. We don't have to worry about this here.
While the C and C++ assembly for the fib function was the same, Fortran's was different.
Julia's assembly was extremely brief in comparison, because it doesn't have any recursion optimizations -- it is just the check and then two calls to itself.
Yes, Julia doesn't do tail call optimizations (TCO) which it could do with LLVM. Just not enabled yet. I find it funny when people try to say that Julia's website benchmarks are cherrypicked to look good when the first example shows that it's tracking an optimization which it's missing...
One can improve the JAVA result by allowing the JIT compiler to inline the recursive calls.
-XX:MaxRecursiveInlineLevel=1 (default): 6.667 s
-XX:MaxRecursiveInlineLevel=2: 6.141 s
-XX:MaxRecursiveInlineLevel=3: 5.768 s
-XX:MaxRecursiveInlineLevel=4: 5.400 s
-XX:MaxRecursiveInlineLevel=5: 5.361 s
-XX:MaxRecursiveInlineLevel=6: 5.072 s
fib.c with -O3: 3.764 s
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.
$ swiftc -Ounchecked -g fib.swift
$ time ./fib
2971215073
real 0m6.341s user 0m6.297s sys 0m0.023s
Using unchecked mode is closer to what C is doing (skipping bounds and overflow checks).
real 0m6.341s user 0m6.297s sys 0m0.023s
Using unchecked mode is closer to what C is doing (skipping bounds and overflow checks).
I would submit an entry for my own project, Snabl [0]; but it intentionally doesn't support the algorithm since naive recursion beyond a few levels doesn't make much sense in practice. I added a separate keyword to force tail calls since that's usually what you want.
[0] https://github.com/codr4life/snabl#function
[0] https://github.com/codr4life/snabl#function
A few observations:
- on my machine, C++ is slower than C.
- I thought that in Julia, startup and compile time could be a factor, but they're pretty negligible (maybe 1 to 5% or so of the runtime, for Julia 0.7).
- Without the -O3 switch, the runtime more or less doubles for C and C++, making these languages slower than Swift, Go, Java, Dart, Julia, etc. That surprised me.
- on my machine, C++ is slower than C.
- I thought that in Julia, startup and compile time could be a factor, but they're pretty negligible (maybe 1 to 5% or so of the runtime, for Julia 0.7).
- Without the -O3 switch, the runtime more or less doubles for C and C++, making these languages slower than Swift, Go, Java, Dart, Julia, etc. That surprised me.
The -O3 switch removes a recursive call, among other things (https://godbolt.org/z/oS3Cju).
Interesting. (Awesome compiler explorer website, btw).
The Julia version (whose runtime is halfway between the C versions with vs without -O3) contains both recursive calls, FWIW.
The Julia version (whose runtime is halfway between the C versions with vs without -O3) contains both recursive calls, FWIW.
Yeah, startup and compilation time in Julia is not a big deal. One could even make the compiler work a bit harder, but you would have to ask a lawyer if this still counts as recursion ;-)
julia> function fib(::Val{n}) where n
if n <= 1 return 1 end
return fib(Val(n - 1)) + fib(Val(n - 2))
end
julia> fib(n) = fib(Val(n))
julia> @time fib(46) # Compilation and execution
0.095409 secondsI decided to try this challenge using Solidity and made a little writeup comparing four implementations.
https://medium.com/@jpa_of_snc/fibonacci-in-solidity-8477d90...
https://medium.com/@jpa_of_snc/fibonacci-in-solidity-8477d90...
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.
Elixir can be made much faster via tail call optimization.
Something like:
Something like:
def fibonacci(n) when n >= 0, do: fib(0, 1, n)
defp fib(a, b, n) do
case n do
0 ->
a
_ ->
fib(b, a + b, n - 1)
end
endAgreed. Everybody uses TCO in Elixir. It's the standard way to write servers and store state. So it makes sense to use it the benchmark or it will be very un-Elixir.
You could do that in python as well:
def fib(a, b, n):
return a if n == 0 else fib(b, a+b, n-1)
There's a PR there to do just that. I don't follow the reasoning that it's not been accepted. It's also using Elixir script instead of precompiled Elixir.
https://github.com/drujensen/fib/pull/33
https://github.com/drujensen/fib/pull/33
Yeah, I don't think this breaks any of the rules. We are still using recursion. Just leveraging what the language has to offer.
The algorithm being benchmarked is the naive double-recursive fibonacci algorithm, which ends up performing over a billion addition operations in this case. The tail-recursive function above is the iterative bottom-up fibonacci algorithm that does it in about 50 addition operations. It's true that both use recursion, but the second is definitely not the tail-recursive version of the first.
It is possible to do a form of tail call optimization for the double-recursive algorithm, described here: https://news.ycombinator.com/item?id=18096804
This reduces the number of total function calls but not the number of additions (since it's not changing the algorithm, just the way the function invocation strategy when running the algorithm).
It is possible to do a form of tail call optimization for the double-recursive algorithm, described here: https://news.ycombinator.com/item?id=18096804
This reduces the number of total function calls but not the number of additions (since it's not changing the algorithm, just the way the function invocation strategy when running the algorithm).
Something isn't quite right. Nim 'compiles' into C code ready for compilation. It should not be faster than the raw C and C++ implementation. Frankly even the C/C++ implementation shouldn't be so different.
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"?).
Sure but which languages are still there to calculate fib(100) and which bailed out?
For Haskell try:
-- Memorized variant is near instant even after 10000 memoized_fib :: Int -> Integer memoized_fib = (map fib [0 ..] !!) where fib 0 = 0 fib 1 = 1 fib n = memoized_fib (n-2) + memoized_fib (n-1)
or
fibM = \n -> values !! n where values = [fibAux m | m <- [0..]] fibAux n | n <= 1 = n | otherwise = fibM (n-2) + fibM (n-1)
or
fibM2 :: Int -> Integer fibM2 = \n -> values !! n where values = [fibAux m | m <- [0..]] fibAux 0 = 0 fibAux 1 = 1 fibAux n = fibM2 (n-2) + fibM2 (n-1)
Run the following at the ghci Haskell prompt:
memoized_fib 47
fibM 47
fibM2 47
If you want to wait try:
-- Traditional implementation of fibonacci, hangs after about 30 slow_fib :: Int -> Integer slow_fib 0 = 0 slow_fib 1 = 1 slow_fib n = slow_fib (n-2) + slow_fib (n-1)
-- Memorized variant is near instant even after 10000 memoized_fib :: Int -> Integer memoized_fib = (map fib [0 ..] !!) where fib 0 = 0 fib 1 = 1 fib n = memoized_fib (n-2) + memoized_fib (n-1)
or
fibM = \n -> values !! n where values = [fibAux m | m <- [0..]] fibAux n | n <= 1 = n | otherwise = fibM (n-2) + fibM (n-1)
or
fibM2 :: Int -> Integer fibM2 = \n -> values !! n where values = [fibAux m | m <- [0..]] fibAux 0 = 0 fibAux 1 = 1 fibAux n = fibM2 (n-2) + fibM2 (n-1)
Run the following at the ghci Haskell prompt:
memoized_fib 47
fibM 47
fibM2 47
If you want to wait try:
-- Traditional implementation of fibonacci, hangs after about 30 slow_fib :: Int -> Integer slow_fib 0 = 0 slow_fib 1 = 1 slow_fib n = slow_fib (n-2) + slow_fib (n-1)
The sport here seems to be which compiler manages to re-write the bad code best.
Tail call optimization is only marginally relevant here, since the tail call is the addition, not one of the recursions.
Tail call optimization is only marginally relevant here, since the tail call is the addition, not one of the recursions.
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 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.
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.
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.
The example was indeed not playing to its strengths, it wasn't making use of tail call optimization.
I made a PR to fix that: https://github.com/drujensen/fib/pull/33
I made a PR to fix that: https://github.com/drujensen/fib/pull/33
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.
18> timer:tc(fun fib:main/0).
2971215073
{59352962,ok} % 59s… slooow
19> hipe:c(fib, [o3]). % compile with Hipe
{ok,fib}
20> timer:tc(fun fib:main/0).
2971215073
{12570352,ok} % 12.5s!
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).
What do you mean by redo?
Does Zig get a mention? https://godbolt.org/z/G0uvIU
It would be great to see webassembly on here as well! (Maybe hand-written and compiled from a few different languages.)
A pretty fast way in Haskell/ghci[0] is:
λ: fibs = 1 : 1 : zipWith (+) fibs (tail fibs) λ: last $ take 47 fibs 2971215073
[0]: https://wiki.haskell.org/The_Fibonacci_sequence#Canonical_zi...
λ: fibs = 1 : 1 : zipWith (+) fibs (tail fibs) λ: last $ take 47 fibs 2971215073
[0]: https://wiki.haskell.org/The_Fibonacci_sequence#Canonical_zi...
It got mingled without newlines (and "λ:" prompt doesn't help readability). In one line:
let fibs = 0 : 1 : zipWith (+) fibs (tail fibs) in fibs !! 47
Shorter but less readable:
fix (scanl (+) 0 . (1:)) !! 47
let fibs = 0 : 1 : zipWith (+) fibs (tail fibs) in fibs !! 47
Shorter but less readable:
fix (scanl (+) 0 . (1:)) !! 47
What happened to the "Great Programminglanguage Shootout"?
Google can be your friend :-)
https://www.google.com/search?q=Great+Programminglanguage+Sh...
https://www.google.com/search?q=Great+Programminglanguage+Sh...
Yeah, I meant why is the project so quiet lately, and why doesn't HN refer to it more often.
Updates continue as usual:
https://salsa.debian.org/benchmarksgame-team/benchmarksgame/...
HN does refer to it:
https://hn.algolia.com/?query=benchmarksgame&sort=byDate&pre...
As-always people crave novelty.
As-always it's easier to write simple 10 line programs rather than 100 line programs for 10 different tasks.
https://salsa.debian.org/benchmarksgame-team/benchmarksgame/...
HN does refer to it:
https://hn.algolia.com/?query=benchmarksgame&sort=byDate&pre...
As-always people crave novelty.
As-always it's easier to write simple 10 line programs rather than 100 line programs for 10 different tasks.
The rigth way to do fibonacci would probably be to add memoization...
Or turn it into a simple iterative process, instead of a recursive process. They explain how quite simply in SICP:
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:
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:
def fib(n):
a = 1
b = 0
i = 0
while i < n:
temp = a
a += b
b = temp
i += 1
return a
The "right" way to do Fibonacci is to use matrix multiplication to get the nth Fibonacci number in logarithmic time (google Fibonacci log n matrix).
A matrix implementatiom in JavaScript:
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
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
Why not calculate it in constant time ?
https://artofproblemsolving.com/wiki/index.php?title=Binet%2...
https://artofproblemsolving.com/wiki/index.php?title=Binet%2...
As mentioned in other comments, working with floating point numbers in practice is trickier than it looks in theory:
http://raganwald.com/2013/03/26/the-interview.html
http://raganwald.com/2013/03/26/the-interview.html
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?
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?
true: adding 2 64 bit numbers is constant time for me, but adding 2 4096 bit numbers is not. Eventually, even the simplest operation becomes O(ln n)
[deleted]
This is bullshit.
IMHO, the recursive pattern is one of the worst constructs, this is really bad engineering and should not be used for benchmarking...
So you're saying never use recursion? Or never benchmark it? I don't get it, it's a tool; a pretty good tool when combined with tail call optimization. Yes, the algorithm they use is naive; I believe that's part of the point.
[deleted]
Why is python 2.7 faster than 3? I thought one of the big reasons to switch to 3 was because of performance
[deleted]
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).
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).
Something to do with python 3 using long† integer as the default int, which can be arbitrarily long, so it may have slower arithmetics.
† not to be confused with the typical C long int type.
† not to be confused with the typical C long int type.
I'm just going to put this out there: this benchmark is silly, and only good for making languages with specific types of calling styles look good. It doesn't predict any real world performance. It doesn't speak to real world optimizer outcomes. It really just measures how shallow your call abstraction is. Several languages here perform much worse than equivalent code because the way the language interprets and executes naive recursion is different.
I've seen this game before, so the very first place I looked was the Haskell version. Sure enough, it doesn't even try to force the call graph at all. There's even a section entitled, "breaks the benchmark" and it doesn't note Haskell or other languages with different call semantics are not doing the same thing at all. It just says Haskell doesn't terminate.
Confusingly, there is then a "mem" benchmark which seems to ask "What happens if we do this with even the vaguest damn about algorithmic complexity?" But these are so all-over-the-map they don't even come close to measuring the same thing and have different memory usage.
What's frustrating about this is that the double-uncached is always the wrong way to write this code. It's never good, it really doesn't benchmark anything real world. It's not even a very good compiler benchmark because many optimizers actually go under the hood and rewrite code that is in this obvious style to be something else entirely, just to do better on these benchmarks.
For the Haskell benchmark as an example, the best way to to write this lazily is to write a function that consumes and drops a list like so:
This approach isn't even particularly fair to other languages that are good at producing performant machine code, like Rust.
These games are not really indicative of anything. They waste energy. Folks should understand what their language runtimes and compilers are capable of, rather than asking, "How well does this fare on the worst possible algorithm for an operation who's semantics are only loosely defined?"
I've seen this game before, so the very first place I looked was the Haskell version. Sure enough, it doesn't even try to force the call graph at all. There's even a section entitled, "breaks the benchmark" and it doesn't note Haskell or other languages with different call semantics are not doing the same thing at all. It just says Haskell doesn't terminate.
Confusingly, there is then a "mem" benchmark which seems to ask "What happens if we do this with even the vaguest damn about algorithmic complexity?" But these are so all-over-the-map they don't even come close to measuring the same thing and have different memory usage.
What's frustrating about this is that the double-uncached is always the wrong way to write this code. It's never good, it really doesn't benchmark anything real world. It's not even a very good compiler benchmark because many optimizers actually go under the hood and rewrite code that is in this obvious style to be something else entirely, just to do better on these benchmarks.
For the Haskell benchmark as an example, the best way to to write this lazily is to write a function that consumes and drops a list like so:
fibF n = head $ drop n fibs
where
fibs = 0 : 1 : next fibs
next (first : rest) = (first + head rest) : next rest
-- Or using a library function most Haskell Fp devs know.
fibZip :: Int -> Int
fibZip n = head $ drop n fibz
where fibz = 0 : 1 : zipWith (+) fibz (tail fibz)
This approach isn't even particularly fair to other languages that are good at producing performant machine code, like Rust.
These games are not really indicative of anything. They waste energy. Folks should understand what their language runtimes and compilers are capable of, rather than asking, "How well does this fare on the worst possible algorithm for an operation who's semantics are only loosely defined?"
so node 18 and python 500? really?
Lua would probably outperform most languages on the list.
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
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.
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;
}
function fib(n)
if n <= 1 then
return 1
else
return fib(n - 1) + fib(n - 2)
end
end
print(fib(46))
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))
Hardware used is listed at the top of the readme. https://github.com/drujensen/fib/blob/master/README.md
In what way? Are you saying that Lua would be faster than the assembly that the processor executes to run the Lua program?
I have a similar GitHub repo, but with a more complicated example:
https://github.com/octonion/puzzles/tree/master/blackjack
https://github.com/octonion/puzzles/tree/master/blackjack
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"
$ time ./fibonacci.py 46
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
real 0m0.038s
user 0m0.015s
sys 0m0.018sRecursive fibonacci benchmark - you are doing something different in which case you could just evaluate the closed form φⁿ / √5 and be even faster.
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.
I decided to add the top languages on github to help give some idea of how crystal performed against them.
I'm happy to see so much discussion about it and was taken by surprise when my inbox was full this morning. Thanks @anonfunction. ;-)
The breaking benchmark examples were just that, examples of how to break the benchmark. I didn't expect to get a memoized version of every language and really don't think comparing them from a performance benchmark makes much sense. Let me know if i'm wrong about that.
I am fine adding all of your change requests and will try to keep the benchmarks up to date.