Prime numbers

The prime number generator examples various implementations of the Sieve of Eratosthenes to find prime numbers up to a numeric limit. For a detailed description of how the sieve works see primes-1-generator.cpp, but the short version is that a stack of coroutines per prime only let through numbers not multiples of their prime.

The times are recorded on my desktop (AMD R9 5950X) without really controlling for thermals or boost clocks, so they're a bit noisy, but the differences are large enough that the differences are clear anyway.

Because the sieve only requires addition and comparison, it should make this quite a good benchmark for the underlying coroutine machinery and the compiler's ability to optimise them.

primes-1-generator.cpp

This is a very simple and straight forward implementation of the idea. It's simple enough that it didn't require any debugging -- it simply worked first time.

As you push clang to looking at larger numbers it also dumps core. The core dump is due to stack exhaustion due to all of the interconnected coroutines. Basically the generator has to call in to the one below in order to pull the next value. Eventually the stack of coroutines in the sieve becomes large enough that they cause a stack overflow.

primes-2-stream.cpp

This just changes the generator type to stream (an asynchronous generator type) and adds the required co_await. Now we also need to lift the old main into a coroutine, which can be easily done using task.

This implementation is clearly a good deal slower, but has the advantage that it can be pushed to much larger values due to the fact that the stream together with the co_await allows for symmetric transfer when values are fetched from further down in the sieve. This means that this version never needs more than a handful of stack frames to work so the sieve size is limited only by available RAM and not by available stack.

Lewis Baker has a good write up about symmetric transfer here.

primes-3-optimised.cpp

The straight forward implementations above always added all primes to the sieve, but it isn't necessary to add the prime until the number we're wanting to check is larger than the primes square. This version implements that and does it in such a way that it preserves the "only use addition and comparisons" rule, meaning it keeps track of the squares without using multiplication.

The speed up is impressive, and allows us to check much larger numbers with reasonable cost.

Conclusions

It seems that clang is more efficient with the stack usage, but gcc is slightly better at optimising the code. At up to 10-25% improvement this is a significant win for gcc though.

It's also clear that the generator type is generally much faster than the stream, but the inability to do real symmetric transfer (the continuation must be called directly) means that you must be careful about stack usage if you have very long chains of them. The stream type is far more scalable, but it comes with the cost that it can only be used from coroutines due to the required co_await.

The optimised implementation just goes to show that micro-optimisations are great and all, but looking for more efficient algorithms is a far better use of time.