哪一个更适合访问阵列？

Question

解决以下练习:

编写三个不同版本的程序来打印ia的元素.一个版本应该使用一个范围来管理迭代,另外两个应该在一个案例中使用普通的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可以被认为只是一个编码快捷方式(这当然不是严格意义上的,因为使用auto可能会导致获得与您预期不同的类型,从而导致不同的运行时行为.但大多数情况下这是真的.)

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缓存中,它需要花费大约相当于几百个CPU周期的时间(这只是一个球场号码)来从RAM中获取这些字节.由于所有示例都以完全相同的顺序访问内存,因此它们在内存和缓存方面的行为将是相同的,并且将具有大致相同的运行时间.

   作为旁注,这些示例访问内存的方式是访问它的最佳方式!线性,连续,从头到尾.同样,在那里存在问题cout,这可能是一个非常复杂的操作,甚至在每次调用时调用OS,这可能导致几乎完全删除(驱逐)CPU缓存中有用的一切.

6. 在32位系统和程序中,a int和指针的大小通常相等(都是32位!)这意味着无论你是否传递并使用索引值或指针到数组都没关系.但是,在64位系统上,指针是64位,但int通常仍然是32位.这表明在64位系统和程序上使用索引而不是指针(甚至是迭代器)通常更好.

   在这个特定的例子中,这根本不重要.

7. 您的代码非常具体和简单,但一般情况下,尽可能多地向编译器提供有关代码的信息总是更好.这意味着您必须使用可用的最窄,最具体的设备来完成工作.这又意味着,通用for环路(即for (int i = 0; i < n; ++i))是更糟比基于范围的for循环(即for (auto i : v)编译器),因为在后一种情况下,编译器只是知道你要遍历整个范围,而不是去外面在通用for循环的情况下,特别是如果您的代码更复杂,编译器无法确定这一点,并且必须插入额外的检查和测试以确保代码作为C++标准执行说它应该.

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

相关数字是"最小"次数(每次测试超过2000次运行,对于1000x1000阵列.)如您所见,测试之间绝对没有区别.请注意,您应该启用编译器优化,否则测试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;