c++ - 使用带模数的不同值时的速度差异

Question

我正在使用 gcc 4.6.3 并创建大量随机短裤。我使用以下语句生成它们：

val = SHRT_MAX; //as defined by limits.h
while(array<end) {
    *array++ = rand() % val;
}

这是一个相当快的操作，即使对于多达 5,000,000 个元素的数组也几乎可以立即完成。我对数字变化较小的排序效率感到好奇，并将其更改为：

val = 3;

这导致了相当大的速度差异，它的运行速度比原始语句慢得多。是什么导致了如此大的速度差异？

score 3 · Accepted Answer

SHRT_MAX很可能大于或等于RAND_MAX。该声明：

*array++ = rand() % val;

可以优化为：

int rand_value= rand();
if (rand_value==RAND_MAX) rand_value= 0;
*array++= rand_value;

这更快，因为它用分支替换了模数。第二个版本，其中val3，不能优化为一个没有模数的更简单的版本。

% SHRT_MAX不能简化为按位运算。但是结合如何rand()指定的知识，编译器当然可以优化处理rand()大于或等于的值的语句RAND_MAX。

score 2 · Accepted Answer

编译器可以优化模数 (a%B) 的计算，其中 B 是一个常数。它用更简单的算术运算代替了实际的模数。详细信息在诸如“在 C 中计算模数的最优化方法”之类的主题中进行了解释。然而，对于某些 B 值，这种优化比其他值更快。

甚至 CPU 除法/模指令也可以完成不同数量的周期（至少在某些 CPU 上）。在此处查看 x86 的数字：http: //gmplib.org/~tege/x86-timing.pdf。

score 0 · Accepted Answer

SHRT_MAX 是一个2^n-1值，可以针对除法进行优化。除以 3 要困难得多，因此编译器很可能会决定除以 3（或者执行一些其他比2^n-1变体慢的魔术操作。

您可以使用的最快模数是 for 2^n，可以用单个 and-instruction 替换，对于正值：x % 256与相同x & 255。不幸的是，当值可能是负数时，这并不那么容易......

3 回答 3