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).
CodePudding user response:
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
}