Arsthbt

I was trying to solve a coding problem in C++ which counts the number of prime numbers less than a non-negative number n.

So I first came up with some code:

int countPrimes(int n) 
 vector<bool> flag(n+1,1);
 for(int i =2;i<n;i++)
 
 if(flag[i]==1)
 for(long j=i;i*j<n;j++)
 flag[i*j]=0;
 
 int result=0;
 for(int i =2;i<n;i++)
 result+=flag[i];
 return result;

which takes 88 ms and uses 8.6 MB of memory. Then I changed my code into:

int countPrimes(int n) 
 // vector<bool> flag(n+1,1);
 bool flag[n+1] ;
 fill(flag,flag+n+1,true);
 for(int i =2;i<n;i++)
 
 if(flag[i]==1)
 for(long j=i;i*j<n;j++)
 flag[i*j]=0;
 
 int result=0;
 for(int i =2;i<n;i++)
 result+=flag[i];
 return result;

which takes 28 ms and 9.9 MB. I don't really understand why there is such a performance gap in both the running time and memory consumption. I have read relative questions like this one and that one but I am still confused.

EDIT: I reduced the running time to 40 ms with 11.5 MB of memory after replacing vector<bool> with vector<char>.

std::vector<bool> isn't like any other vector. The documentation says:

std::vector<bool> is a possibly space-efficient specialization of
std::vector for the type bool.

That's why it may use up less memory than an array, because it might represent multiple boolean values with one byte, like a bitset. It also explains the performance difference, since accessing it isn't as simple anymore. According to the documentation, it doesn't even have to store it as a contiguous array.

std::vector<bool> is special case. It is specialized template. Each value is stored in single bit, so bit operations are needed. This memory compact but has couple drawbacks (like no way to have a pointer to bool inside this container).

Now bool flag[n+1]; compiler will usually allocate same memory in same manner as for char flag[n+1]; and it will do that on stack, not on heap.

Now depending on page sizes, cache misses and i values one can be faster then other. It is hard to predict (for small n array will be faster, but for larger n result may change).

As an interesting experiment you can change std::vector<bool> to std::vector<char>. In this case you will have similar memory mapping as in case of array, but it will be located at heap not a stack.

I'd like to add some remarks to the good answers already posted.

• 
  

  The performance differences between std::vector<bool> and std::vector<char> may vary (a lot) between different library implementations and different sizes of the vectors.

  
  
  

  See e.g. those quick benches: clang++ / libc++(LLVM) vs. g++ / libstdc++(GNU).

  
  



• This: bool flag[n+1]; declares a Variable Length Array, which (despites some performance advantages due to it beeing allocated in the stack) has never been part of the C++ standard, even if provided as an extension by some (C99 compliant) compilers.




• Another way to increase the performances could be to reduce the amount of calculations (and memory occupation) by considering only the odd numbers, given that all the primes except for 2 are odd.

If you can bare the less readable code, you could try to profile the following snippet.

int countPrimes(int n)

 if ( n < 2 )
 return 0;
 // Sieve starting from 3 up to n, the number of odd number between 3 and n are
 int sieve_size = n / 2 - 1;
 std::vector<char> sieve(sieve_size); 
 int result = 1; // 2 is a prime.

 for (int i = 0; i < sieve_size; ++i)
 
 if ( sieve[i] == 0 )
 
 // It's a prime, no need to scan the vector again
 ++result;
 // Some ugly transformations are needed, here
 int prime = i * 2 + 3;
 for ( int j = prime * 3, k = prime * 2; j <= n; j += k)
 sieve[j / 2 - 1] = 1;
 
 

 return result;