Comments 55
И всё как бы ничего, однако меня всё же насторожила такая казалось бы пустячная «оптимизация» с уклоном в арифметику.
Помимо того, что не следует смешивать разные блоки кода, и операторы ветвления в один блок, используя арифметические псевдооптимизации — понятно, что это общее правило, и долго объяснять, почему это так — конкретно в этом коде серьезный залет, который не приводит ни к какой оптимизации, а только вредит.
В исходном коде были оператор ветвления и сложение, а в новом… еще и умножение.
(На этом можно и закончить, и не говорить о таких пустяках, что в новом коде почему то и операторов сложения больше, и операторы вычитания появились...)
index = opnd + (opnd <= TCL_INDEX_END)*(objc - 1 - TCL_INDEX_END);нет оператора сложения (как и умножение, так и вычитания) между константами, кроме «1 — TCL_INDEX_END»
Надеюсь, не будете выкручиваться, утверждая, что opnd и objc — константы.
Так что учите матчасть сами.
Только умножение он хотел вместо условного перехода (то что вы назвали „оператор ветвления“), так что — ваше „ещё и“ все равно мимо.
На старых процессорах без cmov оптимизация не имеет смысла. На новых процессорах с cmov — тем более.
Так где оно может, хотя бы теоретически, иметь смысл???
Проблема в том, что умножение — весьма дорогая операция.
Да ну? Тот же imul в интелях всего с максимально 3 cycle latency если мне не изменяет память.
А условный переход, он как привило длиннее (в реальности).
И потом у ув. профессора Портера здесь было умножение на 0/1, т.е. как-раз как бы с надеждой заменить при компиляции на что-нибудь более подходящее.
Просто он забыл, что компиляторы давно и буквально следуют первому правилу при процессорной оптимизации (машинного кода):
Always avoid a branch if you can.
Т.е. что условный переход на таком коротком if тоже не получится...
Ну и еще забылось что имеем: branch prediction / ILP, instruction reordering, instruction, TLB and/or data cache (hits/misses/page faults) т.д., и register renaming и прочее впридачу.
Работать компилятором нынче очень сложно. :)
Так где оно может, хотя бы теоретически, иметь смысл???
Я видел вполне себе хорошую реализацию switch на imul для коротких выравненных кусков кода. Даже очень. Побило всё остальное, вплоть до многоуровневых jump-tables, и прочие дериваты.
Другое дело что оно, так-то, не универсально конечно.
И не забывайте, что кэш процессора ограничен. Часто Ofast оптимизация, создающая код чуть длиннее чем O2, много быстрее на искусственных тестах, пока в бою не проявляются проблемы на multithreading, паразитной нагрузке и т.п.
Да ну? Тот же imul в интелях всего с максимально 3 cycle latency если мне не изменяет память.Изменяет. Pentium — 9/11, более старые процессоры — ещё медленнее. И даже на Skylake может до 4 циклов занимать.
Но с учётом того, что на процессорах новее Pentium Pro есть
cmov критическое число — 9.И потом у ув. профессора Портера здесь было умножение на 0/1, т.е. как-раз как бы с надеждой заменить при компиляции на что-нибудь более подходящее.Напишите тогда уж XOR, тогда есть шансы.
Давно, но не буквально. Это мы уже обсуждали.Просто он забыл, что компиляторы давно и буквально следуют первому правилу при процессорной оптимизации (машинного кода):Always avoid a branch if you can.
Я видел вполне себе хорошую реализациюЯ, наверное, ничего не понимаю в колбасных обрезках, но в подобных случаях ведь умножать нужно на константу, а не на переменную… то есть этоswitchнаimulдля коротких выравненных кусков кода. Даже очень. Побило всё остальное, вплоть до многоуровневых jump-tables, и прочие дериваты.
lea, а не imul… сложение, а не умножение…2-operand form, при умножении на 0/1? Вы серьезно?
> Я, наверное, ничего не понимаю в колбасных обрезках
Наверное… :) выше под умножением понималось умножение в сишном коде, как его уже реализует компилятор не очень интересно.
Конкретно в контексте того упомянутого `switch`, ужо не упомнить (а думать некогда), но чисто для примера:
```asm
; в EAX передается значение для switch-а…
; дефоулт всё что больше 50, размер каждой ветки (паддинг) = 24
cmp EAX, 50
ja switch_default
imul EAX, const_padding_size ;# EAX *= 24
jmp EAX
sw0th:
...; instr (24 bytes)
sw1st:
...; instr (24 bytes)
sw2nd:
...; instr (24 bytes)
…
sw50th:
...; instr (24 bytes)
switch_default:
ret
```
2-operand form, при умножении на 0/1? Вы серьезно?При умножении на 0/1 — скорее всего нет. Я не знаю как оно у них зависит от аргументов. У Agnerа таблицы не настолько детализованы.
Наверное… :) выше под умножением понималось умножение в сишном коде, как его уже реализует компилятор не очень интересно.Не очень понятно как сишный код сочетать с «короткими выравненными кусками кода» — это уже явно ассемблерный уровень.
imul EAX, const_padding_size ;# EAX *= 24Тут я бы два LEA поставил. Или LEA + SAL, как компилятор делает:
$ cat test.c
int foo(int x) {
return x*24;
}
$ gcc test.c -march=native -O3 -S -o-
.file "test.c"
.text
.p2align 4,,15
.globl foo
.type foo, @function
foo:
.LFB0:
.cfi_startproc
leal (%rdi,%rdi,2), %eax
sall $3, %eax
ret
.cfi_endproc
.LFE0:
.size foo, .-foo
.ident "GCC: (Debian 6.3.0-18+deb9u1) 6.3.0 20170516"
.section .note.GNU-stack,"",@progbits
Тут та же самая петрушка, что и с переходами. Не всё то, что выглядит как умнодение в C является умножением на ассемблере.P.S. А вообще ваш трюк, как и многое подобное, не нов и не уникален. GCC старых версий подобное творит. С
lea, конечно, не с imul. Впрочем последние версии не заморачиваются…
> if ((index = opnd) <= (-2)) {
В чём проблема инициализировать index сразу значением opnd в примере test2? (int index = opnd) Вы приводите аргументы против смешивания математики и flow в одном выражении, но при этом именно это и делаете в test2.
В чём проблема инициализировать index сразу значением opnd
Как раз это компилятору все равно, а в такой форме оно нагляднее, и речь тут не о том… Да и в оригинальной функции оно не так...
но при этом именно это и делаете в test2.
Совершенно нет, и при "ассемблерном мышлении" как раз проще — результат присвоения в eax, потом cmp eax, и условное действие (переход или присвоение-пересылка).
Все дело в том, что условный переход действие не дешевое, и раньше их часто заменяли, умножением в том числе...
что там компилятор наоптимизировал, выходит иногда боком при исполнении на современном железе с собственной оптимизацией внутри, типа внеочередное или спекулятивное исполнение, параллелизм на уровне команд (ILP) и прочее.
Опция -m arch=686 должна в этом случае помогать.
index = opnd + (~((opnd<-1)-1))&(1 + objc)
вариант с магией битов 2 место, с умножением — 3 место
Но при этом нужно учитывать, что условный оператор != условный переход.
В C нет типа Boolean. Типом результата сравнения является int.
The == (equal to) and != (not equal to) operators are analogous to the relational
operators except for their lower precedence.108) Each of the operators yields 1 if the
specified relation is true and 0 if it is false. The result has type int. For any pair of
operands, exactly one of the relations is true.
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf
Страница 96.
А тут вы вообще хотите, что бы она любое значение выдала, ну вы даете. Ей для этого, что генератор псевдослучайных чисел нужен? Ну или случайный через генератор на физ. феномене?
Но функции в языках программирования не обязательно подчиняется математическим определениям, например:
int foo(int x, int y) { return x % y; }
В C89 для (3, -2) может вернуть как 1, так и -1.
Генератор псевдослучайных чисел тут не нужен. Просто если бы разработчики стандарта сказали, что результат сравнения — любое ненулевое число, то разработчики компилятора могли бы начать экономить такты, к примеру, вместо использования единицы копируя указатель на вершину стека — просто потому, что компилятор знает, что здесь он не ноль, а на данной архитектуре копирование указателя на вершину стека быстрее.
По этой причине эта функция еще и самая большая (порядка 6 тысяч строк + примитивы и макросы)
Сдается мне, не в оптимизациях там проблема.
А можно другие компиляторы clang и VS так же себя ведут?
Под gcc для AArch64 тоже получается одинаковым.
В общем, не настолько компиляторы глупы, как sebres их пытается выставить.
Главным аргументом при выборе между двумя вариантами должна быть читаемость кода, а не то, в какую последовательность команд он оттранслируется конкретной версией компилятора с конкретным набором флагов.
не настолько компиляторы глупы, как sebres их пытается выставить.
А нельзя ткнуть носом, где я пытаюсь их такими выставить?
Наоборот я их всегда, всячески хвалю, например — "Не стоит забывать про оптимизацию в современных компиляторах, которая достигла если не совершенства, то уже очень и очень на уровне."
И потом я же написал — "во всех вариантах (и даже с максимальной оптимизацией) test1 ничем не лучше, а то и проигрывает test2".
Про собственно clang же много историй можно рассказывать. Он у меня был любимый долгое время… даже кастомная собственная сборка с измененным поведением при оптимизации.
Потом я столько всего под clang словил, что окончательно забросил...
смешивается в кучу математика и собственно flow процесса, что например усложняет разбор его для компилятора
--здесь уместнее было написать «усложнял», потому что более навороченным компиляторам уже и такой смешанный код по зубам.
Здесь конкретно да, а в других примерах ещё как посмотреть...
Про "более навороченным компиляторам" тоже могу поспорить.
Оно местами настолько "навороченно", что неявное (а то и неопределённое) поведение на нормальном течении словить можно (было как-то, долго боролся, помог откат на пред. версию).
Из последнего вот к примеру, expressive diagnostics у них вообще таким местом реализован, что варнинг на варнинге и третьим погоняет (даже без "-Wextra"). А если например в проекте варнинг к ошибке преравнивается?
Интересно, а если убрать index, который здесь совсем не нужен, а делать все операции над передаваемым параметром opnd, то результат оптимизации изменится?
А мне кажется, что самое неправильное в данном коммите — полное уничтожение читаемости. До коммита — ясно, что, почему и как, а после — сим-салябим, ахалай махалай, тыдыщ — ЧУДО!
Даже если бы оно работало быстрее, сокращение комментария вместо добавления обоснования применённого метода — чистой воды вредительство.
Поправьте меня если я ошибся.
Не хватает варианта "не занимаюсь пессимизацией кода прямо в процессе разработки".
Я за алгоритмическую оптимизацию — если есть возможность сделать из квадратичной сложности линейную или из линейной логарифмическую — почему нет?
Важно только помнить, что логарифмическая сложность не всегда быстрее линейной :-)
Сколько я видел «сурово оптимизированных» программ с пресловутым алгоритмом маляра Шлемиэля… Не сосчитать. И они все легко «обходятся» совершенно неоптимизированным кодом, в котором пресловутого «Шлемиэля» нету.
А вот если вы всех «Шлемиэлей» извели — тогда уже можно и о тактах думать.
Впрочем есть ощущение, что сегодня, сейчас, закладываться на более старую версию clang'а не стоит — тем более, что и icc и MSVC лучше обрабатывают test2.
Т.е. напрасно — да, ИМХО возможно даже показательно (в качестве примера, отсюда статья).
Однако это писалось однозначно не для того, что бы кого-то тыкать носом.
В общем кто-то мог просто пройти мимо, не оставляя таких «капитанских» и очень содержательных комментариев.
П.С. Ну и наверно стоит всё же немного уважительней относится к людям, тратящим своё время и нервы на опенсорс…
Оптимизация кода в уме, или «Ну так же однозначно быстрее»