optimize binary search via L1 dcache prefetching using `__builtin_prefetch`

[christianparpart]

libunicode/src/unicode/ucd_private.h

Lines 30 to 47 in a0f7291

	auto a = size_t{0};
	auto b = static_cast<size_t>(_ranges.size()) - 1;
	while (a < b)
	{
	auto const i = ((b + a) / 2);
	auto const& I = _ranges[i];
	if (I.to < _codepoint)
	a = i + 1;
	else if (I.from > _codepoint)
	{
	if (i == 0)
	return false;
	b = i - 1;
	}
	else
	return true;
	}
	return a == b && _ranges[a].from <= _codepoint && _codepoint <= _ranges[a].to;

See: https://stackoverflow.com/a/31688096/386670

[data-man]

From my collection 😄

https://github.com/scandum/binary_search
https://github.com/ehrmann/branchless-binary-search
https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/extra/binsearch.c
https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/tree/master/extra/search

But I'm guessing that case ranges in switch statement can be faster.
gcc & clang supports it, not sure for MSVC.

[christianparpart]

I currently have a naive O(log2) implementation. I had a look at some of your proposals and it seems they all cover interesting points. I would love to have a solution that improves table lookup performance.

[christianparpart]

Can be closed because the new codepoint_properties API (#46) comes with O(1) lookup. The existing API implementations still using binary-search tables will either be removed (other ticket) or rewritten to use the new API.