手动优化嵌套循环

Question

我正在做一个家庭作业,我必须手动优化嵌套循环(我的程序将在禁用优化的情况下编译).分配的目标是在不到6秒的时间内运行整个程序(额外的功劳少于4.5秒).

我只允许更改一小段代码,起点是这样的:

    for (j=0; j < ARRAY_SIZE; j++) {
        sum += array[j];
    }

哪里ARRAY_SIZE是9973.这个循环被包含在运行20万次到另一个循环中.此特定版本在16秒内运行.

到目前为止我所做的是更改实现以展开循环并使用指针作为我的迭代器:

(这些声明不超过200,000次)

 register int unroll_length = 16;
 register int *unroll_end = array + (ARRAY_SIZE - (ARRAY_SIZE % unroll_length));
 register int *end = array + (ARRAY_SIZE -1);
 register int *curr_end;

curr_end = end;

while (unroll_end != curr_end) {
 sum += *curr_end;
 curr_end--;
}

do {
 sum += *curr_end + *(curr_end-1) + *(curr_end-2) + *(curr_end-3) +
  *(curr_end-4) + *(curr_end-5) + *(curr_end-6) + *(curr_end-7) +
  *(curr_end-8) + *(curr_end-9) + *(curr_end-10) + *(curr_end-11) +
  *(curr_end-12) + *(curr_end-13) + *(curr_end-14) + *(curr_end-15);
}
while ((curr_end -=  unroll_length) != array);

sum += *curr_end;

使用这些技术,我能够将执行时间缩短到5.5秒,这将给予我充分的信任.然而; 我确实想要获得额外的功劳,但我也很好奇我可以忽略的其他优化措施是什么？

编辑#1(添加外循环)

 srand(time(NULL));
 for(j = 0; j < ARRAY_SIZE; j++) {
  x = rand() / (int)(((unsigned)RAND_MAX + 1) / 14);
  array[j] = x;
  checksum += x;
 }

 for (i = 0; i < N_TIMES; i++) {

  // inner loop goes here

  if (sum != checksum)
   printf("Checksum error!\n");

  sum = 0;

 }

Answer 1

你可以尝试将你的变量存储在CPU寄存器中：

register int *unroll_limit = array + (ARRAY_SIZE - (ARRAY_SIZE % 10));
register int *end = array + ARRAY_SIZE;
register int *curr;

并尝试使用不同大小的手动循环来检查何时最大化缓存使用率。