KEMBAR78
Vectorize `basic_string::find` by AlexGuteniev · Pull Request #5101 · microsoft/STL · GitHub
Skip to content

Vectorize basic_string::find #5101

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 2 commits into from
Dec 5, 2024
Merged

Vectorize basic_string::find #5101

merged 2 commits into from
Dec 5, 2024

Conversation

@AlexGuteniev
Copy link
Contributor

@AlexGuteniev AlexGuteniev commented Nov 19, 2024 •
edited
Loading

Resolves #5036

⚠️ Need to decide whether this CRT replacing vectorization is needed ⚠️

🏁 Race against the runtime!

basic_string::find is already vectorized for 8 and 16 bit characters via calling memchr and wmemchr

memchr shows good results for smaller positions, but if the distance from the beginning to the result is long the memchr results are noticeably worse. There's strong indication that such a results are due to not using AVX in memchr.

wmemchr is not fast at all. It was promised to be fast in a new CRT in #4873 though.

For larger characters the vectorization is novel, there's no CRT implementation, but these characters are rare anyway.

⏱️ Benchmark results

Benchmark main this
bm<char, not_highly_aligned_allocator, Op::StringFind>/8021/3056 89.6 ns 49.3 ns
bm<char, not_highly_aligned_allocator, Op::StringFind>/63/62 11.3 ns 3.70 ns
bm<char, not_highly_aligned_allocator, Op::StringFind>/31/30 9.90 ns 8.70 ns
bm<char, not_highly_aligned_allocator, Op::StringFind>/15/14 4.94 ns 7.10 ns
bm<char, not_highly_aligned_allocator, Op::StringFind>/7/6 2.83 ns 3.49 ns
bm<char, highly_aligned_allocator, Op::StringFind>/8021/3056 78.0 ns 48.0 ns
bm<char, highly_aligned_allocator, Op::StringFind>/63/62 12.4 ns 4.11 ns
bm<char, highly_aligned_allocator, Op::StringFind>/31/30 10.2 ns 7.85 ns
bm<char, highly_aligned_allocator, Op::StringFind>/15/14 5.18 ns 7.42 ns
bm<char, highly_aligned_allocator, Op::StringFind>/7/6 2.76 ns 3.42 ns
bm<wchar_t, not_highly_aligned_allocator, Op::StringFind>/8021/3056 754 ns 85.3 ns
bm<wchar_t, not_highly_aligned_allocator, Op::StringFind>/63/62 31.1 ns 3.84 ns
bm<wchar_t, not_highly_aligned_allocator, Op::StringFind>/31/30 16.2 ns 2.92 ns
bm<wchar_t, not_highly_aligned_allocator, Op::StringFind>/15/14 4.65 ns 3.66 ns
bm<wchar_t, not_highly_aligned_allocator, Op::StringFind>/7/6 2.45 ns 2.93 ns
bm<char32_t, not_highly_aligned_allocator, Op::StringFind>/8021/3056 749 ns 159 ns
bm<char32_t, not_highly_aligned_allocator, Op::StringFind>/63/62 18.5 ns 5.25 ns
bm<char32_t, not_highly_aligned_allocator, Op::StringFind>/31/30 9.60 ns 3.55 ns
bm<char32_t, not_highly_aligned_allocator, Op::StringFind>/15/14 6.42 ns 2.91 ns
bm<char32_t, not_highly_aligned_allocator, Op::StringFind>/7/6 2.80 ns 2.95 ns

@AlexGuteniev AlexGuteniev requested a review from a team as a code owner November 19, 2024 12:54
@CaseyCarter CaseyCarter added the performance Must go faster label Nov 19, 2024
@StephanTLavavej StephanTLavavej self-assigned this Nov 19, 2024
@StephanTLavavej
Copy link
Member

5950X benchmarks look good:

Benchmark Before After Speedup
bm<char, not_highly_aligned_allocator, Op::StringFind>/8021/3056 150 ns 49.3 ns 3.04
bm<char, not_highly_aligned_allocator, Op::StringFind>/63/62 14.9 ns 4.83 ns 3.08
bm<char, not_highly_aligned_allocator, Op::StringFind>/31/30 16.6 ns 8.50 ns 1.95
bm<char, not_highly_aligned_allocator, Op::StringFind>/15/14 9.86 ns 7.93 ns 1.24
bm<char, not_highly_aligned_allocator, Op::StringFind>/7/6 5.92 ns 5.61 ns 1.06
bm<char, highly_aligned_allocator, Op::StringFind>/8021/3056 149 ns 49.9 ns 2.99
bm<char, highly_aligned_allocator, Op::StringFind>/63/62 17.0 ns 4.88 ns 3.48
bm<char, highly_aligned_allocator, Op::StringFind>/31/30 16.5 ns 8.04 ns 2.05
bm<char, highly_aligned_allocator, Op::StringFind>/15/14 9.84 ns 7.75 ns 1.27
bm<char, highly_aligned_allocator, Op::StringFind>/7/6 5.93 ns 5.42 ns 1.09
bm<wchar_t, not_highly_aligned_allocator, Op::StringFind>/8021/3056 656 ns 87.6 ns 7.49
bm<wchar_t, not_highly_aligned_allocator, Op::StringFind>/63/62 16.1 ns 4.70 ns 3.43
bm<wchar_t, not_highly_aligned_allocator, Op::StringFind>/31/30 9.77 ns 4.26 ns 2.29
bm<wchar_t, not_highly_aligned_allocator, Op::StringFind>/15/14 5.78 ns 5.81 ns 0.99
bm<wchar_t, not_highly_aligned_allocator, Op::StringFind>/7/6 3.36 ns 5.37 ns 0.63
bm<char32_t, not_highly_aligned_allocator, Op::StringFind>/8021/3056 1289 ns 165 ns 7.81
bm<char32_t, not_highly_aligned_allocator, Op::StringFind>/63/62 32.9 ns 5.33 ns 6.17
bm<char32_t, not_highly_aligned_allocator, Op::StringFind>/31/30 14.9 ns 4.53 ns 3.29
bm<char32_t, not_highly_aligned_allocator, Op::StringFind>/15/14 8.18 ns 4.05 ns 2.02
bm<char32_t, not_highly_aligned_allocator, Op::StringFind>/7/6 4.22 ns 4.68 ns 0.90

@StephanTLavavej StephanTLavavej removed their assignment Dec 3, 2024
@StephanTLavavej StephanTLavavej mentioned this pull request Dec 3, 2024
Open
@StephanTLavavej StephanTLavavej self-assigned this Dec 3, 2024
@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 126f4eb into microsoft:main Dec 5, 2024
39 checks passed
@StephanTLavavej
Copy link
Member

Detective Beans and the Case of the Missing char! 🐱 🕵️ 🔎

@AlexGuteniev AlexGuteniev deleted the race-against-the-runtime branch December 5, 2024 06:19
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@StephanTLavavej StephanTLavavej StephanTLavavej approved these changes

Assignees

@StephanTLavavej StephanTLavavej

Labels

performance Must go faster

Projects

STL Code Reviews
Archived in project

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Use vector algorithms in basic_string::find and basic_string::rfind

3 participants

@AlexGuteniev @StephanTLavavej @CaseyCarter