7 ms·

Some weeks ago I tried to start learning Lisp too. I found it odd, but I’ve seen weirder. Then I tried the simple example of writing a function to compute the

Some weeks ago I tried to start learning Lisp too. I found it odd, but I’ve seen weirder. Then I tried the simple example of writing a function to compute the nth fibonacci number (it’s almost the first example). After testing some numbers, I thought it seemed slow, so I quickly implemented the same function in Rust (with recursion too). Rust took less time in compiling, and computing fib(n) for n 1..50 than Lisp to compute fib(50). Maybe I did something very wrong, but for now I’d rather learn Rust better.

Jtsummers 5y ago
The only way anyone but you can know if you did anything wrong is if you include your code, and your common lisp implementation. They don’t all have the same performance.
- xondono 5y ago
  It’s not like I did something weird, I pretty much copy pasted from https://lisp-lang.org/learn/functions https://lisp-lang.org/learn/functions I know the reason for the time taken is because it’s not tail recursive, and that making it tail recursive would make it almost immediate, but for me that was not the point. The thing is, I don’t really know how to write performant rust code, and yet my naive implementation in rust works better than the example in learn-lisp. To me that means performant Lisp is non trivial (meaning you need deep understanding to achieve it). If you show a slow but easier to understand example, it’s because fast examples are way harder to understand.
  - aidenn0 5y ago
    > I know the reason for the time taken is because it’s not tail recursive, and that making it tail recursive would make it almost immediate, but for me that was not the point. Assuming your rust version is not tail-recursive, this is not true. Of course a tail-recursive (or iterative for that matter) version would be way faster, but that is independent of the language used[1]. The naive algorithm in both Rust and Lisp should be relatively similar in runtimes, and for me (after I properly enabled optimiations) they were. Also, tail recursion is a red-herring here for another reason. For both Rust and Lisp, I would use an iterative approach, not a tail-recursive approach, like the example in the Rust num_bigint docs[2]. 1: A theoretical language that automatically memoized pure functions would make this false, but that doesn't apply to the current discussion. 2: https://docs.rs/num-bigint/0.4.2/num_bigint/ https://docs.rs/num-bigint/0.4.2/num_bigint/ The equivalent Lisp would be: CL-USER> (defun fib (n) (let ((f0 0) (f1 1)) (loop repeat n do (shiftf f0 f1 (+ f0 f1))) f0)) FIB CL-USER> (time (fib 1000)) Evaluation took: 0.000 seconds of real time 0.000171 seconds of total run time (0.000136 user, 0.000035 system) 100.00% CPU 471,103 processor cycles 65,456 bytes consed 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875 CL-USER> For small values the difference is lost in the noise. For larger values (e.g. 1000000) Rust is about 2x faster than SBCL, which is about what I would expect for a test like this.
- xondono 5y ago
  Just because someone else asked: here's the Rust code: fn fib(n: usize) -> u64 { match n { 0 => 1, 1 => 1, _ => fib(n - 1) + fib(n - 2), } } fn main() { println!("{}", fib(50)); } Here's the Lisp code: (defun fib (n) "Return the nth Fibonacci number." (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))) Again, I'm not trying to benchmark the languages, I'm not interested in this language drag racing competition/flamewar, I don't care about how performant a language is in the end. I care about how fast a language is for unit of time I spent. This metric is obviously only useful to me, because if you know a lot of Lisp but little Rust, your time spent will be very different. I also know the Rust snippet will crash at fib(~100), and that I could write the thing in a loop and get there under 1ms. The same is surely true about Lisp.
  - randomswede 5y ago
    Once you exceed the size of a fixnum (this depends on the implementation), Common Lisp will silently spill to bignums (since you have not declared your variable to be a fixnum; you could declare it as an integer and still get the fixnum->bignum spill).
