Sieve of Eratosthenes Optimization in Rust

Question

When I want to try a new language, I first try to write a fairly basic sieve of Eratosthenes project in said language. This is a very simple algorithm, with predictable results, and can even be optimized somewhat to compare versions of different languages' compilers. I've done this in (chronological order) python, ruby, C, Java, D, Go, and am now tackling rust. The Cargo.toml file dependencies are very simple, as we just need to import the number crate:

...
[dependencies]
num = "*"

To get the pow command, which seems odd to me, along with some other things that I will ask at the end of the code portion. Here is my code, whose running time actually favors comparable with C on my machine.

/// Eratosthenes prime sieve program
/// Mostly used as a programming learning experience
extern crate num;

use num::pow;
use num::iter::range;
use num::iter::range_step;

fn main() {
    // The hint hat cmd_args will be a vector of type _ 
    // which is a placeholder for the type, which only 
    // rust knows.  The args() is the normal topography
    // of the location on the machine and what the program
    // was called with.  The map is an iterator adaptor.
    // it returns each x with to_string being called on it
    // and then finally collected into our vector
    let cmd_args: Vec<_> = std::env::args()
        .map(|x| x.to_string())
        .collect();
    println!("Hello, world: {:?}", cmd_args);

    // Cast to our u64 limit
    // Parse the first arg (no checking) into a u64
    // Then use the power to raise 2^num for the limit
    let input_num = cmd_args[1].parse::<u64>();
    let limit:usize = pow(2u64, input_num.unwrap() as usize) as usize;

    println!("Limit: {}", limit);

    // Use destructuring to bind the two variables to eratosthenes
    let (era_pc, era_max) = eratosthenes(limit);
    println!("Eratosthenes");
    println!("\tPrimesCounted: {}", era_pc);
    println!("\tMax prime: {}", era_max);
}

// Basic eratosthenes functin that takes a limit and counts all
// all of the prime numbers below it
fn eratosthenes(limit: usize) -> (u64, u64) {
    let mut pc: u64 = 0;
    let mut maxprime: u64 = 7;

    // Allocate the array and initialize
    let mut primes = vec![true; limit];
    primes[0] = false;
    primes[1] = false;

    let slimit = (limit as f64).sqrt() as usize;
    for i in range(2, slimit) {
        if primes[i] {
            for j in num::iter::range_step(i*i, limit, i) {
                primes[j] = false;
            }
        }
    }

    //let testp: Vec<usize> = primes.iter()
    //                      .enumerate()
    //                      .filter_map(|(pr, &is_pr)| if is_pr { Some(pr) } else {None} )
    //                      .collect();
    //println!("{:?}",testp);

    for p in (0..limit) {
        if primes[p] {
            pc = pc + 1;
            maxprime = p as u64;
        }
    }

    (pc, maxprime)
}

For my code, I am mostly looking for ways to improve coding in idiomatic Rust. I know there are many ways to improve that I'm doing, and many ways to rust-ify some things that are in there, like the map reduce at the end of the eratosthenes function call itself to find the largest prime and number of primes.

Now for my gripes. I guess the biggest thing that bothered me was the different ways of using pow vs sqrt. They're both mathematical operators, and both show up a lot in scientific computing. So why shouldn't they be treated the same when we try to access then? Why is pow buried more deeply than sqrt. Second, why is sqrt a method that is accessed AFTER the expression? Also, finding the documentation that says that both arrays and vectors are created and filled, dare I say initialized, with the same number is

let mut v: i<32> = vec![10; 10];

Was not obvious at all.

Finally, and this isn't just a rust thing, but I wish there was a better way to get some of the concepts like enumerate, filter, map, filter_map, collect better tutorials, because I sure need some, but that's my problem, not rusts.

So overall, how can I make my code more idiomatic rust?

Answer 1

End result

extern crate num;

use num::iter::range_step;

fn main() {
    let input_num =
        std::env::args()
        .nth(1)
        .and_then(|x| x.parse().ok())
        .unwrap();

    let limit = usize::pow(2, input_num);
    println!("Limit: {}", limit);

    let (era_pc, era_max) = eratosthenes(limit);

    println!("Eratosthenes");
    println!("\tPrimesCounted: {}", era_pc);
    println!("\tMax prime: {}", era_max);
}

