Further optimize find_first_of

[AlexGuteniev]

• For one-element needle use find
• For more than 16 bytes needle check it by parts
• Do something for 4 and 8 byte size elements
• Consider enabling for some cases basic_string::find_first_of (or prove it is not possible)

[frederick-vs-ja]

• Consider enabling for some cases basic_string::find_first_of (or prove it is not possible)

I think this fallback part (wouldn't be used with char or char8_t, but may be used with wide character types) is definitely doable.

STL/stl/inc/xstring

Lines 732 to 737 in 8e2d724

	const auto _End = _Haystack + _Hay_size;
	for (auto _Match_try = _Haystack + _Start_at; _Match_try < _End; ++_Match_try) {
	if (_Traits::find(_Needle, _Needle_size, *_Match_try)) {
	return static_cast<size_t>(_Match_try - _Haystack); // found a match
	}
	}

[AlexGuteniev]

I think this fallback part (wouldn't be used with char or char8_t, but may be used with wide character types) is definitely doable.

I now see that it is possible. I agree that it would work here. But I'm not sure whether the bitmap thing is worth doing for narrow string, if the vector algorithm can be used.

The bitmap would check up to 256 characters of the needle at a time, but only one character of the source string at a time. The pcmpestri would check 16 needle characters against 16 source string characters at a time. The later looks better, unless we usually deal with short strings and long needles, which is not what I'd expect.

Even for wide characters, the pcmpestri would check 8 chars of the needle and 8 chars of the source string at a time, and this looks typically better than what the bitmap gives. And the bitmap may fail in this case.

Of course, there's more than just number of comparisons. There are different instructions, with different latencies and throughputs. Overall, the bitmap is expected to use more instructions, but these are the usual fast ones, unlike high latency pcmpestri, so one iteration of the bitmap loop is likely to be faster. All this should be measured. But my expectation is that vectorized find_first_of may be better than a bitmap.