c++ - 哪一个更适合访问数组？

Question

解决以下练习：

编写三个不同版本的程序来打印 ia 的元素。一个版本应该使用范围 for 来管理迭代，另外两个版本应该使用普通的 for 循环，一种情况下使用下标，另一种情况下使用指针。在所有三个程序中直接编写所有类型。也就是说，不要使用类型别名、auto 或 decltype 来简化代码。[C++ Primer]

出现了一个问题：这些访问数组的方法中，哪些在速度方面进行了优化，为什么？

---

我的解决方案：

1. Foreach 循环：

   int ia[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};    
   for (int (&i)[4]:ia)        //1st method using for each loop
       for(int j:i)
           cout<<j<<" ";
   

2. 嵌套 for 循环：

   for (int i=0;i<3;i++)       //2nd method normal for loop
       for(int j=0;j<4;j++)
           cout<<ia[i][j]<<" ";
   

3. 使用指针：

   int (*i)[4]=ia;
   for(int t=0;t<3;i++,t++){  //3rd method.  using pointers.
       for(int x=0;x<4;x++)
           cout<<(*i)[x]<<" ";
   

4. 使用auto：

   for(auto &i:ia)             //4th one using auto but I think it is similar to 1st.  
       for(auto j:i)
            cout<<j<<" ";
   

---

使用基准测试结果clock()

1st: 3.6  (6,4,4,3,2,3) 
2nd: 3.3  (6,3,4,2,3,2)
3rd: 3.1  (4,2,4,2,3,4)
4th: 3.6  (4,2,4,5,3,4)

模拟每种方法 1000 次：

1st: 2.29375  2nd: 2.17592  3rd: 2.14383  4th: 2.33333
Process returned 0 (0x0)   execution time : 13.568 s

使用的编译器：MingW 3.2 c++11 标志已启用。IDE:代码块

Answer 1

我有一些观察和要点，希望你能从中得到答案。

1. 第四版，正如你自己提到的，与第一版基本相同。auto可以被认为只是一种编码快捷方式（这当然不是严格意义上的正确，因为 usingauto可能会导致获得与您预期不同的类型，从而导致不同的运行时行为。但大多数情况下这是正确的。）

2. 您使用指针的解决方案可能不是人们说他们正在使用指针时的意思！一种解决方案可能是这样的：

   for (int i = 0, *p = &(ia[0][0]); i < 3 * 4; ++i, ++p)
       cout << *p << " ";
   

   或使用两个嵌套循环（这可能毫无意义）：

   for (int i = 0, *p = &(ia[0][0]); i < 3; ++i)
       for (int j = 0; j < 4; ++j, ++p)
           cout << *p << " ";
   

   从现在开始，我假设这是您编写的指针解决方案。

3. 在这种微不足道的情况下，绝对会支配你的运行时间的部分是cout. 与执行 I/O 相比，记账和检查循环所花费的时间完全可以忽略不计。因此，您使用哪种循环技术并不重要。

4. 现代编译器非常擅长优化此类普遍存在的任务和访问模式（遍历数组）。因此，所有这些方法很可能会生成完全相同的代码（指针版本可能例外，我将在稍后讨论。 )

5. 大多数这样的代码的性能将更多地取决于内存访问模式，而不是编译器如何准确地生成汇编分支指令（以及其余操作）。这是因为如果所需的内存块不在 CPU 缓存中，从 RAM 中获取这些字节大约需要数百个 CPU 周期（这只是一个大概的数字）。由于所有示例以完全相同的顺序访问内存，因此它们在内存和缓存方面的行为将是相同的，并且将具有大致相同的运行时间。

   附带说明一下，这些示例访问内存的方式是访问内存的最佳方式！线性的，连续的，从头到尾。同样，其中存在问题cout，这可能是一个非常复杂的操作，甚至在每次调用时都会调用操作系统，除其他外，这可能会导致几乎完全删除（驱逐）CPU 缓存中所有有用的东西。