fn eratosthenes(limit: usize) -> (u64, u64) {
    let mut primes = vec![true; limit];
    primes[0] = false;
    primes[1] = false;

    let slimit = f64::sqrt(limit as f64) as usize;
    for i in 2..slimit {
        if primes[i] {
            for j in num::iter::range_step(i*i, limit, i) {
                primes[j] = false;
            }
        }
    }

    (0..limit).fold((0, 7), |(count, max), prime| {
        if primes[prime] {
            (count + 1, prime as u64)
        } else {
            (count, max)
        }
    })
}

Breakdown of changes

for the type, which only Rust knows.

A human can know this type too, but we will tend to use _ just to avoid telling the compiler something it already knows. This lets the compiler infer the proper type, so we don't wear out our keyboards needlessly. ^_^

Instead of reading the args, converting them to Strings (which allocates memory), and then parsing them, I would probably just convert them in one pass. We can also just take the one number (thanks to Veedrac for pointing out that nth would be a better choice here):

let input_num =
    std::env::args()
    .nth(1)
    .and_then(|x| x.parse().ok())
    .unwrap();

You can use Unified Function Call Syntax (UFCS) to call usize::pow as a function, not just as a method. This is also a built-in method, so you don't need to use an external crate for this:

let limit = usize::pow(2, input_num);

We can make a similar change for sqrt, and use range syntax (start..end) for easy ranges:

let slimit = f64::sqrt(limit as f64) as usize;
for i in 2..slimit {
    if primes[i] {
        for j in num::iter::range_step(i*i, limit, i) {
            primes[j] = false;
        }
    }
}

Sadly, range notation with a step size bigger than 1 is still unstable, so we continue using the external crate for this.

I would encourage you to move your variable declarations (pc, maxprime) closer to where they are used. This isn't C89, where it's required to put the variables at the top! ^_^

You can also make that code a bit more functional:

(0..limit).fold((0, 7), |(count, max), prime| {
    if primes[prime] {
        (count + 1, prime as u64)
    } else {
        (count, max)
    }
})

Bigger picture

the different ways of using pow vs sqrt

In bog-standard Rust, they are the same. sqrt and pow are methods on their respective types, and there are versions for each type. Using UFCS, you can call any method as a function — value.pow(5) or u32::pow(value, 5) for example.

However, you are using the num crate, which tries to provide an abstraction on top of all the concrete numeric types.

the documentation that says that both arrays and vectors are created and filled

I'm not sure what could be improved here. The docs for vec! indicate that it can be used this way, and the docs for Vec point out vec!. I don't know that it makes sense to copy-and-paste the docs from every method into every other method...

a better way to get some of the concepts like enumerate, filter, map, filter_map, collect better tutorials

If you are asking for a way to get better understanding of these, then the best bet is to use them! Go through each method in Iterator and write small programs that use each one.

Most (if not all) of those methods are documented with examples that show their use as well.

Benchmarking

Benchmarking is stull unstable, so you'll need to be using a nightly compiler and opt-in to the feature by adding #![feature(test)] to your crate.

You can then add something like this:

#[cfg(test)]
mod bench {
    extern crate test;

    #[bench]
    fn sieve_2(b: &mut test::Bencher) {
        b.iter(|| test::black_box(super::eratosthenes(2)))
    }

    #[bench]
    fn sieve_3(b: &mut test::Bencher) {
        b.iter(|| test::black_box(super::eratosthenes(3)))
    }

    #[bench]
    fn sieve_4(b: &mut test::Bencher) {
        b.iter(|| test::black_box(super::eratosthenes(4)))
    }

    #[bench]
    fn sieve_5(b: &mut test::Bencher) {
        b.iter(|| test::black_box(super::eratosthenes(5)))
    }

    #[bench]
    fn sieve_6(b: &mut test::Bencher) {
        b.iter(|| test::black_box(super::eratosthenes(6)))
    }
}

And run it:

$ cargo bench

running 5 tests
test bench::sieve_2 ... bench:        34 ns/iter (+/- 6)
test bench::sieve_3 ... bench:        35 ns/iter (+/- 5)
test bench::sieve_4 ... bench:        37 ns/iter (+/- 4)
test bench::sieve_5 ... bench:        40 ns/iter (+/- 21)
test bench::sieve_6 ... bench:        40 ns/iter (+/- 3)

test result: ok. 0 passed; 0 failed; 0 ignored; 5 measured

Benchmarking is done with optimizations enabled. Unfortunately, the optimizer can be too good sometimes ^_^. In this case, the optimizer completely throws away the result of your function and says that the benchmarking loop took zero time. The mysterious test::black_box function is needed in this case, as the optimizer can't see inside of it and thus can't optimize away your code.