It’s not like I did something weird, I pretty much copy pasted from

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.

> 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/

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.

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.

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).