Недавно я увидел следующую рекомендацию по рефакторингу кода с целью оптимизации:
Изначальный вариант Оптимизированный вариант return pow (base, exp/2) *
pow (base, exp/2); let result = pow (base, exp/2);
return result * result;
В книге было написано, что результатом такого рефакторинга будет увеличение скорости работы представленного участка кода. Но почему такой рефакторинг должен привести к ускорению работы этого кода? Большинство авторов/советчиков/специалистов не раскрывают суть своих советов и не дают понимания почему что-либо нужно делать так или иначе. Если вам интересно действительно ли здесь произошло ускорение работы и за счёт чего, то читайте — эта заметка для вас. В ней я рассмотрю, что происходит на вычислительной машине в данной ситуации, чем достигается результат, поясню как именно происходит оптимизация и дам информацию для некоторого понимания «масштаба» этой оптимизации. Пояснения в этой заметке раскрывают суть подобной оптимизации не только в данном случае — а в общем. Вы сможете применять это во множестве подобных ситуаций в вашей практике.
По синтаксису можно предположить, что представленный участок кода написан на JavaScript'е. Я же буду работать на общепринятых языках ИТ/ВТ — С, Aseembler x86_64 и стандартном ABI x86_64.
Для начала мы видим, что автор, ценой добавления ещё одной переменной, сократила вызовы функции pow () в два раза. Рассмотрим, что происходит при вызове функции pow (). Её прототип выглядит следующим образом:
double pow (double x, double y);Из прототипа понятно, что функция работает с параметрами с плавающей точкой и возвращает такой же результат, а это значит, что она будет задействовать сопроцессор (FPU).
Сокращение вызовов функции pow () действительно даёт оптимизацию, и вот почему. Вызов любой функции требует ощутимых накладных расходов. Рассмотрим, что происходит на центральном процессоре при вызове функции в общем, и в частности при вызове функции pow (). В скобках, рядом с командами процессора, стоит приблизительное количество «циклов» (микроопераций) процессора на команду. Рассматриваем на примере x86-ой машины:
1. (При необходимости) вычисление или каким-то иным образом получение всех входных параметров, передаваемых функции (в данном примере это вычисление выражения exp/2). Здесь возможна работа с памятью (а она медленная) и вызовы других, вложенных функций. Если они есть, то стоит пройти все их начиная с этого же пункта.
2. «Раскладывание» параметров, вычисленных или полученных на предыдущем этапе в соответствии с ABI. После вычисления их, они могут оказаться в «местах» (память, регистры), не соответствующих сигнатуре рассматриваемой функции. Это некоторое количество команд mov (~1).
3. Вызов команды call (~10), которая, в свою очередь, сохраняет адрес возврата в стеке, затем осуществляет переход потока выполнения на (указанный адрес) рассматриваемой нами функции.
4. Сама функция pow (), как и любая другая, имеет в себе «преамбулу» (или «пролог»). В этой секции кода происходит сохранение регистров общего назначения путём выполнения нескольких команд семейства push, резервирование пространства в стеке для внутренних нужд функции несколькими манипуляциями с указателем стека. Напомним, что всё это уже происходит один раз в нашей, вызывающей функции.
5. Так как pow () работает с числами с плавающей точкой, она должна сохранить регистры и состояние сопроцессора — так называемую «среду сопроцессора», включающую в себя стек сопроцессора, регистры его состояния, управления, тегов, указатели данных и команд. Так же функция должна сбросить состояние FPU при входе, так как неизвестно в каком состоянии он будет к этому моменту. К счастью у нас есть простые команды для сохранения всей среды сопроцессора — fsave/fnsave (120-150 и более) и finit/fninit (15-20 и более) — для сброса его состояния. Как эти, так и описанные ниже команды восстановления среды FPU, достаточно тяжёлые, так как работают с достаточно большим объёмом информации — всей средой сопроцессора и с памятью (а она, не забываем, у нас — медленная).
6. pow (), вероятно, имеет множество проверок и инициализацию локальных переменных в своей реализации, а они нам здесь не нужны.
8. После завершения своей работы, функции нужно восстановить регистры FPU и его состояние (что так же уже, возможно, делается в нашей функции). Это команда frstor (~100).
9. В конце функции есть «эпилог», включающий в себя восстановление состояния стека — некоторые манипуляции с указателем стека и регистров общего назначения CPU при выходе — выполнение нескольких команд семейства pop.
10. По завершению вызывается команда ret (15-25), которая извлекает адрес возврата из стека и изменяет указатель текущей инструкции процессора на этот адрес. Таким образом, модуль выборки команд x86, после окончания обработки команды ret, начнёт загружать и выполнять команды с адреса, хранящегося в указателе текущей инструкции.
На ARM'е накладные расходы будут схожими.
Таким образом, мы видим, что основные накладные расходы, исключением которых достигнута оптимизация в этом примере, заключаются в управлении потоком исполнения, исключении некоторых проверок, встроенных в вызываемую функцию (что, в данной ситуации, нужно лишь для вычисления значения, которое уже есть).
Но есть и ещё один нюанс. Мы никогда не знаем сколько раз операционная система переключит контекст нашего приложения (в данной ситуации — функции), пока оно работает. А любая, современная операционная система работает по принципу вытесняющей многозадачности. Следовательно, чем меньше список команд, требуемый для получения результата — тем больше вероятность, что наш код будет прерван меньшее количество раз — наша задача будет делиться на меньшее количество квантов выделяемого времени. В критических ко времени вычислениях, когда результат зависит от внешних обстоятельств, например — поток данных, приходящих по сети, такая оптимизация может глобально улучшить результат работы приложения (либо и вовсе спасти код/алгоритм от признания непригодным).
Из этого можно сделать вывод, что такая оптимизация особенно желательна в критичных местах — в «верхних половинах» kernel-space (там лучше вообще не делать никаких вычислений, но мы рассматриваем оптимизацию через сокращение количества вызовов функций в общем), в обработчиках прерываний на Bare-Metal/RTOS.
Теперь опишем, что происходит в оптимизированном варианте. Умножая, в данной ситуации, число само на себя, без вызова функции, мы всего лишь пишем одну команду из семейства fmul, которая в упрощённом варианте (при правильном использовании) умножает два верхних регистра FPU и кладёт результат в самый верхний — ST(0). Который по правилам ABI x86_64, в свою очередь, является возвращаемым значением функции, работающей с числами с плавающей точкой. А если мы пойдём дальше, и сами будем писать код этих операций, то мы сделаем так, чтобы к моменту этого умножения, у нас операнды были уже в двух верхних регистрах FPU, в правильной последовательности. Вот какая оптимизация происходит — практически автоматическая работа процессора на нас.
Кто-то может возразить, что x86-ая машина имеет множество оптимизаций и, что, благодаря им, многие операции из рассмотренного участка кода будут выполнены в параллель, на опережение, или вовсе опущены. Да, это так. Но зачем нам грузить вычислительную машину лишними операциями, когда мы можем избежать их на этапе написания кода? Пусть она использует свои возможности для оптимизации чего-то другого.
P.S.
По описанным выше причинам, предостерегу вас от достаточно очевидного манёвра с этим участком кода. А именно, использовать вместо умножения вызов всё той же функции pow () с result в качестве первого параметра и двойкой — в качестве второго. Умножение числа на само себя — есть возведение его в квадрат. Математически и идеологически, кому-то это может показаться правильнее или «красивее», но технически — правильнее так, как мы рассмотрели. В противном случае это будет «пример плохого кода».
P.P.S.
А вот, например, сократить количество машинных операций, передавая в функцию выражение exp/2 вычисленное заранее извне — хороший вариант. Во-первых, внутри функции не будет заниматься лишнее место на стеке (для проведения этой операции). Во-вторых, при множественном вызове такой функции, с одинаковым значением какого-то из параметров, сократится время на вычисления — он будет вычислен единожды в вызывающей функции и затем повторно использоваться. А если у нас exp/2 будет равно двойке, то и вовсе проще дважды умножить base на себя и выйти, вернув этот результат.
