Why is std::vector<bool> faster?

Question

As I was implementing the Sieve of Eratosthenes I ran into an issue with std::vector<bool> : there is no access to the raw data.

So I decided to use a custom minimalistic implementation where I would have access to the data pointer.

#ifndef LIB_BITS_T_H
#define LIB_BITS_T_H

#include <algorithm>
template <typename B>

class bits_t{

public:

    typedef B block_t;
    static const size_t block_size = sizeof(block_t) * 8;

    block_t* data;
    size_t size;
    size_t blocks;

    class bit_ref{
    public:
        block_t* const block;
        const block_t mask;

        bit_ref(block_t& block, const block_t mask) noexcept : block(&block), mask(mask){}

        inline void operator=(bool v) const noexcept{
            if(v) *block |= mask;
            else  *block &= ~mask;
        }

        inline operator bool() const noexcept{
            return (bool)(*block & mask);
        }
    };



    bits_t() noexcept : data(nullptr){}

    void resize(const size_t n, const bool v) noexcept{
        block_t fill = v ? ~block_t(0) : block_t(0);
        size = n;
        blocks = (n + block_size - 1) / block_size;
        data = new block_t[blocks];
        std::fill(data, data + blocks, fill);
    }

    inline block_t& block_at_index(const size_t i) const noexcept{
        return data[i / block_size];
    }

    inline size_t index_in_block(const size_t i) const noexcept{
        return i % block_size;
    }

    inline bit_ref operator[](const size_t i) noexcept{
        return bit_ref(block_at_index(i), block_t(1) << index_in_block(i));
    }

    ~bits_t(){
        delete[] data;
    }

};

#endif // LIB_BITS_T_H

The code is nearly the same than the one in /usr/include/c++/4.7/bits/stl_bvector.h but is slower.

I tried an optimization,

#ifndef LIB_BITS_T_H
#define LIB_BITS_T_H

#include <algorithm>
template <typename B>

class bits_t{

const B mask[64] = {
    0b0000000000000000000000000000000000000000000000000000000000000001,
    0b0000000000000000000000000000000000000000000000000000000000000010,
    0b0000000000000000000000000000000000000000000000000000000000000100,
    0b0000000000000000000000000000000000000000000000000000000000001000,
    0b0000000000000000000000000000000000000000000000000000000000010000,
    0b0000000000000000000000000000000000000000000000000000000000100000,
    0b0000000000000000000000000000000000000000000000000000000001000000,
    0b0000000000000000000000000000000000000000000000000000000010000000,
    0b0000000000000000000000000000000000000000000000000000000100000000,
    0b0000000000000000000000000000000000000000000000000000001000000000,
    0b0000000000000000000000000000000000000000000000000000010000000000,
    0b0000000000000000000000000000000000000000000000000000100000000000,
    0b0000000000000000000000000000000000000000000000000001000000000000,
    0b0000000000000000000000000000000000000000000000000010000000000000,
    0b0000000000000000000000000000000000000000000000000100000000000000,
    0b0000000000000000000000000000000000000000000000001000000000000000,
    0b0000000000000000000000000000000000000000000000010000000000000000,
    0b0000000000000000000000000000000000000000000000100000000000000000,
    0b0000000000000000000000000000000000000000000001000000000000000000,
    0b0000000000000000000000000000000000000000000010000000000000000000,
    0b0000000000000000000000000000000000000000000100000000000000000000,
    0b0000000000000000000000000000000000000000001000000000000000000000,
    0b0000000000000000000000000000000000000000010000000000000000000000,
    0b0000000000000000000000000000000000000000100000000000000000000000,
    0b0000000000000000000000000000000000000001000000000000000000000000,
    0b0000000000000000000000000000000000000010000000000000000000000000,
    0b0000000000000000000000000000000000000100000000000000000000000000,
    0b0000000000000000000000000000000000001000000000000000000000000000,
    0b0000000000000000000000000000000000010000000000000000000000000000,
    0b0000000000000000000000000000000000100000000000000000000000000000,
    0b0000000000000000000000000000000001000000000000000000000000000000,
    0b0000000000000000000000000000000010000000000000000000000000000000,
    0b0000000000000000000000000000000100000000000000000000000000000000,
    0b0000000000000000000000000000001000000000000000000000000000000000,
    0b0000000000000000000000000000010000000000000000000000000000000000,
    0b0000000000000000000000000000100000000000000000000000000000000000,
    0b0000000000000000000000000001000000000000000000000000000000000000,
    0b0000000000000000000000000010000000000000000000000000000000000000,
    0b0000000000000000000000000100000000000000000000000000000000000000,
    0b0000000000000000000000001000000000000000000000000000000000000000,
    0b0000000000000000000000010000000000000000000000000000000000000000,
    0b0000000000000000000000100000000000000000000000000000000000000000,
    0b0000000000000000000001000000000000000000000000000000000000000000,
    0b0000000000000000000010000000000000000000000000000000000000000000,
    0b0000000000000000000100000000000000000000000000000000000000000000,
    0b0000000000000000001000000000000000000000000000000000000000000000,
    0b0000000000000000010000000000000000000000000000000000000000000000,
    0b0000000000000000100000000000000000000000000000000000000000000000,
    0b0000000000000001000000000000000000000000000000000000000000000000,
    0b0000000000000010000000000000000000000000000000000000000000000000,
    0b0000000000000100000000000000000000000000000000000000000000000000,
    0b0000000000001000000000000000000000000000000000000000000000000000,
    0b0000000000010000000000000000000000000000000000000000000000000000,
    0b0000000000100000000000000000000000000000000000000000000000000000,
    0b0000000001000000000000000000000000000000000000000000000000000000,
    0b0000000010000000000000000000000000000000000000000000000000000000,
    0b0000000100000000000000000000000000000000000000000000000000000000,
    0b0000001000000000000000000000000000000000000000000000000000000000,
    0b0000010000000000000000000000000000000000000000000000000000000000,
    0b0000100000000000000000000000000000000000000000000000000000000000,
    0b0001000000000000000000000000000000000000000000000000000000000000,
    0b0010000000000000000000000000000000000000000000000000000000000000,
    0b0100000000000000000000000000000000000000000000000000000000000000,
    0b1000000000000000000000000000000000000000000000000000000000000000
};

public:

