主页 / 问题 / 1596305
Accepted
Пьяная фея
Asked:2024-10-11 01:17:35 +0000 UTC2024-10-11 01:17:35 +0000 UTC

C++ 嵌套数组数据访问和优化

  • 772

让我们想象一个存储数值的嵌套（二维）10x10 数组。我通常看到的迭代值的经典方法是嵌套循环，顺序读取第一个“行”的元素，然后转到下一个。

如果这些行中的每一行都占用一个单独的内存区域，则将有 10 次通过这些区域的转换，以及对行中各个元素的 10 次访问。
（模式：元素=数组[X][Y]）

据我所知，访问行（X）比访问其中的元素（Y）花费更多的计算资源。

问题： 当非顺序访问数组元素时，并且行间跳转更加频繁（总共会产生超过 10 次转换），搜索时间会增加吗？

c++

1 个回答

  1. Best Answer

    您没有指出您实际上想要哪种二维数组。那么我们就来看最简单的一个：int arr[10][10];

    为了“跳”得更猛烈，我们逐行、逐列地总结一下……

    int enumer1()
{
    int sum = 0;
    for(int i = 0; i < 10; ++i)
        for(int j = 0; j < 10; ++j)
            sum += arr[i][j];
    return sum;
}
int enumer2()
{
    int sum = 0;
    for(int j = 0; j < 10; ++j)
        for(int i = 0; i < 10; ++i)
            sum += arr[i][j];
    return sum;
}

    让我们编译并查找汇编代码中的差异。

    ?enumer2@@YAHXZ PROC                                  ?enumer1@@YAHXZ PROC                                 ; enumer2, COMDAT

; 31   :     int sum = 0;                             ; 23   :     int sum = 0;

        xor     eax, eax                                      xor     eax, eax
        lea     r8, OFFSET FLAT:?arr@@3PAY0CHBA@HA            lea     r8, OFFSET FLAT:?arr@@3PAY0CHBA@HA   ; arr
        mov     edx, eax                                      mov     edx, eax
        npad    5                                             npad    5
$LL4@enumer2:                                         $LL4@enumer1:

; 32   :     for(int j = 0; j < 10; ++j)              ; 24   :     for(int i = 0; i < 10; ++i)
; 33   :         for(int i = 0; i < 10; ++i)          ; 25   :         for(int j = 0; j < 10; ++j)
; 34   :             sum += arr[i][j];                ; 26   :             sum += arr[i][j];

        mov     ecx, DWORD PTR [rdx+r8+32]                    mov     ecx, DWORD PTR [rdx+r8+32]
        add     ecx, DWORD PTR [rdx+r8+28]                    add     ecx, DWORD PTR [rdx+r8+28]
        add     ecx, DWORD PTR [rdx+r8+24]                    add     ecx, DWORD PTR [rdx+r8+24]
        add     ecx, DWORD PTR [rdx+r8+20]                    add     ecx, DWORD PTR [rdx+r8+20]
        add     ecx, DWORD PTR [rdx+r8+16]                    add     ecx, DWORD PTR [rdx+r8+16]
        add     ecx, DWORD PTR [rdx+r8+12]                    add     ecx, DWORD PTR [rdx+r8+12]
        add     ecx, DWORD PTR [rdx+r8+8]                     add     ecx, DWORD PTR [rdx+r8+8]
        add     ecx, DWORD PTR [rdx+r8+4]                     add     ecx, DWORD PTR [rdx+r8+4]
        add     ecx, DWORD PTR [rdx+r8+36]                    add     ecx, DWORD PTR [rdx+r8+36]
        add     ecx, DWORD PTR [rdx+r8]                       add     ecx, DWORD PTR [rdx+r8]
        add     rdx, 40000                                    add     rdx, 40000                           ; 00009c40H
        add     eax, ecx                                      add     eax, ecx
        cmp     rdx, 400000                                   cmp     rdx, 400000                          ; 00061a80H
        jl      SHORT $LL4@enumer2                            jl      SHORT $LL4@enumer1

; 35   :     return sum;                              ; 27   :     return sum;
; 36   : }                                            ; 28   : }

        ret     0                                             ret     0
?enumer2@@YAHXZ ENDP                                  ?enumer1@@YAHXZ ENDP                                 ; enumer2

    你也没有看出区别吗？ :)

    好吧，让我们关闭优化。循环看起来相同，对数组元素的调用也相同：

    ; 26   :             sum += arr[i][j];          ; 34   :             sum += arr[i][j];

movsxd  rax, DWORD PTR i$1[rsp]                 movsxd  rax, DWORD PTR i$1[rsp]
imul    rax, rax, 40000                         imul    rax, rax, 40000
lea     rcx, OFFSET FLAT:?arr@@3PAY0CHBA@HA     lea     rcx, OFFSET FLAT:?arr@@3PAY0CHBA@HA
add     rcx, rax                                add     rcx, rax
mov     rax, rcx                                mov     rax, rcx
movsxd  rcx, DWORD PTR j$2[rsp]                 movsxd  rcx, DWORD PTR j$2[rsp]
mov     eax, DWORD PTR [rax+rcx*4]              mov     eax, DWORD PTR [rax+rcx*4]
mov     ecx, DWORD PTR sum$[rsp]                mov     ecx, DWORD PTR sum$[rsp]

    所以对于数组来说int[][]，内存是一块分配的，本质上没有什么区别。尤其是这种大小的数组，当整个数组可以轻松放入处理器缓存中时......

    但如果你考虑

    int ** arr = new int*[10];
for(int i = 0; i < 10; ++i) arr[i] = new int[10];

    差异最终会出现。但你不太可能在 10x10 矩阵上捕捉到它。现在在 1000x1000 下更加真实。请参阅此处的代码和结果： https: //bit.ly/3Y091w6

    你的好奇心满足了吗？

    • 3

相关问题