Looks like there is a big degradation of performance for recursive algorithms between nim-10.1 and MASTER. The runtime of Fibonacci (50) on my machine compiled with nim-10.1 is ~31s (the binary file is 65k):
time ./fibonacci_10_1
12586269025.0
real 0m31.707s
user 0m31.687s
sys 0m0.002s
The same code compiled with nim-master (the binary file is 161k) running on the same machine, I stopped it after 2 min:
time ./fibonacci
^CTraceback (most recent call last)
fibonacci.nim(8) fibonacci
.......
fibonacci.nim(6) fibonaci
fibonacci.nim(6)
fibonaci
SIGINT: Interrupted by Ctrl-C.
real 2m51.741s
user 2m51.580s
sys 0m0.052s
He talks about the code in his other post I bet:
proc fibonacci(n: int): float =
if n < 2:
result = float(n)
else:
result = fibonacci(n-1) + fibonacci(n-2)
echo fibonacci(50)
Some details may shed some light on xyz32's config issue. If gcc is his backend C compiler then the last few levels of recursion can be unrolled yielding a full 8X speedup (since almost all time is in call overhead). You can see the unrolling in generated asm. The Nim-generated C code looks like this (simplified/C-ified):
#include <stdio.h>
double fibonacci(const long long n) {
if (n < 2) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
void callIt(void) {
double f = fibonacci(50);
printf("%.16g\n", f);
}
void main(void) {
void (*volatile inner)() = callIt;
(*inner)();
}
@OderWat Yes That is the nim code.
@Araq Both versions are built using nimble build
@mora I will post the c code once I get home.
I will try to do some more investigation on this.
If you want to cheat and speed it up, {.inline.} the proc and add caching ;-)
var f: seq[float] = newSeq[float](50)
proc fibonacci*(n: int): float {.inline.} =
if n < 2: result = n.float
else:
if f[n-1] == 0:
f[n-1] = fibonacci(n-1)
if f[n-2] == 0:
f[n-2] = fibonacci(n-2)
result = f[n-2] + f[n-1]
echo fibonacci(50)
@jlp765 Yes, there are better ways of calculating Fibonacci, if that is your goal :)
The purpose of the code I wrote is to be as simple as possible (syntactically) and to test the language ability of handling large recursive code (javascrip will crash if you implement the same algorithm in it). And at the end you get a time measure and a number that you can check.
To put it another way, CPU designers use PI or other numbers to check their CPU: https://en.wikipedia.org/wiki/Pentium_FDIV_bug
This recursive Fibonacci looks to me like a decent enough way of testing the stability of a compiler.
@Araq You are right it looks like an environment issue:
/* Generated by Nim Compiler v0.11.2 */
...
/* Command for C compiler:
gcc -c -w -O3 -fno-strict-aliasing -I/media/data/xyz/devel/nim/Nim/lib -o
/media/data/xyz/devel/performance/fibonacci_nim/nimcache/fibonaci_fibanaci.o
/media/data/xyz/devel/performance/fibonacci_nim/nimcache/fibonaci_fibanaci.c */
/* Generated by Nim Compiler v0.12.1 */
...
/* Command for C compiler:
gcc -c -w -I/media/data/xyz/programare/nim/compiler/Nim/lib -o
/media/data/xyz/programare/performance/fibonacci_nim/nimcache/fibonacci_fibonacci.o
/media/data/xyz/programare/performance/fibonacci_nim/nimcache/fibonacci_fibonacci.c */
Does this mean nimble build no longer builds in release mode?
You can use nimble c and pass whatever options you want. nimble c will do the same as nim c but also resolve the dependencies.
Once this PR lands, you will be able to use nimble together with nimscript (so, no, nimble is not superseded)
@filcuc I have an old installation of nim/nimble on a VM, and nimble build always used to build in release mode. Personaly I think that is how it should be. By default the point of building a software is to be given to the people :).
So I would call this a bug, or a functionality change in nimble.
@andrea nimble c also requires a nim file name, the same file name that is stored in the nimble project file so it is error prone, and hacky to automate.