0

这是我第一次在这个网站上发帖，希望能得到一些帮助/提示。我有一个任务，我需要优化内部 for 循环的性能，但我不知道该怎么做。代码在作业中给出。我需要计算时间（我能够做到）并提高性能。

这是代码：

//header files

#define N_TIMES     200   //This is originally 200000 but changed it to test the          program faster    
#define ARRAY_SIZE    9973

int main (void) {
  int  *array = (int*)calloc(ARRAY_SIZE, sizeof(int));
  int  sum = 0;
  int  checksum = 0;
  int  i;
  int  j;
  int  x; 

  // Initialize the array with random values 0 to 13. 
  srand(time(NULL));
  for (j=0; j < ARRAY_SIZE; j++) {    
    x = rand() / (int)(((unsigned)RAND_MAX + 1) / 14);
    array[j] = x;
    checksum += x;
  }
  //printf("Checksum is %d.\n",checksum);

  for (i = 0; i < N_TIMES; i++) {
    // Do not alter anything above this line.
    // Need to optimize this for loop----------------------------------------
    for (j=0; j < ARRAY_SIZE; j++) {
      sum += array[j];
      printf("Sum is now: %d\n",sum);
    }


    // Do not alter anything below this line.
    // ---------------------------------------------------------------

    // Check each iteration.  
    //
    if (sum != checksum) {
      printf("Checksum error!\n");
    }
    sum = 0;

  } 
  return 0;
}

代码运行大约需要 695 秒。请问如何优化它的任何帮助？多谢。

4

4 回答 4

3

该循环中的瓶颈显然是由printf;完成的 IO。由于您可能正在控制台上编写输出，因此输出是行缓冲的，这意味着每次迭代都会刷新 stdio 缓冲区，这会大大减慢速度。

如果你必须做所有的打印，你可以通过强制流做块缓冲来大大提高性能：在for添加之前

setvbuf(stdout, NULL, _IOFBF, 0);

或者，如果这种方法被认为无效，您可以通过自己分配一个大缓冲区并进行自己的缓冲来进行自己的缓冲：使用 写入缓冲区sprintf，并使用 定期在输出流中清空它fwrite。

此外，您可以使用穷人的缓冲方法 - 只需使用足够大的缓冲区来写入所有内容（您可以很容易地计算出它必须有多大）并在其中写入而不用担心它何时已满，何时清空它, ... - 在循环结束时将其清空。编辑：请参阅@paxdiablo 的答案以获取此示例

仅应用第一个优化，我得到的time是

real    0m6.580s
user    0m0.236s
sys     0m2.400s

对比原版

real    0m8.451s
user    0m0.700s
sys     0m3.156s

因此，我们的实时时间减少了约 3 秒，用户时间减少了半秒，系统时间减少了约 0.7 秒。但是这里我们可以看到的是user+sys和real之间的巨大差异，也就是说时间不是花在进程内部做某事，而是等待。

因此，这里真正的瓶颈不在我们的进程中，而在虚拟终端模拟器的进程中：无论我们在程序中进行什么优化，向控制台发送大量文本都会很慢；换句话说，你的任务不是 CPU 密集型的，而是 IO 密集型的，所以以 CPU 为目标的优化不会有太大的好处，因为最后你必须等待你的 IO 设备做他慢的事情。

加速此类程序的真正方法要简单得多：避免使用慢速 IO 设备（控制台），只需将数据写入文件（顺便说一下，默认情况下是块缓冲的）。

matteo@teokubuntu:~/cpp/test$ time ./a.out > test

real    0m0.369s
user    0m0.240s
sys     0m0.068s
于 2013-06-11T02:59:58.553 回答
2

由于基于i（外循环）的循环绝对没有变化，因此您不需要每次都计算它。

此外，数据的打印应该在内部循环之外，以免对计算产生 I/O 成本。

考虑到这两件事，一种可能性是：

static int sumCalculated = 0;
if (!sumCalculated) {
    for (j=0; j < ARRAY_SIZE; j++) {
        sum += array[j];
    }
    sumCalculated = 1;
}
printf("Sum is now: %d\n",sum);

尽管这与原始输出有不同的输出，这可能是一个问题（最后一行而不是每次添加一行）。

如果您确实需要在循环中打印累积和，我也会简单地缓冲它（因为它不会在每次i循环中都发生变化。

字符串Sum is now: 999999999999\n（12 位，可能因int大小而异）占用 25 个字节（不包括终止 NUL）。将其乘以 9973，您需要大约 250K 的缓冲区（包括终止 NUL）。所以是这样的：

static char buff[250000];
static int sumCalculated = 0;

if (!sumCalculated) {
    int offset = 0;
    for (j=0; j < ARRAY_SIZE; j++) {
        sum += array[j];
        offset += sprintf (buff[offset], "Sum is now: %d\n",sum);
    }
    sumCalculated = 1;
}
printf ("%s", buff);

现在，这有点违背了作为基准工具的外循环的全部意图，但循环不变的删除是一种有效的优化方法。

于 2013-06-11T03:02:46.137 回答
0

将 printf 移到 for 循环之外。

   // Do not alter anything above this line.
   //Need to optimize this for loop----------------------------------------
    for (j=0; j < ARRAY_SIZE; j++) {
        sum += array[j];
    }
   printf("Sum is now: %d\n",sum);

    // Do not alter anything below this line.
    // ---------------------------------------------------------------
于 2013-06-11T02:57:53.503 回答
0
  1. 让 I/O 脱离循环是一个很大的帮助。
  2. 根据编译器和机器的不同，您可能会通过使用指针而不是索引来稍微提高速度（尽管在现代硬件上，它通常不会产生影响）。
  3. 循环展开可能有助于增加有用工作与循环开销的比率。
  4. 您可以使用向量指令（例如 SIMD）并行进行大量计算。
  5. 你可以打包数组吗？你能使用比 int 更小的类型的数组吗（假设所有的值都非常小）？使阵列在物理上更短可以提高局部性。

循环展开可能看起来像这样：

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

如果数组不是展开大小的精确倍数（这可能是赋值使用质数的原因），您必须弄清楚该怎么做。

您将不得不进行试验，看看展开多少才是正确的。

于 2013-06-11T03:32:44.497 回答