Обращение к данным вложенного массива C++ и оптимизация

Question

Представим вложенный(двумерный) массив 10x10, хранящий числовые значения. Классический способ перебора значений, который я обычно встречаю - это вложенный цикл, последовательно читающий элементы 1-й "строки", а затем переходящий к следующей.

Если каждая из таких строк, занимает отдельную область памяти, то будет 10 переходов по этим областям, и по 10 обращений к отдельным элементам в строках.
(Шаблон: element = array[X][Y])

Насколько мне известно, обращение к строке(X) - будет стоить дороже по вычислительным ресурсам, чем к элементу в ней(Y).

ВОПРОС: При обращениях к элементам массива не последовательно, и с более частыми перескакиваниями между строк(что в сумме даст больше 10-ти переходов), время перебора увеличится ?

Answer 1

У вас не указано, какой, собственно двумерный массив имеется в виду. Так что возьмем простейший: 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];

разница, наконец, появится. Но поймать ее на матрице 10х10 вряд ли вы сумеете. Вот на 1000х1000 - уже реальнее. Смотрите код с результатами здесь: https://bit.ly/3Y091w6

Ваша любознательность удовлетворена?

БЛОГ НА HUSL

Обращение к данным вложенного массива C++ и оптимизация

Ответы (1 шт):