Code and Stuff

May 20, 2011

stl::vector performance

While profiling a piece of software I came across a quite surprising finding: a lot of cycles were lost in
stl::vector<bool>::operator[]

It took me quite some time to actually believe that it was really that method that was slow. Some test and a quick Internet search showed that the implementation of the stl::vector is memory usage optimized when the template argument is bool.

Two possible solution to this problem that I found are:

  • use a stl::deque<bool> instead of a stl::vector<bool>
  • use an integer instead of a boolean
The speedup gained by opting for the second solution was in the order 4x.