On vector<bool>—Howard Hinnant

Save to:
Instapaper Pocket Readability

On vector<bool>

by Howard Hinnant

 

vector<bool> has taken a lot of heat over the past decade, and not without reason. However I believe it is way past time to draw back some of the criticism and explore this area with a dispassionate scrutiny of detail.

There are really two issues here:

  1. Is the data structure of an array of bits a good data structure?
  2. Should the aforementioned data structure be named vector<bool>?

I have strong opinions on both of these questions. And to get this out of the way up front:

  1. Yes.
  2. No.

The array of bits data structure is a wonderful data structure. It is often both a space and speed optimization over the array of bools data structure if properly implemented. However it does not behave exactly as an array of bools, and so should not pretend to be one.

First, what's wrong with vector<bool>?

Because vector<bool> holds bits instead of bools, it can't return a bool& from its indexing operator or iterator dereference. This can play havoc on quite innocent looking generic code. For example:

template <class T>
void
process(T& t)
{
    // do something with t
}

template <class T, class A>
void
test(std::vector<T, A>& v)
{
    for (auto& t : v)
        process(t);
}

The above code works for all T except bool. When instantiated with bool, you will receive a compile time error along the lines of:

error: non-const lvalue reference to type 'std::__bit_reference<std::vector<bool, std::allocator<bool>>, true>' cannot bind to
      a temporary of type 'reference' (aka 'std::__bit_reference<std::vector<bool, std::allocator<bool>>, true>')
    for (auto& t : v)
               ^ ~
note: in instantiation of function template specialization 'test<bool, std::allocator<bool>>' requested here
    test(v);
    ^
vector:2124:14: note: selected 'begin' function
      with iterator type 'iterator' (aka '__bit_iterator<std::vector<bool, std::allocator<bool>>, false>')
    iterator begin()
             ^
1 error generated.

This is not a great error message. But it is about the best the compiler can do. The user is confronted with implementation details of vector and in a nutshell says that the vector is not working with a perfectly valid ranged-based for statement. The conclusion the client comes to here is that the implementation of vector is broken. And he would be at least partially correct.

But consider if instead of vector<bool> being a specialization instead there existed a separate class template std::bit_vector<A = std::allocator<bool>> and the coder had written:

template <class A>
void
test(bit_vector<A>& v)
{
    for (auto& t : v)
        process(t);
}

Now one gets a similar error message:

error: non-const lvalue reference to type 'std::__bit_reference<std::bit_vector<std::allocator<bool>>, true>' cannot bind to
      a temporary of type 'reference' (aka 'std::__bit_reference<std::bit_vector<std::allocator<bool>>, true>')
    for (auto& t : v)
               ^ ~
note: in instantiation of function template specialization 'test<std::allocator<bool>>' requested here
    test(v);
    ^
bit_vector:2124:14: note: selected 'begin' function
      with iterator type 'iterator' (aka '__bit_iterator<std::bit_vector<std::allocator<bool>>, false>')
    iterator begin()
             ^
1 error generated.

And although the error message is similar, the coder is far more likely to see that he is using a dynamic array of bits data structure and it is understandable that you can't form a reference to a bit.

I.e. names are important. And creating a specialization that has different behavior than the primary, when the primary template would have worked, is poor practice.

But what's right with vector<bool>?

For the rest of this article assume that we did indeed have a std::bit_vector<A = std::allocator<bool>> and that vector was not specialized on bool. bit_vector<> can be much more than simply a space optimization over vector<bool>, it can also be a very significant performance optimization. But to achieve this higher performance, your vendor has to adapt many of the std::algorithms to have specialized code (optimizations) when processing sequences defined by bit_vector<>::iterators.

find

For example consider this code:

template <class C>
typename C::iterator
test()
{
    C c(100000);
    c[95000] = true;
    return std::find(c.begin(), c.end(), true);
}

