Chicken compiles to C

    $ csc fib.scm
    $ time ./fib

    real 0m8.461s
    user 0m8.383s
    sys  0m0.061s

    $ cat fib.rkt 
    #lang racket
    (define (fibonacci n)
      (if (<= n 1)
          n
          (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
    (fibonacci 40)
    $ time racket fib.rkt
    102334155

    real 0m1.396s
    user 0m1.142s
    sys  0m0.127s

    $ sysctl -a | grep .brand_string
    machdep.cpu.brand_string: Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz

For lulz, I clocked a dumb loop version.

    (defun fib (n)
        (loop repeat n
              for a = 1 then b
              for b = 1 then c
              for c = (+ a b)
              finally (return a)))

Edit: I confess the speed of the loop got me curious and.... javascript has numeric overflow. That would be a hell of a surprise if you weren't expecting it.

Edit2: (I realize overflow isn't the right term, but it is amusing that I can calc the 10000th fib in elisp... not so much in javascript. And yes, even elisp falls over sooner than sbcl does.)

OFC I would rewrite that as a iterative form (and any Schemer here could :D), but here we are testing performance :D.

I suppose there is a bit of something in there about using the right algorithm. But I can understand picking one that will take time for comparing speed. I'm not sure either is really representative of work you expect an editor to do, though. Curse of benchmarks.

Intuition: if you were to expand and flatten the recursive calls, you'd end up with something like

(+ 1 0 1 1 0 1 1 0 ... 1 0)

with exactly (fib n) 1s (base case (fib 1)), and no more than (fib n) 0s (base case (fib 0)).

Simple example:

     (fib 3)
     = (+ (fib 2) (fib 1))
     = (+ (+ (fib 1) (fib 0)) 1)
     = (+ (+ 1 0) 1)
     = (+ 1 0 1)

  With scm, using (trace proc):
 
 scm -f fib.scm
 
 call fib 9
    call fib 8
      call fib 7
        call fib 6
          call fib 5
          retn fib 5
          call fib 4
          retn fib 3
        retn fib 8
        call fib 5
          call fib 4
          retn fib 3
          call fib 3
          retn fib 2
        retn fib 5
      retn fib 13
      call fib 6
        call fib 5
          call fib 4
          retn fib 3
          call fib 3
          retn fib 2
        retn fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
      retn fib 8
    retn fib 21
    call fib 7
      call fib 6
        call fib 5
          call fib 4
          retn fib 3
          call fib 3
          retn fib 2
        retn fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
      retn fib 8
      call fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
        call fib 3
          call fib 2
          retn fib 1
          call fib 1
          retn fib 1
        retn fib 2
      retn fib 5
    retn fib 13
  retn fib 34
  call fib 8
    call fib 7
      call fib 6
        call fib 5
          call fib 4
          retn fib 3
          call fib 3
          retn fib 2
        retn fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
      retn fib 8
      call fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
        call fib 3
          call fib 2
          retn fib 1
          call fib 1
          retn fib 1
        retn fib 2
      retn fib 5
    retn fib 13
    call fib 6
      call fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
        call fib 3
          call fib 2
          retn fib 1
          call fib 1
          retn fib 1
        retn fib 2
      retn fib 5
      call fib 4
        call fib 3
          call fib 2
          retn fib 1
          call fib 1
          retn fib 1
        retn fib 2
        call fib 2
          call fib 1
          retn fib 1
          call fib 0
          retn fib 0
        retn fib 1
      retn fib 3
    retn fib 8
  retn fib 21
  55
 
 scm -f fib-iter.scm
 
 call fib-iter 1 0 10
    call fib-iter 1 1 9
      call fib-iter 2 1 8
        call fib-iter 3 2 7
          call fib-iter 5 3 6
          retn fib-iter 55
        retn fib-iter 55
      retn fib-iter 55
    retn fib-iter 55
  retn fib-iter 55
  55

That is, knowing all of these facts, it is still impressive how fast you can get (fib 1000000) using iteration and bignums.

Which is still not fast -- on my laptop, Python takes about 9s for fib(1000000). But compared to an exponentially-growing function, that's a blink of an eye.

Granted, this is also true of fixednum in common lisp. At least "biting you" with that should only be performance. (I can't think of many other ways for that one to get you.)

Edit: I should further ack that "getting around" it is as simple as adding "n" to one of the constants. So, it is nicely done.

I wonder if there’s some room for improvement since using GMP is pretty standard for most languages.

Edit: forgot to link to a BigInt comparison in major language implementations http://www.wilfred.me.uk/blog/2014/10/20/the-fastest-bigint-...

> (time (fibonacci 40)) (time (fibonacci 40)) no collections 1.364130664s elapsed cpu time 1.364456065s elapsed real time 0 bytes allocated 102334155

    $ csc -optimize-level 5 fib.scm 
    $ time ./fib

    real 0m5.506s
    user 0m5.489s
    sys  0m0.010s

    $ csc -optimize-level 5 -stack-size 4m fib.scm 
    $ time ./fib

    real 0m5.295s
    user 0m5.277s
    sys  0m0.011s

I stopped writing Chicken scheme code a few years ago; it was fun due to the ease of interoperating with C, but I found Chibi a better fit for that niche eventually.

        guile --version?

Guile always compiles code before running it, but adding a JIT it's only from v > 2.91.x, and by default at v3.

    $  time guile3 fib.scm
    guile3 fib.scm  2.01s user 0.02s system 99% cpu 2.047 total

Guile3 will improve that, too.

Which Emacs version is this?

Any chance you want to try the native-comp branch and post its numbers here as well?

I can install native-comp via AUR. It'll take some time.

    time emacs --script fib-0b03fe9a-6b386e71.eln    
    emacs --script fib-0b03fe9a-6b386e71.eln  22.47s user 0.09s system 99% cpu 22.664 total

(I copied the .eln from the cache to confirm that's what I'm running against; I got a similar speedup from running against fib.elc.)

That should be considerably relevant in this benchmark.

PS you can also run a wider set of benchmarks to compare against stock Emacs using:

https://elpa.gnu.org/packages/elisp-benchmarks.html

Here some not very updated results:

http://akrl.sdf.org/gccemacs.html#org4297f0f

IIUC, you're saying the fib benchmark gets optimized out at speed 3 (and thus run faster than all the implementations discussed here).

But what about speed 2, which is the current default? If we're 15 times slower on this benchmark, does that mean that Node has much cheaper function calls, or something like that?

Because we have to keep Emacs Lisp functions advice-able (which I agree is a good thing)?

Specifically a single fibonacci example is not a good performance indicator by any means.

For instance let's assume V8 is faster in average at running this kind of nanobenchmarks (probably at least for now it is), but how much does it cost to convert non trivial data structures from Lisp to JS and back in a real case?

I expect there will be a lot of back and forward if the system if JS and Lisp get mixed and have to cooperate.

How much does it cost to go through foreign functions calls?

This are just initial thoughts that are not accounted at all here.

And even benchmarking nano-benchmarks can be surprisingly tricky ;) :) https://github.com/emacs-ng/emacs-ng/issues/187#issuecomment...

My questions here are about whether these results indicate further optimization potential for native-comp (in the default configuration, hopefully).

emacs-ng is an interesting experiment, but I think I will only be able to seriously consider it if it comes to reimplementing the Elisp VM on top of V8. Then it will be a single runtime, and little to no data structure conversion and FFI will be required.

In the meantime, I'll keep following the native-comp progress ;), as well as dreaming of Web Workers in stock Elisp API.