The Crystal Programming Language Forum

Crystal vs Rust: A Comparison

I just finished a Rosetta Code task translation from Crystal to Rust and thought I’d share some observations.

  1. Even for this simple example, Rust caused me all kinds of tears and pain to learn how to do string->number and number->string conversions. Crystal|Ruby is so much simpler. (See: https://users.rust-lang.org/t/number-string-back-to-string-reverse-number/51913/15)

  2. Rust is a bit faster, on an apples-to-apples comparison doing this algorithm.

  3. Rust raw executable is larger, but stripped is almost half the size.

  4. Conclusion: If you really, Really, REALLY need optimal speed, use Rust. If you want to get stuff done quickly, and still have time to live your life, use Crystal. YMMV! :blush:

Hear are some statistics:

        | speed  | exe (raw) bytes | exe (stripped) bytes
Crystal | 25.40s |     886,520     |     434,600
Rust    | 20.06s |    1,373,528    |     268,576

Compiled as:

Crystal:
$ crystal build --release palindromicgapfuls.cr

Rust:
$ rustc -C opt-level=3 -C target-cpu=native -C codegen-units=1 -C lto palindromicgapuls.rs

Here’s the Crystal code:

def palindromicgapfuls(digit, count, keep)
  skipped = 0                       # initial count of skipped values
  to_skip = count - keep            # count of unwanted values to skip
  gapfuls = [] of UInt64            # array of palindromic gapfuls
  nn = digit * 11                   # digit gapful divisor: 11, 22,...88, 99
  (2..).select do |power|
    base    = 10_u64**(power >> 1)  # value of middle digit position: 10..
    base11  = base * 11             # value of middle two digits positions: 110..
    this_lo = base * digit          # starting half for this digit: 10.. to  90..
    next_lo = base * (digit + 1)    # starting half for next digit: 20.. to 100..
    this_lo.step(to: next_lo - 1, by: 10) do |front_half|   # d_00; d_10; d_20; ...
      palindrome, left_half = 0_u64, front_half.to_s
      palindrome = (left_half       + left_half.reverse).to_u64 if power.odd?
      palindrome = (left_half.rchop + left_half.reverse).to_u64 if power.even?
      basep      = power.odd? ? base11 : base
      10.times do
        (gapfuls << palindrome if (skipped += 1) > to_skip) if palindrome.divisible_by?(nn)
        palindrome += basep
      end
      return gapfuls[0...keep] unless gapfuls.size < keep
    end
  end
end
 
start = Time.monotonic
 
count, keep = 20, 20
puts "First 20 palindromic gapful numbers ending with:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }
 
count, keep = 100, 15
puts "\nLast 15 of first 100 palindromic gapful numbers ending in:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }
 
count, keep = 1_000, 10
puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }
 
count, keep = 100_000, 1
puts "\n100,000th palindromic gapful number ending with:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }
 
count, keep = 1_000_000, 1
puts "\n1,000,000th palindromic gapful number ending with:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }
 
count, keep = 10_000_000, 1
puts "\n10,000,000th palindromic gapful number ending with:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }
 
puts (Time.monotonic - start).total_seconds

Here’s the Rust code:

fn palindromicgapfuls(digit: u64, count: u64, keep: usize) -> Vec<u64> {
  let mut skipped = 0u64;              // initial count of skipped values
  let to_skip = count - keep as u64;   // count of unwanted values to skip
  let mut gapfuls: Vec<u64> = vec![];  // array of palindromic gapfuls
  let nn = digit * 11;                 // digit gapful divisor: 11, 22,...88, 99
  let (mut power, mut base) = (1, 1u64);
  loop { power += 1;
    if power & 1 == 0 { base  *= 10 }; // value of middle digit position: 10..
    let base11  = base * 11;           // value of middle two digits positions: 110..
    let this_lo = base * digit;        // starting half for this digit: 10.. to  90..
    let next_lo = base * (digit + 1);  // starting half for next digit: 20.. to 100..
    for front_half in (this_lo..next_lo).step_by(10) { // d_00; d_10; d_20; ...
      let (mut left_half, mut basep) = (front_half.to_string(), 0);
      let right_half = left_half.chars().rev().collect::<String>();
      if power & 1 == 1 { basep = base11; left_half.push_str(&right_half) }
      else              { basep = base;   left_half.pop(); left_half.push_str(&right_half) };
      let mut palindrome = left_half.parse::<u64>().unwrap();
      for _ in 0..10 {
        if palindrome % nn == 0 { skipped += 1; if skipped > to_skip { gapfuls.push(palindrome) } };
        palindrome += basep;
      } 
      if gapfuls.len() >= keep { return gapfuls[0..keep].to_vec() };
    }
  }
}

