`<xstring>`: `__builtin_wmemcmp` is slow

Original report:

Reported by @lhecker to an internal mailing list, quoted with his permission, edited for Markdown:

Related to this it should also be noted that the default implementation for STL wide string comparisons uses __builtin_wmemcmp, which is about 4x (+/- something) slower than good old memcmp.

Here are some benchmarks with 128-byte long strings (meaning 64 chars for wide strings):

• Run on (32 X 3400 MHz CPU s)
• CPU Caches:
  • L1 Data 32 KiB (x16)
  • L1 Instruction 32 KiB (x16)
  • L2 Unified 512 KiB (x16)
  • L3 Unified 32768 KiB (x2)

Benchmark	Time	CPU	Iterations
std_string_view	7.84 ns	7.85 ns	89600000
std_wstring_view	32.0 ns	32.1 ns	22400000
standard_wmemcmp	17.8 ns	18.0 ns	37333333
standard_memcmp	6.88 ns	6.80 ns	89600000

Most curiously, as you can see here, is that __builtin_wmemcmp seems to be significantly slower than regular wmemcmp (the former produces rather abstruse assembly). In any case, if you want performance for string equality tests, I can only suggest using memcmp instead of wmemcmp. Our STL should likely replace any use of wmemcmp for such pure equality tests.

More analysis from me:

Here's where the STL calls __builtin_wmemcmp:

https://github.com/microsoft/STL/blob/d8f03cf399d730780b6ca0e5321a9ff4fc76bb0f/stl/inc/xstring#L240-L245

This is called by:

https://github.com/microsoft/STL/blob/d8f03cf399d730780b6ca0e5321a9ff4fc76bb0f/stl/inc/xstring#L564-L569
https://github.com/microsoft/STL/blob/d8f03cf399d730780b6ca0e5321a9ff4fc76bb0f/stl/inc/xstring#L1441-L1443
https://github.com/microsoft/STL/blob/d8f03cf399d730780b6ca0e5321a9ff4fc76bb0f/stl/inc/xstring#L1715-L1719

There are a few issues here:

1. If __builtin_wmemcmp is slower than wmemcmp at runtime, that should be reported as a compiler bug.
2. For wstring/wstring_view relational comparison (</<=/>/>=/<=>), we can work around that compiler bug by checking is_constant_evaluated and calling wmemcmp at runtime. This is less convenient than calling the builtin form unconditionally, but it's worth paying that code complexity for runtime performance (fixing a regression). As usual, compiler bug workarounds should be commented as TRANSITION.
3. For wstring/wstring_view equality comparison (==/!=), we need to retain a constexpr-compatible codepath, but at runtime, we can take advantage of the knowledge that we only need an "equal / non-equal" answer, for which memcmp is inherently faster than wmemcmp as Leonard measured.
   • I believe that _Traits_equal is the right place to make this change. We still need to handle user-defined traits, but it should be possible to use if constexpr to detect when the traits are char_traits<wchar_t> or char_traits<char16_t>.

Start in stl/inc/xstring around lines 240-245, then trace the calls around lines 564-569, 1441-1443, and 1715-1719. Check how the wstring and wstring_view equality and relational paths handle constexpr evaluation and user-defined traits; done means the proposed runtime comparison behavior is covered without losing constexpr compatibility and addresses the reported performance regression.