remexre 5y ago
I believe that unless you put the inline pragma on the Lisp function, the compiler isn't allowed to optimize the recursion. In general, Common Lisp doesn't favor recursive functions (as opposed to Scheme), and as far as I know, most implementations don't put huge amounts of effort into optimizing it. I'd be interested to see whether the same written using the loop (or iterate:iter) macros would still be as slow.
- gibsonf1 5y ago
  If you make it tail recursive, its insanely fast in common lisp. (sbcl)
  - jonsen 5y ago
    How would you code a tail recursive Fibonacci in LISP?
    - gibsonf1 5y ago
      I haven't looked at trying and don't really have time to, so I don't know, but with lisp, you can make anything fast as a general rule, very very fast. (at least with compiled sbcl)
    - emptybits 5y ago
      There may be a faster or cleverer way to do it but here's a basic tail recursive fibonacci: (defun nth-fibonacci (n &optional (a 0) (b 1)) (if (= n 0) a (nth-fibonacci (- n 1) b (+ a b))))
      - Jtsummers 5y ago
        Yep, that's how you'd do it. So long as your CL implementation supports tail call optimization, that will be on par with the same algorithm using loop or another looping construct.
      - gibsonf1 5y ago
        WEB> (time (nth-fibonacci 9999)) Evaluation took: 0.005 seconds of real time 0.004520 seconds of total run time (0.000168 user, 0.004352 system) 100.00% CPU 13,120,881 processor cycles 4,716,256 bytes consed 20793608237133498072112648988642836825087036094015903119682945866528501423455686648927456034305226515591757343297190158010624794267250973176133810179902738038231789748346235556483191431591924532394420028067810320408724414693462849062668387083308048250920654493340878733226377580847446324873797603734794648258113858631550404081017260381202919943892370942852601647398213554479081823593715429566945149312993664846779090437799284773675379284270660175134664833266377698642012106891355791141872776934080803504956794094648292880566056364718187662668970758537383352677420835574155945658542003634765324541006121012446785689171494803262408602693091211601973938229446636049901531963286159699077880427720289235539329671877182915643419079186525118678856821600897520171070499437657067342400871083908811800976259727431820539554256869460815355918458253398234382360435762759823179896116748424269545924633204614137992850814352018738480923581553988990897151469406131695614497783720743461373756218685106856826090696339815490921253714537241866911604250597353747823733268178182198509240226955826416016690084749816072843582488613184829905383150180047844353751554201573833105521980998123833253261228689824051777846588461079790807828367132384798451794011076569057522158680378961532160858387223882974380483931929541222100800313580688585002598879566463221427820448492565073106595808837401648996423563386109782045634122467872921845606409174360635618216883812562321664442822952537577492715365321134204530686742435454505103269768144370118494906390254934942358904031509877369722437053383165360388595116980245927935225901537634925654872380877183008301074569444002426436414756905094535072804764684492105680024739914490555904391369218696387092918189246157103450387050229300603241611410707453960080170928277951834763216705242485820801423866526633816082921442883095463259080471819329201710147828025221385656340207489796317663278872207607791034431700112753558813478888727503825389066823098683355695718137867882982111710796422706778536913192342733364556727928018953989153106047379741280794091639429908796650294603536651238230626 WEB>
fsckboy 5y ago
I don't know for certain at all, but I'd propose that you are being downvoted for not going far enough with lisp to grasp the point of lisp, which has more to do with recursive data structures--and data that is code--than just recursive procedure calling. Factorial and Fibonacci as a pair are good introductions to the issue of recursion--and lisp had recursion back in the dark ages before other languages did--but they're aren't what lisp is about. so, were some other newbie to read your comment, it might really put them off learning lisp for entirely the wrong reasons. cheers :)
rscho 5y ago
Maybe not knowing how to use a tool efficiently is a good reason to refrain from strong criticism?
aidenn0 5y ago
That's pretty darn close to the single worst benchmark you could use for CL vs. rust. It's going to make a lot of memory allocations and make a lot of uninlinable function calls, both of which are places that I would expect rust to have an advantage. That being said, I'd be curious to see your rust version, as just the number of bignum operations done for fib(50) is going to take a long time.
- xondono 5y ago
  > worst benchmark you could use for CL vs. rust. I wasn’t benchmarking CL vs Rust, but my CL vs my Rust. What I was trying to see is, can I do something useful with this? Or do I need to invest a good amount of time (something I don’t really have now) before being productive. As for the rust version, I did the “trivial” (and terrible) translation. Match on input, recursive call on the _ arm.
  - aidenn0 5y ago
    Did you use num_bigint for bignums?
  - aidenn0 5y ago
    Here's my code, which is about 30x faster on lisp than on rust for fib(40). I'm currently waiting on fib(50)... Lisp (SBCL): (defun fib (n) (case n (0 0) (1 1) (otherwise (+ (fib (- n 1)) (fib (- n 2)))))) (time (fib 40)) Rust: use num_bigint::BigUint; use num_traits::{Zero, One}; // Calculate large fibonacci numbers. fn fib(n: usize) -> BigUint { match n { 0 => Zero::zero(), 1 => One::one(), _ => fib(n-1) + fib(n-2), } } fn main() { println!("fib(40) = {}", fib(40)); }
    - LegionMammal978 5y ago
      I get ~1.5s on the Lisp program and ~2.1s on the Rust program for fib(40), and ~186s vs. ~257s for fib(50). Did you forget to compile the Rust program with --release?
