Why nim-1.6.20 only takes 2s but nim-2.0.14 66s when calculating fib(46)

[forchid]

Description

Nim-2.0.14 takes too long time (about 66s) when calculating fib(46) than nim-1.6.20 (only 2s), and nim-2.0.8 also takes 33s.

The test case

import times

proc fib(n: int): int =
 if n <= 1:
   return n
 else:
   return fib(n - 1) + fib(n - 2)

let a = cpuTime()
let r = fib(46)
let b = cpuTime()
echo "fib(46) = " & $r & "(" & $(b - a) & "s)"

Nim Version

nim-1.6.20, nim-2.0.8, and nim-2.0.14

Current Output

>nim c -d:release fib.nim
Hint: used config file '..\nim-1.6.20\config\nim.cfg' [Conf]
...
Hint: gc: refc; opt: speed; options: -d:release
43862 lines; 0.813s; 60.84MiB peakmem; proj: ..\fib.nim; out: ..\fib.exe [SuccessX]
perf>fib
fib(46) = 1836311903(2.133s)

>%nim2014_home%\bin\nim c -d:release fib.nim
Hint: used config file '..\nim-2.0.14\config\nim.cfg' [Conf]
..................
Hint: mm: orc; threads: on; opt: speed; options: -d:release
46463 lines; 4.234s; 74.207MiB peakmem; proj: ..\fib.nim; out: ..\fib.exe [SuccessX]
>fib
fib(46) = 1836311903(66.274s)

>%nim20_home%\bin\nim c -d:release fib.nim
Hint: used config file '..\nim-2.0.8\config\nim.cfg' [Conf]
..................
Hint: mm: orc; threads: on; opt: speed; options: -d:release
46354 lines; 4.203s; 71.148MiB peakmem; proj: ..\fib.nim; out: ..\fib.exe [SuccessX]
>fib
fib(46) = 1836311903(33.569s)

Expected Output

nim-2.0.8 and nim-2.0.14 takes a few seconds.

Known Workarounds

No response

Additional Information

No response

[juancarlospaco]

Memory management changed?
refc to orc, and also --threads:on became default, try --gc:arc --threads:off ?

[forchid]

@juancarlospaco This is a table of testing gc and threads in nim-2.0.14:
--mm --threads time

arc on 67s
arc off 3s
refc on 2s
refc off 2s

The test details

>%nim2014_home%\bin\nim c -d:release --mm:arc --threads:on fib.nim
Hint: used config file '..\nim-2.0.14\config\nim.cfg' [Conf]
Hint: used config file '..\nim-2.0.14\config\config.nims' [Conf]
...
Hint: mm: arc; threads: on; opt: speed; options: -d:release
45886 lines; 3.344s; 74.223MiB peakmem; proj: ..\fib.nim; out: ..\fib.exe [SuccessX]

>fib
fib(46) = 1836311903(67.44399999999999s)

>%nim2014_home%\bin\nim c -d:release --mm:arc --threads:off fib.nim
Hint: used config file '..\nim-2.0.14\config\nim.cfg' [Conf]
Hint: used config file '..\nim-2.0.14\config\config.nims' [Conf]
...
Hint: mm: arc; opt: speed; options: -d:release
44592 lines; 4.655s; 74.301MiB peakmem; proj: ..\fib.nim; out: ..\fib.exe [SuccessX]

>fib
fib(46) = 1836311903(3.624s)

>%nim2014_home%\bin\nim c -d:release --mm:refc --threads:on fib.nim
Hint: used config file '..\nim-2.0.14\config\nim.cfg' [Conf]
Hint: used config file '..\nim-2.0.14\config\config.nims' [Conf]
...
Hint: mm: refc; threads: on; opt: speed; options: -d:release
47578 lines; 4.391s; 73.598MiB peakmem; proj: ..\fib.nim; out: ..\fib.exe [SuccessX]

>fib
fib(46) = 1836311903(2.135s)

>%nim2014_home%\bin\nim c -d:release --mm:refc --threads:off fib.nim
Hint: used config file '..\nim-2.0.14\config\nim.cfg' [Conf]
Hint: used config file '..\nim-2.0.14\config\config.nims' [Conf]
...
Hint: mm: refc; opt: speed; options: -d:release
46178 lines; 3.969s; 74.047MiB peakmem; proj: ..\fib.nim; out: ..\fib.exe [SuccessX]

>fib
fib(46) = 1836311903(2.106s)

This shows that its' too slow when using --mm:arc and --threads:on.

[rockcavera]

With --threads:off there is an improvement, but the real problem is in --exceptions:goto. Just compile with --exceptions:setjmp and the time is the same between versions

[rockcavera]

Of course, the analysis must go deeper and perform a disassembly of the executables to see if there is a difficulty for the C compiler to optimize (pre-calculate) the C code generated by Nim with --exceptions:goto.

[forchid]

With --threads:off there is an improvement, but the real problem is in --exceptions:goto. Just compile with --exceptions:setjmp and the time is the same between versions

Sure!

[Araq]

You don't have to change the exceptions mode globally, a single .quirky should also do the trick:

proc fib(n: int): int {.quirky.} =
 if n <= 1:
   return n
 else:
   return fib(n - 1) + fib(n - 2)

I doubt 1.6 supports this annotation though.

[forchid]

You don't have to change the exceptions mode globally, a single .quirky should also do the trick

@Araq After adding the pragma .quirky, there has been a significant improvement, and the cost time 8s of this nim-2.0.14 program is same as java, rust, or c++, but is greater than the nim-1.6.20's.

[Araq]

The nim-1.6 uses a cheat that nim-2.0 could reimplement but it pretty much improves the one meaningless fib benchmark and nothing else. You still get this cheat with 2.0 and mm:refc.

[juancarlospaco]

Maybe {.quirky.} can be documented?, is it supported on the stdlib? 🤔