13

标stdint.h头缺少int_fastest_t与类型uint_fastest_t相对应的和{,u}int_fastX_t。对于整数类型的宽度无关紧要的情况，如何选择允许处理最多位且对性能的影响最小的整数类型？例如，如果使用一种简单的方法在缓冲区中搜索第一个设置位，则可能会考虑这样的循环：

// return the bit offset of the first 1 bit
size_t find_first_bit_set(void const *const buf)
{
    uint_fastest_t const *p = buf; // use the fastest type for comparison to zero
    for (; *p == 0; ++p); // inc p while no bits are set
    // return offset of first bit set
    return (p - buf) * sizeof(*p) * CHAR_BIT + ffsX(*p) - 1;
}

自然， usingchar会导致比 . 更多的操作int。但可能会导致比在32 位系统上long long使用的开销等更昂贵的操作。int

我目前的假设是针对主流架构，使用long是最安全的选择：在 32 位系统上是 32 位，在 64 位系统上是 64 位。

4

9 回答 9

11

int_fast8_t始终是正确实现中最快的整数类型。永远不可能有小于 8 位的整数类型（因为CHAR_BIT>=8是必需的），并且由于int_fast8_t它是最快的整数类型，至少有 8 位，因此它是最快的整数类型，周期。

于 2010-09-12T14:45:10.733 回答
3

我不确定我是否真的理解这个问题，但你为什么不只使用int？引用我的（错误的免费草稿副本，即 C++）标准，“普通整数具有执行环境架构所建议的自然大小。”

但我认为，如果你想对某个操作有最佳的整数类型，它会根据它是哪个操作而有所不同。试图在大数据缓冲区中找到第一位，或者在整数序列中找到一个数字，或者移动它们，很可能会有完全不同的最优类型。

编辑：

不管它值多少钱，我做了一个小基准测试。在我的特定系统（带有 Linux 的 Intel i7 920，gcc -O3）上，在这个特定的示例中，长整数（64 位）比普通整数（32 位）快很多。我会猜到相反的。

于 2010-09-12T08:25:49.900 回答
3

理论上，int是最好的选择。它应该映射到 CPU 的本机寄存器大小，因此在您所询问的意义上是“最佳的”。

但是，您可能仍然会发现 int-64 或 int-128 在某些 CPU 上比 int-32 更快，因为尽管它们大于寄存器大小，但它们会减少循环的迭代次数，因此可能通过最小化循环开销和/或利用 DMA 更快地加载/存储数据来提高效率。

（例如，在 ARM-2 处理器上，加载一个 32 位寄存器需要 4 个内存周期，但仅需要 5 个周期来顺序加载两个，而需要 7 个周期来顺序加载 4 个。您上面建议的例程将被优化为可以释放许多寄存器（通常是 8 到 10 个），因此每次循环迭代使用多个寄存器可以使运行速度提高 3 或 4 倍）

唯一可以确定的方法是编写几个例程，然后在特定的目标机器上对它们进行分析，以找出哪个产生最佳性能。

于 2010-09-12T08:27:49.303 回答
2

如果你想确定你有最快的实现，为什么不在你期望运行的系统上对每一个进行基准测试而不是试图猜测呢？

于 2010-09-12T08:03:36.847 回答
1

答案是int它自己。至少在 C++ 中，标准的 3.9.1/2 说：

Plainint具有执行环境架构所建议的自然大小

我希望 C 语言也是如此，尽管我没有任何标准文档。

于 2010-09-12T08:26:34.880 回答
1

我猜想类型size_t（对于无符号类型）和ptrdiff_t（对于有符号类型）通常对应于任何给定平台上非常有效的整数类型。

但没有什么比检查生产的汇编器并做基准测试更能证明这一点了。

在此处和其他回复中编辑，包括不同的评论：

size_t并且ptrdiff_t是唯一在 C99 中规范的 typedef，并且可以合理地假设它们与体系结构相关。

标准整数类型有 5 种不同的可能等级（char、short、int、long、long long）。所有的力量都朝着宽度为 8、16、32、64 以及在不久的将来为 128 的类型发展。因此int 将卡在 32 位上。它的定义与平台上的效率无关，而只是受到宽度要求的限制。

于 2010-09-12T08:15:17.460 回答
0

For all existing mainstream architectures long is the fastest type at present for loop throughput.

于 2010-09-14T02:45:49.177 回答
0

由于问题不完整，无法回答此问题。作为一个类比，考虑以下问题：

什么车最快

布加迪威龙？当然很快，但不适合从伦敦到纽约。

问题中缺少的是整数将在其中使用的上下文。在上面的原始示例中，如果数组又大又稀疏，我怀疑你会看到 8、32 或 64 位值之间的很大差异，因为你会在 CPU 限制之前达到内存带宽限制。

要点是，体系结构没有定义各种整数类型的大小，而是编译器设计者做到了这一点。设计师将仔细权衡给定架构的每种类型的各种尺寸的优缺点，并选择最合适的。

我猜选择 64 位系统上的 32 位 int 是因为对于大多数操作而言，int 用于 32 位就足够了。由于内存带宽是一个限制因素，因此节省内存使用可能是最重要的因素。

于 2010-09-13T09:41:36.000 回答
0

如果您使用 gcc 进行编译，我建议使用__builtin_ffs()来查找第一个位集：

内置函数： int __builtin_ffs (unsigned int x) 返回 x 的最低有效 1 位的索引加一，或者如果 x 为零，则返回零。

这将被编译成（通常是单个）本机汇编指令。

于 2010-09-12T20:18:22.557 回答