    typedef B block_t;
    static const size_t block_size = sizeof(block_t) * 8;

    block_t* data;
    size_t size;
    size_t blocks;

    class bit_ref{
    public:
        block_t* const block;
        const block_t mask;

        bit_ref(block_t& block, const block_t mask) noexcept : block(&block), mask(mask){}

        inline void operator=(bool v) const noexcept{
            if(v) *block |= mask;
            else  *block &= ~mask;
        }

        inline operator bool() const noexcept{
            return (bool)(*block & mask);
        }
    };



    bits_t() noexcept : data(nullptr){}

    void resize(const size_t n, const bool v) noexcept{
        block_t fill = v ? ~block_t(0) : block_t(0);
        size = n;
        blocks = (n + block_size - 1) / block_size;
        data = new block_t[blocks];
        std::fill(data, data + blocks, fill);
    }

    inline block_t& block_at_index(const size_t i) const noexcept{
        return data[i / block_size];
    }

    inline size_t index_in_block(const size_t i) const noexcept{
        return i % block_size;
    }

    inline bit_ref operator[](const size_t i) noexcept{
        return bit_ref(block_at_index(i), mask[index_in_block(i)]);
    }

    ~bits_t(){
        delete[] data;
    }

};

#endif // LIB_BITS_T_H

(Compiling with g++4.7 -O3)

Eratosthenes sieve algorithm (33.333.333 bits)

std::vector<bool> 19.1s

bits_t<size_t> 19.9s

bits_t<size_t> (with lookup table) 19.7s

ctor + resize(33.333.333 bits) + dtor

std::vector<bool> 120ms

bits_t<size_t> 150ms

QUESTION : Where does the slowdown come from?

Answer 1

Outside of all the problems as pointed out by some other users, your resize is allocating more memory each time the current block limit is reached to add ONE block. The std::vector will double the size of the buffer (so if you already had 16 blocks, now you have 32 blocks). In other words, they will do less new than you.

This being said, you do not do the necessary delete & copy and that could have a "positive" impact in your version... ("positive" impact speed wise, it is not positive that you do not delete the old data, nor copy it in your new buffer.)

Also, the std::vector will properly enlarge the buffer and thus copy data that is likely already in your CPU cache. With your version, that cache is lost since you just ignore the old buffer on each resize().

Also when a class handles a memory buffer it is customary to implement the copy and assignment operators, for some reasons... and you could look into using a shared_ptr<>() too. The delete is then hidden and the class is a template so it is very fast (it does not add any code that you would not already have in your own version.)

=== Update

There is one other thing. You're operator [] implementation:

inline bit_ref operator[](const size_t i) noexcept{
    return bit_ref(block_at_index(i), mask[index_in_block(i)]);
}

(side note: the inline is not required since the fact that you write the code within the class already means you okayed the inline capability already.)

You only offer a non-const version which "is slow" because it creates a sub-class. You should try implementing a const version that returns bool and see whether that accounts for the ~3% difference you see.

bool operator[](const size_t i) const noexcept
{
    return (block_at_index(i) & mask[index_in_block(i)]) != 0;
}

Also, using a mask[] array can also slow down things. (1LL << (index & 0x3F)) should be faster (2 CPU instructions with 0 memory access).