c - 在 64 位机器上分析 Set 实现

Question

我的系统的相关信息:酷睿2双核T6500gcc(GCC)4.4.1 20090725(红帽4.4.1-2)

使用基本的集合实现，其中存储的每个集合实际上只是存储的集合的字典顺序，您可以对集合操作使用标准位操作，例如并集、交集、elementQ 等。

我的问题是关于确定集合的大小。实现如 Cliquer使用

static int set_bit_count[256]

存储任何给定的可能的 8 位字符串中有多少位，然后算法将一次遍历 8 位来确定集合的大小。

这样我有两个问题:

1. 如果寄存器的速度比缓存或 RAM 快 8 倍以上，就会浪费速度。
2. 在 64 位机器中，int 操作并不比 unsigned long long int 慢，我认为这是 64 位 CPU 上的标准操作整数。

但我想只使用一个简单的

while(x)
  x&=x-1;
  ++count;

可能会更快，因为所有内容都可以存储在寄存器中。但不利的一面是，除了明显的 8 倍操作次数之外，还能有其他方法吗？

此外， int、uint、unsigned long、unsigned long long 有很多不同的组合，我不知道从哪里开始测试。

你知道关于这个主题的任何文章吗？

您还知道有关此主题的其他问题吗？

您对此有什么见解吗？

您对如何分析此内容有什么建议吗？我从来没有用过gprof。当我使用 time.h 时，我无法获得比一秒更精细的粒度。

如果您这样做，我将非常感激。

Answer 1

最有可能(虽然我现在懒得测试)，最快的是

int popcount(unsigned x) {
    int count;
#if defined(__GNUC__)
    __asm__("popcnt %1,%0" : "=r" (count) : "r" (x));
#elif defined(_MSC_VER)
    __asm {
        POPCNT x, count
    };
#else
    /* blah, who cares */
    for (count = 0; x; count += x&1, x >>= 1);
#endif
    return count;
}

(尽管如果CPU不支持SSE4.2，这会爆炸。)当然，使用编译器的内置内在函数会更好(并且更便携)，一般来说我会信任编译器选择最适合当前目标平台的实现。

int popcount(unsigned x);
#if defined(__GNUC__)
# define popcount __builtin_popcount
#elif defined(_MSC_VER)
# define popcount __popcnt
#else
/* fallback implementation */
#fi