c++ - 访问三个静态数组比访问一个包含 3x 数据的静态数组更快？

Question

我有 700 个项目，我循环遍历 700 个项目，获取项目的三个属性并执行一些基本计算。我使用两种技术实现了这一点:

1) 三个 700 个元素的数组，一个数组对应三个属性中的每一个。所以:

 item0.a = array1[0]
 item0.b = array2[0]
 item0.e = array3[0]

2) 一个 2100 元素的数组，连续包含三个属性的数据。所以:

 item0.a = array[(0*3)+0]
 item0.b = array[(0*3)+1]
 item0.e = array[(0*3)+2]

现在三个项目属性 a、b 和 e 在循环中一起使用 - 因此如果您存储它们在一个阵列中的性能应该比使用三阵列技术更好(由于空间局部性)。然而:

• 三个 700 元素数组 = 3300 个 CPU 周期整个循环平均
• 一个 2100 元素数组 = 3500 个 CPU 周期整个循环平均

这是 2100 阵列技术的代码:

unsigned int x;
unsigned int y;
double c = 0;
double d = 0;
bool data_for_all_items = true;
unsigned long long start = 0;
unsigned long long finish = 0;
unsigned int array[2100];

//I have left out code for simplicity. You can assume by now the array is populated.

start = __rdtscp(&x);

for(int i=0; i < 700; i++){
    unsigned short j = i * 3;
    unsigned int a = array[j + 0];     
    unsigned int b = array[j + 1];     

    data_for_all_items = data_for_all_items & (a!= -1 & b != -1);

    unsigned int e = array[j + 2];    

    c += (a * e);
    d += (b * e);
}

finish = __rdtscp(&y);

这里是三个 700 元素数组技术的代码:

unsigned int x;
unsigned int y;
double c = 0;
double d = 0;
bool data_for_all_items = true;
unsigned long long start = 0;
unsigned long long finish = 0;
unsigned int array1[700];
unsigned int array2[700];
unsigned int array3[700];

//I have left out code for simplicity. You can assume by now the arrays are populated.

start = __rdtscp(&x);

for(int i=0; i < 700; i++){
    unsigned int a= array1[i];     //Array 1
    unsigned int b= array2[i];     //Array 2

    data_for_all_items = data_for_all_items & (a!= -1 & b != -1);

    unsigned int e = array3[i];    //Array 3

    c += (a * e);
    d += (b * e);
}

finish = __rdtscp(&y);

为什么使用 one-2100 元素数组的技术没有更快？应该是因为三个属性一起使用，每700个item。

我使用的是 MSVC 2012，Win 7 64

3x 700 元素阵列技术的组装:

            start = __rdtscp(&x);
 rdtscp  
 shl         rdx,20h  
 lea         r8,[this]  
 or          rax,rdx  
 mov         dword ptr [r8],ecx  
 mov         r8d,8ch  
 mov         r9,rax  
 lea         rdx,[rbx+0Ch]  

            for(int i=0; i < 700; i++){
 sub         rdi,rbx  
                unsigned int a = array1[i];
                unsigned int b = array2[i];

                data_for_all_items = data_for_all_items & (a != -1 & b != -1);
 cmp         dword ptr [rdi+rdx-0Ch],0FFFFFFFFh  
 lea         rdx,[rdx+14h]  
 setne       cl  
 cmp         dword ptr [rdi+rdx-1Ch],0FFFFFFFFh  
 setne       al  
 and         cl,al  
 cmp         dword ptr [rdi+rdx-18h],0FFFFFFFFh  
 setne       al  
 and         cl,al  
 cmp         dword ptr [rdi+rdx-10h],0FFFFFFFFh  
 setne       al  
 and         cl,al  
 cmp         dword ptr [rdi+rdx-14h],0FFFFFFFFh  
 setne       al  
 and         cl,al  
 cmp         dword ptr [rdx-20h],0FFFFFFFFh  
 setne       al  
 and         cl,al  
 cmp         dword ptr [rdx-1Ch],0FFFFFFFFh  
 setne       al  
 and         cl,al  
 cmp         dword ptr [rdx-18h],0FFFFFFFFh  
 setne       al  
 and         cl,al  
 cmp         dword ptr [rdx-10h],0FFFFFFFFh  
 setne       al  
 and         cl,al  
 cmp         dword ptr [rdx-14h],0FFFFFFFFh  
 setne       al  
 and         cl,al  
 and         r15b,cl  
 dec         r8  
 jne         013F26DA53h  

                unsigned int e = array3[i];

                c += (a * e);
                d += (b * e);
            }


            finish = __rdtscp(&y);
 rdtscp  
 shl         rdx,20h  
 lea         r8,[y]  
 or          rax,rdx  
 mov         dword ptr [r8],ecx 

2100 元素数组技术的汇编程序:

            start = __rdtscp(&x);
 rdtscp  
 lea         r8,[this]  
 shl         rdx,20h  
 or          rax,rdx  
 mov         dword ptr [r8],ecx  

            for(int i=0; i < 700; i++){
 xor         r8d,r8d  
 mov         r10,rax  
                unsigned short j = i*3;
 movzx       ecx,r8w  
 add         cx,cx  
 lea         edx,[rcx+r8]  
                unsigned int a = array[j + 0];
                unsigned int b = array[j + 1];

                data_for_all_items = data_for_all_items & (best_ask != -1 & best_bid != -1);
 movzx       ecx,dx  
 cmp         dword ptr [r9+rcx*4+4],0FFFFFFFFh  
 setne       dl  
 cmp         dword ptr [r9+rcx*4],0FFFFFFFFh  
 setne       al  
 inc         r8d  
 and         dl,al  
 and         r14b,dl  
 cmp         r8d,2BCh  
 jl          013F05DA10h  

                unsigned int e = array[pos + 2];

                c += (a * e);
                d += (b * e);
            }


            finish = __rdtscp(&y);
 rdtscp  
 shl         rdx,20h  
 lea         r8,[y]  
 or          rax,rdx  
 mov         dword ptr [r8],ecx  

Answer 1

编辑:给定您的汇编代码，第二个循环展开五次。展开版本可以在无序执行 CPU(例如任何现代 x86/x86-64 CPU)上运行得更快。

---

第二个代码是可向量化的——每个数组的两个元素可以在每次迭代时分别加载到一个 XMM 寄存器中。由于现代 CPU 将 SSE 用于标量和 vector FP 算法，这将周期数大致减少了一半。使用支持 AVX 的 CPU，可以将四个 double 值加载到 YMM 寄存器中，因此周期数应减少为四个。

第一个循环不可沿 i 向量化，因为迭代 i+1 中 a 的值来自位置 3 个元素之后迭代 i 中 a 的值来自哪里。在这种情况下，矢量化需要收集 vector 负载，这些负载仅在 AVX2 指令集中受支持。

在对具有 vector 功能的 CPU 进行编程时，使用适当的数据结构至关重要。将第一个循环之类的代码转换为第二个循环之类的代码是为了在具有非常宽的 vector 寄存器但非常慢的顺序执行引擎的英特尔至强融核上获得良好性能而必须完成的工作的 90%。