Арифметика указателей vs индексация

[GAA]

Много разного пишут и говорят. Например, в (достаточно старой) книге
Шилдт Г. Полный справочник по C++, 4-е издание. . Пер. с англ. — М. : Издательский дом “Вильямс”, 2006 на с. 123 и далее (§ Указатели и массивы)

Цитата:

По сути, в языке C/C++ существуют два способа обращения к элементам массива: индексация и адресная арифметика. Хотя индексация массива нагляднее, адресная арифметика иногда оказывается эффективнее. Поскольку быстродействие программы относится к одним из ее важнейших свойств, программисты на языке C/C+ + широко используют указатели для обращения к элементам массива.
/* Индексация указателя. */
void putstrfchar *s)
{
register int t;
for(t=0; s[t]; ++t) putchar(s[t]);
}
/* Доступ с помощью указателя. */
void putstrfchar *s)
{
while(*s) putchar(*s++);
}
Большинство профессиональных программистов сочтут вторую версию более понятной и наглядной. На практике именно этот способ доступа к элементам массива распространен наиболее широко.

С другой стороны. В общем случае, указатели затрудняют оптимизацию кода компиляторами. На скорую руку нагуглил в Сети Оптимизация кода: процессор. В разделе «Блокировщики оптимизации»:

Цитата:

Нам, как программистам, нужно понимать, что существуют определённые характеристики кода, которые не позволят компилятору совершить оптимизацию. Мы их называем блокировщиками оптимизации. Рассмотрим два типа блокировщиков оптимизации. Одним из них являются указатели. Компилятор не может точно знать, будут ли два указателя указывать на одну и ту же область памяти, и поэтому не выполняет некоторые оптимизации.

Найти в Сети подробный разбор обсуждаемого вопроса с ходу не смог, поэтому, думаю, многим будет интересны конкретные примеры: исходный текст, ассемблерный листинг, указание компилятора и настроек, результаты сравнения скоростей выполнения.

Mihaylo, приведите свой пример, а то трудно угадать о чём Вы пишите.

[Sdy]

GAA в сообщении #1435861 писал(а):

Шилдт Г. Полный справочник по C++, 4-е издание. . Пер. с англ. — М. : Издательский дом “Вильямс”, 2006 на с. 123 и далее (§ Указатели и массивы)

Приведу тогда и я ссылку.
Это правда старая версия стандарта для C, но должна соблюдать (надеюсь) права правообладателя.
Соответственно - http://c0x.coding-guidelines.com/6.5.2.1.html
Выдержка -

Цитата:

The definition of the subscript operator [] is that E1[E2] is identical to (*((E1)+(E2))).

Как я уже замечал выше, если например компилировать с помощью gcc последней (и не только) версии оба варианта обращения, ассемблерный код будет полностью идентичен. И gcc как раз обычно рассматривают как "тот самый" компилятор, "следующий стандарту".
А вот когда я поэкспериментировал с компилятором Micorosoft, оказалось, что ассемблерный код этих обращений различается.
Поэтому Вы полностью согласны, в том что

GAA в сообщении #1435861 писал(а):

Mihaylo, приведите свой пример, а то трудно угадать о чём Вы пишите.

[Mihaylo]

В нейронных сетях получается код такого рода:

Используется синтаксис C++

