vodimitriy9 янв в 10:00

Может ли устареть инкремент: обзор выполнения оператора на современных вычислительных платформах

Средний

19 мин

8.9K

Программирование * C * C++ * Процессоры

Обзор

+13

Комментарии 25

BorisU 9 янв в 10:23

Правильнее сказать, что на большинстве современных платформ команда сложения (ADD) выполняется быстрее, чем инкремент (INC).

Да неужели 😂

yamifa_1234 9 янв в 20:23

А это кстати неожиданная информация. Надеюсь автор на 100% уверен в ней. А то как то даже не верится

AndreyDmitriev 10 янв в 16:47

У инструкций процессора есть два параметра - латентность и пропускная способность. Формально они одинаковы что для инкремента, что для сложения. Но операция сложения устанавливает доп флаги, чего не делает inc и в принципе (в теории) может влиять на параллелизацию последующих инструкций.

Ну то есть вот такой цикл

    xor rax, rax
    mov rcx, 1000
L0: add rax, 1
    cmp rax, rcx 
    jl L0

может оказаться быстрее чем

    xor rax, rax
    mov rcx, 1000
L0: inc rax
    cmp rax, rcx 
    jl L0

за счёт того, что в первом случае последующие cmp и jl склеятся вместе, а во втором случае - нет. Я только что проверил это на Хасвелле, но разницы вообще не вижу, а современный ноут на рапторе я не стал домой тащить, это я в понедельник проверю.

BorisU 12 янв в 12:43

проверка в uiCA показывает, что и то и другое исполняется 1 такт на итерацию :)

AndreyDmitriev 12 янв в 13:02

Абсолютно верно, но, пожалуй, только в том случае, если это предсказанный и взятый переход (что на подавляющем большинстве итераций так и есть), в этом случае он исполнится на шестом порту (это я проверял), а ALU будет свободен для параллельной команды, поэтому всё вместе за один такт, да.

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

Balling 11 янв в 22:51

Да, Intel может сделать 5 операций сложения за clock cycle, если ОПЕРАЦИИ НЕЗАВИСИМЫ, НО ДАЖЕ ЕСЛИ зависимы, например x +1000 -500: (начиная с Alder Lake) операции типо +1000 или там -500 исполняются с нулевой латентностью, т.е. вообще не влияют на скорость.

BorisU 12 янв в 12:45

там есть тонкости, есть предельное (и не такое большое значение) инкремента после которого сложение таки будет исполняться, но в таких простых примерах этого не увидеть, у процессора достаточно ALU

AndreyDmitriev 12 янв в 13:17

Мой эксперимент на Raptor Lake показывает, что те же пять (зависимых) команд, но только на Р ядрах. А вот на Е ядрах - одна команда сложения за такт, как и на Haswell. Это и uops.info вроде подтверждает.

D_T 9 янв в 10:42

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

Современные компиляторы далеко ушли, включенный оптимизатор сам заменит i++ на ++i если это действительно дает какое-то ускорение. В оптимизаторы зашиты наиболее эффективные решения компиляции, которые позволят по максимуму использовать скрытые резервы процессора.

Если есть возможность затестите компилятор от Intel и скорее всего получите еще более быстрое решение.

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

vodimitriy 9 янв в 13:19

Доброго дня! Про компилятор полностью согласен. В руководствах по оптимизации приложений приводят следующие шаги оптимизации (в порядке приоритета):

1) Изучите и включите параметры оптимизации компилятора.

2) Если оптимизации компилятора не хватает, то поищите фреймворки или библиотеки, оптимизированные под вашу платформу, и замените свой код на них.

3) Запустите профайлер, найдите узкие места. Попытайтесь оптимизировать алгоритм и структуры данных. Например, использование «дерева» значительно сократит число итераций поиска (или в целом лишней работы) относительно связного списка.

4) Используйте оптимизацию на уровне ассемблера (ISA).

5) Оптимизируйте работу с кэшем.

6) Оптимизируйте код под особенности микроархитектуры (объединение операций, повышение пропускной способности инструкций и т.д.).

Спасибо за напоминание о компиляторе Intel. Обязательно его протестирую.

Пока проверил в Compiler Explorer поведение x86‑64 ICC 2021.6.0. Без оптимизации в обоих циклах используется сложение. При -O3 для первого цикла – INC, для второго – смесь ADD и INC. При -Os для первого цикла – INC, для второго – ADD, но все команды векторные, в отличие от MSVC, поэтому цикл получается очень компактным.

BorisU 9 янв в 13:41

Актуальный компилятор от Intel называется icx
Есть такой чудный ресурс https://uica.uops.info/ который покажет вам реальные такты, вместо гадания, что быстрее.

vodimitriy 9 янв в 14:14

Благодарю за ссылку на анализатор кода x86_64. Обязательно ознакомлюсь и протестирую.

shigorin 10 янв в 21:33

