Sieve32Fast - A very fast, memory efficient, multi-threaded Sieve of Eratosthenes

An improved version Sieve32FastV2 is available.

The classical solutions for the Sieve of Eratosthenes fall into 2 camps: one uses a bool[], which is fast but very memory bloated; the other uses a BitArray, which is more sluggish but uses far less memory. Refusing to accept that those are the only 2 possibilities, I’ve created a multi-threaded sieve that is as fast as a bool[] while using only 4% more memory than a BitArray.

I don’t consider the code to be complicated but is quite a bit longer than a simple sieve. If a simple sieve is more of your speed, stick with Sieve31 or Sieve32.

The class is no longer static; however all public methods remain static. The public methods will create a private instance, and that private instance uses 2 embedded private classes as well: Vector and VectorList, which implements List.

Related versions

Sieve31 a simple sieve for 31 bit primes, or int. Uses BitArray. Likely candidate for ToList().

Sieve32 a simple sieve for 32 bit primes, or uint. Uses BitArray. Due to memory needs, a bool[] version is not possible.

EBrown’s answer to Sieve31. Uses a bool[]. Over 40% faster than Sieve31 but uses 600% the memory. Due to memory constraints, cannot use ToList().

The version below is as fast if not faster than EBrown’s answer (depends on number of cores) but requires only 4% more memory than Sieve31.

```
public class Sieve32Fast
{
private static ArgumentException BadUpperLimitException => new ArgumentException("upperLimit be must greater than or equal to 2.", "upperLimit");

// NOTE TO 'Sam The Maintainer'
//
// As the code deals with primes, composites, indices, and lengths, all of which are integers,
// it helps to have context over what type of entity a given value represents.
//
// A 'Number' will be a uint representing some natural number {0, 1, 2, ..., uint.MaxValue}.
// The constants Zero, One, Two, Three are such 'Numbers'.
// If I were to a

Micro-Optimizations

One very micro-optimization you can make is, instead of subtracting numbers, add the negative variants.

For example:

var stopIndex = vector.BitLength - 1;

Is faster as:

var stopIndex = vector.BitLength + -1;

It's just the nature of the beast. Subtraction takes more cycles than addition, so if you add the negative complements of your values, you gain speed. (When calculating the first 100,000,000 primes I saw times drop from 3808ms to 3653ms, averaged over 5 runs.)

The same can be said about division and multiplication. Multiplying by the reciprocal is faster than dividing. (These are only beneficial if the calculation for the reciprocal happens fewer times than the multiplication.)

Another extremely micro-optimization you can make is to replace certain modulo operations with bitwise and operations.

Consider:

(this.UpperLimit & Two) == Zero)

This is slightly faster as:

((this.UpperLimit & 0x01U) == Zero)

This doesn't have much effect on the results, but I saw times drop further from 3653ms to 3622ms (5 run average).

Readability

Apart from the few micro-optimizations above, one of the issues I see with your code is just how packed it is.

For example, this is hard to read:

// output remaining primes 
for (var vectorIndex = 0; vectorIndex < _vectors.Count; vectorIndex++)
{
    var vector = _vectors[vectorIndex];
    var startIndex = (vectorIndex == 0) ? rootBitIndex + 1 : 0;
    // Due to high frequency of access, its ever so slightly faster to have copies created outside the loop
    // rather than called inside the loop directly and repeatedly with vector.BitLength and vector.StartingNumber.
    var length = vector.BitLength;
    var startingNumber = vector.StartingNumber;
    for (var bitIndex = startIndex; bitIndex < length; bitIndex++)
    {
        if (vector[bitIndex]) { yield return ToNumber(bitIndex, startingNumber); }
    }
}

It's ever so slightly easier to follow with a little more whitespace:

// output remaining primes 
for (var vectorIndex = 0; vectorIndex < _vectors.Count; vectorIndex++)
{
    var vector = _vectors[vectorIndex];
    var startIndex = (vectorIndex == 0) ? rootBitIndex + 1 : 0;
    // Due to high frequency of access, its ever so slightly faster to have copies created outside the loop
    // rather than called inside the loop directly and repeatedly with vector.BitLength and vector.StartingNumber.
    var length = vector.BitLength;
    var startingNumber = vector.StartingNumber;

    for (var bitIndex = startIndex; bitIndex < length; bitIndex++)
    {
        if (vector[bitIndex])
        {
            yield return ToNumber(bitIndex, startingNumber);
        }
    }
}

General Concerns

As far as your general questions:


But then there’s the constants Zero, One, Two, and Three. Are they magic numbers, or even if they aren't, is it overkill to use this?

The problem with having these constants is that the name of the constant doesn't imply what it means, but instead what it is. This means that any usage of them within the code is meaningless, as the only thing we know about them is that Zero is a uint valued at 0. If this is all the magic numbers are for, then having a constant adds absolutely no value to the code. It's only noise.

When you use the Find All References feature, it should be clear that each instance of that constant, property, field, method, class, struct, etc. is used in a specific scenario. However, these constants are not. So what is the point? I don't actually care about what references the constant Zero, so why is it a constant? Would I ever need to change it? No, so there's no value added.


Should there be a Vector.Id property?


Should VectorList have a RootVector property?


Using Three instead of rootVector.StartingNumber

All three of these have the same response:

Properties exist to allow is to idiomatically access information within them. By not using/creating properties, you fall into the trap of having to remember just exactly what the operation means. So, for:

var prime32 = ToNumber(bitIndex, Three);

Why did I choose Three for this? Ah, right, because that's what rootVector.StartingNumber is. However, now you have to either: add a comment explaining such, or remind yourself every time you get there what that value means. It adds no value to the code. You should use the property rootVector.StartingNumber, simply because it's self-explanatory. (It's also no slower than using the constant Three, which we should remove anyway as it adds no value to the code either.)

Generally speaking, you should use whatever practice adds the most value to your code, not whatever practice is the simplest. For example, you have the functions:

```
private static Func ToIndex => (uint number, uint startingNumber) => (int)((number - startingNumber) >> 1);
private static Func ToNumber => (int bitIndex, uint startingNumber) => (uint)(bitIndex

StackExchange Code Review Q#104056, answer score: 5