fn main() {

    let t = std::time::Instant::now();

    let (count, keep) = (20, 20);
    println!("First 20 palindromic gapful numbers ending with:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    let (count, keep) = (100, 15);
    println!("\nLast 15 of first 100 palindromic gapful numbers ending in:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    let (count, keep) = (1_000, 10);
    println!("\nLast 10 of first 1000 palindromic gapful numbers ending in:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    let (count, keep) = (100_000, 1);
    println!("\n100,000th palindromic gapful number ending with:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    let (count, keep) = (1_000_000, 1);
    println!("\n1,000,000th palindromic gapful number ending with:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    let (count, keep) = (10_000_000, 1);
    println!("\n10,000,000th palindromic gapful number ending with:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    println!("{:?}", t.elapsed())
  }

Here is the full code and output on Rosettacode.org

Crystal:

Rust:

3 Likes

I just saw I could simplify the code, and for Crystal, make it faster too.
The similar code simplification for Rust actually makes it a smidgen slower, so I didn’t change it.

Crystal simplified|faster:

def palindromicgapfuls(digit, count, keep)
  skipped = 0                       # initial count of skipped values
  to_skip = count - keep            # count of unwanted values to skip
  gapfuls = [] of UInt64            # array of palindromic gapfuls
  nn, base = digit * 11, 1_u64      # digit gapful divisor: 11, 22,...88, 99
  (2..).select do |power|
    base   *= 10 if power.even?     # value of middle digit position: 10..
    base11  = base * 11             # value of middle two digits positions: 110..
    this_lo = base * digit          # starting half for this digit: 10.. to  90..
    next_lo = base * (digit + 1)    # starting half for next digit: 20.. to 100..
    this_lo.step(to: next_lo - 1, by: 10) do |front_half| # d_00; d_10; d_20; ...
      palindrome, left_half = 0_u64, front_half.to_s
      basep, right_half     = base11, left_half.reverse
      (basep = base; left_half = left_half.rchop) if power.even?
      palindrome = (left_half + right_half).to_u64
      10.times do
        (gapfuls << palindrome if (skipped += 1) > to_skip) if palindrome % nn == 0
        palindrome += basep
      end
      return gapfuls[0...keep] unless gapfuls.size < keep
    end
  end
end

Here’s the simplification for Rust, but it’s slightly slower:

fn palindromicgapfuls(digit: u64, count: u64, keep: usize) -> Vec<u64> {
  let mut skipped = 0u64;              // initial count of skipped values
  let to_skip = count - keep as u64;   // count of unwanted values to skip
  let mut gapfuls: Vec<u64> = vec![];  // array of palindromic gapfuls
  let nn = digit * 11;                 // digit gapful divisor: 11, 22,...88, 99
  let (mut power, mut base) = (1, 1u64);
  loop { power += 1;
    if power & 1 == 0 { base  *= 10 }; // value of middle digit position: 10..
    let base11  = base * 11;           // value of middle two digits positions: 110..
    let this_lo = base * digit;        // starting half for this digit: 10.. to  90..
    let next_lo = base * (digit + 1);  // starting half for next digit: 20.. to 100..
    for front_half in (this_lo..next_lo).step_by(10) { // d_00; d_10; d_20; ...
      let (mut left_half, mut basep) = (front_half.to_string(), base11);
      let right_half = left_half.chars().rev().collect::<String>();
      if power & 1 == 0 { basep = base; left_half.pop(); }
      left_half.push_str(&right_half);
      let mut palindrome = left_half.parse::<u64>().unwrap();
      for _ in 0..10 {
        if palindrome % nn == 0 { skipped += 1; if skipped > to_skip { gapfuls.push(palindrome) } };
        palindrome += basep;
      } 
      if gapfuls.len() >= keep { return gapfuls[0..keep].to_vec() };
    }
  }
}

Someone in the Rust forum did a version to numerically form the palindromes to eliminate the number<->string conversions, and I did the equivalent for Crystal. The times are literally the same now, and almost 2.5x faster (from ~25.5s to ~9.3s for Crystal). Here’s the code.

Crystal:

def palindromicgapfuls(digit, count, keep)
  skipped = 0                       # initial count of skipped values
  to_skip = count - keep            # count of unwanted values to skip
  gapfuls = [] of UInt64            # array of palindromic gapfuls
  nn, base = digit * 11, 1_u64      # digit gapful divisor: 11, 22,...88, 99
  (2..).select do |power|
    base   *= 10 if power.even?     # value of middle digit position: 10..
    base11  = base * 11             # value of middle two digits positions: 110..
    this_lo = base * digit          # starting half for this digit: 10.. to  90..
    next_lo = base * (digit + 1)    # starting half for next digit: 20.. to 100..
    this_lo.step(to: next_lo - 1, by: 10) do |front_half| # d_00; d_10; d_20; ...
      basep = power.odd? ? base11 : base 
      palindrome = make_palindrome(front_half, power)
      10.times do
        (gapfuls << palindrome if (skipped += 1) > to_skip) if palindrome.divisible_by?(nn)
        palindrome += basep
      end
      return gapfuls[0...keep] unless gapfuls.size < keep
    end
  end
end

def make_palindrome(front_half, power) 
  result = front_half
  result //= 10 if power.even?
  while front_half > 0
    result *= 10
    result += front_half.remainder(10)
    front_half //= 10
  end
  result
end

t = Time.monotonic

count, keep = 20, 20
puts "First 20 palindromic gapful numbers ending with:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

count, keep = 100, 15
puts "\nLast 15 of first 100 palindromic gapful numbers ending in:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

count, keep = 1_000, 10
puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

count, keep = 100_000, 1
puts "\n100,000th palindromic gapful number ending with:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

count, keep = 1_000_000, 1
puts "\n1,000,000th palindromic gapful number ending with:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

count, keep = 10_000_000, 1
puts "\n10,000,000th palindromic gapful number ending with:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

puts (Time.monotonic - t).total_seconds

Here’s the Rust code:

fn palindromicgapfuls(digit: u64, count: u64, keep: usize) -> Vec<u64> {
    let mut skipped = 0u64;               // initial count of skipped values
    let to_skip = count - keep as u64;    // count of unwanted values to skip
    let mut gapfuls: Vec<u64> = Vec::with_capacity(keep);
    let nn = digit * 11;                  // digit gapful divisor: 11, 22,...88, 99
    let (mut power, mut base) = (1, 1u64);
    loop {
        power += 1;
        if power & 1 == 0 { base *= 10 }  // value of middle digit position: 10..
        let base11 = base * 11;           // value of middle two digits positions: 110..
        let this_lo = base * digit;       // starting half for this digit: 10.. to  90..
        let next_lo = base * (digit + 1); // starting half for next digit: 20.. to 100..
        for front_half in (this_lo..next_lo).step_by(10) { // d_00; d_10; d_20; ...
            let basep = if power & 1 == 1 { base11 } else { base };
            let mut palindrome = make_palindrome(front_half, power);
            for _ in 0..10 {
                if palindrome % nn == 0 {
                    skipped += 1;
                    if skipped > to_skip {
                        gapfuls.push(palindrome);
                        if gapfuls.len() >= keep { return gapfuls; }
                    }
                };
                palindrome += basep;
            }
        }
    }
}

fn make_palindrome(mut front_half: u64, power: u64) -> u64 {
    let mut result = front_half;
    if power & 1 == 0 { result /= 10; }
    while front_half > 0 {
        result *= 10;
        result += front_half % 10;
        front_half /= 10;
    }
    result
}

fn main() {
    let t = std::time::Instant::now();

    let (count, keep) = (20, 20);
    println!("First 20 palindromic gapful numbers ending with:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    let (count, keep) = (100, 15);
    println!("\nLast 15 of first 100 palindromic gapful numbers ending in:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    let (count, keep) = (1_000, 10);
    println!("\nLast 10 of first 1000 palindromic gapful numbers ending in:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    let (count, keep) = (100_000, 1);
    println!("\n100,000th palindromic gapful number ending with:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    let (count, keep) = (1_000_000, 1);
    println!("\n1,000,000th palindromic gapful number ending with:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    let (count, keep) = (10_000_000, 1);
    println!("\n10,000,000th palindromic gapful number ending with:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    println!("{:?}", t.elapsed())
  }
5 Likes

This was an interesting read, thank you!

replacing // with tdiv can save a few. benchmark says // is 1.14x slower than tdiv.

just saying

I wasn’t aware if this method, but I tried it and it made no performance difference.

def make_palindrome(front_half, power) 
  result = front_half
  result //= 10 if power.even?  # result = result.tdiv(10) if power.even?
  while front_half > 0
    result *= 10
    result += front_half.remainder(10)
    front_half //= 10          # front_half = front_half.tdiv(10)
  end
  result
end

The performance results I got from your original code aren’t like the ones you saw, which is interesting.

Rust: 38.819887975s
Crystal: 18.292799228

On the latest version you posted, I do get pretty equivalent performance (within 1.5%):

Rust: 6.641630889s
Crystal: 6.730964135

I didn’t look much into the code itself but I enjoy comparing Crystal performance to that of other languages. It amuses me how often Crystal comes out ahead of the “fast” languages, like when I compared Crystal to Rust with Redis where Crystal was up to 3.13x as fast.

1 Like

Rust shouldn’t be any slower. Check compilation opts (see how I compiled Rust).
Are you using latest version 1.48?

I posted this in the Rust forum too, and been getting interesting comments, suggestions.

Maybe it will come as no surprise (or it shouldn’t) that some people there said they never heard of Crystal. I think once Crystal goes 1.0 allot of the psychological resistance to programmers will deflate, especially for commercial users who think 1.0 means stable-ready, for use in enterprise projects.

Beside just the mechanical code comparison exercise, I would just like to point out that the approach I used to solve this problem is totally different than any other approach shown. And that’s because I studied to be, and worked as, a digital hardware engineer most of my life, and approach problems from that perspective, and try to code like it too. So take a step back and appreciate the simplicity and directness of my approach versus the other examples.

And also, it probably took me an actual 24+ hours of masochistic head banging before I understood how to make Rust do the number<->string version. In Crystal|Ruby, maybe a half an hour of actual coding to get my first prototype implementation producing desired output. So programmer productivity is another feature that needs to be promoted about Crystal.

I see big things ahead in 2021 for Crystal, after the Big 1.0 occurs! :partying_face: :star_struck: :mega: :sparkler:

Lastly, as today (Thursday, November 26, 2020) is observed as Thanksgiving Day in the U.S. I’d like to be thankful for being alive, and hoping for more Peace, Love, and Understanding in the World.

11 Likes

I suppose it is to be expected that Crystal and Rust have comparable performance for such an example. They’re both using LLVM as a backend and benefit from the same optimizations.
Major differences exist in the language runtimes, however. But they don’t matter much for this example which focuses on primitive stack operations. Only a very limited amount memory allocations is involved.

5 Likes

I was using 1.46. Looks like the latest on Homebrew for macOS is 1.47. I’ll give it a shot with that and see if it changes anything.

But yes, I used the command you pasted to compile the Rust app :slightly_smiling_face: That’s why I decided to reply. I was really confused! :-D

Last days I was doing an experiment just for fun and to learn more about Crystal compiler. The experiment consist in see how Crystal language would look like if it had the Rust ownership model instead of a GC. The experiment will probably end in nothing on in something that work just for the basic use cases (no threads/closures), but in the way I’m learning a lot, my primary objective :slight_smile: .

Meanwhile I have some written ideas about what should be added to the syntax to identify ownership taken, etc (but I’ll probably try to do this using ugly Crystal annotations first to avoid touch the parser and reduce my work in this POC) and now I’m looking on how to implement a simple borrowchecker in a visitor before the CodeGenVisitor run… it’s being delightful, despite Crystal compiler code re-open some classes in different places what at first is bad to follow the code, the overall code is way easier to follow than I expected, you guys did an awesome work!

As I said, main reason I’m doing this is to study the compiler, not to have anything done, but I could credit 1% of the reason due to https://github.com/jhass/crystal-gobject/issues/69

4 Likes

Well done, but Phix calculates the 10,000,000,000,000,000,000th in 0.8s… :grinning:

1 Like

Could you post your hardware specs that was run on.

An apples-to-apples test would be to implement the Phix method in Crystal and run on the same machine to see performance difference. I can’t devote the brain cells to that exercise now, too many other things to concentrate on, but it looks nice. :relaxed:

Feel free to profile the original in crystal and see where it bottlenecks and if there is a way to improve :)

But the Phix one seems to be using a different algorithm. So it’s pointless to optimize the existing Crystal one. You need to trqnslate the Phix one to Crystal.

Exactly! That’s what I said in my previous post. To make an apples-to-apples comparison the same algorithm needs to be implemented|run on the same machine in both languages to determine their performance differences.

2 Likes