void CNNThread::conv_backward(double *ci_error, double **ci_error_map, double *co_error, double *co, double **kmap, double **dkmap, double **cimap, int filters_size1_sq, int filters_size3_sq)
{
    // m, n - input indexes; i, j - output indexes

    ci_error_ptr = ci_error;
    t = filters_size1_sq;
    while (t-- > 0)
        *ci_error_ptr++ = 0.0;


    co_ptr = co;
    co_error_ptr = co_error;
    cimap_ptr = cimap;
    ci_error_map_ptr = ci_error_map;
    kmap_ptr = kmap;
    dkmap_ptr = dkmap;
    t = filters_size3_sq;
    while (t-- > 0)
    {
        u = kernel_size_sq;
        while (u-- > 0)
        {

            if (*co_ptr>=0.0)
            {
                **dkmap_ptr++ += **cimap_ptr++ * *co_error_ptr;
                **ci_error_map_ptr++ += **kmap_ptr++ * *co_error_ptr;
            }
            else
            {
                tmp = leak_coeff * *co_error_ptr;
                **dkmap_ptr++ += tmp * **cimap_ptr++;
                **ci_error_map_ptr++ += tmp * **kmap_ptr++;
            }
        }
        *co_error_ptr++ = 0.0;
        co_ptr++;
    }
 

[Dmitriy40]

Почему бы два цикла не упростить до

Используется синтаксис C++

while (t-- > 0) {
        u = kernel_size_sq;
        tmp = *co_error_ptr;
        if (*co_ptr < 0.0) tmp *= leak_coeff;
        while (u-- > 0) {
                **dkmap_ptr++ += tmp * **cimap_ptr++;
                **ci_error_map_ptr++ += tmp * **kmap_ptr++;
        }
        *co_error_ptr++ = 0.0;
        co_ptr++;
}

Не уверен что компилятор тоже это сделает (вынос вычисления tmp за внутренний цикл и объединение обеих условных веток). Заодно и на один указатель меньше надо во внутреннем цикле.
Интересно сравнить ручной асм код и результат компиляции C/C++ ...

[Mihaylo]

Спасибо, посмотрю. А я думаю, почему не могу обогнать Tensorflow по скорости вычислений.

[arseniiv]

(Оффтоп)

Может быть потому что над ним работало достаточно людей?

P. S. Так он же опенсорсный, код посмотрите и всё.

[Dmitriy40]

У меня всё упирается в скорость чтения, надо прочитать 8 переменных (4 указателя и 4 данных), что возможно лишь за 4 такта. Вычисления занимают меньше 2 тактов. Сохранение результатов тоже быстрее, ровно 2 такта. Т.е. суммарная скорость должна быть 4 такта на итерацию. Разумеется это всё throughput, не latency, она не интересна. Ручной код (порты и такты указаны для Haswell):

Используется синтаксис ASM

        mov     EBX,dkmap_ptr
        mov     EDX,ci_error_map_ptr
        mov     ESI,cimap_ptr
        mov     EDI,kmap_ptr
;тут внешний цикл, не интересно
;тут вычисление tmp в xmm0, тоже малоинтересно
        mov     ECX,u           ;Ports  Latency/Throughput
.cycle: mov     EAX,[ESI]       ;23     3/0.5
        add     ESI,4           ;0156   1/0.25
        movapd  xmm1,xmm0       ;-      0/0
        mulsd   xmm1,[EAX]      ;23+01  3+5/0.5
        mov     EAX,[EBX]       ;23     3/0.5
        add     EBX,4           ;0156   1/0.25
        addsd   xmm1,[EAX]      ;23+1   3+3/0.5+1
        movsd   [EAX],xmm1      ;4      1/1
        mov     EAX,[EDI]       ;23     3/0.5
        add     EDI,4           ;0156   1/0.25
        movapd  xmm1,xmm0       ;-      0/0
        mulsd   xmm1,[EAX]      ;23+01  3+5/0.5
        mov     EAX,[EDX]       ;23     3/0.5
        add     EDX,4           ;0156   1/0.25
        addsd   xmm1,[EAX]      ;23+1   3+3/0.5+1
        movsd   [EAX],xmm1      ;4      1/1
        sub     ECX,1           ;06     1/0.5
        jnz     .cycle          ;-      0/0
;весь цикл 21 микрооперация

Ускорять вычисления возможно (при наличии поддержки FMA команд), но смысла не имеет, тормозит чтение. Вот если бы отказаться от косвенной адресации основных массивов (или априори положить что указатели в массивах всегда меняются ровно на 8), то можно подумать и ещё, там и векторизация пригодится, думаю можно было бы уложить всё в 1 такт на итерацию (с AVX даже и меньше) ...

Mihaylo в сообщении #1435975 писал(а):

А я думаю, почему не могу обогнать Tensorflow по скорости вычислений.

А сколько у Вас занимает одна итерация в тактах (в среднем разумеется)?

[Mihaylo]

Я сравниваю не в тактах, а в миллисекундах.

-- 19.01.2020, 20:02 --

arseniiv в сообщении #1435981 писал(а):

P. S. Так он же опенсорсный, код посмотрите и всё.

Ээ, ну я вряд ли найду, в каком файле лежит нужный код.

[Dmitriy40]

Mihaylo в сообщении #1435986 писал(а):

Я сравниваю не в тактах, а в миллисекундах.

Ну так умножьте миллисекунды на частоту своего процессора в ГГц в момент вычислений (и разделите на количество итераций если миллисекунды это не на одну итерацию, а всего, что кстати плохо в плане точности).

[Mihaylo]

Операция, которую я выложил здесь - самая нагруженная вроде из всего кода. Все операции в сумме за один проход выполняются примерно за 5 мс. Короче, достаточно трудно измерять отдельные операции.

[Mihaylo]

Dmitriy40 в сообщении #1435970 писал(а):

Почему бы два цикла не упростить до

Посмотрел. Что-то правда я не догадался, это же было просто! :) Это условие if просто было для меня как будто совсем очевидным внутри цикла.