How long does std::find take in the above example for:

  1. A hypothetical non-specialized vector<bool>?
  2. A hypothetical bit_vector<> using an optimized find?
  3. A hypothetical bit_vector<> using the unoptimized generic find?

I'm testing on an Intel Core i5 in 64 bit mode. I am normalizing all answers such that the speed of A is 1 (smaller is faster):

  1. 1.0
  2. 0.013
  3. 1.6

An array of bits can be a very fast data structure for a sequential search! The optimized find is inspecting 64 bits at a time. And due to the space optimization, it is much less likely to cause a cache miss. However if the implementation fails to do this, and naively checks one bit at a time, then this giant 75X optimization turns into a significant pessimization.

count

std::count can be optimized much like std::find to process a word of bits at a time:

template <class C>
typename C::difference_type
test()
{
    C c(100000);
    c[95000] = true;
    return std::count(c.begin(), c.end(), true);
}

My results are:

  1. 1.0
  2. 0.044
  3. 1.02

Here the results are not quite as dramatic as for the std::find case. However any time you can speed up your code by a factor of 20, one should do so!

fill

std::fill is yet another example:

template <class C>
void
test()
{
    C c(100000);
    std::fill(c.begin(), c.end(), true);
}

My results are:

  1. 1.0
  2. 0.40
  3. 38.

The optimized fill is over twice as fast as the non-specialized vector<bool>. But if the vendor neglects to specialize fill for bit-iterators the results are disastrous! Naturally the results are identical for the closely related fill_n.

copy

std::copy is yet another example:

template <class C>
void
test()
{
    C c1(100000);
    C c2(100000);
    std::copy(c1.begin(), c1.end(), c2.begin());
}

My results are:

  1. 1.0
  2. 0.36
  3. 34.

The optimized copy is approaches three times as fast as the non-specialized vector<bool>. But if the vendor neglects to specialize fill for bit-iterators the results are not good. If the copy is not aligned on word boundaries (as in the above example), then the optimized copy slows down to the same speed as the copy for A. Results for copy_backward, move and move_backward are similar.

swap_ranges

std::swap_ranges is yet another example:

template <class C>
void
test()
{
    C c1(100000);
    C c2(100000);
    std::swap_ranges(c1.begin(), c1.end(), c2.begin());
}

My results are:

  1. 1.0
  2. 0.065
  3. 4.0

Here bit_vector<> is 15 times faster than an array of bools, and over 60 times as fast as working a bit at a time.

rotate

std::rotate is yet another example:

template <class C>
void
test()
{
    C c(100000);
    std::rotate(c.begin(), c.begin()+c.size()/4, c.end());
}

My results are:

  1. 1.0
  2. 0.59
  3. 17.9

Yet another example of good results with an optimized algorithm and very poor results without this extra attention.

equal

std::equal is yet another example:

template <class C>
bool
test()
{
    C c1(100000);
    C c2(100000);
    return std::equal(c1.begin(), c1.end(), c2.begin());
}

My results are:

  1. 1.0
  2. 0.016
  3. 3.33

If you're going to compare a bunch of bools, it is much, much faster to pack them into bits and compare a word of bits at a time, rather than compare individual bools, or individual bits!

Summary

The dynamic array of bits is a very good data structure if attention is paid to optimizing algorithms that can process up to a word of bits at a time. In this case it becomes not only a space optimization but a very significant speed optimization. If such attention to detail is not given, then the space optimization leads to a very significant speed pessimization.

But it is a shame that the C++ committee gave this excellent data structure the name vector<bool> and that it gives no guidance nor encouragement on the critical generic algorithms that need to be optimized for this data structure. Consequently, few std::lib implementations go to this trouble.

Add a Comment

You must sign in or register to add a comment.

Comments (9)

0 0

Tianyu Zhu said on Nov 22, 2012 02:58 PM:

Could the following code

for (auto& t : v)
process(t);

