KEMBAR78
Vectorize `mismatch` for clang-cl for odd element sizes by AlexGuteniev · Pull Request #5591 · microsoft/STL · GitHub
Skip to content

Conversation

@AlexGuteniev
Copy link
Contributor

Towards #5479

Unlike other comparing algorithms, mismatch vectorization can be expanded towards arbitrary element size easily, without even adding separately-compiled code. This is currently possible for clang-cl only, and it requires defaulted operator==, and trivially-comparable types, and unique object representation.

The mismatch result can be divided by element size in the header, thus truncating any offset into the middle, giving the element index. The division is likely to be optimized to large multiplication by the compiler.

Rather than using just __std_mismatch_1, attempt to use as large element mismatch as possible, for the following reasons:

  • Primarily, optimal tail processing. The reason to have _2 / _4 / _8 versions in the first place.
  • Also potentially smaller divisor is more likely to be optimized to the multiplication by the compiler. Though I haven't checked whether the compiler can get rid of power-of-two factor on its own; probably it can.

lexicographical_compare vectorization cannot be expanded this way, as it requires a different flavor of trivial comparability.

Benchmark results

Benchmark Before After Speedup
bm<color, op::mismatch, c1, c2>/8/3 1.97 ns 1.92 ns 1.03
bm<color, op::mismatch, c1, c2>/24/22 11.4 ns 4.22 ns 2.70
bm<color, op::mismatch, c1, c2>/105/-1 52.6 ns 11.4 ns 4.61
bm<color, op::mismatch, c1, c2>/4021/3056 1456 ns 294 ns 4.95

@AlexGuteniev AlexGuteniev requested a review from a team as a code owner June 15, 2025 15:27
@github-project-automation github-project-automation bot moved this to Initial Review in STL Code Reviews Jun 15, 2025
@StephanTLavavej StephanTLavavej added the performance Must go faster label Jun 16, 2025
@StephanTLavavej StephanTLavavej self-assigned this Jun 16, 2025
@StephanTLavavej StephanTLavavej removed their assignment Oct 3, 2025
@StephanTLavavej StephanTLavavej moved this from Initial Review to Ready To Merge in STL Code Reviews Oct 3, 2025
@StephanTLavavej StephanTLavavej moved this from Ready To Merge to Merging in STL Code Reviews Oct 3, 2025
@StephanTLavavej
Copy link
Member

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

@StephanTLavavej StephanTLavavej merged commit 64c0c4f into microsoft:main Oct 4, 2025
39 checks passed
@github-project-automation github-project-automation bot moved this from Merging to Done in STL Code Reviews Oct 4, 2025
@StephanTLavavej
Copy link
Member

🥉 5️⃣ 7️⃣

@AlexGuteniev AlexGuteniev deleted the color-mismatch branch October 4, 2025 04:54
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

performance Must go faster

Projects

Archived in project

Development

Successfully merging this pull request may close these issues.

2 participants