Confused about performance

help
1

Hi folks! First time posting here.

So I have been learning Rust in my spare time, and I'm currently working my way through the Exercism problems. All is going well, but I am experiencing some performance characteristics that I cannot explain, and I hope someone here can shed some light!

( Please prepend "http" to the following link, forum won't let me post more than two links since I'm new here :frowning: )
The code in question is in my solutions the nth prime problem: ://exercism.io/exercises/rust/nth-prime/readme
1st iteration: [irrelevant]
2nd iteration: http://exercism.io/submissions/52e21b2bc5ed45078e71b5c377f8bfd8
3rd iteration: http://exercism.io/submissions/bb33e47988094ec9bcfea67ecd07a7ce

All iterations pass the tests, so no issue there. However, the 2nd iteration is fairly naive, in that it does more many more modulo operations than necessary. In the 3rd iteration, I attempted to improve performance by stealing ideas from the Sieve of Eratosthenes. I was expecting it to be roughly 10x faster, but instead it appears to be roughly 10x slower! There's not much going on here, so I feel like an explanation should be fairly obvious, but I'm totally stumped. Anyone see what I'm missing?

2 Likes
2

The second algorithm actually does more modulus operations than the first one :slight_smile:

The first one check about sqrt(n) numbers, while the second one checks all primes smaller than n, and there are about n / ln(n) such primes, which is larger than sqrt(n).

However, the ideas from the first and the second algorithms could be combined together:

    fn is_next_prime(&self) -> bool {
       (&self.known).into_iter()
           .take_while(|&num| num*num <= self.current)
           .all(|num| self.current % num != 0)
    }

This indeed produces a faster solution.

1 Like
3

Ah, thank you! That is indeed the issue. I am very relieved that it is something so easy to understand! I made a mistake of assumption.

I tried your tweak, and it works well, and is easier to read than my 2nd iteration. Thanks again!

2 Likes