The ranges algorithms aren't optimized for vector<bool>

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.

http://llvm.org

Other

28.02k stars 11.57k forks source link

The ranges algorithms aren't optimized for vector<bool> #64038

Open philnik777 opened 1 year ago

philnik777 commented 1 year ago

Currently we are missing a lot of vector<bool> optimizations, because we are overloading the public interface instead of a private one.

[ ] std::equal
[ ] std::rotate
[ ] std::swap_ranges
[ ] std::move_backward
[ ] std::move
[ ] std::copy_backward
[ ] std::copy
[x] std::fill
[x] std::fill_n
[x] std::count
[x] std::find

changkhothuychung commented 10 months ago

Just curious, since I am new to the codebase, can you give me the links to the files where the optimizations are done for the vector of other types?

philnik777 commented 10 months ago

In general, there aren't special optimizations for other types. If there are any optimizations, they are there because the vector iterator models a contiguous iterator. e.g. std::find(vec.begin(), vec.end(), 23) (assuming vector<int>) would be optimized to a wmemchr on most platforms, because that is optimized for contiguous iterators. That kind of optimization would be done in libcxx/include/__algorithm/find.h and friends.