Mirror of forum.nim-lang.org

10322 :: Recursive Fibonacci function

• phoenix27 (orginal) [2023-07-04T16:29:19+02:00] view original

  import std/[times, os]
  proc fib(n: uint64): uint64 =
      if n <= 1: return n
      return fib(n - 1) + fib(n - 2)
  let time = cpuTime()
  echo fib(47)
  echo "Time taken: ", cpuTime() - time
  Run

  
  #include <stdio.h>
  #include <stdlib.h>
  #include <stdint.h>
  #include <time.h>
  static uint64_t fib(uint64_t n) {
      if (n <= 1) return n;
      return fib(n - 1) + fib(n - 2);
  }
  
  
  int main() {
      time_t t1 = time(NULL);
      uint64_t res = fib(47);
      time_t t2 = time(NULL);
      printf("%llu seconds\n", t2 - t1);
      return 0;
  }
  Run

  I'm trying to learn C because i'm tired of the new buzz word "safe" that, like a virus(i would say even worse than the FAKE corona "virus"), has contamined the minds and hearts of all you professional programmers(i'm an amateur), and so i chose the most unsafe language that there is, C (Btw i love pointers, although i still don't understand them well and i don't know if i'll ever understand them ahaha). Anyway i tried to benchmark these 2 functions, one in C and one in Nim, a language that i like, but pls Araq stop with this safety thing, LIFE ITSELF IS NOT SAFE and that's the beauty of it and of the most unsafe language out there, C!! , Anyway i was surprised to know that the C version executes in ~17 seconds while the Nim one, with '-d:release' flag of course, in 7.something seconds. What kind of sorcery does your "safe" language do? If i remember well, when i was learning a bit about Nim i read that the compiler first spits out C code which is then compiled to native code. Well, i used the same compiler for the C and Nim version, so how can C be so much slower than the Nim version? Anybody knows?

---

• mratsim (orginal) [2023-07-04T17:11:17+02:00] view original

  See:

  • https://forum.nim-lang.org/t/4253

  Nim code is easier to analyze for the C compiler so the C compiler has an easier time doing constant folding and precomputing fibonacci .

  Besides that, it's also possible that the compiled code has (by a stroke of luck) better alignment:

  • https://easyperf.net/blog/2018/01/18/Code_alignment_issues

  Or have link order interfere with benchmark:

  • https://web.archive.org/web/20170929071306/https://www.cis.upenn.edu/~cis501/papers/producing-wrong-data.pdf

---

• r3c (orginal) [2023-07-04T17:27:32+02:00] view original

  What C compiler and what flags? You can see the c-flags Nim used in the generated source/json. Try compiling the C code with those flags.

---

• ingo (orginal) [2023-07-04T17:30:35+02:00] view original

  Because the compiler recognizes yet an other Fibobenchmark and just uses Binet's formula. ;)

---

• phoenix27 (orginal) [2023-07-04T17:35:06+02:00] view original

  I used gcc 8.1.0 with the MingW distribution on windows 7. As IDE i use code::blocks. For the c version i used the -O3 flag. The strange thing is that on the web page where i took the function from (https://github.com/drujensen/fib) the C result is in line with the Nim one, whereas on my pc, an i5 20gb ram, is much slower

---

• phoenix27 (orginal) [2023-07-04T17:36:13+02:00] view original

  Thank you

---

• SpotlightKid (orginal) [2023-07-04T21:47:28+02:00] view original

  You should mention that you already posted this question on Stackoverflow:

  https://stackoverflow.com/questions/76611371/execution-time-of-recursive-fibonacci-function-is-slower-in-c-than-equivalent-ni/76611867

  It has already been pointed out there that your environment (Mingw, Windows, gcc 8.10, different CPU, etc.) is not directly comparable to the results published in the repo (Linux/docker, gcc 9.3.0, etc.).

---

• sls1005 (orginal) [2023-07-05T07:11:29+02:00] view original

  You are using cpuTime, which gives you the time spent for running the current process. Since there could be two or more processes, a result of cpuTime might not be the real time and can be shorter. However, C's time() gives the UNIX time, which counts every second after 1970, therefore the difference between every two UNIX times is always in real time. To get the real time in Nim, use epochTime instead.

---