<algorithm>: algorithms should use TMP to provide optimized implementation for vector<bool> iterators

[horenmar]

MS's STL already uses metaprogramming to help the optimizer produce
optimized code. As an example, std::fill delegates to std::memset
if safe, which has the advantage of guaranteed good performance in
Debug mode, as well as not having to rely on the optimizer to salvage
reasonable ASM out of the actual code.

I would like optimizations like this to also happen when calling various
algorithms on std::vector<bool>, which currently does not happen.

As an example, this code

void clean_out(std::vector<bool>& vec) {
    std::fill(vec.begin(), vec.end(), false);
}

should end up calling memset, rather than doing whatever this is.

Other algorithms that could be optimized:

• std::copy
• std::count
• std::find
• std::equal
• possibly others?

---

This would also improve the performance of std::vector<bool>'s member functions, as it internally uses std algorithms.

[miscco]

So I was playing around a bit with this. As far as I understand one would need to specialize _Copy_unchecked for _Vb_const_iterator and _Vb_iterator as argument type.

First, one would have to check whether _First._Myoff == _Dest._Myoff. If not do the slow thing.

Second offsets. As far as I understand one could use unaligned memcopy but I am really unsure whether that is really wanted, especially as this would only really work if we copy full bytes. So I would do it by hand

1. copy the masked first byte
2. memcopy the full bytes from there
3. copy the masked last byte

Does that sound like an improvement?

[StephanTLavavej]

This is something that might not be a pure win because of the extra logic needed to handle partial bytes at the beginning and end, as you observed, but there's a potential improvement (8x or more) in the middle, so I think it's worth doing. Previously, optimizing operator== was an incredible win.

[rhalbersma]

Probably well-known, but Howard Hinnant wrote a blog about optimized algorithms for vector<bool> back in 2012: https://isocpp.org/blog/2012/11/on-vectorbool The libc++ sources have the details.

[rodiers]

In our code base me made huge performance improvements by not doing algorithms on vector but doing them on the underlying implementation instead.

For example instead of doing

      std::transform(mv_Flags.begin(), mv_Flags.end(),
        ac_Other.mv_Flags.begin(), mv_Flags.begin(),
        std::logical_and<bool>());

we changed it to

std::transform(mv_Flags._Myvec.begin(), mv_Flags._Myvec.end(),
        ac_Other.mv_Flags._Myvec.begin(), mv_Flags._Myvec.begin(),
        std::bit_and<unsigned int>());

It would be great if we could get decent performance wouldn't needing to rely on the underlying implementation.

[miscco]

I have implementations for most of the algorithms, waiting for the first to be reviewed again. That said using algorithms in the implementation is super risky if one does not go over full blocks