使C代码运行得更快

Question

我写了一段代码,用于计算0到255之间的数字频率.

unsigned char arr[4096]; //aligned 64 bytes, filled with random characters

short counter[256]; //aligned 32 bytes

register int i;

for(i = 0; i < 4096; i++)
    ++counter[arr[i]];

执行需要花费大量时间; 随机访问计数器阵列非常昂贵.

有没有人有任何想法,我可以使用顺序访问或我可以使用的任何其他方法？

Answer 1

是什么让你认为对计数器阵列的随机访问是昂贵的？你介绍过吗？试试Valgrind,它有一个名为"cachegrind"的缓存分析工具.分析还可以让您知道代码是否实际上很慢,或者您认为它是否因为它应该是慢的.

这是一段非常简单的代码,在优化之前,了解它是否是内存绑定或者是否与内存绑定(数据,而不是直方图表)非常重要.我不能回答这个问题.尝试比较一个简单的算法,它只是对整个输入进行求和:如果两者都以大约相同的速度运行,那么你的算法是内存限制的,你就完成了.

我最好的猜测是,可能减慢你速度的主要问题是:

   Registers                      RAM
1.  <-- read data[i] ---------------
2.  <-- read histogram[data[i]] ----
3. increment
4.  --- write histogram[data[i]] -->
5.  <-- read data[i] ---------------
6.  <-- read histogram[data[i]] ----

编译器和处理器不允许对此处的大多数指令进行重新排序(#1和#5除外,这可以提前完成),因此您基本上会受到较小者的限制:L1缓存的带宽(这是直方图的位置和主RAM的带宽,每个乘以一些未知的常数因子.(注意:如果编译器展开循环,编译器只能移动#1/5,但处理器可能无论如何都可以移动它.)

这就是为什么你在尝试变得聪明之前进行分析的原因 - 因为如果你的L1缓存有足够的带宽,那么你将总是渴望数据,你无能为力.

脚注:

这段代码:

register int i;
for(i = 0; i < 4096; i++)
    ++counter[arr[i]];

生成与此代码相同的程序集:

int i;
for(i = 0; i < 4096; i++)
    counter[arr[i]]++;

但是这段代码更容易阅读.