<bit>: consider leaving only static CPU dispatch for lzcnt/bsr and tzcnt/bsr

[AlexGuteniev]

Inspired by #2097 .

Try this code:

STL/stl/inc/format

Lines 2496 to 2504 in 737ce4a

	// Since the bit width of 0 is 0x0, special-case it instead of complicating the math even more.
	int _Width = 3;
	if (_Value != nullptr) {
	// Compute the bit width of the pointer (i.e. how many bits it takes to be represented).
	// Add 3 to the bit width so we always round up on the division.
	// Divide that by the amount of bits a hexit represents (log2(16) = log2(2^4) = 4).
	// Add 2 for the 0x prefix.
	_Width = static_cast<int>(2 + (_STD bit_width(reinterpret_cast<uintptr_t>(_Value)) + 3) / 4);
	}

On Godbolt's compiler explorer: https://godbolt.org/z/z99vjeEhh

[AlexGuteniev]

Actually not much better. MSVC optimizer is far from perfect for this case

[StephanTLavavej]

@barcharcraz notes that these functions are typically called in perf-critical loops, so micro-optimizations can be important.

Additionally, I note that as long as we don't regress MSVC codegen quality, changes could be worthwhile if they improve Clang/LLVM codegen quality.

[AlexGuteniev]

Tried to benchmark what is better and got controversial results.

[AlexGuteniev]

The bsr countl_zero:

STL/stl/inc/bit

Lines 149 to 176 in 3c2fd04

	template <class _Ty>
	_NODISCARD int _Countl_zero_bsr(const _Ty _Val) noexcept {
	constexpr int _Digits = numeric_limits<_Ty>::digits;
	unsigned long _Result;
	if constexpr (_Digits <= 32) {
	if (!_BitScanReverse(&_Result, _Val)) {
	return _Digits;
	}
	} else {
	#ifdef _M_IX86
	const unsigned int _High = _Val >> 32;
	if (_BitScanReverse(&_Result, _High)) {
	return static_cast<int>(31 - _Result);
	}
	const auto _Low = static_cast<unsigned int>(_Val);
	if (!_BitScanReverse(&_Result, _Low)) {
	return _Digits;
	}
	#else // ^^^ _M_IX86 / !_M_IX86 vvv
	if (!_BitScanReverse64(&_Result, _Val)) {
	return _Digits;
	}
	#endif // _M_IX86
	}
	return static_cast<int>(_Digits - 1 - _Result);
	}

Is branchy, and avoiding it seem to be a worth thing.

The bsf countr_zero

STL/stl/inc/limits

Lines 1092 to 1124 in 3c2fd04

	_NODISCARD int _Countr_zero_bsf(const _Ty _Val) noexcept {
	constexpr int _Digits = numeric_limits<_Ty>::digits;
	constexpr _Ty _Max = (numeric_limits<_Ty>::max) ();
	unsigned long _Result;
	if constexpr (_Digits <= 32) {
	// Intended widening to int. This operation means that a narrow 0 will widen
	// to 0xFFFF....FFFF0... instead of 0. We need this to avoid counting all the zeros
	// of the wider type.
	if (!_BitScanForward(&_Result, static_cast<unsigned int>(~_Max | _Val))) {
	return _Digits;
	}
	} else {
	#ifdef _M_IX86
	const auto _Low = static_cast<unsigned int>(_Val);
	if (_BitScanForward(&_Result, _Low)) {
	return static_cast<int>(_Result);
	}
	const unsigned int _High = _Val >> 32;
	if (!_BitScanForward(&_Result, _High)) {
	return _Digits;
	} else {
	return static_cast<int>(_Result + 32);
	}
	#else // ^^^ _M_IX86 / !_M_IX86 vvv
	if (!_BitScanForward64(&_Result, _Val)) {
	return _Digits;
	}
	#endif // _M_IX86
	}
	return static_cast<int>(_Result);
	}

Is branchless (cmov is used), and avoiding it seem to be not really useful.

[StephanTLavavej]

We'd like to see the specific perf data before making a decision here.

[AlexGuteniev]

So here's a program:

#include <bit>
#include <chrono>
#include <iostream>
#include <random>

constexpr int N = 1000;
constexpr int R = 2000000;
unsigned    int_in[N];
int         int_out;

int main() {
    std::mt19937 gen(53342);
    std::uniform_int_distribution<unsigned> int_dis(0, 1000);
    for (unsigned& element : int_in) {
        element = int_dis(gen);
    }

    auto t1 = std::chrono::steady_clock::now();
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < N; j++) {
            int_out += std::countl_zero(int_in[j]);
        }
    }
    auto t2 = std::chrono::steady_clock::now();
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < N; j++) {
            int_out += std::countr_zero(int_in[j]);
        }
    }
    auto t3 = std::chrono::steady_clock::now();

    auto countl = std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1);
    auto countr = std::chrono::duration_cast<std::chrono::duration<double>>(t3 - t2);

    std::cout << "countl: " << countl.count() << "\n"
        << "countr: " << countr.count() << "\n";
}

With /arch:AVX2 the results are steady:

countl: 0.772265
countr: 0.747112

Currently without /arch:AVX2 the results depend on data, as follows:

uniform int 0...1000:

countl: 2.04804
countr: 1.5294

uniform int 1...1000:

countl: 1.03282
countr: 1.83459

If I remove runtime dispatch, results depend on data as follows:

uniform int 0...1000

countl: 1.6128
countr: 2.04258

uniform int 1...1000:

countl: 2.67733
countr: 2.05943

@StephanTLavavej , I admit I have no clue what is happening here. Overall, the data suggests we should not change anything, still there's interesting case for 0...1000 and countl

It somehow overlaps with #2334 , as countl is branchy and countr is branchless.
It might suggest that we may want to force the compiler to generate branchless code (which looks possible).

I'm surprised that unexecuted branch affects the benchmark.

[AlexGuteniev]

@StephanTLavavej , I figured it out!

So overall the advantage of lzcnt/tzcnt worth a branch with fallback, so the implementation is optimal as it is!

All animalities I see are explained by Intel JCC Errata. Compiling with /QIntel-jcc-erratum fixes the performance for these cases.

I've created DevCom-1603517 to make /QIntel-jcc-erratum default unless tuning for AMD.

Otherwise the data suggests that we should do dynamic dispatch, the occurrences where static-only dispatch wins are purely random. I'm closing this.

[CaseyCarter]

Great work, @AlexGuteniev - thanks for digging into this.