1

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

 3 months ago
source link: https://gist.github.com/jakobkogler/e6359ea9ced24fe304f1a8af3c9bee0e
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[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;
}

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK