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

[Mihaylo]

Выделено из ветки «Распараллеливание программы (ядра/потоки)» / GAA

Второй момент: чтобы ускорить свою программу еще в несколько раз (не за счет распределения по ядрам), надо вместо обращения к массиву по индексу A[i], использовать указатели и разыменовывание указателей. Я такое делал, это реально ускоряет программу.

[realeugene]

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

Второй момент: чтобы ускорить свою программу еще в несколько раз (не за счет распределения по ядрам), надо вместо обращения к массиву по индексу A[i], использовать указатели и разыменовывание указателей. Я такое делал, это реально ускоряет программу.

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

[photon]

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

Второй момент: чтобы ускорить свою программу еще в несколько раз (не за счет распределения по ядрам), надо вместо обращения к массиву по индексу A[i], использовать указатели и разыменовывание указателей. Я такое делал, это реально ускоряет программу.

Обращение A[i], i[A], *(pA + i) в любом варианте не даст вам "ускорения в несколько раз", во всяком случае, в релизной сборке на не самом древнем компиляторе и выполнении на не самом древнем процессоре. Иногда может быть удастся ускорить на какие-то крохи за счет отказа от инкремента/декремента индекса, а напрямую инкремента/декремента указателя, но, в лучшем случае, речь будет о процентах, а не о разах.

[Mihaylo]

photon в сообщении #1435644 писал(а):

Обращение A[i], i[A], *(pA + i) в любом варианте не даст вам "ускорения в несколько раз", во всяком случае, в релизной сборке на не самом древнем компиляторе и выполнении на не самом древнем процессоре. Иногда может быть удастся ускорить на какие-то крохи за счет отказа от инкремента/декремента индекса, а напрямую инкремента/декремента указателя, но, в лучшем случае, речь будет о процентах, а не о разах.

Может быть. В моем случае считывание значения массива - это была самая массовая операция, чаще чем сложение и умножение с плавающей запятой. Нейронные сети.
Замедления не было, было однозначное ускорение. Среда Qt, компилятор MinGW.

[realeugene]

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

Замедления не было, было однозначное ускорение.

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

[mihaild]

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

Нейронные сети

Так там же всё равно нужно либо передавать ссылку на данные в какой-нибудь cblas, либо руками грузить всё в simd регистры (компилятор, который умеет в simd но не умеет в такую оптимизацию указателей).

[Dmitriy40]

А мне итерации по индексу в статических массивах нравятся больше, часто можно обойтись одним регистром индекса на все массивы, с использованием непосредственного адреса начала каждого массива. Экономится N-1 регистров, которых всегда мало. Скорость же выполнения команд mov EAX,[ESI] и mov EAX,[ESI*8+base-const] одинакова.

[Dmitriy40]

Пожалуй стоит пояснить подробнее, раз выделили в специальную тему.
Ситуация с одним и даже двумя массивами не интересна, что указатели, что индексы, всё едино в плане скорости. Возьмём для определённости сразу 100 массивов и будем считать что адресация к ним идёт не в произвольном порядке, а согласовано, но допустимы небольшие постоянные смещения для каждого массива. Да, это ограничивает круг задач, однако он остаётся ещё весьма и весьма объёмным.
Итак, 100 указателей в регистры не поместится, они будут в лучшем случае в стеке, адресация к ним будет по [EBP-const]. Посмотрим во что выльется код к примеру суммирования элементов массивов типа a[i]=b[i]+c[i-1]-d[i+10] (показываю всего 4 указателя, но в стеке, лень больше набирать, и так идея видна):

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

;инициализацию указателей не показываю, суть не в ней, положим она правильная для начального значения i
mov EBX,[EBP-const2];указатель на b[i]
mov EAX,[EBX];b[i]
add EBX,4
mov [EBP-const2],EBX
mov EBX,[EBP-const3];указатель на c[i-1]
add EAX,[EBX]
add EBX,4
mov [EBP-const3],EBX
mov EBX,[EBP-const4];указатель на d[i+10]
sub EAX,[EBX]
add EBX,4
mov [EBP-const4],EBX
mov EBX,[EBP-const1];указатель на a[i]
mov [EBX],EAX
add EBX,4
mov [EBP-const1],EBX

А теперь посмотрим на тот же код, но с индексацией по i:

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

;i хранится в EBX
mov EAX,[EBX*4+const2];читаем сразу b[i]
add EAX,[EBX*4+const3-1*4];добавляем сразу c[i-1]
sub EAX,[EBX*4+const4+10*4];добавляем сразу d[i+10]
mov [EBX*4+const1],EAX
inc EBX

Разница налицо.

Что будет со скоростью выполнения — вопрос. В первом коде загрузка EBX и чтение данных по [EBX] и увеличение EBX и запись его обратно в стек могут и будут параллелиться, плюс буфера отложенной записи и методика предвыборки последовательных данных, и в принципе если все указатели в кэше L1, то скорость может быть и одинаковой. Но, в первом коде заметно больше инструкций, в том числе и микроопераций, а очереди и глубина просмотра в процессорах не бесконечные.
С другой стороны, второй способ подходит только для статических массивов, когда их адреса известны на этапе компиляции. И незначительно замедляется загрузка exe файла в память из-за увеличения списка коррекции адресов при размещении сегментов данных в памяти.