xondono 5y ago
Maybe it came out wrong (English is not my first language). I did not mean to say that I believe it inferior or anything, just that I felt writing performant code in Lisp is non trivial to learn, while rust feels pretty natural (to me). I’ll try again at some point, but I don’t think it’s a wise investment of time at this point, I’d rather be “fluent” in rust first, then maybe try lisp.
- mike_ivanov 5y ago
  I feel that playing saxophone is non trivial to learn, while guitar feels pretty natural (to me).

Jtsummers 5y ago

The only way anyone but you can know if you did anything wrong is if you include your code, and your common lisp implementation. They don’t all have the same performance.

xondono 5y ago
It’s not like I did something weird, I pretty much copy pasted from https://lisp-lang.org/learn/functions https://lisp-lang.org/learn/functions I know the reason for the time taken is because it’s not tail recursive, and that making it tail recursive would make it almost immediate, but for me that was not the point. The thing is, I don’t really know how to write performant rust code, and yet my naive implementation in rust works better than the example in learn-lisp. To me that means performant Lisp is non trivial (meaning you need deep understanding to achieve it). If you show a slow but easier to understand example, it’s because fast examples are way harder to understand.
- aidenn0 5y ago
  > I know the reason for the time taken is because it’s not tail recursive, and that making it tail recursive would make it almost immediate, but for me that was not the point. Assuming your rust version is not tail-recursive, this is not true. Of course a tail-recursive (or iterative for that matter) version would be way faster, but that is independent of the language used[1]. The naive algorithm in both Rust and Lisp should be relatively similar in runtimes, and for me (after I properly enabled optimiations) they were. Also, tail recursion is a red-herring here for another reason. For both Rust and Lisp, I would use an iterative approach, not a tail-recursive approach, like the example in the Rust num_bigint docs[2]. 1: A theoretical language that automatically memoized pure functions would make this false, but that doesn't apply to the current discussion. 2: https://docs.rs/num-bigint/0.4.2/num_bigint/ https://docs.rs/num-bigint/0.4.2/num_bigint/ The equivalent Lisp would be: CL-USER> (defun fib (n) (let ((f0 0) (f1 1)) (loop repeat n do (shiftf f0 f1 (+ f0 f1))) f0)) FIB CL-USER> (time (fib 1000)) Evaluation took: 0.000 seconds of real time 0.000171 seconds of total run time (0.000136 user, 0.000035 system) 100.00% CPU 471,103 processor cycles 65,456 bytes consed 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875 CL-USER> For small values the difference is lost in the noise. For larger values (e.g. 1000000) Rust is about 2x faster than SBCL, which is about what I would expect for a test like this.
xondono 5y ago
Just because someone else asked: here's the Rust code: fn fib(n: usize) -> u64 { match n { 0 => 1, 1 => 1, _ => fib(n - 1) + fib(n - 2), } } fn main() { println!("{}", fib(50)); } Here's the Lisp code: (defun fib (n) "Return the nth Fibonacci number." (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))) Again, I'm not trying to benchmark the languages, I'm not interested in this language drag racing competition/flamewar, I don't care about how performant a language is in the end. I care about how fast a language is for unit of time I spent. This metric is obviously only useful to me, because if you know a lot of Lisp but little Rust, your time spent will be very different. I also know the Rust snippet will crash at fib(~100), and that I could write the thing in a loop and get there under 1ms. The same is surely true about Lisp.
- randomswede 5y ago
  Once you exceed the size of a fixnum (this depends on the implementation), Common Lisp will silently spill to bignums (since you have not declared your variable to be a fixnum; you could declare it as an integer and still get the fixnum->bignum spill).

remexre 5y ago

I believe that unless you put the inline pragma on the Lisp function, the compiler isn't allowed to optimize the recursion. In general, Common Lisp doesn't favor recursive functions (as opposed to Scheme), and as far as I know, most implementations don't put huge amounts of effort into optimizing it. I'd be interested to see whether the same written using the loop (or iterate:iter) macros would still be as slow.

