Let Over Lambda - 50 Years of Lisp / Let Over Lambda - 50 лет Lisp-у: Глава 7 - Темы Эффективности Макросов

7.1 Лисп быстр

Charlz_Klug 07.04.14 в 06:06

Если вы облицовываете пол плиткой, размер которой с ноготь, вы не тратите излишних усилий.
- Пол Грем

Charlz_Klug 07.04.14 в 06:10

Некоторые люди думают что лисп - это медленный язык. Это высказывание может быть правдивым для некоторых ранних реализаций лиспа, но явно ложное в наши дни. На самом деле такие современные лиспы как COMMON LISP спроектированы так, чтобы мы могли использовать макросы и тем самым ускорять лисп. По-настоящему ускорять. Основная цель этой главы возможно удивит вас если вы верите в миф о производительности, который гласит что низкоуровневые языки более эффективны чем лисп. Эта глава демонстрирует что лисп может быть более быстрым чем любые другие языки программирования и что такие низкоуровневые языки как C на самом деле - по причине отсутствия макросов - уступают лиспу в производительности. Лисп позволяет нам писать код более эффективный чем код, написанный на других языках. Особенно при разработке больших и сложных программ, макросы позволяют создавать код, превосходящий в производительности Блаб языки. Иногда языки проектируются с упором на эффективные реализации, но чаще они проектируются с расчётом предоставления максимальной выразительности для программиста. Когда мы выбираем выразительность, то здесь лисп оказывается более быстрым. По-настоящему быстрым.

Charlz_Klug 07.04.14 в 09:03

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

Charlz_Klug 08.04.14 в 06:14

Но конечно другие языки могут быть написаны в менее эффективном, но более удобном способе. Например Perl позволяет программисту творить чудеса с помощью одного короткого выражения, но, помимо этого содержит в себе много способов улучшения быстродействия кода. Так о чём мы говорим когда рассуждаем о том, что лисп позволяет нам контролировать эффективность наших абстракций так, как это не в состоянии сделать ни один язык? Как вы можете ожидать, ответ заключается в теме нашей книги: макросы.

Charlz_Klug 08.04.14 в 07:08

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

Charlz_Klug 08.04.14 в 10:38

Все реализации языков нуждаются в хороших алгоритмах. Алгоритм - это предположительно хорошо исследованное процедурное описание исполнения программной задачи. На разработку алгоритма расходуется гораздо больше усилий чем на их реализацию, поэтому алгоритмы используются повсеместно во всех компьютерных науках. Кто-то уже описал как, почему и как быстро работают алгоритмы; всё что вам нужно - это взять алгоритм и перевести его псевдо-код на что-то, что понимает ваша система. Поскольку реализации COMMON LISP, как правило, хорошо реализовывались умными людьми и последовательно улучшались на протяжении десятилетий, то, в целом, в таких реализациях используются самые лучшие и самые быстрые алгоритмы для наиболее часто решаемых задач. Например CMUCL использует специальную реализацию сортировки кучи для сортирования списков и векторов и алгоритм Вихря Мерсенна 19937 и его огромный период 1 для генерирования случайных чисел 2.

Charlz_Klug 08.04.14 в 11:12

1 (1- (expt 2 19937))

Charlz_Klug 08.04.14 в 11:12

2 Последовательность MT19937 порождается линейной рекурсией и, поэтому, не пригодна для криптографии.

Charlz_Klug 08.04.14 в 11:15

Хорошие структуры данных также необходимы для любого приличного языка программирования. Структуры данных очень важны и их игнорирование может привести к тому, что любой язык созданный без должных структур данных будет еле ползти. Оптимизация структур данных по сути сводится к концепции локальности (locality). Описание концепции очень простое - доступ к наиболее часто используемым данным должен осуществляться как можно быстрее. Структуры данных и локальность настолько важны, что их можно обнаружить почти во всех вычислениях, где важна производительность: большие наборы CPU регистров, кэши памяти, базы данных и кэширующие сетевые прокси - это всего лишь некоторые примеры. Лисп предлагает большой набор стандартных структур данных с очень хорошей реализацией. Хэш таблицы, связанные списки (очевидно), векторы с заполняемыми указателями, пакеты с добавляемыми (internable) символами и другие более специфицированные структуры данных и их преимущества доступны для COMMON LISP программистов.

