Benchmark prime sieve speed between vector<char> and vector<bool>

Did you try with std::bitset?

@jxu
Just did a small experiment. Only for 1e9 though (as bitsets require the size to be known at compile time). Looks like std::bitset is a bit slower than std::vector<bool> during the normal sieve, but a bit faster during the segmented sieve. Not sure why.

N = 1000000000: 
    norm: vector<bool>:   7775 ms
    norm: vector<char>:  11992 ms
    norm: bitset:         9291 ms
    seg:  vector<bool>:   7305 ms
    seg:  vector<char>:   3110 ms
    seg:  bitset:         6501 ms

Maybe it's possible to optimize the bitset solution a little bit. I basically just replaced std::vector<T> v(size) with std::bitset<size> v in the code. But maybe there are some clever bitmask tricks that you can use.

For reference:

int count_primes_seg_bitset(int n) {
    if (n != 1000000000)
        return 0;
    constexpr int S = 10'000;

    vector<int> primes;
    constexpr int nsqrt = 31623;
    auto is_prime = std::move(bitset<nsqrt + 1>{}.set());
    for (int i = 2; i <= nsqrt; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= nsqrt; j += i)
                is_prime[j] = false;
        }
    }

    int result = 0;
    bitset<S> block;
    for (int k = 0; k * S <= n; k++) {
        block.set();
        int start = k * S;
        for (int p : primes) {
            int start_idx = (start + p - 1) / p;
            int j = max(start_idx, p) * p - start;
            for (; j < S; j += p)
                block[j] = false;
        }
        if (k == 0)
            block[0] = block[1] = false;
        for (int i = 0; i < S && start + i <= n; i++) {
            if (block[i])
                result++;
        }
    }
    return result;
}

int count_primes_bitset(int n) {
    if (n != 1000000000)
        return 0;
    auto is_prime = std::move(bitset<1000000000>{}.set());
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i])
            cnt++;
    }
    return cnt;
}

The point of bitmask is not to need clever bitmask tricks I suppose, so if there's no significant difference then vector being dynamic makes it easier to use.