On: Learning Common Lisp to beat Java and Rust on a phone encoding problem

[aidenn0]

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 → aidenn0]

> 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 → xondono]

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));
  }

[randomswede → aidenn0]

FWIW, the number of recursive calls to compute fib(n) is fib(n+1). So, expect fib(50) to take approxímately 20365011074/165580141 (roughly 123) times longer than fib(40) took (this is taking the somewhat optimistic assumption that there's no actual slow-down from the larger bignums, this is NOT a safe assumption).

[LegionMammal978 → aidenn0]

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?

[aidenn0 → LegionMammal978]

I didn't use --release, but I also didn't use an optimization declaration in lisp.

[paavohtl → aidenn0]

You should never benchmark Rust without the --release flag - it can regularly speed up the code by 1-2 orders of magnitude.

[aidenn0 → paavohtl]

I think I just inadvertently proved the point that a lot of replies to the original commenter were making. If you just say "I benchmarked this and X was way slower than Y" without posting code or other details, then it's likely that you're doing something wrong, particularly when you aren't familiar with X or Y.

The original poster said:

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

And

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

I could have equally said that my example demonstrates that "To me that means that performant Rust is non trivial" or that I would "need to invest a good amount of time ... before being productive"

Both of which are clearly not true. Posting my code let other people find the extremely trivial change to fix the huge performance difference.

[aidenn0 → xondono]

Did you use num_bigint for bignums?