5 ms·

This got me curious about other Scheme implementations. Chicken compiles to C $ csc fib.scm $ time ./fib real 0m8.461s user 0m8.383s sys

by eddieh 6y ago

This got me curious about other Scheme implementations. Chicken compiles to C $ csc fib.scm $ time ./fib real 0m8.461s user 0m8.383s sys 0m0.061s Racket has a modern JIT $ 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 For reference $ sysctl -a | grep .brand_string machdep.cpu.brand_string: Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz

taeric 6y ago
This got me interested in other lisps, as well. Looks like sbcl gives (time (fib 40)) to be about 1.7 seconds on my machine. (Ryzen 5 3600x.) 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))) And... well, serves as an amusing reminder that tree recursion has its downsides. :D 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.)
- eddieh 6y ago
  Try BigInt in JS https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
  - taeric 6y ago
    Apologies, I should have acknowledged there are ways to get around that today. My guess is most folks writing javascript are not aware of BigInt. And will only become so when it bites them. 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.
    - eddieh 6y ago
      I don’t think I’ve seen BigInt in the wild Wild West of JS at all, so that’s probably true that most folks are not aware of it. 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-in-the-west/ http://www.wilfred.me.uk/blog/2014/10/20/the-fastest-bigint-...
- anthk 6y ago
  >And... well, serves as an amusing reminder that tree recursion has its downsides. :D OFC I would rewrite that as a iterative form (and any Schemer here could :D), but here we are testing performance :D.
  - taeric 6y ago
    Agreed. I didn't mean that necessarily as a criticism of anything. Just hard to have an intuition for just how much it slows down. 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.
    - vitus 6y ago
      The speed of the naive recursive fib scales with the number it computes, which is roughly 1.6 ^ n (the eigenvalue of the matrix for the recurrence relation is the golden ratio, phi). 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)
      - taeric 6y ago
        Right. I "know" how tree recursion scales up. It is still neat to "see" the impact on the speed. That is, knowing all of these facts, it is still impressive how fast you can get (fib 1000000) using iteration and bignums.
        vitus 6y ago
        There, that runtime is roughly O(n^2) when dealing with bignums, since addition scales linearly with bit length of the operands, and bit length increases linearly with the number of iterations (~0.7 bits per iteration). 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.
dleslie 6y ago
Chicken's default is fairly unoptimized; try higher optimization levels.
- eddieh 6y ago
  Oh dang...you're right $ csc -optimize-level 5 fib.scm $ time ./fib real 0m5.506s user 0m5.489s sys 0m0.010s I could get a few fractions of a second better playing with the stack size (4 MB was the best, 8 MB or above would segfault) $ csc -optimize-level 5 -stack-size 4m fib.scm $ time ./fib real 0m5.295s user 0m5.277s sys 0m0.011s Everything else was negligible or extremely varied.
  - dleslie 6y ago
    Yep, to get beyond that you basically have to stop writing scheme and start writing a tortured variant of Chicken, for performance. ;) 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.
deleted 6y ago
[deleted]
the-smug-one 6y ago
Chez Scheme gives: > (time (fibonacci 40)) (time (fibonacci 40)) no collections 1.364130664s elapsed cpu time 1.364456065s elapsed real time 0 bytes allocated 102334155

by eddieh 6y ago

taeric 6y ago

This got me interested in other lisps, as well. Looks like sbcl gives (time (fib 40)) to be about 1.7 seconds on my machine. (Ryzen 5 3600x.) 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))) And... well, serves as an amusing reminder that tree recursion has its downsides. :D 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.)

eddieh 6y ago
Try BigInt in JS https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- taeric 6y ago
  Apologies, I should have acknowledged there are ways to get around that today. My guess is most folks writing javascript are not aware of BigInt. And will only become so when it bites them. 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.
  - eddieh 6y ago
    I don’t think I’ve seen BigInt in the wild Wild West of JS at all, so that’s probably true that most folks are not aware of it. 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-in-the-west/ http://www.wilfred.me.uk/blog/2014/10/20/the-fastest-bigint-...
anthk 6y ago
>And... well, serves as an amusing reminder that tree recursion has its downsides. :D OFC I would rewrite that as a iterative form (and any Schemer here could :D), but here we are testing performance :D.
- taeric 6y ago
  Agreed. I didn't mean that necessarily as a criticism of anything. Just hard to have an intuition for just how much it slows down. 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.
  - vitus 6y ago
    The speed of the naive recursive fib scales with the number it computes, which is roughly 1.6 ^ n (the eigenvalue of the matrix for the recurrence relation is the golden ratio, phi). 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)
    - taeric 6y ago
      Right. I "know" how tree recursion scales up. It is still neat to "see" the impact on the speed. That is, knowing all of these facts, it is still impressive how fast you can get (fib 1000000) using iteration and bignums.
      - vitus 6y ago
        There, that runtime is roughly O(n^2) when dealing with bignums, since addition scales linearly with bit length of the operands, and bit length increases linearly with the number of iterations (~0.7 bits per iteration). 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.

dleslie 6y ago

Chicken's default is fairly unoptimized; try higher optimization levels.

eddieh 6y ago
Oh dang...you're right $ csc -optimize-level 5 fib.scm $ time ./fib real 0m5.506s user 0m5.489s sys 0m0.010s I could get a few fractions of a second better playing with the stack size (4 MB was the best, 8 MB or above would segfault) $ csc -optimize-level 5 -stack-size 4m fib.scm $ time ./fib real 0m5.295s user 0m5.277s sys 0m0.011s Everything else was negligible or extremely varied.
- dleslie 6y ago
  Yep, to get beyond that you basically have to stop writing scheme and start writing a tortured variant of Chicken, for performance. ;) 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.

deleted 6y ago

[deleted]

the-smug-one 6y ago

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