Mirror of forum.nim-lang.org

280 :: Fibonacci series recursive computation

• sigmaml (orginal) [2013-10-17T20:49:12+02:00] view original

  The following code computes the usual Fibonacci series number for a given n.

  
  import
    parseopt, strutils
  
  proc fib(n: int): int =
    if n < 2:
      return 1
    else:
      return fib(n-1) + fib(n-2)
  
  when isMainModule:
    var n = 0
    for kind, key, value in parseopt.getopt():
      case kind
      of parseopt.cmdArgument:
        n = strutils.parseInt(key)
      else:
        echo "!! Error"
    
    echo fib(n)
  Run

  For n = 40, the above code takes about 8.9 seconds. On the same machine, under the same conditions, the equivalent Julia code takes less than 1.5 seconds. What makes Nimrod so slow in comparison? Thanks.

  -- 0|0

---

• Orion (orginal) [2013-10-17T22:52:42+02:00] view original

  Try building with -d:release

  i.e. nimrod c -d:release fib.nim

  Edit: Here's my results

  fib 40

  165580141

  Time taken 0.335

  Note I added:

  import times
  ...
  let clockBegin = epochTime()
  echo fib(n)
  echo "Time taken ", formatFloat(epochTime() - clockBegin, ffDecimal, precision = 3)
  Run

---

• sigmaml (orginal) [2013-10-18T05:14:02+02:00] view original

  Yes, indeed! I forgot to compile it in release mode. Now for n = 40, it takes 0.287 seconds. Thanks!

  -- 0|0

---

• Jehan (orginal) [2013-10-18T14:46:23+02:00] view original

  To expand on Orion's answer, it can be useful to understand what precisely -d:release entails in order to only selectively turn the relevant options on and off for development and release.

  By default, Nimrod compiles (1) without optimization, (2) with line number/stack frame information enabled, (3) with checks turned on, and (4) with dead code elimination turned off. You can turn them on/off selectively during development, and several may be useful for release code, too.

  1. You can enable that selectively with -opt:speed or --opt:size. Note that size optimization is not mutually exclusive with optimization for speed; it is "optimize for speed, except for those optimizations that blow up the code size". Going for --opt:size can be useful if cache pressure is a problem. Optimization is good (even during development) when run time of your code contributes more to your turnaround time than compile time.
  2. Nimrod adds instructions to the generated C code to remember what position in the Nimrod source code the generated C code corresponds to and what functions have been called. These can be disabled with --stacktrace:off and --linetrace:off; note that if you specify --stacktrace:off, this implies --linetrace:off. If you use --stacktrace:off, then tracebacks on exceptions will no longer be printed; if you just use --linetrace:off, tracebacks will only contain function names, but no line information. Here, --linetrace:off can be useful if you have a long-running program, but still need some idea where an error occurs.
  3. Unlike C/C++ and like other Pascal-ish languages, Nimrod by default instruments the code with a lot of checks to ensure correctness. The one that kills performance in the fibonacci example is the --overflowChecks:on, which checks integer operations for overflow. You can turn all checks off (--checks:off) if you are certain that your code is bugfree; however, bound checks, field checks, and object conversion checks can still be useful in release code to prevent memory corruption. In this case, you can turn off checks individually (see nimrod --help for the list of options that relate to that). You can also enable/disable checks for part of the code with pragmas.
  4. Dead code elimination generally does little for the speed of a program, but only keeps the size of the final binary down by removing unreachable code. This can actually increase compile time; if you have very large modules, you may want to enable dead code elimination selectively for these modules with the {. deadCodeElim: on .} pragma during development.

  If you want to avoid typing in long lists of options, you can also put them in a configuration file and also make them conditional on other -d options; see the default config/nimrod.cfg for how -d:release and -d:quick work.

---

• sigmaml (orginal) [2013-10-18T15:48:17+02:00] view original

  Thank you, Jehan, for the detailed description of the compiler flags and their mechanisms of operation. It is very useful.

  These kinds of posts should be made sticky!

  -- 0|0

---

• fowl (orginal) [2013-10-27T22:04:14+01:00] view original

  agreed this should be archived somewhere

---