Computing the first n primes: an example from Clean Code revised for C++

Question

I'm trying to improve on examples from Clean Code* while re-implementing them in C++. This time it's the Sieve of Eratosthenes prime-computing example from pp. 71-74.

Below is the original adapted for C++, without improvements:

.h

class PrimeGenerator { 
public:
    PrimeGenerator() = default;
    ~PrimeGenerator() = default;

    static std::vector<unsigned> generatePrimes(unsigned maxValue);

private:
    static void uncrossIntegersUpTo(unsigned maxValue);
    static void crossOutMultiples();
    static unsigned determineIterationLimit();
    static void crossOutMultiplesOf(unsigned i);
    static bool notCrossed(unsigned i);
    static void putUncrossedIntegersIntoResult();
    static unsigned numberOfUncrossedIntegers();

    static std::vector<bool> crossedOut;
    static std::vector<unsigned> result; 
};

.cpp

std::vector<bool> PrimeGenerator::crossedOut;
std::vector<unsigned> PrimeGenerator::result;

std::vector<unsigned> PrimeGenerator::generatePrimes(unsigned maxValue)
{
    if (maxValue < 2)
        return {};

    uncrossIntegersUpTo(maxValue);
    crossOutMultiples();
    putUncrossedIntegersIntoResult();
    return result;
}

void PrimeGenerator::uncrossIntegersUpTo(unsigned maxValue)
{
    crossedOut = std::vector<bool>(maxValue + 1, false);
    crossedOut[0] = true;
    crossedOut[1] = true;
}

void PrimeGenerator::crossOutMultiples()
{
    unsigned limit = determineIterationLimit();
    for (size_t i = 2; i <= limit; ++i)
    {
        if (notCrossed(i))
            crossOutMultiplesOf(i);
    }
}

unsigned PrimeGenerator::determineIterationLimit()
{
    // Every multiple in the array has a prime factor that
    // is less than or equal to the root of the array size,
    // so we don't have to cross out multiples of numbers
    // larger than that root.
    double iterationLimit = std::sqrt(crossedOut.size());
    return static_cast<unsigned>(iterationLimit);
}

void PrimeGenerator::crossOutMultiplesOf(unsigned i)
{
    for (size_t multiple = 2 * i; multiple < crossedOut.size(); multiple += i)
    {
        crossedOut[multiple] = true;
    }
}

bool PrimeGenerator::notCrossed(unsigned i)
{
    return !crossedOut[i];
}

void PrimeGenerator::putUncrossedIntegersIntoResult()
{
    result = std::vector<unsigned>(numberOfUncrossedIntegers());
    size_t j = 0;
    for (size_t i = 2; i < crossedOut.size(); ++i)
    {
        if (notCrossed(i))
            result[j++] = i;
    }
}

unsigned PrimeGenerator::numberOfUncrossedIntegers()
{
    unsigned count = 0;
    for (size_t i = 2; i < crossedOut.size(); ++i)
    {
        if (notCrossed(i))
            count++;
    }

    return count;
}

What we see here is a static class with static functions and members. We don't like these in C++, so it seems this code could be better served with a namespace and some free functions. Let's try - my improvement attempt coming below.

.h

namespace PrimeGenerator
{
    std::vector<unsigned> generatePrimes(unsigned maxValue);
}

.cpp

namespace {

std::vector<bool> uncrossIntegersUpTo(int maxValue)
{
    std::vector<bool> crossedOut(maxValue + 1, false);
    crossedOut[0] = true;
    crossedOut[1] = true;

    return crossedOut;
}

unsigned determineIterationLimit(size_t size)
{
    // Every multiple in the array has a prime factor that
    // is less than or equal to the root of the array size,
    // so we don't have to cross out multiples of numbers
    // larger than that root.
    double iterationLimit = std::sqrt(size);
    return static_cast<unsigned>(iterationLimit);
}

void crossOutMultiplesOf(unsigned i, std::vector<bool>& crossedOut)
{
    for (size_t multiple = 2 * i; multiple < crossedOut.size(); multiple += i)
    {
        crossedOut[multiple] = true;
    }
}

void crossOutMultiples(std::vector<bool>& crossedOut)
{
    unsigned limit = determineIterationLimit(crossedOut.size());
    for (size_t i = 2; i <= limit; ++i)
    {
        if (!crossedOut[i])
            crossOutMultiplesOf(i, crossedOut);
    }
}

std::vector<unsigned> putUncrossedIntegersIntoResult(const std::vector<bool>& crossedOut)
{
    std::vector<unsigned> result;
    for (size_t i = 2; i < crossedOut.size(); ++i)
    {
        if (!crossedOut[i])
            result.push_back(i);
    }

    return result;
}

}