[Mihaylo]

Я только сейчас смог приступить к анализу кода нейросети.

Будем сравнивать ассемблерные коды. Будем смотреть, насколько компиляторы умные... Компилятор MingW 64-bit.

КЛАССИЧЕСКИЙ ВАРИАНТ (#1)

Используется синтаксис C++

    bool *array1, *array2, *pnt1, *pnt2;
    int N = 100000;
    array1 = static_cast<bool *> (malloc(N * sizeof(bool)));
    array2 = static_cast<bool *> (malloc(N * sizeof(bool)));
    
    for (int j = 0; j<N; j++)
    {
        pnt1 = array1;
        pnt2 = array2;
        for (int i = 0; i<N; i++)
        {
            *pnt1 = !*pnt2;
            pnt1++;
            pnt2++;
        }
    }
 

Используется синтаксис ASM

        22 [1]      for (int j = 0; j<N; j++)
0x401657  <+  165>        c7 45 1c 00 00 00 00           movl   $0x0,0x1c(%rbp)
0x40165e  <+  172>        8b 45 1c                       mov    0x1c(%rbp),%eax
0x401661  <+  175>        3b 45 14                       cmp    0x14(%rbp),%eax
0x401664  <+  178>        7d 47                          jge    0x4016ad <qMain(int, char**)+251>
        24 [1]      pnt1 = array1;
0x401666  <+  180>        48 8b 45 08                    mov    0x8(%rbp),%rax
0x40166a  <+  184>        48 89 45 28                    mov    %rax,0x28(%rbp)
        25 [1]      pnt2 = array2;
0x40166e  <+  188>        48 8b 45 00                    mov    0x0(%rbp),%rax
0x401672  <+  192>        48 89 45 20                    mov    %rax,0x20(%rbp)
        29 [1]      for (int i = 0; i<N; i++)
0x401676  <+  196>        c7 45 18 00 00 00 00           movl   $0x0,0x18(%rbp)
0x40167d  <+  203>        8b 45 18                       mov    0x18(%rbp),%eax
0x401680  <+  206>        3b 45 14                       cmp    0x14(%rbp),%eax
0x401683  <+  209>        7d 22                          jge    0x4016a7 <qMain(int, char**)+245>
        31 [1]      *pnt1 = !*pnt2;
0x401685  <+  211>        48 8b 45 20                    mov    0x20(%rbp),%rax
0x401689  <+  215>        0f b6 00                       movzbl (%rax),%eax
0x40168c  <+  218>        83 f0 01                       xor    $0x1,%eax
0x40168f  <+  221>        89 c2                          mov    %eax,%edx
0x401691  <+  223>        48 8b 45 28                    mov    0x28(%rbp),%rax
0x401695  <+  227>        88 10                          mov    %dl,(%rax)
        32 [1]      pnt1++;
0x401697  <+  229>        48 83 45 28 01                 addq   $0x1,0x28(%rbp)
        33 [1]      pnt2++;
0x40169c  <+  234>        48 83 45 20 01                 addq   $0x1,0x20(%rbp)
        29 [1]      for (int i = 0; i<N; i++)
0x4016a1  <+  239>        83 45 18 01                    addl   $0x1,0x18(%rbp)
0x4016a5  <+  243>        eb d6                          jmp    0x40167d <qMain(int, char**)+203>
        22 [1]      for (int j = 0; j<N; j++)
0x4016a7  <+  245>        83 45 1c 01                    addl   $0x1,0x1c(%rbp)
0x4016ab  <+  249>        eb b1                          jmp    0x40165e <qMain(int, char**)+172>
 

ВАРИАНТ WHILE (#2)

Используется синтаксис C++

    bool *array1, *array2, *pnt1, *pnt2;
    int N = 100000, t, u;
    array1 = static_cast<bool *> (malloc(N * sizeof(bool)));
    array2 = static_cast<bool *> (malloc(N * sizeof(bool)));
    
    t = N;
    while (t-- > 0)
    {
        pnt1 = array1;
        pnt2 = array2;
        u = N;
        while (u-- > 0)
        {
            *pnt1++ = !*pnt2++;
        }
    }
 

Используется синтаксис ASM

        19 [1]      t = N;
0x401657  <+  165>        8b 45 14                       mov    0x14(%rbp),%eax
0x40165a  <+  168>        89 45 1c                       mov    %eax,0x1c(%rbp)
        21 [1]      while (t-- > 0)
0x40165d  <+  171>        8b 45 1c                       mov    0x1c(%rbp),%eax
0x401660  <+  174>        8d 50 ff                       lea    -0x1(%rax),%edx
0x401663  <+  177>        89 55 1c                       mov    %edx,0x1c(%rbp)
0x401666  <+  180>        85 c0                          test   %eax,%eax
0x401668  <+  182>        0f 9f c0                       setg   %al
0x40166b  <+  185>        84 c0                          test   %al,%al
0x40166d  <+  187>        74 4c                          je     0x4016bb <qMain(int, char**)+265>
        24 [1]          pnt1 = array1;
0x40166f  <+  189>        48 8b 45 08                    mov    0x8(%rbp),%rax
0x401673  <+  193>        48 89 45 28                    mov    %rax,0x28(%rbp)
        25 [1]          pnt2 = array2;
0x401677  <+  197>        48 8b 45 00                    mov    0x0(%rbp),%rax
0x40167b  <+  201>        48 89 45 20                    mov    %rax,0x20(%rbp)
        26 [1]          u = N;
0x40167f  <+  205>        8b 45 14                       mov    0x14(%rbp),%eax
0x401682  <+  208>        89 45 18                       mov    %eax,0x18(%rbp)
        28 [1]          while (u-- > 0)
0x401685  <+  211>        8b 45 18                       mov    0x18(%rbp),%eax
0x401688  <+  214>        8d 50 ff                       lea    -0x1(%rax),%edx
0x40168b  <+  217>        89 55 18                       mov    %edx,0x18(%rbp)
0x40168e  <+  220>        85 c0                          test   %eax,%eax
0x401690  <+  222>        0f 9f c0                       setg   %al
0x401693  <+  225>        84 c0                          test   %al,%al
0x401695  <+  227>        74 c6                          je     0x40165d <qMain(int, char**)+171>
        31 [1]              *pnt1++ = !*pnt2++;
0x401697  <+  229>        48 8b 45 20                    mov    0x20(%rbp),%rax
0x40169b  <+  233>        48 8d 50 01                    lea    0x1(%rax),%rdx
0x40169f  <+  237>        48 89 55 20                    mov    %rdx,0x20(%rbp)
0x4016a3  <+  241>        0f b6 08                       movzbl (%rax),%ecx
0x4016a6  <+  244>        48 8b 45 28                    mov    0x28(%rbp),%rax
0x4016aa  <+  248>        48 8d 50 01                    lea    0x1(%rax),%rdx
0x4016ae  <+  252>        48 89 55 28                    mov    %rdx,0x28(%rbp)
0x4016b2  <+  256>        83 f1 01                       xor    $0x1,%ecx
0x4016b5  <+  259>        89 ca                          mov    %ecx,%edx
0x4016b7  <+  261>        88 10                          mov    %dl,(%rax)
        28 [1]          while (u-- > 0)
0x4016b9  <+  263>        eb ca                          jmp    0x401685 <qMain(int, char**)+211>
 

ВАРИАНТ GOTO (#3)

Используется синтаксис C++

bool *array1, *array2, *pnt1, *pnt2;
    int N = 100000, t, u;
    array1 = static_cast<bool *> (malloc(N * sizeof(bool)));
    array2 = static_cast<bool *> (malloc(N * sizeof(bool)));

    t = N;
t_label:
    pnt1 = array1;
    pnt2 = array2;
    u = N;
u_label:
    *pnt1++ = !*pnt2++;
    if (u-- > 0) goto u_label;
    if (t-- > 0) goto t_label;
 

Используется синтаксис ASM

        19 [1]      t = N;
0x401657  <+  165>        8b 45 14                       mov    0x14(%rbp),%eax
0x40165a  <+  168>        89 45 1c                       mov    %eax,0x1c(%rbp)
        24 [1]          pnt1 = array1;
0x40165d  <+  171>        48 8b 45 08                    mov    0x8(%rbp),%rax
0x401661  <+  175>        48 89 45 28                    mov    %rax,0x28(%rbp)
        25 [1]          pnt2 = array2;
0x401665  <+  179>        48 8b 45 00                    mov    0x0(%rbp),%rax
0x401669  <+  183>        48 89 45 20                    mov    %rax,0x20(%rbp)
        26 [1]          u = N;
0x40166d  <+  187>        8b 45 14                       mov    0x14(%rbp),%eax
0x401670  <+  190>        89 45 18                       mov    %eax,0x18(%rbp)
        31 [1]              *pnt1++ = !*pnt2++;
0x401673  <+  193>        48 8b 45 20                    mov    0x20(%rbp),%rax
0x401677  <+  197>        48 8d 50 01                    lea    0x1(%rax),%rdx
0x40167b  <+  201>        48 89 55 20                    mov    %rdx,0x20(%rbp)
0x40167f  <+  205>        0f b6 08                       movzbl (%rax),%ecx
0x401682  <+  208>        48 8b 45 28                    mov    0x28(%rbp),%rax
0x401686  <+  212>        48 8d 50 01                    lea    0x1(%rax),%rdx
0x40168a  <+  216>        48 89 55 28                    mov    %rdx,0x28(%rbp)
0x40168e  <+  220>        83 f1 01                       xor    $0x1,%ecx
0x401691  <+  223>        89 ca                          mov    %ecx,%edx
0x401693  <+  225>        88 10                          mov    %dl,(%rax)
        34 [1]          if (u-- > 0) goto u_label;
0x401695  <+  227>        8b 45 18                       mov    0x18(%rbp),%eax
0x401698  <+  230>        8d 50 ff                       lea    -0x1(%rax),%edx
0x40169b  <+  233>        89 55 18                       mov    %edx,0x18(%rbp)
0x40169e  <+  236>        85 c0                          test   %eax,%eax
0x4016a0  <+  238>        0f 9f c0                       setg   %al
0x4016a3  <+  241>        84 c0                          test   %al,%al
0x4016a5  <+  243>        74 02                          je     0x4016a9 <qMain(int, char**)+247>
0x4016a7  <+  245>        eb ca                          jmp    0x401673 <qMain(int, char**)+193>
        36 [1]      if (t-- > 0) goto t_label;
0x4016a9  <+  247>        8b 45 1c                       mov    0x1c(%rbp),%eax
0x4016ac  <+  250>        8d 50 ff                       lea    -0x1(%rax),%edx
0x4016af  <+  253>        89 55 1c                       mov    %edx,0x1c(%rbp)
0x4016b2  <+  256>        85 c0                          test   %eax,%eax
0x4016b4  <+  258>        0f 9f c0                       setg   %al
0x4016b7  <+  261>        84 c0                          test   %al,%al
0x4016b9  <+  263>        74 02                          je     0x4016bd <qMain(int, char**)+267>
0x4016bb  <+  265>        eb a0                          jmp    0x40165d <qMain(int, char**)+171>
 

===========================================================================

Результат анализа:

Используется синтаксис C++

for (int i = 0; i<N; i++)

реализуется шестью инструкциями, при чем одна из них - инициализация

Варианты while и goto в принципе идентичны друг другу, отличаются лишь расположением проверки условия выхода из цикла. Всего используют 10 инструкций, 2 из них - инициализация.

Используется синтаксис C++

t = N;
while (t-- > 0)

и

Используется синтаксис C++

t = N;
t_label:
...
if (t-- > 0) goto t_label;
 

Цикл for прост, лаконичен и не портит содержимое регистров кроме одного eax. Попытка использовать while и if-goto для написания as simple as assembler не увенчалась успехом! Компилятор просто не понимает, чего хочет программист.

-- 02.02.2020, 01:00 --

==================================================
Еще один нюанс есть в кодах выше. Следующие коды идентичны по действию:

*pnt1 = !*pnt2;
pnt1++;
pnt2++;

*pnt1++ = !*pnt2++;

и второй вариант кажется лаконичным и оптимальным с точки зрения ассемблера. Однако компилятор и тут не понимает, чего хочет программист.
Первый вариант: 8 инструкций
Второй вариант: 10 инструкций

[arseniiv]

Mihaylo в сообщении #1437831 писал(а):

Первый вариант: 8 инструкций
Второй вариант: 10 инструкций

Такая разница в количестве инструкций вроде ещё ни о чём сама по себе не говорит.

[Mihaylo]

Сейчас сравнил инструкции почленно, разница только в реализации инкремента:

Используется синтаксис ASM

        32 [1]      pnt1++;
0x401697  <+  229>        48 83 45 28 01                 addq   $0x1,0x28(%rbp)
        33 [1]      pnt2++;
0x40169c  <+  234>        48 83 45 20 01                 addq   $0x1,0x20(%rbp)
 

Используется синтаксис ASM

0x40169b  <+  233>        48 8d 50 01                    lea    0x1(%rax),%rdx
0x40169f  <+  237>        48 89 55 20                    mov    %rdx,0x20(%rbp)
0x4016aa  <+  248>        48 8d 50 01                    lea    0x1(%rax),%rdx
0x4016ae  <+  252>        48 89 55 28                    mov    %rdx,0x28(%rbp)
 

[tolstopuz]

Судя по всему, вы забыли включить оптимизацию.