CODEWITHSUNDEEP
performancerust
georch
georch

Reputation: 1444

Why is iterating over a vector of integers slower in Rust than in Python, C# and C++?

I'm learning Rust right now and I'm using this simple Sieve of Erathostenes implementation:

fn get_primes(known_primes: &Vec<i64>, start: i64, stop: i64) -> Vec<i64> {
    let mut new_primes = Vec::new();
    for number in start..stop {
        let mut is_prime = true;
        let limit = (number as f64).sqrt() as i64;
        for prime in known_primes {
            if number % prime == 0 {
                is_prime = false;
                break;
            }
            if *prime > limit {
                break;
            }
        }
        if is_prime {
            new_primes.push(number);
        }
    }
    return new_primes;
}

I'm comparing it to virtually the same code (modulo syntax) in Python (with numba), C#, and C++ (gcc/clang). All of them are about 3x faster than this implementation on my machine.

I am compiling in release mode. To be exact, I've added this to my Cargo.toml, which seems to have the same effect:

[profile.dev]
opt-level = 3

I've also checked the toolchain, there is a slight (15% or so) difference between MSVC and GNU, but nothing that would explain this gap.

Am I getting something wrong here? Am I making a copy somewhere?

Is this code equivalent to the following C++ code?

vector<int> getPrimes(vector<int> &knownPrimes, int start, int stop) {
    vector<int> newPrimes;
    for (int number = start; number < stop; number += 1) {
        bool isPrime = true;
        int limit = (int)sqrt(number);
        for (auto& prime : knownPrimes) {
            if (number % prime == 0) {
                isPrime = false;
                break;
            }
            if (prime > limit)
                break;
        }
        if (isPrime) {
            newPrimes.push_back(number);
        }
    }
    return newPrimes;
}

Upvotes: 2

Views: 679

Answers (1)

Nathan
Nathan

Reputation: 10784

The size of a C++ int depends on target architecture, compiler options etc.. In the Rust code, you explicitly state a 64-bit integer. You may be comparing code using different underlying type sizes.

Upvotes: 1

Related Questions