将性能从 size_t 提高一倍

Question

TL;DR:为什么在 size_t 中乘法/转换数据慢，为什么这会因平台而异？

我遇到了一些我不完全理解的性能问题。上下文是一个相机图像采集卡，其中以数百赫兹的速率读取和后处理 128x128 uint16_t 图像。

在后期处理中，我生成了一个直方图 frame->histo这是 uint32_t并且有 thismaxval = 2^16 个元素，基本上我计算所有强度值。使用此直方图，我计算总和和平方和:

double sum=0, sumsquared=0;
size_t thismaxval = 1 << 16;

for(size_t i = 0; i < thismaxval; i++) {
    sum += (double)i * frame->histo[i];
    sumsquared += (double)(i * i) * frame->histo[i];
}

使用配置文件对代码进行分析，我得到以下信息(示例、百分比、代码):

 58228 32.1263 :  sum += (double)i * frame->histo[i];
116760 64.4204 :  sumsquared += (double)(i * i) * frame->histo[i];

或者，第一行占用 32% 的 CPU 时间，第二行 64%。

我做了一些基准测试，似乎是数据类型/转换有问题。当我将代码更改为

uint_fast64_t isum=0, isumsquared=0;

for(uint_fast32_t i = 0; i < thismaxval; i++) {
    isum += i * frame->histo[i];
    isumsquared += (i * i) * frame->histo[i];
}

它的运行速度快了约 10 倍。但是，这种性能影响也因平台而异。在工作站上，Core i7 CPU 950 @ 3.07GHz 代码快 10 倍。在配备 Intel Core i7 Sandy Bridge 2.7 GHz (2620M) 的 Macbook8,1 上，代码仅快 2 倍。

现在我想知道:

1. 为什么原始代码如此缓慢并且很容易加速？
2. 为什么每个平台的差异如此之大？

更新:

我编译了上面的代码

g++ -O3  -Wall cast_test.cc -o cast_test

更新2:

我通过分析器运行优化代码(在 Mac 上为 Instruments，如 Shark)并发现两件事:

1) 在某些情况下，循环本身会花费大量时间。 thismaxval类型为 size_t .

1. for(size_t i = 0; i < thismaxval; i++)占我总运行时间的 17%
2. for(uint_fast32_t i = 0; i < thismaxval; i++)占 3.5%
3. for(int i = 0; i < thismaxval; i++)没有出现在分析器中，我认为它小于 0.1%

2) 数据类型和类型转换如下:

1. sumsquared += (double)(i * i) * histo[i]; 15%(与 size_t i )
2. sumsquared += (double)(i * i) * histo[i]; 36%(用 uint_fast32_t i )
3. isumsquared += (i * i) * histo[i]; 13%(有 uint_fast32_t i , uint_fast64_t isumsquared )
4. isumsquared += (i * i) * histo[i]; 11%(有 int i , uint_fast64_t isumsquared )

令人惊讶的是，int比 uint_fast32_t 快？

更新4:

我在一台机器上用不同的数据类型和不同的编译器运行了更多测试。结果如下。

对于testd 0 -- 2相关的代码是

    for(loop_t i = 0; i < thismaxval; i++)
        sumsquared += (double)(i * i) * histo[i];

与 sumsquared双，和loop_t size_t , uint_fast32_t和 int对于测试 0、1 和 2。

测试3--5的代码是

    for(loop_t i = 0; i < thismaxval; i++)
        isumsquared += (i * i) * histo[i];

与 isumsquared类型 uint_fast64_t和 loop_t再次size_t , uint_fast32_t和 int对于测试 3、4 和 5。

我使用的编译器是 gcc 4.2.1、gcc 4.4.7、gcc 4.6.3 和 gcc 4.7.0。计时以代码的总 CPU 时间的百分比表示，因此它们显示的是相对性能，而不是绝对性能(尽管运行时间在 21 秒时非常稳定)。 cpu 时间是两行的，因为我不太确定探查器是否正确分隔了两行代码。

gcc:    4.2.1  4.4.7  4.6.3  4.7.0----------------------------------test 0: 21.85  25.15  22.05  21.85test 1: 21.9   25.05  22     22test 2: 26.35  25.1   21.95  19.2test 3: 7.15   8.35   18.55  19.95test 4: 11.1   8.45   7.35   7.1test 5: 7.1    7.8    6.9    7.05

或:

基于此，无论我使用什么整数类型，转换似乎都很昂贵。

此外，gcc 4.6 和 4.7 似乎无法正确优化循环 3(size_t 和 uint_fast64_t)。

Answer 1

对于您的原始问题:

1. 代码很慢，因为它涉及从整数到 float 数据类型。这就是为什么当你也使用它时它很容易加速的原因总和变量的整数数据类型，因为它不需要不再是 float 转换。
2. 差异是几个结果因素。例如，这取决于平台的效率执行 int->float 转换。此外这种转换也可能会扰乱程序中的处理器内部优化流和预测引擎，缓存，......以及内部处理器的并行化特性会对这样的计算。

对于附加问题:

• “令人惊讶的是 int 比 uint_fast32_t 快”？什么是您平台上的 sizeof(size_t) 和 sizeof(int)？我可以做出的一种猜测是，两者都是可能是 64 位，因此转换为 32 位不仅可以给你计算错误，但也包括不同尺寸的铸件罚款。

一般来说，如果不是真的需要，尽量避免可见和隐藏的强制转换。例如，尝试找出在您的环境 (gcc) 中隐藏在“size_t”后面的真实数据类型，并将该数据类型用于循环变量。在你的例子中，uint 的平方不能是 float 数据类型，所以在这里使用 double 是没有意义的。坚持使用整数类型以获得最佳性能。