13
Скорость
На самом деле, Лисп сочетает в себе два языка: язык для быстрого на писания программ и язык для написания быстрых программ. На пер вых этапах создания программы вы можете пожертвовать ее скоростью ради удобства разработки, а когда ее структура примет окончательную форму, можно воспользоваться инструментами языка, позволяющими увеличить скорость работы программы.
Довольно сложно давать общие рекомендации по поводу оптимизации из-за внушительного разнообразия реализаций Common Lisp. Дейст вие, ускоряющее выполнение вашей программы в одной из них, может замедлить работу в другой. Чем мощнее язык, тем дальше он отстоит от аппаратной части, а чем дальше вы от аппаратной части, тем выше шансы, что разные реализации по-разному будут возвращаться к ней при генерации программного кода. Поэтому, несмотря на то что некото рые методики, описанные ниже, почти наверняка ускорят выполнение кода в любой реализации, все же не стоит забывать о рекомендательном характере содержимого этой главы.
13.1. Правило бутылочного горлышка
Независимо от реализации есть три момента, касающиеся оптимиза ции: она должна быть сосредоточена на бутылочных горлышках, она не должна начинаться слишком рано и она должна начинаться с алгорит мов. Пожалуй, по поводу оптимизации важнее всего понять, что в лю бой программе, как правило, есть несколько узких мест, выполнение которых занимает большую часть времени. По мнению Кнута, «подав ляющая часть времени выполнения программы, не связанной с вводом- выводом, сосредоточена в примерно 3% исходного кода».° Оптимизация таких участков даст существенно большее увеличение скорости, чем оптимизация остальных частей, которая будет пустой тратой времени.
13.2. Компиляция |
221 |
Поэтому исключительно важный первый шаг оптимизации любой про граммы – поиск подобных узких мест, или бутылочных горлышек. Мно гие реализации Лиспа включают собственные профилировщики, кото рые наблюдают за выполнением программы и предоставляют отчет о времени, затраченном на каждую из ее частей, выявляя тем самым уз кие места. Профилировщик – ценный инструмент, совершенно необхо димый для создания действительно эффективного кода. Если ваша реа лизация Лиспа включает профилировщик, то наверняка предоставля ет и документацию на него, которую следует изучить. Если же такого инструмента у вас нет, то узкие места придется угадывать самостоя тельно, и вы будете удивлены, когда узнаете, как часто подобные догад ки бывают ошибочными.
Следствие правила бутылочных горлышек: не стоит вкладывать слиш ком много усилий в оптимизацию на ранних стадиях написания про граммы. Кнут предлагает еще более жесткую формулировку: «Прежде временная оптимизация является корнем всех зол (или, по крайней ме ре, большей части) в программировании».° Пока программа не написа на, сложно сказать, где возникнет узкое место, поэтому не тратьте свое время зря. Кроме того, оптимизация затрудняет модификацию, и по пытка оптимизировать программу в момент ее написания сродни по пытке писать картину быстросохнущими красками.
Вероятность того, что программа получится хорошей, возрастет, если на каждой подзадаче можно будет сфокусироваться в подходящий момент времени. Одним из достоинств Лиспа является возможность работать в разном ритме: быстро писать медленный код или медленно писать бы стрый код. На первых этапах вы используете первый метод, а на стадии оптимизации переключаетесь на второй. Эта модель соответствует пра вилу бутылочного горлышка. В низкоуровневых языках, таких как ас семблер, вы фактически оптимизируете каждую строку кода. Большая часть этих усилий тратится напрасно, так как бутылочные горлышки составляют лишь небольшую часть всего кода. Более абстрактный язык позволяет уделить узким местам значительную долю времени, поэтому при меньших усилиях вы получаете существенно большую выгоду.
Приступая к оптимизации, начинайте с самого верху. Для начала убе дитесь, что используете наиболее оптимальный алгоритм, и лишь по том переходите к низкоуровневым трюкам при написании кода. Потен циальная выгода велика – возможно даже настолько, что вам, может быть, вообще не придется прибегать к каким-либо трюкам. Это утвер ждение нужно сочетать с предыдущим правилом: часто решение об ал горитме нужно принимать на ранней стадии написания программы.
13.2. Компиляция
Для управления процессом компиляции доступно пять параметров: speed (скорость производимого кода), compilation-speed (скорость самого
222 |
Глава 13. Скорость |
процесса компиляции), safety (количество проверок на ошибки в объ ектном коде), space (размер памяти, выделяемой для объектного кода) и debug (объем информации, оставляемой в коде для отладки) .
Параметры компиляции не являются переменными в привычном пони мании. Это своего рода веса, определяющие важность каждого пара метра: от 0 (не важно) до 3 (очень важно). Представим, что узкое место находится во внутреннем цикле некоторой функции. Мы можем доба вить декларацию следующего вида:
(defun bottleneck (...) (do (...)
(...) (do (...)
(...)
(declare (optimize (speed 3) (safety 0)))
...)))
Как правило, подобные декларации добавляются лишь после заверше ния основной работы по созданию программы.
Чтобы глобально запросить наиболее быстрый компилируемый код, можно сказать:
(declaim (optimize (speed 3) (compilation-speed 0) (safety 0)
(debug 0)))
Это весьма радикальный и часто ненужный шаг. Не забывайте про бу тылочное горлышко.1
Важным классом оптимизаций, производимых компиляторами Лиспа, является оптимизация хвостовых вызовов. Задавая максимальный вес параметра speed, вы включаете эту опцию, если она поддерживается компилятором.
Вызов считается хвостовым, если после него не нужно ничего вычис лять. Следующая функция возвращает длину списка:
(defun length/r (lst) (if (null lst)
0
(1+ (length/r (cdr lst)))))
Данный рекурсивный вызов не является хвостовым, так как его значе ние передается функции 1+. А вот в следующей версии есть хвостовая рекурсия:
(defun length/tr (lst) (labels ((len (lst acc)
(if (null lst)
1Старые реализации могут не предоставлять declaim. В этом случае исполь зуйте proclaim с цитируемым аргументом.
13.2. Компиляция |
223 |
acc
(len (cdr lst) (1+ acc))))) (len lst 0)))
Вообще говоря, хвостовая рекурсия имеет здесь место в локальной функции len, поскольку рекурсивный вызов является последним дей ствием в функции. Вместо того чтобы вычислять результирующее зна чение на обратном пути рекурсии, как это делает length/r, она аккуму лирует его на пути вперед. Для этого и нужен аргумент acc, значение которого возвращается в конце рекурсивного вызова.
Хороший компилятор может преобразовывать хвостовой вызов в goto, и таким образом хвостовая рекурсия скомпилируется в обычный цикл.° В машинном коде, когда управление впервые передается той его части, которая реализует функцию len, на стек кладется информация, указы вающая, что нужно сделать для завершения вызова. Но, поскольку по сле самого рекурсивного вызова делать ничего не надо, эти инструкции остаются действительными также и для второго вызова: для возврата из второго вызова нужно сделать то же самое, что и для возврата из пер вого. Таким образом, мы можем просто заменить старые аргументы функции новыми значениями, а после этого прыгнуть назад к началу функции и действовать так, как если бы это был второй вызов. При этом нет необходимости делать реальный вызов функции.
Другой способ уйти от затрат на полноценный вызов функции – заста вить компилятор встраивать функции построчно (inline). Это особенно ценно для небольших функций, затраты на выполнение которых сопо ставимы с затратами на сам вызов. Например, следующая функция вы ясняет, является ли ее аргумент списком или одиночным элементом:
(declaim (inline single?))
(defun single? (lst)
(and (consp lst) (null (cdr lst))))
Интерактивный или интерпретируемый
Лисп – это интерактивный язык, но это не обязывает его быть ин терпретируемым. Ранние версии Лиспа реализовывались как ин терпретаторы, в результате чего сложилось мнение, что все пре имущества Лиспа вытекают из его интерпретируемости. Эта идея ошибочна: Common Lisp является интерпретируемым и компи лируемым языком одновременно.
Некоторые реализации Common Lisp и вовсе не используют ин терпретацию. В них все, что вводится в toplevel, компилируется перед вычислением. Таким образом, называть toplevel интерпре татором не только старомодно, но и, строго говоря, ошибочно.