Crystal to 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: Number -> string back to string.reverse -> number)

  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

I'd be interested to see if people can make the code faster, and it's performance on different systems (Mac, ARM, AMD, etc).

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:

2 Likes

Considering that the string conversions are probably the slowest part of the program, one might argue that Rust is trying to tell you something there. It seems like a lot of what you're benchmarking is how fast you can create and destroy small strings, which while interesting in its own right, is incidental to the problem as posed.

Skimming the other languages on the site, it looks like the solutions for C, C++ and Go do not use string operations in the numeric code, whereas Crystal and most of the others do (of the ones I can read, at least).

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

I'm sorry but the conclusion doesn't follow automatically from your premises.

Perhaps it holds if you're familiar with crystal and not all that familiar with rust, as is the case with you at this time.

But for someone like me (5+ years of experience with rust and 0 with crystal) the conclusion doesn't follow at all.

3 Likes

You do note I said YMMV (Your Mileage May Vary), and that this is a Rust forum. :slightly_smiling_face:

But really, if you know Rust it would be much, much easier to translate the Rust code into Crystal or Ruby, even with no knowledge of either, especially for Ruby.

By replacing the string manipulation with this purely numeric version, I was able to make the Rust version about 2.5 times faster:

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
}

Complete code on Playground

7 Likes

Hey @mbrubeck that was great!

If you don't mind, I'll also post your numeric version to show how to do it that way.
I'll also see how a similar Crystal version compares to it too.

Thanks!

2 Likes

Thanks!

FYI, on my laptop it went from ~20.1s to 9.28s.

Also for general incentive, there are allot of Rosetta code tasks that don't have Rust examples, and some of the old Rust examples need updating to take advantage of current features.

The Crystal equivalent version went from ~25.4s to ~9.3s.
Thus the numerical version for both Rust and Crystal are essentially just as fast.

Here's the update 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, 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
2 Likes

Very cool!

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.