И наоборот, если все нужные указатели влезают в регистры, то использование плюс к ним ещё и индекса тратит лишний регистр не давая выигрыша в скорости:

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

;указатели на массивы: EAX,EBX,ECX,EDX
mov ESI,[EBX]
add EBX,4
add ESI,[ECX]
add ECX,4
sub ESI,[EDX]
add EDX,4
mov [EAX],ESI
add EAX,4

Вариант с индексом в EDI:

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

;указатели на массивы: EAX,EBX,ECX,EDX
mov ESI,[EBX+EDI*4]
add ESI,[ECX+EDI*4-1*4]
sub ESI,[EDX+EDI*4+10*4]
mov [EAX+EDI*4],ESI
inc EDI

И снова код меньше, но скорость может быть и одинаковой из-за параллельности операций в первом варианте. Зато нужно на один регистр больше. Зато уже не обязательно статические массивы.
В этом случае выбор затруднён, смотря что ещё есть вокруг этого кода в цикле, может лишний свободный регистр пересилит увеличение длины кода этого куска.

PS. Всё написано из головы без проверки, могут быть опечатки. Что вместо этого нагеренит компилятор ЯВУ — даже не спрашивайте, боюсь заранее.

[realeugene]

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

Возьмём для определённости сразу 100 массивов

В одной функции нижнего уровня? Выглядит как плохо спроектированная программа.

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

Посмотрим во что выльется код

Под какую именно версию процессора включена оптимизация?

[Dmitriy40]

realeugene
Вы "PS" заметили? Думаю там достаточно для ответа.
Но вообще ориентировался на Intel Core i3/5/7-4xxx Haswell, правда с тех пор в новых процессорах ничего не улучшилось в этом плане насколько мне известно.

Добавлю про 100 указателей. Это конечно выдумано для обоснования почему не всё в регистрах, но вот даже 3-4-5 указателя в регистрах хранить часто расточительно, регистров может просто не хватить (напомню, из 8 доступно лишь 6, ESP и EBP всегда заняты) если делать что-то более сложное, как например: умножение/деление (которые тратят два выделенных регистра всегда), счётчик цикла может понадобиться, временные регистры под промежуточные результаты умножения/деления, под аргументы вызываемых функций, а уж если данные 64-х битные, то в регистрах умещаются всего 3 числа (и два если используются команды умножения/деления). Так что ситуация с указателями не в регистрах совсем не такая уж редкая как можно подумать.
Под x64 виндой обычно заняты RCX,RDX,RBP,RSP,R8,R9,R10,R11 — любой вызов функции их может испортить и из 16 регистров остаются свободными лишь 8 (или 7 если RAX используется умножением/делением или возвращаемым значением функций). И да, мне часто реально не хватает регистров (даже под x64) чтобы всё удержать в регистрах, даже во внутреннем цикле вычислений (или на уровень выше, откуда функции вызываются).

[Sdy]

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

чтобы ускорить свою программу еще в несколько раз (не за счет распределения по ядрам), надо вместо обращения к массиву по индексу A[i], использовать указатели и разыменовывание указателей.

Не надо, если мы говорим о языке С++ или C.
Компилятор автоматически преобразует выражения вида arr[i] к виду *(arr+i).
Просто потому что операция индексации массива в стандарте языка определена как тождественно равная операции разыменования по конкретному адреса.
То есть запись arr[i] по стандарту полностью эквивалентна записи *(arr+i)
Вы можете проверить это на любом современном компиляторе, который следует стандарту.
Другое дело, что например Microsoft со своей Visual Studio ему не следует и как показывает https://godbolt.org/, там эквивалентность этих операций на уровне ассемблера и правда не гарантируется. При этом нередко о C++, использующемся Microsoft, говорят как о Visual C++, как раз-таки чтобы не мешать язык стандарта ISO/IEC с ним.
Добавлю также, что вследствие вышенаписанного, в C++ (как и C) нет разницы и между записями arr[i] и i[arr].

[Mihaylo]

Sdy в сообщении #1435830 писал(а):

Компилятор автоматически преобразует выражения вида arr[i] к виду *(arr+i).

Это не правда. Запись arr[i] безопасна в плане выхода индекса за пределы (возникает системная ошибка), запись *(arr+i) - не контролируется системой. И это не только у Майкрософта, но и в Qt.

Надо правда проверить, чтобы не обманываться.

[arseniiv]

Sdy
Я так понимаю, у Mihaylo имелись в виду указатели даже сразу на элемент, а не сложение каждый раз указателя на нулевой элемент с индексом. То есть (якобы) мы бы экономили на сложении.

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

И это не только у Майкрософта, но и в Qt.

А в машинерии Qt что, какой-то особый компилятор, чтобы его так называть?

[Sdy]

Mihaylo,
Я не хочу повторяться.
Если я написал, что по стандарту они эквиваленты, то это ровно то и означает.
Но уж напишу, что по стандарту, конечно же, в обоих случаях нет никакого контроля выхода за рамки массива.
И Qt предоставляет API, а компилятор вы выбираете сами. Можно выбрать как gcc, так и компилятор Microsoft (или ещё какой).

[Mihaylo]

Qt/MingW

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

Я так понимаю, у Mihaylo имелись в виду указатели даже сразу на элемент, а не сложение каждый раз указателя на нулевой элемент с индексом.

Да, в нейронных сетях происходит пробежка по элементам с инкрементом.