2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Арифметика указателей vs индексация
Сообщение17.01.2020, 06:11 


12/07/15
3316
г. Чехов


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

 Профиль  
                  
 
 Re: Распараллеливание программы (ядра/потоки)
Сообщение17.01.2020, 09:06 


27/08/16
10217
Mihaylo в сообщении #1435579 писал(а):
Второй момент: чтобы ускорить свою программу еще в несколько раз (не за счет распределения по ядрам), надо вместо обращения к массиву по индексу A[i], использовать указатели и разыменовывание указателей. Я такое делал, это реально ускоряет программу.
Оптимизация программы была отключена? На самом деле, этот совет может ешё и замедлить программу, из-за алиасинга.

 Профиль  
                  
 
 Re: Распараллеливание программы (ядра/потоки)
Сообщение17.01.2020, 14:03 
Экс-модератор
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Распараллеливание программы (ядра/потоки)
Сообщение17.01.2020, 17:50 


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

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

 Профиль  
                  
 
 Re: Распараллеливание программы (ядра/потоки)
Сообщение17.01.2020, 18:15 


27/08/16
10217
Mihaylo в сообщении #1435702 писал(а):
Замедления не было, было однозначное ускорение.
В таких случаях полезно смотреть на ассемблер, что именно ускорилось? Современные компиляторы умеют сами преобразовывать итерацию индексов в итерацию указателей.

 Профиль  
                  
 
 Re: Распараллеливание программы (ядра/потоки)
Сообщение17.01.2020, 18:18 
Заслуженный участник
Аватара пользователя


16/07/14
9151
Цюрих
Mihaylo в сообщении #1435702 писал(а):
Нейронные сети
Так там же всё равно нужно либо передавать ссылку на данные в какой-нибудь cblas, либо руками грузить всё в simd регистры (компилятор, который умеет в simd но не умеет в такую оптимизацию указателей).

 Профиль  
                  
 
 Распараллеливание программы (ядра/потоки)
Сообщение17.01.2020, 19:00 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Арифметика указателей vs индексация
Сообщение17.01.2020, 22:10 
Заслуженный участник


20/08/14
11780
Россия, Москва
Пожалуй стоит пояснить подробнее, раз выделили в специальную тему.
Ситуация с одним и даже двумя массивами не интересна, что указатели, что индексы, всё едино в плане скорости. Возьмём для определённости сразу 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. Всё написано из головы без проверки, могут быть опечатки. Что вместо этого нагеренит компилятор ЯВУ — даже не спрашивайте, боюсь заранее.

 Профиль  
                  
 
 Re: Арифметика указателей vs индексация
Сообщение18.01.2020, 10:05 


27/08/16
10217
Dmitriy40 в сообщении #1435746 писал(а):
Возьмём для определённости сразу 100 массивов
В одной функции нижнего уровня? Выглядит как плохо спроектированная программа. :mrgreen:

Dmitriy40 в сообщении #1435746 писал(а):
Посмотрим во что выльется код

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

 Профиль  
                  
 
 Re: Арифметика указателей vs индексация
Сообщение18.01.2020, 15:27 
Заслуженный участник


20/08/14
11780
Россия, Москва
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) чтобы всё удержать в регистрах, даже во внутреннем цикле вычислений (или на уровень выше, откуда функции вызываются).

 Профиль  
                  
 
 Re: Арифметика указателей vs индексация
Сообщение18.01.2020, 17:23 


07/08/16
328
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].

 Профиль  
                  
 
 Re: Арифметика указателей vs индексация
Сообщение18.01.2020, 18:40 


12/07/15
3316
г. Чехов
Sdy в сообщении #1435830 писал(а):
Компилятор автоматически преобразует выражения вида arr[i] к виду *(arr+i).

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

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

 Профиль  
                  
 
 Re: Арифметика указателей vs индексация
Сообщение18.01.2020, 18:42 
Заслуженный участник


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

Mihaylo в сообщении #1435842 писал(а):
И это не только у Майкрософта, но и в Qt.
А в машинерии Qt что, какой-то особый компилятор, чтобы его так называть?

 Профиль  
                  
 
 Re: Арифметика указателей vs индексация
Сообщение18.01.2020, 18:49 


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

 Профиль  
                  
 
 Re: Арифметика указателей vs индексация
Сообщение18.01.2020, 20:04 


12/07/15
3316
г. Чехов
Qt/MingW

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 40 ]  На страницу 1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group