让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]];

执行需要很长时间；对计数器数组的随机访问非常昂贵。

有没有人有任何想法，可以让访问变得顺序或者使用其他方法？

- randy7

---

FYI：现代编译器几乎忽略 register 关键字，而 counter[arr[i]]++ 更易读（其结果代码相同）。 - Dietrich Epp

@randy7 - 我修改了你的 for 循环，但是你又撤销了它。这有意义吗？ - Jared Farrish

无论如何，它最终仍将被记录在寄存器中。请检查汇编代码。 - Dietrich Epp

@Klee1：因为counter只有512字节，所以它具有空间局部性，可以轻松地适应L1缓存。 - Dietrich Epp

执行时间很长吗？这段代码几乎在零时间内运行。你是如何衡量“很长时间”的？ - Zan Lynx

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]]++;

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

- Dietrich Epp

---

有趣的问题是编译器是否能够确保没有别名问题（对于发布的代码来说应该很简单），在这种情况下，他可以几乎完全并行处理代码。因此，我会检查一下gcc是否合理地向量化了代码（有一些选项可以显示哪些循环被向量化）-如果没有，那可能会导致性能损失。 - Voo

@Voo：我怀疑这段代码无法手动向量化，更不用说自动向量化了，如果标量代码受到内存限制，那么这并不重要。 - Dietrich Epp

Answer 2

更加惯用的：

// make sure you actually fill this with random chars
// if this is declared in a function, it _might_ have stack garbage
// if it's declared globally, it will be zeroed (which makes for a boring result)
unsigned char arr[4096]; 
// since you're counting bytes in an array, the array can't have more
// bytes than the current system memory width, so then size_t will never overflow
// for this usage
size_t counter[256];

for(size_t i = 0; i < sizeof(arr)/sizeof(*arr); ++i)
    ++counter[arr[i]];

现在关键是使用C99编译，并加入一些严格的优化标志：

cc mycode.c -O3 -std=c99

对于像这样的简单循环，任何优化都会使其变得非常快。不要再浪费时间去让这么简单的东西变得更快。

- Matt Joiner

---

short 可能比 size_t 更适合缓存。更好的选择是 int_least16_t。 - Ben Voigt

在这个例子中，这不太可能有太大的影响。在大多数系统上，它将是1-2K。 - Matt Joiner

Answer 3

这段代码处理大小为4k的数据...它将每3个连续字节相加，并将结果存储在一个大小为4k的临时缓冲区中。该临时缓冲区用于生成直方图。

使用SIMD指令可以对3个连续字节进行向量化处理。

根据Dietrich的建议，如果不生成直方图，而是简单地将临时缓冲区中的值相加，执行速度非常快。但生成直方图是需要时间的部分。我使用cache grind对代码进行了分析...输出如下：

==11845== 
==11845== I   refs:      212,171
==11845== I1  misses:        842
==11845== LLi misses:        827
==11845== I1  miss rate:    0.39%
==11845== LLi miss rate:    0.38%
==11845== 
==11845== D   refs:       69,179  (56,158 rd   + 13,021 wr)
==11845== D1  misses:      2,905  ( 2,289 rd   +    616 wr)
==11845== LLd misses:      2,470  ( 1,895 rd   +    575 wr)
==11845== D1  miss rate:     4.1% (   4.0%     +    4.7%  )
==11845== LLd miss rate:     3.5% (   3.3%     +    4.4%  )
==11845== 
==11845== LL refs:         3,747  ( 3,131 rd   +    616 wr)
==11845== LL misses:       3,297  ( 2,722 rd   +    575 wr)
==11845== LL miss rate:      1.1% (   1.0%     +    4.4%  )

完整的输出结果为：

I1 cache:         65536 B, 64 B, 2-way associative
D1 cache:         65536 B, 64 B, 2-way associative
LL cache:         1048576 B, 64 B, 16-way associative
Command:          ./a.out
Data file:        cachegrind.out.11845
Events recorded:  Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Events shown:     Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Thresholds:       0.1 100 100 100 100 100 100 100 100
Include dirs:     
User annotated:   
Auto-annotation:  off

--------------------------------------------------------------------------------
     Ir I1mr ILmr     Dr  D1mr  DLmr     Dw D1mw DLmw 
--------------------------------------------------------------------------------
212,171  842  827 56,158 2,289 1,895 13,021  616  575  PROGRAM TOTALS

--------------------------------------------------------------------------------
    Ir I1mr ILmr     Dr  D1mr  DLmr     Dw D1mw DLmw  file:function
--------------------------------------------------------------------------------
97,335  651  642 26,648 1,295 1,030 10,883  517  479  ???:???
59,413   13   13 13,348   886   829     17    1    0  ???:_dl_addr
40,023    7    7 12,405    10     8    223   18   17  ???:core_get_signature
 5,123    2    2  1,277    64    19    256   64   64  ???:core_get_signature_parallel
 3,039   46   44    862     9     4    665    8    8  ???:vfprintf
 2,344   11   11    407     0     0    254    1    1  ???:_IO_file_xsputn
   887    7    7    234     0     0    134    1    0  ???:_IO_file_overflow
   720    9    7    250     5     2    150    0    0  ???:__printf_chk
   538    4    4    104     0     0    102    2    2  ???:__libc_memalign
   507    6    6    145     0     0    114    0    0  ???:_IO_do_write
   478    2    2     42     1     1      0    0    0  ???:strchrnul
   350    3    3     80     0     0     50    0    0  ???:_IO_file_write
   297    4    4     98     0     0     23    0    0  ???:_IO_default_xsputn

- randy7

---

计数器随后用于排序并获取前8个最常出现的值。有趣的观察是：如果我禁用排序功能，则直方图的生成非常快（0-1微秒-使用gettimeofday函数），但如果启用排序，则生成直方图的时间跳到22微秒。我相信CPU正在将缓存中的数据写回内存，这就是需要时间的原因。 - randy7

Answer 4

嗯，Richard 当然是对的。这是因为编译器必须将数组转换为指针，但这需要一些时间，从而增加了执行时间。例如，尝试这样做：

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

- aresh

---

C语言不指定任何执行时间。 - jørgensen

Answer 5

首先，我完全同意Dietrich的观点，请先证明（你自己和我们）真正的瓶颈在哪里。

我唯一能看到的可能改进是在你的short中。表的大小在这里不会成为问题，我想，但晋升和溢出会。使用默认处理此类情况的类型，即unsigned。

无论如何，计数器应始终为unsigned（甚至更好的是size_t），这是基数的语义。作为额外的优势，无符号类型不会溢出，而是以受控方式包裹。编译器不必为此使用额外的指令。

然后，在C中进行算术运算的宽度至少为int的宽度。然后必须将其强制转换回短。

- Jens Gustedt

Answer 6

考虑使用指向arr的指针，而不是索引。

unsigned char p = &arr;
for (i = 4096-1; 0 <= i; --i)
  ++counter[*p++];

- Richard Schneider

---

更糟糕的是，char* 可以与任何东西别名，因此您可能会使编译器难以证明 *p 不会与其他数据别名，甚至是其他类型的数据。而且还有一个拼写错误，您将 p 声明为 char 而不是 char *。所有这些因素加起来导致了我否决了本来不需要费心的投票。 - Peter Cordes