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

Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Benchmark prime sieve speed between vector<char> and vector<bool>

### jxu commented on Oct 16, 2021

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 = block = 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 = is_prime = 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;
}``````

### jxu commented on Oct 17, 2021

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.