Is super long redundant code efficient?

Question

I'm trying to find some primes with the Sieve of the greek guy algorithm. I have some efficiency concerns. Here's the code:

void check_if_prime(unsigned number)
{
    unsigned index = 0;
    while (primes[index] <= std::sqrt(number))
    {
        if (number % primes[index] == 0) return;
        ++index;
    }
    primes.push_back(number);
}

And, because I coded huge 2/3/5/7/11/13 prime wheel, the code is 5795 lines longs.

for (unsigned i = 0; i < selection; ++i)
{
    unsigned multiple = i * 30030;
    if (i!=0) check_if_prime( multiple+1 );
    check_if_prime ( multiple+17 );
    check_if_prime ( multiple+19 );
    check_if_prime ( multiple+23 );
    // ...so on until 30029
}

Optimization flags: -O3, -fexpensive-optimizations, -march=pentium2

25 million primes in 20 minutes with CPU stuck at 50% (no idea why, tried real time priority but it didn't change much). Size of output text file is 256MB (going to change to binary later on).

• Compilation takes ages! Is it okay? How can I make it faster without compromising efficiency?
• Is that if statement at the start of for loop OK? I've read if statements take the longest.
• Anything else concerning the code, not the algorithm? Anything to make it faster? What statements are faster than others?
• Would even a bigger wheel (up to 510510, not just 30030, hell a lot of lines) compile within a day?

I want to find all primes up to 2^32 and little optimizations would save some hours and electricity. Thank you in advance!

EDIT: not seeking for an algorithm, seeking for code improvement if there can be done any!

Answer 1

Here is what I can say about the performance of your program:

1. Likely your main problem is the call to std::sqrt(). This is a floating point function that's designed for full precision of the result, and it definitely take quite a few cycles. I bet you'll be much faster if you use this check instead:

   while (primes[index]*primes[index] < number)
   

   That way you are using an integer multiplication which is trivial for modern CPUs.

2. The if statement at the start of your for() loop is irrelevant to performance. It's not executed nearly enough times. Your inner loop is the while loop within check_if_prime(). That's the one you need to optimize.

3. I can't see how you are doing output. There are ways to do output that can severely slow you down, but I don't think that's the main issue (if it is an issue at all).

4. Code size can be an issue: your CPU has an instruction cache with limited capacity. If your 6k lines don't fit into the first level instruction cache, the penalty can be severe. If I were you, I'd reimplement the wheel using data instead of code, i. e.:

   unsigned const wheel[] = {1, 17, 19, 23, ...};    //add all your 6k primes here
   for (unsigned i = 0; i < selection; ++i)
   {
       unsigned multiple = i * 30030;
       for(unsigned j = 0; j < sizeof(wheel)/sizeof(*wheel); j++) {
           check_if_prime(multiple + wheel[j]);
       }
   }
   

Answer 2

Get it running under a debugger, and single-step it, instruction by instruction, and at each point understand what it is doing, and why.

This makes you walk in the shoes of the CPU, and you will see all the silliness that nutty programmer is making you do, and you will see what you could do better.

That's one way to make your code go as fast as possible.

Program size, by itself, only affects speed if you've got it so fast that caching becomes an issue.

Answer 3

Here's a stab at some techniques for checking if a number is a prime:

bool is_prime(unsigned int number) // negative numbers are not prime.
{
  // A data store for primes already calculated.
  static std::set<unsigned int> calculated_primes;

  // Simple checks first:
  // Primes must be >= 2.
  // Primes greater than 2 are odd.
  if (   (number < 2)
      || ((number > 2) && ((number & 1) == 0) )
  {
    return false;
  }

  // Initialize the set with a few prime numbers, if necessary.
  if (calculated_primes.empty())
  {
     static const unsigned int primes[] =
     { 2, 3, 5, 7, 13, 17, 19, 23, 29};
     static const unsigned int known_primes_quantity =
         sizeof(primes) / sizeof(primes[0]);
     calculated_primes.insert(&primes[0], &primes[known_primes_quantity]);
  }
  // Check if the number is a prime that is already calculated:
  if (calculated_primes.find(number) != calculated_primes.end())
  {
    return true;
  }

  // Find the smallest prime to the number:
  std::set<unsigned int>::iterator prime_iter =
      calculated_primes.lower_bound(number);
  // Use this value as the start for the sieve.
  unsigned int prime_candidate = *prime_iter;
  const unsigned int iteration_limit = number * number;
  while (prime_candidate < iteration_limit)
  {
     prime_candidate += 2;
     bool is_prime = true;
     for (prime_iter = calculated_primes.begin();
          prime_iter != calculated_primes.end();
          ++prime_iter)
     {
       if ((prime_candidate % (*prime_iter)) == 0)
       {
         is_prime = false;
         break;
       }
     }
     if (is_prime)
     {
       calculated_primes.insert(prime_candidate);
       if (prime_candidate == number)
       {
         return true;
       }
     }
  }
  return false;
}

Note: This is untested code but demonstrates some techniques for checking if a number is prime.