C++ Fast Bitset Short-Circuit Bitwise Operations

Question

A demo problem: Given two std::bitset<N>s, a and b check if any bit is set in both a and b.

There are two rather obvious solutions to this problem. This is bad because it creates a new temporary bitset, and copies values all sorts of places just to throw them away.

template <size_t N>
bool any_both_new_temp(const std::bitset<N>& a, const std::bitset<N>& b)
{
    return (a & b).any();
}

This solution is bad because it goes one bit at a time, which is less than ideal:

template <size_t N>
bool any_both_bit_by_bit(const std::bitset<N>& a, const std::bitset<N>& b)
{
    for (size_t i = 0; i < N; ++i)
        if (a[i] && b[i])
            return true;
    return false;
}

Ideally, I would be able to do something like this, where block_type is uint32_t or whatever type the bitset is storing:

template <size_t N>
bool any_both_by_block(const std::bitset<N>& a, const std::bitset<N>& b)
{
    typedef std::bitset<N>::block_type block_type;
    for (size_t i = 0; i < a.block_count(); ++i)
        if (a.get_block(i) & b.get_block(i))
            return true;
    return false;
}

Is there an easy way to go about doing this?

Elope

Create your own class if you're not happy. – Subulate

Answer 1

I compiled your first example with optimization in g++ and it produced code identical to your third solution. In fact, with a smallish bitset (320 bits) it fully unrolled it. Without calling a function to ensure that the contents of a and b were unknown in main it actually optimized the entire thing away (knowing both were all 0).

Lesson: Write the obvious, readable code and let the compiler deal with it.

Might

Answer 2

You say that your first approach "copies values all sorts of places just to throw them away." But there's really only one extra value-copy (when the result of operator& is returned to any_both_new_temp), and it can be eliminated by using a reference instead of a value:

template <size_t N>
bool any_both_new_temp(const std::bitset<N>& a, const std::bitset<N>& b)
{
    std::bitset<N> tmp = a;
    tmp &= b;
    return tmp.any();
}

(But obviously it will still create a temporary bitset and copy a into it.)

Scuttle

Or better pass a by value and directly work on it. It does actually do the same (create a copy of the argument) but it better enables copy elision if possible. – Feucht

@ChristianRau: That's true, but in my experience people tend to have a "WTF?" moment when they see an argument getting modified within the function, even when it's passed by value. I remember seeing once, in a C++ Usenet-group archive, a question that compared pass-by-reference-with-explicit-copy to pass-by-value-without-it; the first gazillion responses all (wrongly) explained that the pass-by-value version was actually modifying the object. (I think the respondents did understand how pass-by-value and copy-constructors work, but they failed to notice the value arg where they expected a ref.) – Scuttle

Though the readability argument is understandable, the question was explicitly about efficiency and in this case I wouldn' want to miss the advantage of a possible copy elision. And I think with the advent of the copy-and-swap idiom and similar things, the pass-by-value-to-get-copy idiom should be quite established nowadays. – Feucht