6. 在 32 位系统和程序上，anint和指针的大小通常相等（都是 32 位！）这意味着您是否传递并使用索引值或指向数组的指针并不重要。然而，在 64 位系统上，指针是 64 位，但 int 通常仍然是 32 位。这表明在 64 位系统和程序上，通常最好使用数组索引而不是指针（甚至迭代器）。

   在这个特定的例子中，这一点都不重要。

7. 您的代码非常具体和简单，但一般情况下，向编译器提供尽可能多的关于您的代码的信息几乎总是更好。这意味着您必须使用可用的最窄、最具体的设备来完成工作。这反过来意味着对于编译器而言，通用for循环 (ie for (int i = 0; i < n; ++i))比基于范围的循环(ie )更糟糕，因为在后一种情况下，编译器只知道您将迭代整个范围而不是超出范围它或跳出循环或其他东西，而在通用循环情况下，特别是如果您的代码更复杂，编译器无法确定这一点，并且必须插入额外的检查和测试以确保代码按照 C++ 标准执行说应该。forfor (auto i : v)for

8. 在许多（大多数？）情况下，尽管您可能认为性能很重要，但事实并非如此。而且大多数时候你重写一些东西来获得性能，你并没有获得太多。在大多数情况下，您获得的性能提升与您所维持的可读性和可维护性的损失是不值得的。因此，正确设计您的代码和数据结构（并牢记性能），但要避免这种“微优化”，因为它几乎总是不值得，甚至还会损害代码的质量。

9. 一般来说，速度方面的性能很难推理。理想情况下，您必须使用可靠的科学测量和统计方法，在真实工作条件下使用真实硬件上的真实数据来测量时间。即使测量一段代码运行所花费的时间也不是一件容易的事。衡量性能很难，推理也更难，但如今它是识别瓶颈和优化代码的唯一方法。

我希望我已经回答了你的问题。

编辑：我为你想要做的事情写了一个非常简单的基准。代码在这里。它是为 Windows 编写的，应该可以在 Visual Studio 2012 上编译（因为基于范围的 for 循环。）这里是计时结果：

Simple iteration (nested loops): min:0.002140, avg:0.002160, max:0.002739
    Simple iteration (one loop): min:0.002140, avg:0.002160, max:0.002625
   Pointer iteration (one loop): min:0.002140, avg:0.002160, max:0.003149
 Range-based for (nested loops): min:0.002140, avg:0.002159, max:0.002862
 Range(const ref)(nested loops): min:0.002140, avg:0.002155, max:0.002906

相关数字是“最小”时间（对于 1000x1000 阵列，每个测试运行超过 2000 次。）如您所见，测试之间绝对没有区别。请注意，您应该打开编译器优化，否则测试 2 将是一场灾难，案例 4 和 5 会比 1 和 3 差一点。

以下是测试代码：

// 1. Simple iteration (nested loops)
unsigned sum = 0;
for (unsigned i = 0; i < gc_Rows; ++i)
    for (unsigned j = 0; j < gc_Cols; ++j)
        sum += g_Data[i][j];

// 2. Simple iteration (one loop)
unsigned sum = 0;
for (unsigned i = 0; i < gc_Rows * gc_Cols; ++i)
    sum += g_Data[i / gc_Cols][i % gc_Cols];

// 3. Pointer iteration (one loop)
unsigned sum = 0;
unsigned * p = &(g_Data[0][0]);
for (unsigned i = 0; i < gc_Rows * gc_Cols; ++i)
    sum += *p++;

// 4. Range-based for (nested loops)
unsigned sum = 0;
for (auto & i : g_Data)
    for (auto j : i)
        sum += j;

// 5. Range(const ref)(nested loops)
unsigned sum = 0;
for (auto const & i : g_Data)
    for (auto const & j : i)
        sum += j;

Answer 2

影响它的因素有很多：

1. 这取决于编译器
2. 这取决于使用的编译器标志
3. 这取决于使用的计算机

只有一种方法可以知道确切的答案：测量处理大型数组（可能来自随机数生成器）时使用的时间，这与您已经完成的方法相同，只是数组大小应至少为 1000x1000。