Vectorize `basic_string::find` #5101

AlexGuteniev · 2024-11-19T12:54:41Z

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

StephanTLavavej · 2024-12-03T20:27:49Z

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 · 2024-12-03T22:22:55Z

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

StephanTLavavej · 2024-12-05T06:17:27Z

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

Vectorize basic_string::find

95d3776

AlexGuteniev requested a review from a team as a code owner November 19, 2024 12:54

start at

97b4cfa

CaseyCarter added the performance Must go faster label Nov 19, 2024

StephanTLavavej self-assigned this Nov 19, 2024

StephanTLavavej approved these changes Dec 3, 2024

View reviewed changes

StephanTLavavej removed their assignment Dec 3, 2024

StephanTLavavej mentioned this pull request Dec 3, 2024

Maintainer priorities #4700

Open

StephanTLavavej self-assigned this Dec 3, 2024

StephanTLavavej merged commit 126f4eb into microsoft:main Dec 5, 2024
39 checks passed

AlexGuteniev deleted the race-against-the-runtime branch December 5, 2024 06:19

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Vectorize `basic_string::find` #5101

Vectorize `basic_string::find` #5101

Uh oh!

AlexGuteniev commented Nov 19, 2024 •

edited

Loading

Uh oh!

StephanTLavavej commented Dec 3, 2024

Uh oh!

StephanTLavavej commented Dec 3, 2024

Uh oh!

Uh oh!

StephanTLavavej commented Dec 5, 2024

Uh oh!

Uh oh!

Vectorize basic_string::find #5101

Vectorize basic_string::find #5101

Uh oh!

Conversation

AlexGuteniev commented Nov 19, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

🏁 Race against the runtime!

⏱️ Benchmark results

Uh oh!

StephanTLavavej commented Dec 3, 2024

Uh oh!

StephanTLavavej commented Dec 3, 2024

Uh oh!

Uh oh!

StephanTLavavej commented Dec 5, 2024

Uh oh!

Uh oh!

Vectorize `basic_string::find` #5101

Vectorize `basic_string::find` #5101

AlexGuteniev commented Nov 19, 2024 •

edited

Loading