Держите и по эльбрусу (спасибо @a1batross); что на VLIW ещё интересно в обсуждаемом плане, так это то, что можно посмотреть непосредственно исполняемое на железе, а не "внешние" последовательные команды, которые затем декодер пережуёт в совсем иное.

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

Melirius 9 янв в 11:25

Мейерс не говорит про примитивные типы, он про сложные: постинкремент размножает объекты, пред- - нет. В большинстве случаев это некритично, компиляторы сейчас умные, но привычка у меня осталась.

vodimitriy 9 янв в 13:44

Добрый день. Да, ошибку увидел. В начале статьи уточнил, что рекомендация особенно актуальна для пользовательских типов. Для встроенных типов компиляторы не генерируют более производительный код. А в выводах указал эту рекомендацию как общую.

Jijiki 9 янв в 16:15

насколько я знаю, инкремент зависит от реализации, если инкремент просто по офсету стека-текущего кадра фрейма, берёт и делает +1 это 1 ситуация, когда инкремент пушится/грузится/инкрементируется/загружается это другое, это разные операции с точки зрения определения инкремента получается, но технически они делают 1 и тоже поидее

по асемблеру я не смотрел, но по синтаксису около этого вроде, я со стеком делал, поэтому запомнил

checkpoint 9 янв в 22:03

Автор, а где результаты измерений на реальном железе ?

В целом, "не верь написанному" в современнром мире как никогда верный подход.

rukhi7 10 янв в 06:29

Почему эта тема очень напоминает мне метафору про академию бубна в музыке?

Тут у нас академия инкремента в программировании.

Gariks 10 янв в 10:50

В программировании мы постоянно балансируем между читаемостью кода, удобством сопровождения, эффективностью разработки и производительностью, и даже внутри каждой из этих областей. Например, оптимизация производительности часто предполагает компромисс между экономией памяти, скоростью выполнения и сложностью реализации. В реальных проектах большинство участков кода не требуют максимальной производительности. Приоритет удобства сопровождения и читаемости, как правило, перевешивает экономию каждого байта или микросекунды.

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

alan008 10 янв в 15:08

Как хорошо, что современные системы упираются чаще не в процессор, а в диск, сеть или на худой конец в объекты многопоточной синхронизации, чтобы не приходилось себя грузить тем, какой инкремент эффективнее (сарказм, но так и есть).

shigorin 10 янв в 21:34

Ещё сэр Сеймур Крей говаривал, что трюк не в том, чтоб построить быстрый процессор, а в том, чтобы построить быструю систему. Но есть нюанс...

rblaze 15 янв в 21:45

AI компании смотрят на вас с недоумением и закупают ещё один грузовик GPU.

alan008 16 янв в 04:09

Это другая крайность. Всё-таки миллиард (или сколько их там) персональных компьютеров в мире выполняет (пока ещё) "классические" программы, не связанные с ИИ, которым, слава богу, хватает типичного/обычного набора железа.

falakh 11 янв в 16:59

C был создан на платформе PDP11, смотрим для примера PDP11/04 handbook, instruction timing. Двухоперандная команда сложения регистров 3.17 мкс. Однооперандная команда инкремента регистра 2.65 мкс. Команда сравнения регистра с непосредственным значением 3.17+2.66=5.83 мкс. Команда сравнения регистра с непосредственным значением и постинкрементом регистра 3.17+2.66+1.20=7.03. Выигрыш использования очевиден. Собственно синтаксис C делался под платформу PDP11, где непосредственно в ISA есть пост/пре инкремент/декремент регистров.

AndreyDmitriev 11 янв в 20:35

PDP11, где непосредственно в ISA есть пост/пре инкремент/декремент регистров.

Справедливости ради надо заметить, что там вроде только пост инкремент и пре декремент были, а вот пре инкремента и пост декремента я не помню. Впрочем это 30+ лет тому назад было, может я забыл. Пятая глава в инструкции MACRO-11.

Хотя, конечно, циклы с постинкрементом по обоим операндам типа

     MOV #SRC, R1
     MOV #DST, R2
10$: MOVB (R1)+, (R2)+
     BNE  10$

просто гениальны - это то, чего в интеловском асме не хватает.

Зато у интела циклы типа

	mov rax, 1_000_000_000
	xor rcx, rcx
.10:
	add rcx, 1
	cmp rcx, rax
	jl .10

или

.10:
	inc rcx
	cmp rcx, rax
	jl .10

"проворачиваются" за один такт, так как инструкции обрабатываются параллельно на разных портах проца (jl фьюзится только если выполняется предсказанный переход, но тут так оно и есть), чего дековскому процессору и не снилось.

Обычно, кстати, декремент используется, это экономит сравнение, но на скорость не влияет, тут ровно столько же тактов (просто выше было 3 IPC, а ниже будет 2 IPC):

	mov rсx, 1_000_000_000
.10:
	dec rcx
	jnz .10

Это выше для хасвелла справедливо, а на рапторе я завтра проверю.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий