为什么 MSVC 在 std::bitset::count 的实现中不使用 __popcnt？

Question

我很好奇 MSVC 是否使用编译器内部函数 __popcnt 来实现

bitset::count

。

环顾四周，我发现这是 VS2017 的

std::bitset::count

的实现：

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

根据这里的答案，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::bitset::count

？我的猜测是要么 MSVC 有一个包罗万象的“STL 中没有编译器内在函数”政策，要么我忽略的两个平台之间存在差异。

Answer 1

GCC 中

__builtin_popcountl

的内部实现并不好，根据架构如下所示。

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

并且仅适用于 SSE4a 指令集，仅在 2006 年开始的 AMD CPU 中受支持，

__builtin_popcountl

由一条汇编指令

POPCNT

组成。

MSDN 说

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

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

我认为 MSVC 团队不想使用带有条件的内在函数，而是选择一种独立于 CPU 和架构的通用解决方案。

Answer 2

从 Visual Studio 2022 版本 17.1 开始，

bitset::count

实现使用

popcnt

指令，具有运行时 CPU 检测和旧版 CPU 的后备功能。

在此之前它确实使用了引用的代码，因为在那之前没有人实现

popcnt

优化。

---

没有“STL 中没有编译器内在函数”政策，但要求 STL 应该在所有受支持的 CPU 上运行，并且最低 CPU 是根据最低操作系统版本的最低要求来选择的。因此，只有在提供旧版 CPU 的回退时，才可以使用内在函数为更高版本的 CPU 注入指令。