代码之家 › 专栏 › 技术社区 › Mike

为什么MSVC在实现std::bitset::count时不使用\uu popcnt?

std-bitset stl visual-c++ gcc c++

Mike · 技术社区 · 8 年前

我很想知道MSVC是否使用编译器内部\uu popcnt bitset::count .

环顾四周,我发现这是 std::bitset::count 对于VS2017:

size_t count() const _NOEXCEPT
        {   // count number of set bits
        const char *const _Bitsperbyte =
            "\0\1\1\2\1\2\2\3\1\2\2\3\2\3\3\4"
            "\1\2\2\3\2\3\3\4\2\3\3\4\3\4\4\5"
            "\1\2\2\3\2\3\3\4\2\3\3\4\3\4\4\5"
            "\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
            "\1\2\2\3\2\3\3\4\2\3\3\4\3\4\4\5"
            "\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
            "\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
            "\3\4\4\5\4\5\5\6\4\5\5\6\5\6\6\7"
            "\1\2\2\3\2\3\3\4\2\3\3\4\3\4\4\5"
            "\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
            "\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
            "\3\4\4\5\4\5\5\6\4\5\5\6\5\6\6\7"
            "\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
            "\3\4\4\5\4\5\5\6\4\5\5\6\5\6\6\7"
            "\3\4\4\5\4\5\5\6\4\5\5\6\5\6\6\7"
            "\4\5\5\6\5\6\6\7\5\6\6\7\6\7\7\x8";
        const unsigned char *_Ptr = &reinterpret_cast<const unsigned char&>(_Array);
        const unsigned char *const _End = _Ptr + sizeof (_Array);
        size_t _Val = 0;
        for ( ; _Ptr != _End; ++_Ptr)
            _Val += _Bitsperbyte[*_Ptr];
        return (_Val);
        }

它看起来像是使用查找表来获取任何给定字节的位数,然后计算每个字节的1数。

According to this answer here ,GCC是这样实现的(按照我的想法):

/// Returns the number of bits which are set.
size_t
count() const { return this->_M_do_count(); }      

size_t
_M_do_count() const
{
  size_t __result = 0;
  for (size_t __i = 0; __i < _Nw; __i++)
  __result += __builtin_popcountl(_M_w[__i]);
  return __result;
}

虽然我没有对任何东西进行基准测试,但我敢打赌GCC的实现速度会更快。

因此,MSVC的实施有什么令人信服的原因吗 std::位集::计数 这样地?我的猜测是,要么MSVC有一个全面的“STL中没有编译器内部函数”策略,要么我忽略了这两个平台之间的差异。

2 回复 | 直到 8 年前

Community Mohan Dere 5 年前

内部实施 __builtin_popcountl 在GCC中并不是更好,根据体系结构,它类似于下面的内容。

i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;

并且仅适用于SSE4a指令集,自2006年起仅在AMD CPU中受支持, __内置popcountl 由一条汇编指令组成 POPCNT .

MSDN表示

每个内部函数都生成popcnt指令。popcnt指令返回的值的大小与其参数的大小相同。在32位模式下,没有64位通用寄存器,因此没有64位popcnt。

要确定popcnt指令的硬件支持,请调用InfoType=0x00000001的\uu cpuid内部函数,并检查CPUInfo[2](ECX)的第23位。如果支持该指令,则该位为1,否则为0。如果在不支持popcnt指令的硬件上运行使用此内在函数的代码,则结果是不可预测的。

我假设MSVC团队不想使用内在的with条件来支持一个独立于CPU和体系结构的公共解决方案。

Alex Guteniev 5 年前

没有 “STL中无编译器内部函数”策略 ,但有一个要求,即STL应该在所有受支持的CPU上运行,而最小CPU是根据最低OS版本的最低要求来选择的。因此,只有在为较旧的CPU提供回退时,才可以使用为以后的CPU注入指令的intrincics。

当前为C++20 std::popcount 在VS 2019中,使用运行时CPU检测,返回到位计数。

std::bitset::count 也可以开始使用相同的方法。有一个 issue 在STL GitHub中,等待维护人员或贡献者实现。