be fixed if we had used auto&& instead?
0 0

AaronMcDaid said on Nov 22, 2012 04:52 PM:

Tianyu is right.

> Could the following code for (auto& t : v) process(t); be fixed if we had used auto&& instead?

auto&& works instead.
0 0

Martin Ba said on Nov 23, 2012 07:00 AM:

"... few std::lib implementations go to this trouble. ..."

It would certainly be interesting which do. (And what about boost::dynamic_bitset ...)
0 0

gmit said on Nov 23, 2012 05:46 PM:

I remember being not too happy with multithreaded modification of vector<bool> members back in VS2003. What does C++ standard say about this?
0 0

Robert Klarer said on Nov 24, 2012 10:43 AM:

To Tianyu and Aaron:

I think that Howard's point is that this is generic code. It shouldn't be necessary to add a workaround -- such as the one that you suggest -- to the example just so that was can handle the vector<bool> special case.
0 0

Robert Klarer said on Nov 24, 2012 10:45 AM:

s:was:we:

Can we get an edit button? grin
0 0

AaronMcDaid said on Nov 24, 2012 10:53 AM:

Robert, I agree with you on both counts, including the desirability of an edit button.

Anyway, is there any way to get an unspecialized vector<bool>? As a workaround, perhaps we could define a class Bool, which behaves very similarly to bool, and then use a vector<Bool>?
0 0

Glen said on Nov 27, 2012 08:14 PM:

Testing testing 123.
0 0

Glen said on Nov 27, 2012 08:31 PM:

So what you're saying about vector<bool> is: It's a bit of a drama...

* It's the sad tail of how a vector of bool wished to be free of the burden of being a bit special. i.e. not.
* Of being a bit_vector, but not quite.
* vector<bool> was not one, and not nothing was going to make it sound like one.
* People still called it vector<bool>, but when you're not one, you're nothing and people booly you all the time and you don't feel right.
* It really just wanted to be what many thought it already was: a dynamic array of bool. But some people couldn't handle the truth.
* If that sounds false, it's not, it's a true story.
* An array of bools just isn't cut out to be a no good two bit vector. Nothing could be clearer!
* An until vector<bool> stopped acting like a bad bit_vector thrown out of alignment, the sorry tail would never come to an easy end.
* So this act just had to end. But when?
* When would a bit_vector reach a standard where it could take over from a vector of bool and give the peformance of a lifetime?
* Well I don't know, that remains to be seen. But the moral of this story is clear enough:
* All great performers are in a class of their own. Nothing is false about that.
* If you think it's not true then, nothing will happen and that might be an error.
* You just can't have a happy ending if you remove your bits from one and have nowhere else to put them.

That's my take on the story so far!

I hope Howard gets this show made because his last movey had a similar plot line: A bit of work meets a lot of performance.

Get tickets early for this show! If you do, I see it playing out like this:

* Code will break but for good reason, and it'll be easy to fix without losing the plot.
* Howard has really made two much better stories from a bad variant of one. The script is simply vector<bool> reborn and a bit better sequel.
* Upgrading to bit_vector will take a bit of work, but the performance will be worth it!
* Upgrading a vector of bool to itself will be no effort and if it's to a vector of char it only gets easier to follow. The plot makes sense.
* bit_vector and vector<bool> themselves will also be a lot cleaner than before! Family viewing and happy times for the STL, both of them!
* bit_vector can even then be implemented using vector<x>. Just a spooky observation on how if you split up you can always get back together again even if no one else thinks it's a good idea...
* With clear names for different things, in the future it'll be obvious before you start watching, what you're going to see.
* With clear guides to the performance that can be expected, we know how this story ends.

The real story is... What are we waiting for? Let's make a move on this!

I wish these changes had made it into the C++11 standard before that final curtain fell. These are excellent changes and welcome, yesterday!

I nominate an Academy Award to: Howard Hinnant.