Оптимизация кода в уме, или «Ну так же однозначно быстрее»08.03.2018 20:33

habr.png

Намедни работая над одной ошибкой в одном опенсорсном проекте, увидел как коллега (тоже работающий параллельно над той же проблемой) залил такой вот коммит [31a078bec7]: 

   	/*
-	 * Select the list item based on the index. Negative operand means
-	 * end-based indexing (-2, ...), and -1 means out of range.
+	 * Decode end-offset index values.
   	 */
-	if (opnd < -1) {
-	    index = opnd+1 + objc;
-	} else {
-	    index = opnd;
-	}
+	index = opnd + (opnd <= TCL_INDEX_END)*(objc - 1 - TCL_INDEX_END);
   	pcAdjustment = 5;


Изменение само по себе правильное (теперь TCL_INDEX_END есть константное определение (-2)).

И грубо говоря в уме это разворачивается в следующее (все переменные int): 

index = opnd + cmp(opnd, (-2))==>(0 | 1) * (objc - 1 - (-2));


Т. е. он как бы тем самым хотел сэкономить здесь один условный переход.
И всё как бы ничего, однако меня всё же насторожила такая казалось бы пустячная «оптимизация» с уклоном в арифметику.

Во первых, это изменение касается самой «главной» функции в этом проекте (TEBCresume), ибо она ответственна за исполнение байт-кода (JIT скомпилированных инструкций языка TCL). По этой причине эта функция еще и самая большая (порядка 6 тысяч строк + примитивы и макросы) и одна из самых сложных в кодовой базе проекта, с множественными `goto`, головоломными макросами для работы со «стеком» исполнения, свёртка/развертка NRE (nonrecursive evaluation) и т.д. и т.п.

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

Во вторых, по роду деятельности мне часто приходится оптимизировать сишный код, разглядывая его ассемблерное отражение, выжимая доли микро-, а то и нано-секунд, и я часто вижу, что там очень всё совсем не однозначно бывает. Как минимум иногда разворачивая такие вот «экономящие» условный jump конструкции обратно в if или даже if/else, я видел улучшение как и в результирующем ассемблерном коде, так и явно при конечном сравнении производительности результатов исполнения.

Собственно к чему я все это писал — хотелось на примере показать как оно бывает, ну и раз уж коснулись этой темы, собрать немного статистики. Посему пара опросов в конце статьи…

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

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

По понятным причинам, не будем разбирать это всё в оригинальной функции…

Поэтому собсвенно в качестве примера две функции test1 (оптимизация в арифметике), и test2 (flow как оно есть с одним `if`), и результирующий ассемблер для обоих функций в разных версиях компилятора, на примере gcc, проверялось с -O2 и -Ofast (практически без, а в trunk совсем без изменений):

c/c++ 
int test1(int opnd, int objc) {
  int index;

  index = opnd + (opnd <= (-2)) * 
                 (objc - 1 - (-2));

  return index;
}


int test2(int opnd, int objc) {
  int index;

  if ((index = opnd) <= (-2)) {
    index += (objc - 1 - (-2));
  }

  return index;
}

x64, gcc 5.1: 
;#test1(int,int)
xor eax, eax
cmp edi, -1
setl al
add esi, 1
imul esi, eax
lea eax, [rsi+rdi]
ret


;#test2(int,int)
lea edx, [rdi+1+rsi]
mov eax, edi
cmp edi, -2
cmovle eax, edx
ret

x64, gcc 7.3: 
;#test1(int,int)
xor eax, eax
cmp edi, -1
setl al
add esi, 1
imul eax, esi
add eax, edi
ret


;#test2(int,int)
lea ecx, [rdi+1+rsi]
mov eax, edi
cmp edi, -1
cmovl eax, ecx
ret

x64, gcc (trunk): 
;#test1(int,int)
add esi, 1
mov eax, 0
cmp edi, -1
cmovge esi, eax
lea eax, [rsi+rdi]
ret


;#test2(int,int)
mov eax, edi
cmp edi, -1
lea ecx, [rdi+1+rsi]
cmovl eax, ecx
ret

x86, gcc 5.1: 
;#test1(int,int)
mov ecx, [esp+4]
mov edx, [esp+8]
xor eax, eax
cmp ecx, -1
setl al
add edx, 1
imul eax, edx
add eax, ecx
ret


;#test2(int,int)
mov eax, [esp+4]
mov edx, [esp+8]
lea edx, [eax+1+edx]
cmp eax, -2
cmovle eax, edx
ret

x86, gcc 7.3: 
;#test1(int,int)
mov ecx, [esp+4]
mov edx, [esp+8]
xor eax, eax
cmp ecx, -1
setl al
add edx, 1
imul eax, edx
add eax, ecx
ret


;#test2(int,int)
mov eax, [esp+4]
mov edx, [esp+8]
lea edx, [eax+1+edx]
cmp eax, -1
cmovl eax, edx
ret

x86, gcc (trunk): 
;#test1(int,int)
mov edx, [esp+4]
mov eax, [esp+8]
mov ecx, 0
add eax, 1
cmp edx, -1
cmovge eax, ecx
add eax, edx
ret


;#test2(int,int)
mov eax, [esp+4]
mov edx, [esp+8]
cmp eax, -1
lea edx, [eax+1+edx]
cmovl eax, edx
ret


Наглядней (с подсветкой и т.д.) это можно увидеть тут или тут.

Что имеем в остатке:

  • во всех вариантах (и даже с максимальной оптимизацией) test1 ничем не лучше, а то и проигрывает test2
  • test2 реализуется компилятором совсем без условного перехода, как можно было подумать, например просто используя условную cmovl
  • даже нативный байт-код test2 более читабелен
  • байт-код test2 короче, местами более удобен для ILP/SEP, меньше размывает CPU-кэш (как минимум instruction cache).


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

Ну и в полном виде всей функции компилятор немного изменил весь flow, что на некоторых искусственных тестах производительности показало падение до одного — двух процентов (может отличатся для других компиляторов/систем/платформ и т.д.).

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

Теперь почему как мне кажется не нужно заниматся такой «слепой» оптимизацией в уме:

  • смешивается в кучу математика и собственно flow процесса, что например усложняет разбор его для компилятора
  • при оптимизации в процессе компиляции у математики ветвление немного слабее чем у того же flow-дерева и inlining-процессов, нужен контроль за overflow, неявным поведением и т.д. (так сложилось исторически, грубо говоря у математики немного смещенный фокус при оптимизации оной).
  • исходный код становится неявным, как минимум тормозит review и анализ (иногда просто очень трудночитаем).


Этот список можно продолжать до бесконечности, например при компиляции исходников под конкретный процессор (если поддерживается компилятором), явное требуемое поведение оставит компилятору (или новой версии его) больше шансов подобрать оптимальный сценарий, например используя какие-нибудь новые инструкции процессора, или вырезав «дубликаты» перевернув весь код полностью и т.д.

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

P.S. Всех девчонок с праздником!

За сим к опросам…

© Habrahabr.ru