Rust - why is my program performing very slowly - over 5 times slower than the same program written in JavaScript using Node

user_17071165 0
Viewed 291

I have finished converting an application that I made in JavaScript to Rust for increased performance. I am learning to program, and all the application does is work out the multiplicative persistence of any number in a range. It multiplies all digits together to form a new number, then repeats until the number becomes less than 10.

My issue is, my program written in JavaScript is over 5 times faster than the same in Rust. I must be doing something wrong with converting Strings to ints somewhere, I even tried swapping i128 to i64 and it made little difference.

If I run "cargo run --release" it is still slower!

Please can somebody look through my code to work out if there is any part of it that is causing the issues? Thank you in advance :)

fn multiplicative_persistence(mut user_input: i128) -> i128 {
    let mut steps: i128 = 0;
    let mut numbers: Vec<i128> = Vec::new();
    while user_input > 10 {
        let string_number: String = user_input.to_string();
        let digits: Vec<&str> = string_number.split("").collect();
        let mut sum: i128 = 1;
        let digits_count = digits.len();

        for number in 1..digits_count - 1 {
            sum *= digits[number].parse::<i128>().unwrap();
        }

        numbers.push(sum);

        steps += 1;
        user_input = sum;
    }

    return steps;
}

fn main() {
    // let _user_input: i128 = 277777788888899;

    let mut highest_steps_count: i128 = 0;
    let mut highest_steps_number: i128 = 0;

    let start: i128 = 77551000000;
    let finish: i128 = 1000000000000000;

    for number in start..=finish {
        // println!("{}: {}", number, multiplicative_persistence(number));
        if multiplicative_persistence(number) > highest_steps_count {
            highest_steps_count = multiplicative_persistence(number);
            highest_steps_number = number;
        }
        if number % 1000000 == 0 {
            println!("Upto {} so far: {}", number, highest_steps_number);
        }
    }

    println!("Highest step count: {} at {}", highest_steps_number, highest_steps_count);
}

I do plan to use the numbers variable in the function but I have not learnt enough to know how to properly return it as an associative array.

rust performance
1 Answers

Maybe the issue is that converting a number to a string, and then re-converting it again into a number is not that fast, and avoidable. You don't need this intermediate step:

fn step(mut x: i128) -> i128 {
  let mut result = 1;
  while x > 0 {
    result *= x % 10;
    x /= 10;
  }
  result
}

fn multiplicative_persistence(mut user_input: i128) -> i128 {
  let mut steps = 0;
  while user_input > 10 {
    user_input = step(user_input);
    steps += 1;
  }
  steps
}

EDIT Just out of curiosity, I'd like to know whether the bottleneck is really due to the string conversion or to the rest of the code that is somehow wasteful. Here is an example that does not call .split(""), does not re-allocate that intermediate vector, and only allocates once, not at each step, the string.

#![feature(fmt_internals)]

use std::fmt::{Formatter, Display};

fn multiplicative_persistence(user_input: i128) -> i128 {
    let mut steps = 0;
    let mut digits = user_input.to_string();
    while user_input > 10 {
        let product = digits
            .chars()
            .map(|x| x.to_digit(10).unwrap())
            .fold(1, |acc, i| acc*i);
        digits.clear();
        let mut formatter = Formatter::new(&mut digits);
        Display::fmt(&product, &mut formatter).unwrap();
        steps += 1;
    }
    steps
}

I have basically inlined the string conversion that would be performed by .to_string() in order to re-use the already-allocated buffer, instead of re-allocating one each iteration. You can try it out on the playground. Note that you need a nightly compiler because it makes use of an unstable feature.

user_59562610
Related