namespace PrimeGenerator {

std::vector<unsigned> generatePrimes(unsigned maxValue)
{
    if (maxValue < 2)
        return {};

    auto crossedOut = uncrossIntegersUpTo(maxValue);
    crossOutMultiples(crossedOut);
    return putUncrossedIntegersIntoResult(crossedOut);
}

}

A quick summary of changes:
- I removed the class, leaving a single interface function in a PrimeGenerator namespace.
- The numberOfUncrossedIntegers() function didn't seem to make much sense, so I refactored putUncrossedIntegersIntoResult(...) to get rid of the former.
- notCrossed(...) would now need to have two parameters, so it stopped making sense either. It's gone now.

Now, I have two questions about my code. First of all, we now need to pass the crossedOut vector around, which is a downside compared to the previous design. Would you propose an alternative solution to mitigate this? Secondly, are there any extra places where I should have used size_t instead of unsigned?

Cheers!

EDIT:
I'd like to stress I care more about good software engineering and coding style here rather than making this algorithm as fast as possible. Though of course it should be correct.

---

* Clean Code: A Handbook of Agile Software Craftsmanship, Robert C. Martin

Answer 1

In general, we try to keep functions small and nice, but in your case, using so many functions is just weird. For example, are you sure the uncrossedIntegersUpTo function is needed at all? How about determineIterationLimit? You can just handle them in the main function.

Also, std::vector<bool> is not like the normal vector. It is not a container because it (usually) packs the bools together to save space. This may result in a significant increase in runtime. (See Howard Hinnant's On vector<bool>) This is definitely a big mistake, but there is no trivial backwards compatible way to fix it at this stage. You may have to consider working around it with, say, std::vector<char> in this case.

Now let's talk about types. First, it is std::size_t, not size_t. Second, your use of unsigned everywhere is like a "magic type" (analogous to magic numbers) — it will help to define an alias like

using number_t = unsigned;

And I think something like std::uint_fast32_t will be better in this case. Also, std::size_t operates on sizes. Are you sure you want to use it for numbers?

std::sqrt operates on floating point numbers and may cause precision problems here. You may want to design some isqrt function for integers.

Putting these together, your code may be as simple as something like: (not tested)

// generate primes less than max
std::vector<number_t> generate_primes(number_t max)
{
    if (max < 2)
        return {};

    // You may need to use char or something like that
    std::vector<bool> table(max, false); // crossed out numbers
    table[0] = table[1] = true;

    const number_t limit = isqrt(max); // like that
    for (number_t i = 2; i < limit; ++i) {
        if (!table[i]) {
            for (number_t j = i * 2; j < max; ++j)
                table[j] = true;
        }
    }

    std::vector<number_t> result;
    for (number_t i = 2; i < max; ++i) {
        if (!table[i])
            result.push_back(i);
    }
    return result;
}

Answer 2

• Starting cross-out from size_t multiple = 2 * i is a serious pessimization. Every multiple of i with other factor less than i has already been crossed out during previous passes, which dealt with these smaller primes. You should start with size_t multiple = i * i.

• Notice that computing i * i eliminates the need to compute sqrt. The outer loop written as

  for (size_t i = 2; i * i < crossedOut.size(); ++i)
  

  terminates in a very natural way. It may also be beneficial to store the square in a variable:

  for (size_t i = 2; (square = i * i) < crossedOut.size(); ++i) {
      crossOutMultiplesOf(square, i, crossedOut);
  }
  

  Now, passing both i and its square seems redundant. OTOH not passing the square forces the callee to recompute it. This is a very rare situation in which I'd advocate against factoring the loop into a function. Consider

  for (size_t i = 2; (square = i * i) < crossedOut.size(); ++i) {
      for (size_t multiple = square; multiple < crossedOut.size(); multiple += i) {
          crossedOut[multiple] = true;
      }
  }