2

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;
}
Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
georch
  • 959
  • 7
  • 18
  • Please post (a link to) the complete program including the tests you're running. – Stefan Mesken Dec 26 '18 at 01:11
  • 7
    Also, what type of processor are you using? And what c++ complier/options are you using? If I'm not mistaken, the size of a c++ int depends on target architecture, etc, whereas in the rust code you explicitly state a 64 bit int. Not sure it's likely, but possibly you are comparing code using different underlying type sizes. – Nathan Dec 26 '18 at 01:34
  • 1
    @Nathan Thanks, that was it! The C++ int is aparrently not word-sized, as I thought. I've replaced it with int64_t and that seemed to make the difference. – georch Dec 26 '18 at 10:44
  • @Nathan And as the difference was quite close to a factor of two, I should've been suspicious about data types... – georch Dec 26 '18 at 11:11
  • 3
    That is not a Sieve of Erathostenes. You are doing trial division. – starblue Dec 26 '18 at 12:13
  • 3
    It is better to answer your own question than to edit the answer into the question. You may give @Nathan a chance to write the answer since it was their suggestion, but you don't have to. – trent Dec 26 '18 at 14:10
  • 2
    [Why is it discouraged to accept a reference to a String (&String), Vec (&Vec) or Box (&Box) as a function argument?](https://stackoverflow.com/q/40006219/155423) – Shepmaster Dec 26 '18 at 15:36
  • @starblue Just read up on it. Sieve of Erathostenes would be removing all multiples of the primes instead of checking whether a number is divisible, right? Sorry for the misunderstanding. – georch Dec 26 '18 at 17:02

1 Answers1

1

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.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
Nathan
  • 10,593
  • 10
  • 63
  • 87