Skip to content

Vectorize swap and ranges::swap for arrays#2689

Merged
StephanTLavavej merged 6 commits intomicrosoft:mainfrom
StephanTLavavej:swap-arrays-faster
May 1, 2022
Merged

Vectorize swap and ranges::swap for arrays#2689
StephanTLavavej merged 6 commits intomicrosoft:mainfrom
StephanTLavavej:swap-arrays-faster

Conversation

@StephanTLavavej
Copy link
Member

@StephanTLavavej StephanTLavavej commented Apr 29, 2022

Fixes #2683.

The (minor) main difficulty here is that the vectorized machinery was defined in <xutility>, but swap() for arrays is defined in its parent header <utility>, and ranges::swap is defined in <concepts>. To solve this, I'm moving the definition of _USE_STD_VECTOR_ALGORITHMS up to <type_traits> (unchanged), then extracting only the declaration of __std_swap_ranges_trivially_swappable_noalias(), with a comment directing the reader to <xutility>. (Any merge conflicts with vectorization PRs in flight should be trivial to resolve.)

Because <utility> and <concepts> are "core" headers, I'm also adding a comment that if users want to use them without linking to the STL, they might need to disable our use of vectorized algorithms.

Since we've already extensively tested this implementation, I'm adding a small amount of incremental test coverage. This covers various element sizes and array lengths (from 1 element of 1 byte, to 512 elements of 8 bytes).

Small cleanup in <utility>: Because the control flow is becoming more complicated, I'm changing the if (&_Left != &_Right) self-swap guard to an if (_First1 == _First2) early return. This uses the named pointers we already need, instead of taking the addresses of the arrays.

In <concepts>, I'm using const auto to decay the arrays; I felt that this looked simpler than saying _Ty1 here even though we know that it's the same as _Ty2. Then, we need to defend __std_swap_ranges_trivially_swappable_noalias with a self-swap check; I believe that it should be within the "we're eligible for vectorization" preprocessor and if constexpr checks (because the condition is rare), but that it didn't need to be within the "we're at runtime" codepath (it's okay for constant evaluation to perform the self-swap check).

@StephanTLavavej StephanTLavavej added the performance Must go faster label Apr 29, 2022
@StephanTLavavej StephanTLavavej requested a review from a team as a code owner April 29, 2022 03:17
@ghost

This comment was marked as outdated.

@StephanTLavavej StephanTLavavej changed the title <utility>: Use vectorized swapping in swap(T (&)[N], T (&)[N]) Vectorize swap and ranges::swap for arrays Apr 29, 2022
@StephanTLavavej StephanTLavavej self-assigned this Apr 30, 2022
@StephanTLavavej
Copy link
Member Author

I'm mirroring this to the MSVC-internal repo - please notify me if any further changes are pushed.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

performance Must go faster

Projects

None yet

Development

Successfully merging this pull request may close these issues.

std::swap of arrays, why is there no specialization for trivial types

2 participants