gibsonf1 5y ago
If you make it tail recursive, its insanely fast in common lisp. (sbcl)
- jonsen 5y ago
  How would you code a tail recursive Fibonacci in LISP?
  - gibsonf1 5y ago
    I haven't looked at trying and don't really have time to, so I don't know, but with lisp, you can make anything fast as a general rule, very very fast. (at least with compiled sbcl)
  - emptybits 5y ago
    There may be a faster or cleverer way to do it but here's a basic tail recursive fibonacci: (defun nth-fibonacci (n &optional (a 0) (b 1)) (if (= n 0) a (nth-fibonacci (- n 1) b (+ a b))))
    - Jtsummers 5y ago
      Yep, that's how you'd do it. So long as your CL implementation supports tail call optimization, that will be on par with the same algorithm using loop or another looping construct.
    - gibsonf1 5y ago
      WEB> (time (nth-fibonacci 9999)) Evaluation took: 0.005 seconds of real time 0.004520 seconds of total run time (0.000168 user, 0.004352 system) 100.00% CPU 13,120,881 processor cycles 4,716,256 bytes consed 20793608237133498072112648988642836825087036094015903119682945866528501423455686648927456034305226515591757343297190158010624794267250973176133810179902738038231789748346235556483191431591924532394420028067810320408724414693462849062668387083308048250920654493340878733226377580847446324873797603734794648258113858631550404081017260381202919943892370942852601647398213554479081823593715429566945149312993664846779090437799284773675379284270660175134664833266377698642012106891355791141872776934080803504956794094648292880566056364718187662668970758537383352677420835574155945658542003634765324541006121012446785689171494803262408602693091211601973938229446636049901531963286159699077880427720289235539329671877182915643419079186525118678856821600897520171070499437657067342400871083908811800976259727431820539554256869460815355918458253398234382360435762759823179896116748424269545924633204614137992850814352018738480923581553988990897151469406131695614497783720743461373756218685106856826090696339815490921253714537241866911604250597353747823733268178182198509240226955826416016690084749816072843582488613184829905383150180047844353751554201573833105521980998123833253261228689824051777846588461079790807828367132384798451794011076569057522158680378961532160858387223882974380483931929541222100800313580688585002598879566463221427820448492565073106595808837401648996423563386109782045634122467872921845606409174360635618216883812562321664442822952537577492715365321134204530686742435454505103269768144370118494906390254934942358904031509877369722437053383165360388595116980245927935225901537634925654872380877183008301074569444002426436414756905094535072804764684492105680024739914490555904391369218696387092918189246157103450387050229300603241611410707453960080170928277951834763216705242485820801423866526633816082921442883095463259080471819329201710147828025221385656340207489796317663278872207607791034431700112753558813478888727503825389066823098683355695718137867882982111710796422706778536913192342733364556727928018953989153106047379741280794091639429908796650294603536651238230626 WEB>

fsckboy 5y ago

I don't know for certain at all, but I'd propose that you are being downvoted for not going far enough with lisp to grasp the point of lisp, which has more to do with recursive data structures--and data that is code--than just recursive procedure calling. Factorial and Fibonacci as a pair are good introductions to the issue of recursion--and lisp had recursion back in the dark ages before other languages did--but they're aren't what lisp is about. so, were some other newbie to read your comment, it might really put them off learning lisp for entirely the wrong reasons. cheers :)

rscho 5y ago

Maybe not knowing how to use a tool efficiently is a good reason to refrain from strong criticism?

aidenn0 5y ago

That's pretty darn close to the single worst benchmark you could use for CL vs. rust. It's going to make a lot of memory allocations and make a lot of uninlinable function calls, both of which are places that I would expect rust to have an advantage. That being said, I'd be curious to see your rust version, as just the number of bignum operations done for fib(50) is going to take a long time.

xondono 5y ago
> worst benchmark you could use for CL vs. rust. I wasn’t benchmarking CL vs Rust, but my CL vs my Rust. What I was trying to see is, can I do something useful with this? Or do I need to invest a good amount of time (something I don’t really have now) before being productive. As for the rust version, I did the “trivial” (and terrible) translation. Match on input, recursive call on the _ arm.
- aidenn0 5y ago
  Did you use num_bigint for bignums?
- aidenn0 5y ago
  Here's my code, which is about 30x faster on lisp than on rust for fib(40). I'm currently waiting on fib(50)... Lisp (SBCL): (defun fib (n) (case n (0 0) (1 1) (otherwise (+ (fib (- n 1)) (fib (- n 2)))))) (time (fib 40)) Rust: use num_bigint::BigUint; use num_traits::{Zero, One}; // Calculate large fibonacci numbers. fn fib(n: usize) -> BigUint { match n { 0 => Zero::zero(), 1 => One::one(), _ => fib(n-1) + fib(n-2), } } fn main() { println!("fib(40) = {}", fib(40)); }
  - LegionMammal978 5y ago
    I get ~1.5s on the Lisp program and ~2.1s on the Rust program for fib(40), and ~186s vs. ~257s for fib(50). Did you forget to compile the Rust program with --release?

xondono 5y ago

Maybe it came out wrong (English is not my first language). I did not mean to say that I believe it inferior or anything, just that I felt writing performant code in Lisp is non trivial to learn, while rust feels pretty natural (to me). I’ll try again at some point, but I don’t think it’s a wise investment of time at this point, I’d rather be “fluent” in rust first, then maybe try lisp.

mike_ivanov 5y ago
I feel that playing saxophone is non trivial to learn, while guitar feels pretty natural (to me).