[libc++] Vectorize all the algorithms

philnik777 commented 8 months ago

There are quite a few algorithms which can be vectorized, or one should at least look into doing so. This issue lists all the algorithms which I think can be vectorized (and a few that shouldn't be with explanations).

To be vectorized:

[ ] find (already done partially by forwarding to {w,}memchr)
[ ] find_end
[ ] find_first_of (possibly not worth it, since clang does it automatically in some cases)
[ ] adjacent_find
[x] mismatch - #73255
[ ] search (not checked whether it actually makes sense)
[ ] search_n
[ ] remove (requires efficient compressstore)
[ ] remove_copy (requires efficient compressstore)
[ ] unique (might require efficient compressstore)
[ ] unique_copy (might require efficient compresstore)
[ ] is_sorted_until
[ ] includes
[ ] min_element
[ ] max_element
[x] minmax (range overload): Should first be checked whether it can be rewritten to allow auto-vectorization - #87335
[ ] minmax_element
[x] lexicographical_compare: Should use mismatch for the actual vectorization, but only forward to it if it's known to vectorize
[ ] lexicographical_compare_three_way: same as lexicographical_compare
[x] replace_if autovectorized since https://github.com/llvm/llvm-project/pull/99808

Should be checked whether they can be vectorized:

[ ] set_union
[ ] set_intersection
[ ] set_difference
[ ] set_symmetric_difference
[ ] merge
[ ] rotate is using memmove when possible, but may make sense to optimize for small ranges

Shouldn't be vectorized:

contains: forwards to find, which should be vectorized instead
count: is auto-vectorized
equal: Already forwards to memcmp for trivially equality comparable types and doesn't seem worth it for floats
fold (and friends): is auto-vectorized
copy (and friends): can be forwarded to memmove
swap_ranges: is auto-vectorized
replace (and friends): is auto-vectorized
fill (and friends): is auto-vectorized
reverse_copy: is auto-vectorized
rotate_copy: is forwarded to two memmove calls if possible
shift_left/shift_right: is forwarded to memmove if possible
is_sorted: forwards to is_sorted_until, which should be vectorized instead
min, max (range overload): is auto-vectorized
reverse: auto-vectorized since https://github.com/llvm/llvm-project/pull/92560

mrdaybird commented 4 months ago

@philnik777 std::reverse auto-vectorized by #92560

philnik777 commented 4 months ago

@mrdaybird thanks, that's great! I've updated the list.

sjoerdmeijer commented 2 months ago

FYI: vectorization of find_first_of for AArch64 is implemented in https://github.com/llvm/llvm-project/pull/101976

llvm / llvm-project

[libc++] Vectorize all the algorithms #84663