Skip to content

<bit>: countr_zero() doesn't need to special-case 0 for uint8_t and uint16_t #1534

Description

std::countr_zero and std::countr_one in <bit> are powered by the following machinery:

STL/stl/inc/bit

Lines 249 to 257 in 335449f

template <class _Ty, enable_if_t<_Is_standard_unsigned_integer<_Ty>, int> = 0>
_NODISCARD constexpr int countr_zero(const _Ty _Val) noexcept {
return _Countr_zero(_Val);
}
template <class _Ty, enable_if_t<_Is_standard_unsigned_integer<_Ty>, int> _Enabled = 0>
_NODISCARD constexpr int countr_one(const _Ty _Val) noexcept {
return _Countr_zero(static_cast<_Ty>(~_Val));
}

We want to use the tzcnt instruction, but if the processor doesn't support it, it'll be treated as bsf which doesn't handle 0 the way we want, so we need to special-case it. We have logic to avoid the special-casing when we detect that tzcnt is available at compile-time or run-time:

STL/stl/inc/limits

Lines 1055 to 1065 in 335449f

template <class _Ty>
_NODISCARD int _Checked_x86_x64_countr_zero(const _Ty _Val) noexcept {
constexpr int _Digits = numeric_limits<_Ty>::digits;
constexpr _Ty _Max = (numeric_limits<_Ty>::max)();
#ifndef __AVX2__
const bool _Definitely_have_tzcnt = __isa_available >= __ISA_AVAILABLE_AVX2;
if (!_Definitely_have_tzcnt && _Val == 0) {
return _Digits;
}
#endif // __AVX2__

Charles Milette (@sylveon) noticed that we can optimize this further. This is immediately followed by:

STL/stl/inc/limits

Lines 1067 to 1072 in 335449f

if _CONSTEXPR_IF (_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.
return static_cast<int>(_TZCNT_U32(static_cast<unsigned int>(~_Max | _Val)));
} else {

For uint8_t and uint16_t, this 1-bit-filled widening means that we'll never actually pass 0 to the instruction, so the ISA check is entirely unnecessary! We can reorganize this code accordingly.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    fixedSomething works now, yay!performanceMust go faster

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions