c - 证明 c 使用行优先顺序排列二维数组

Question

我试图证明 c 使用行优先顺序作为内存结构，因此我正在测量创建行优先数组与列优先数组(乘法 * 2)的时间。

问题是循环 subrow(array) 和 subcol(array) 的算法不太正确。行优先顺序应该在缓存中产生更少的未命中，因此比列优先顺序更快，但我经常得到相反的结果。如果您运行代码，您将得到如下内容:

行优先耗时 6511 毫秒。 Column-major 耗时 5690 毫秒。

请帮我梳理一下算法。

编辑: 有人指出我实际上并没有访问数组，所以我没有测试访问速度。我添加了 sum += array[i][j];到 subcol 和 subrow 循环，但我仍然得到相同的一致结果，即行优先订单执行速度较慢，而相反的情况应该是正确的。也许我在循环中设置 i 和 j 的方式有问题。 输出: 子行总和 = 784293664 Row-major 耗时 6737 毫秒。 子列总和 = 784293664 Column-major 耗时 6594 毫秒。

更新代码:

  #include <stdio.h>
  #include <sys/time.h>

  #define ROW 1000
  #define COL 1000

  void subrow(int array[ROW][COL]);
  void subcol(int array[ROW][COL]);

  int main()
  {

      int array[ROW][COL];

      int i, j;

      for(i=0;i<ROW;i++)        // sets the array to each element to x*y then multiplies by 2
      {
          for (j=0; j<COL; j++)
              {
              array[i][j]=i*j;
              array[i][j]=array[i][j]*2;
              }
      }

      subrow(array);        //calls the max row function
      subcol(array);        //calls the max col function

      return 0;

  }

  void subrow(int array[ROW][COL])
  {
      int i,j;

      struct timeval stop, start;
      gettimeofday(&start, NULL);
  int sum = 0;

      for (i=0;i<ROW;i++)
      {
              for (j=0; j<COL; j++)
         {
    sum += array[i][j];
         }
      }

      printf("subrow sum = %d\n", sum);
      gettimeofday(&stop, NULL);
      printf("Row-major took %lu miliseconds.\n", (stop.tv_usec - start.tv_usec));

      return;
  }

  void subcol(int array[ROW][COL])
  {
      int i,j;

      struct timeval stop, start;    //
      gettimeofday(&start, NULL);

  int sum = 0;

      for (i=0; i<COL;i++)
      {
              for (j=0; j<ROW; j++)
              {
              sum += array[i][j];
              }
      }
      printf("subcol sum = %d\n", sum);
      gettimeofday(&stop, NULL);
      printf("Column-major took %lu miliseconds.\n", (stop.tv_usec - start.tv_usec));

      return;
  }

Answer 1

for (i=0;i<ROW;i++)
{
    for (j=0; j<COL; j++)
    {
    }
}

您实际上并没有访问这些循环中的数组。您只是在迭代几个 int 变量。如果您想测试访问速度，您需要实际读取或写入 array[i][j]。

例如:

int sum = 0;

for (i=0;i<ROW;i++)
{
    for (j=0; j<COL; j++)
    {
        sum += array[i][j];
    }
}

// Do something with `sum` so the compiler doesn't optimize it, and the loops above,
// away.
printf("sum = %d\n", sum);