2

I would like to ask a question that can be summarized in one sentence:

What could be explanation for the performance difference between using vector<bool> (slow) and using vector<uint8_t> (fast)? (compiled with g++ 8.2 -O1 with C++17 standard)

Here is the full story.

It starts with LeetCode's Count Primes problem. Count the number of primes less than n.

One solution is to apply the Sieve of Eratosthenes, whose C++ code I will list below.

However, I interestedly noticed that with only one difference -- the vector type, there is a consistent gap in performance. Namely,

| type            | runtime |  memory |
|-----------------|---------|---------|
| vector<bool>    | 68 ms   | 8.6  MB |
| vector<uint8_t> | 24 ms   | 11.5 MB |

The full code is

class Solution
{
public:
    int countPrimes(int n)
    {
        // vector<uint8_t> isprime(n, true);
        vector<bool> isprime(n, true);
        int res = 0, root = std::sqrt(n);
        for (int i = 2; i < n; ++i) {
            if (isprime[i]) {
                ++res;
                if (i <= root)
                    for (int k = i * i; k < n; k += i)
                            isprime[k] = false;
            }
        }
        return res;
    }
};

For your reference, LeetCode has the following note for C++ compilation

Compiled with g++ 8.2 using the latest C++ 17 standard.

Your code is compiled with level one optimization (-O1). AddressSanitizer is also enabled to help detect out-of-bounds and use-after-free bugs.

Most standard library headers are already included automatically for your convenience.

My question is: what could be the explanation for the observation that using vector<bool> is much slower (68 ms, 60% percentile) than using vector<uint8_t> (24 ms, 95% percentile)?

I repeated the experiment for more than 10 times. The difference in memory usage is also consistent. If you have any explanation for that (vector<uint8_t> uses more memory than vector<bool>), I also would like to hear.

Thank you very much!

aafulei
  • 2,085
  • 12
  • 27
  • `std::vector` can be specialized to use individual bits. – Yashas Mar 17 '19 at 13:52
  • 1
    Remember that accessing whole bytes is faster than accessing individual bits. Also, have you tried `-O3`? – aaaaaa123456789 Mar 17 '19 at 13:53
  • @Yashas I found a comment from a linked post, commented by David Schwartz, saying "Don't use vector if you're super-concerned about performance. It's required by the standard to be very space efficient, and that has a performance cost." I guess this is what you mean. – aafulei Mar 17 '19 at 13:58
  • 1
    The standard allows `std::vector` to be specialized to make use of individual bits. Accessing a byte is fairly fast but to access individual bit, you need to perform additional bitwise operations. You can find more information here: https://en.cppreference.com/w/cpp/container/vector_bool – Yashas Mar 17 '19 at 13:59
  • It's not required by the standard to be more space efficient. It's implementation defined AFAIK. – Yashas Mar 17 '19 at 13:59
  • @aaaaaa123456789 with a combination of your and Yashas' comments, it now becomes clear to me. `vector` can be made space-efficient, but at a cost of speed. Interesting, never knew it before! With `uint8_t` we are accessing the whole byte which is much more faster. Thanks! – aafulei Mar 17 '19 at 14:03

0 Answers0