Why is Node.js faster than Rust at generating primes?

Question

These are two basic code snippets to generate prime numbers in Rust and Node.js respectively. I am generating 100000 prime numbers.

Rust

use std::time::Instant;

fn main(){
    let start = Instant::now();
    generate_primes(100000);
    let elapsed = start.elapsed();
    // println!("{:?}", generate_primes(10));
    println!("Time taken: {}ms", elapsed.as_millis());
}

pub fn generate_primes(n: i32) -> Vec<i32> {
  let mut numbers:Vec<i32> = vec![0; 0];
  let mut iter:i32 = 2;
  let mut generated:i32 = 0;

  while generated < n {
    if is_prime(iter) {
      numbers.push(iter);
      generated += 1;
    }
    iter += 1;
  }

  numbers
}

fn is_prime(n: i32) -> bool {
    let limit = (n as f32).sqrt() as i32;

    for i in 2..=limit {
        if n % i == 0 {
            return false;
        }
    }

    true
}

Time taken for Rust code to execute: 3274ms

Edit: After running cargo run --release: 370ms

Node.js

const t0 = Date.now();
const primes = generatePrimes(100000);
const t1 = Date.now();
console.log(`Time taken: ${t1 - t0}ms`);

function generatePrimes(total) {
  let primes = [];
  let iter = 2;
  let generated = 0;

  while (generated < total) {
    if (isPrime(iter)) {
      primes.push(iter);
      generated++;
    }
    iter++;
  }
  return primes;
}

function isPrime(num) {
  for (let i = 2; i * i <= num; i++) {
    if (num % i === 0) {
      return false;
    }
  }
  return true;
}

Time taken for Javascript to execute: 333ms

I am new to Rust (and typed languages in general), so there must be some optimizations I have missed out on. It would be interesting to know how the time for Rust can be improved (even with cargo run --release, it is slower than Node.js).

Answer 1

In JS, all numbers are floating-point thus division/modulo are performed on floating-point.

However, in current processors, integer division/modulo are much slower than floating-point ones (see here).

In your Rust program, the modulo is naturally computed on integers. When artificially switching to floating-point, I get a substancial improvement (310ms --> 152ms).

fn fmod(
    x: f64,
    y: f64,
) -> f64 {
    x - (x / y).floor() * y
}

fn is_prime(n: i32) -> bool {
    let limit = (n as f32).sqrt() as i32;
    for i in 2..=limit {
        if fmod(n as f64, i as f64) == 0.0 {
            return false;
        }
    }
    true
}

To go further, we can save the sqrt() operation if we compare squares (by the way, you did this in your JS code). (152ms --> 144ms)

fn is_prime(n: i32) -> bool {
    for i in 2.. {
        if i * i > n {
            break;
        }
        if fmod(n as f64, i as f64) == 0.0 {
            return false;
        }
    }
    true
}