Charlz_Klug 09.04.14 в 03:19

Если лисп предоставляет такие хорошие алгоритмы и структуры данных, то почему лисп код может быть медленнее чем код в других языках? Объяснение основывается на наиболее важном архитектурном решении лиспа: обобщённом коде (general code), концепции так или иначе знакомой нам как дуализм синтаксиса. При написании лисп кода мы используем столько дуализма насколько это возможно. Сама структура языка поощряет нас к этому. Одной из причин по которой лисп программы обычно гораздо короче чем Блаб программы является возможность гораздо большего повторного использования лисп кода по сравнению с соответствующим Блаб кодом. Исходя с точки зрения Блаб языка мы сталкиваемся с довольно необычным явлением: писать больше, получать меньше (to write more to get less), но мы говорим о важном решении в лисп архитектуре - дуализме синтаксиса. Чем больше дуализма содержится в каждом выражении, тем короче будет программа. Означает ли это что для достижения и превышения производительности C мы должны сделать наши программы такими же длинными и опасными как их соответствующие C программы? Нет. В лиспе есть макросы.

Charlz_Klug 09.04.14 в 03:50

7.2 Макросы Ускоряют Лисп

Charlz_Klug 09.04.14 в 06:23

Этот раздел показывает примеры использования трёх типов макросов, помогающих создавать эффективные программы: обычные макросы, считывающие макросы и новый тип макросов, вводимых в этой главе: компилирующие макросы (compiler macros).

Charlz_Klug 09.04.14 в 06:26

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

Charlz_Klug 09.04.14 в 06:38

Макро формы не могут расширяться в декларации; выражения деклараций должны появляться только как действительные подвыражения форм, к которым они относятся.

Charlz_Klug 09.04.14 в 08:27

Из ANSI следует что следующий макрос не будет работать так, как было задумано:

Charlz_Klug 09.04.14 в 08:29

(defmacro go-fast C) ; Не исправный код!
’(dec1are (optimize (speed 3) (safety 0))))

Charlz_Klug 09.04.14 в 08:29

Мы не можем вставить вызов макроса туда, где ожидаются декларации. Можно думать и так: системный проходчик-по-коду не требует расширения макросов в телах специальных форм перед их проверкой на декларации. Потребность ускориться возникает очень часто, поэтому мы можем попробовать изобрести что-нибудь получше чем вышеприведённый макрос go-fast. Если мы хотим сжать какой-либо смысл как можно сильнее, то довольно часто мы можем прибегнуть к считывающим макросам. Считывающие макросы очень удобны для расширения в декларации, поскольку они расширяются задолго до того, как проходчик-по-коду приступит к проходу по коду. Они считываются как действительные подвыражения.

Charlz_Klug 09.04.14 в 09:31

Sharp-f - это считывающий макрос, который можно использовать для контроля наиболее важных компромиссов производительности в программах на COMMON LISP: баланс между декларациями speed (скорость) и safety (безопасность). Например, сам sharp-f считывается в то, во что должно было бы расшириться go-fast:

Charlz_Klug 09.04.14 в 09:46

* ’#f
(DECLARE (DPTIMIZE (SPEED 3) (SAFETY 0)))

Charlz_Klug 10.04.14 в 10:56

