1

我很想知道 MSVC 是否使用编译器内在 __popcnt 来处理bitset::count.

环顾四周，我发现这是std::bitset::countVS2017 的实现：

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 的数量。

根据这个答案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 的实现在这里会快很多。

因此，有什么令人信服的理由让 MSVCstd::bitset::count像这样实施吗？我的猜测是 MSVC 有一个包罗万象的“STL 中没有编译器内在函数”策略，或者我忽略的两个平台之间存在差异。

4

2 回答 2

1

在 GCC 中的内部实现__builtin_popcountl并不是更好，它取决于架构如下所示。

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

并且仅对于从 2006 年开始仅在 AMD CPU 中支持的 SSE4a 指令集，__builtin_popcountl由一条汇编指令组成POPCNT。

MSDN 说

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

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

我假设 MSVC 团队不想使用带有条件的内在函数来支持一种独立于 CPU 和架构的通用解决方案。

于 2018-01-23T06:30:48.050 回答
0

没有“STL 中没有编译器内在函数”策略，但要求 STL 应在所有受支持的 CPU 上运行，并且最低 CPU 由最低操作系统版本的最低要求选择。因此，只有在为较旧的 CPU 提供回退的情况下，才可以使用为较晚的 CPU 注入指令的内部函数。

目前 VS 2019 中的 C++20std::popcount使用运行时 CPU 检测，它回退到位计数。

std::bitset::count也可以开始使用相同的方法。STL GitHub 中存在一个等待维护者或贡献者实施的问题。

于 2020-12-10T14:10:09.343 回答