Листинг 7.1: SHARP-F
(set-dispatch-macro-character #\# #\f
(lambda (stream sub-char numarg)
(declare (ignore stream sub-char))
(setq numarg (or numarg 3))
(unless (<- numarg 3)
(error "Bad value for #f: "a" numarg))
‘(declare (optimize (speed ,numarg)
(safety ,(- 3 numarg))))))

Charlz_Klug 10.04.14 в 10:57

Но мы можем изменить это поведение и объявить значение безопасности передав число меньшее чем 3 в качестве аргумента считывателя. Все диспетчеризующие считывающие макросы могут принимать подобные числовые аргументы. В функцию считывающего макроса этот аргумент передаётся как третий аргумент, который часто называется как numarg. В примере ниже мы ставим безопасность превыше скорости передав 0:

Charlz_Klug 10.04.14 в 11:03

* ’#0f
(DECLARE CDPTIMIZE (SPEED 0) (SAFETY 3)))

Charlz_Klug 10.04.14 в 11:03

Значения 1 и 2 могут являться результатами следующих деклараций. Результат этих различных деклараций сильно зависит от компилятора, поэтому вы скорее всего никогда не будете их использовать:

Charlz_Klug 10.04.14 в 11:05

: ’(#1f #2F)
((DECLARE (OPTIMIZE (SPEED 1) (SAFETY 2)))
(DECLARE (OPTIMIZE (SPEED 2) (SAFETY 1))))

Charlz_Klug 10.04.14 в 11:05

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

Charlz_Klug 10.04.14 в 11:12

Листинг 7.2: FAST-PROGN
(defmacro fast-progn (hrest body)
‘(locally #f ,@body))

Charlz_Klug 11.04.14 в 14:59

Листинг 7.3: SAFE-PROGN
(defmacro safe-progn (&rest body)
‘(locally #0f ,@body))

Charlz_Klug 11.04.14 в 15:00

Fast-progn и safe-progn - это простые примеры макросов, которые расширяются в формы, содержащие декларации. Заметьте, что мы использовали неявный progn locally вместо progn поскольку progn не принимает декларации 3. Эти два макроса используют определённый ранее считывающий макрос sharp-f. Мы можем использовать эти формы как разновидности progn, содержащие в себе выражения для оптимизации по скорости (но потенциально опасные) и оптимизацию по безопасности (но потенциально медленные).

Charlz_Klug 11.04.14 в 15:27

3 Поскольку не устанавливает привязки.

Charlz_Klug 11.04.14 в 15:28

* (macroexpand
’(fast-progn
(+ 1 2)))
(LOCALLY
(DECLARE COPTIMIZE (SPEED 3) (SAFETY o)))
(+ 1 2))
T

Charlz_Klug 11.04.14 в 15:28

Мы можем передать другие декларации в аргументах макроса поскольку их расположение не проверяется и не будет проверено, пока макрос не будет расширен:

Charlz_Klug 11.04.14 в 15:47

* (macroexpand
’(fast-progn
(declare (type fixnum a))
(the fixnum (+ a 1))))
(LOCALLY
(DECLARE CDPTIMIZE (SPEED 3) (SAFETY 0)))
(DECLARE (TYPE FIXNUM A))
(THE FIXNUM (+ A 1)))
T

Charlz_Klug 11.04.14 в 15:48

При экспериментировании с расширениями макросов нам может понадобиться выяснить результат встраивания их в различные лексические контексты. Комбинирование макросов вычисляющихся во время чтения описано в разделе 4.1, Время-Исполнения и Время-Считывания с помощью переменной * сохраняющей последние результаты REPL и позволяющей убедиться в том, что наша форма вычисляется так, как и было задумано:

Charlz_Klug 12.04.14 в 11:38

* (let ((a 0))
#.*)

Charlz_Klug 12.04.14 в 11:38

И хотя вышеприведённый код вычисляется корректно, декларации, иногда, применимы только для скомпилированного кода. Например, поскольку наше вышеприведённое вычисление рассматривается как код 4, то он, возможно, будет игнорировать декларации безопасности и может явиться причиной переполнения результата в большое число (bignum). Посмотрим что получится у нас:

Charlz_Klug 12.04.14 в 11:47

4 В большинстве реализаций.

Charlz_Klug 12.04.14 в 11:48

* (let ((a most-positive-fixnum))
# , an)
536870912

Charlz_Klug 12.04.14 в 11:48

Так и есть. CMUCL игнорирует декларации для интерпретируемого кода. Теперь нам нужно продолжать экспериментировать с нашим выражением в ***, но поскольку мы не уверены в том что нужный нам результат будет получен в этот раз, и для того, чтобы не потерять его мы вернёмся к *:

Charlz_Klug 12.04.14 в 11:53

***
(LOCALLY
(DECLARE (OPTIMIZE (SPEED 3) (SAFETY o)))
(DECLARE (TYPE FIXNUM A))
(THE FIXNUM (+ A 1)))

Charlz_Klug 13.04.14 в 13:05

Всё на месте. Теперь у нас есть три попытки запустить этот код. Попробуем скомпилировать этот код и посмотреть как выполняется обёртка fixnum:

Charlz_Klug 13.04.14 в 13:11

* (funcall
(compile nil
‘ (lambda ()
(let ((a most-positive-fixnum))
. *) ) ))
; Warning: This is not a (VALUES FIXNUM &REST T):
; 536870912
536870912

Charlz_Klug 13.04.14 в 13:11

Хм, что у нас получилось? Разве мы не указали лиспу не выполнять проверку? Рассуждения о декларациях усложняются при проведении таких оптимизаций во время компилирования, как свёртка константы (constant folding). Получилось так, что при компиляции формы лисп смог выполнить сложение во время компилирования поскольку мы складываем константы и поэтому он знает что результат также будет константой и его не требуется вычислять во время исполнения. Когда лисп выполнил эти операции, то обнаружил что наша декларация о fixnum определённо неверна. Этим предупреждением лисп говорит нам "Вы дурак, я проигнорирую ваше определение поскольку вам нельзя доверять." Если мы немного перетасуем наше выражение так, чтобы лисп не смог сворачивать константы, то мы наконец увидим эффект от обёртки вокруг fixnum:

Charlz_Klug 13.04.14 в 14:08

* (funcall
(compile nil
‘(lambda (a)
,**))
most-positive-fixnum)
-536870912

Charlz_Klug 13.04.14 в 17:04

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

Charlz_Klug 13.04.14 в 17:21

(defmacro error-checker ()
‘(safe-progn
(declare (type integer var))
do-whatever-other-error-checking))

Charlz_Klug 13.04.14 в 17:21

Обернув ещё один слой, мы можем использовать эти макросы для добавления кода, проверяющего на наличие ошибок некоторый код, для которого важна скорость выполнения, а не безопасность, воспользовавшись вложенным применением другого макроса, fast-progn:

Charlz_Klug 13.04.14 в 17:31

(defun wrapped-operation ()
(safe-progn
do-whatever-error-checking
(fast-progn
but-this-needs-to-go-fast)))

Charlz_Klug 13.04.14 в 17:32

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

Charlz_Klug 13.04.14 в 17:52

COMMON LISP, в первую очередь, спроектирован с упором на мощь в программировании; эффективность находится на втором плане. Однако эти характеристики, мощь и эффективность, не обязательно должны находиться по разную сторону. С помощью макросов мы можем использовать мощь лиспа для решения проблем эффективности. В дополнение к обычным макросам и считывающим макросам - которые сами по себе представляют серьёзную мощь - COMMON LISP позволяет использовать макросы компилятора (compiler macros). Макросы компилятора - это макросы, решающие почти ту же задачу что и обычные макросы: программы, создающие программы. Макросы компилятора не широко описываются в большинстве лисп учебников, что в свою очередь показывает приоритетность производительности для программистов (почти нулевая). Однако, макросы компилятора представляют из себя элегантные решения для определённого класса проблем эффективности и заслуживают своего места в наборе инструментов у каждого лисп профессионала.

Charlz_Klug 13.04.14 в 18:36