Готовый перевод Let Over Lambda - 50 Years of Lisp / Let Over Lambda - 50 лет Lisp-у: Глава 7 - Темы Эффективности Макросов
7.1 Лисп быстр
Если вы облицовываете пол плиткой, размер которой с ноготь, вы не тратите излишних усилий.
- Пол Грем
Некоторые люди думают что лисп - это медленный язык. Это высказывание может быть правдивым для некоторых ранних реализаций лиспа, но явно ложное в наши дни. На самом деле такие современные лиспы как COMMON LISP спроектированы так, чтобы мы могли использовать макросы и тем самым ускорять лисп. По-настоящему ускорять. Основная цель этой главы должна удивить вас если вы верите в миф о производительности, который гласит что низкоуровневые языки более эффективны чем лисп. Эта глава демонстрирует что лисп может быть более быстрым чем любые другие языки программирования и что такие низкоуровневые языки как C на самом деле - по причине отсутствия макросов - уступают лиспу в производительности. Лисп позволяет нам писать код более эффективный чем код, написанный на других языках. Особенно при разработке больших и сложных программ, макросы позволяют создавать код, превосходящий в производительности Блаб языки. Иногда языки проектируются с упором на эффективные реализации, но чаще они проектируются с расчётом предоставления максимальной выразительности для программиста. Когда мы выбираем выразительность, то здесь лисп оказывается более быстрым. По-настоящему быстрым.
В то время когда остальные языки дают вам маленькие, квадратные плитки, лисп даёт вам плитки любого размера и любых форм. В C программисты всегда используют язык, напрямую привязанный к железу. Помимо процедур и структур в C возможны некоторые небольшие абстракции. В отличие от C лисп никогда не был привязан к возможностям и ограничениям машин.
Но конечно другие языки могут быть написаны в менее эффективном, но более удобном способе. Например Perl позволяет программисту творить чудеса с помощью одного короткого выражения, но, помимо этого содержит в себе много способов улучшения быстродействия кода. Так о чём мы говорим когда рассуждаем о том, что лисп позволяет нам контролировать эффективность наших абстракций так, как это не в состоянии сделать ни один язык? Как вы можете ожидать, ответ заключается в теме нашей книги: макросы.
Вместо того, чтобы спрашивать "что позволяет ускорить программы?", лучше спросить "что замедляет программы?". Это один из наиболее исследуемых тем в программировании. Причины можно условно разделить на три широких категорий: плохие алгоритмы, плохие структуры данных и код в целом.
Все реализации языков нуждаются в хороших алгоритмах. Алгоритм - это предположительно хорошо исследованное процедурное описание исполнения программной задачи. На разработку алгоритма расходуется гораздо больше усилий чем на их реализацию, поэтому алгоритмы используются повсеместно во всех компьютерных науках. Кто-то уже описал как, почему и как быстро работают алгоритмы; всё что вам нужно - это взять алгоритм и перевести его псевдо-код на что-то, что понимает ваша система. Поскольку реализации COMMON LISP, как правило, хорошо реализовывались умными людьми и последовательно улучшались на протяжении десятилетий, то, в целом, в таких реализациях используются самые лучшие и самые быстрые алгоритмы для наиболее часто решаемых задач. Например CMUCL использует специальную реализацию сортировки кучи для сортирования списков и векторов и алгоритм Вихря Мерсенна 19937 и его огромный период 1 для генерирования случайных чисел 2.
1 (1- (expt 2 19937))
2 Последовательность MT19937 порождается линейной рекурсией и, поэтому, не пригодна для криптографии.
Хорошие структуры данных также необходимы для любого приличного языка программирования. Структуры данных очень важны и их игнорирование может привести к тому, что любой язык созданный без должных структур данных будет еле ползти. Оптимизация структур данных по сути сводится к концепции под названием локальности (locality). Описание концепции очень простое - доступ к наиболее часто используемым данным должен осуществляться как можно быстрее. Структуры данных и локальность настолько важны, что их можно обнаружить почти во всех вычислениях, где важна производительность: большие наборы CPU регистров, кэши памяти, базы данных и кэширующие сетевые прокси - это всего лишь некоторые примеры. Лисп предлагает большой набор стандартных структур данных с очень хорошей реализацией. Хэш таблицы, связанные списки (очевидно), векторы с заполняемыми указателями, пакеты с добавляемыми (internable) символами и другие более специфицированные структуры данных и их преимущества доступны для COMMON LISP программистов.
Если лисп предоставляет такие хорошие алгоритмы и структуры данных, то по какой причине лисп код может быть медленнее чем код в других языках? Объяснение основывается на наиболее важном архитектурном решении лиспа: обобщённом коде (general code), концепции так или иначе знакомой нам как дуализм синтаксиса. При написании лисп кода мы используем столько дуализма насколько это возможно. Сама структура языка поощряет нас к этому. Одной из причин по которой лисп программы обычно гораздо короче чем Блаб программы является возможность гораздо большего повторного использования лисп кода по сравнению с соответствующим Блаб кодом. Исходя с точки зрения Блаб языка мы сталкиваемся с довольно необычным явлением: писать больше, получать меньше (to write more to get less), но мы говорим о важном решении в лисп архитектуре - дуализме синтаксиса. Чем больше дуализма содержится в каждом выражении, тем короче будет программа. Означает ли это что для достижения и превышения производительности C мы должны сделать наши программы такими же длинными и опасными как и соответствующие C программы? Нет. В лиспе есть макросы.
7.2 Макросы Ускоряют Лисп
Этот раздел показывает примеры использования трёх типов макросов, помогающих создавать эффективные программы: обычные макросы, считывающие макросы и новый тип макросов, вводимых в этой главе: компилирующие макросы (compiler macros).
Макросы могут использоваться для контроля алгоритмов, структур данных, проверки типов, проверки безопасности, уровней оптимизации кода или участков кода и многого другого. Мы можем получить безопасный и обобщённый код программы - или даже функции - работающий со скоростью быстрого и опасного кода. Если кратко: ни один язык не предоставляет такого открытого интерфейса для контролирования компиляторов так, как это делает лисп и всё это благодаря (чему же ещё?) макросам. Из беглого чтения стандарта ANSI можно узнать что макросы и декларации, наиболее короткий способ взаимодействия с компилятором, не совсем хорошо работают вместе:
Макро формы не могут расширяться в декларации; выражения деклараций должны появляться только как действительные подвыражения форм, к которым они относятся.
Из ANSI следует что следующий макрос не будет работать так, как было задумано:
(defmacro go-fast C) ; Не исправный код!
’(dec1are (optimize (speed 3) (safety 0))))
Мы не можем вставить вызов макроса туда, где ожидаются декларации. Можно думать и так: системный проходчик-по-коду не требует расширения макросов в телах специальных форм перед их проверкой на декларации. Потребность ускориться возникает очень часто, поэтому мы можем попробовать изобрести что-нибудь получше чем вышеприведённый макрос go-fast. Если мы хотим сжать какой-либо смысл как можно сильнее, то довольно часто мы можем прибегнуть к считывающим макросам. Считывающие макросы также удобны для расширения в декларации, поскольку они расширяются задолго до того, как проходчик-по-коду приступит к проходу по коду. Они считываются как действительные подвыражения.
Sharp-f - это считывающий макрос, который можно использовать для контроля наиболее важных компромиссов производительности в программах на COMMON LISP: баланс между декларациями speed (скорость) и safety (безопасность). Например, сам sharp-f считывается в то, во что должно было бы расшириться go-fast:
* ’#f
(DECLARE (DPTIMIZE (SPEED 3) (SAFETY 0)))
Листинг 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))))))
Но мы можем изменить это поведение и объявить значение безопасности передав число меньшее чем 3 в качестве аргумента считывателя. Все диспетчеризующие считывающие макросы могут принимать подобные числовые аргументы. В функцию считывающего макроса этот аргумент передаётся как третий аргумент, который часто называется как numarg. В примере ниже мы ставим безопасность превыше скорости передав 0:
* ’#0f
(DECLARE CDPTIMIZE (SPEED 0) (SAFETY 3)))
Также для следующих деклараций можно передавать значения 1 и 2. Результат этих различных деклараций сильно зависит от компилятора, поэтому вы скорее всего никогда не будете их использовать:
: ’(#1f #2F)
((DECLARE (OPTIMIZE (SPEED 1) (SAFETY 2)))
(DECLARE (OPTIMIZE (SPEED 2) (SAFETY 1))))
И хотя макросы не могут прямо расширяться в декларации, мы по прежнему можем использовать обычные макросы для управления декларациями. Поскольку проходчик-по-коду не может пройти по макросу в поисках деклараций до тех пор пока он не расширил макрос, нет никакого способа сказать что декларация является действительным подвыражением написанной вами формы или что макрос добавил декларацию при расширении.
Листинг 7.2: FAST-PROGN
(defmacro fast-progn (hrest body)
‘(locally #f ,@body))
Листинг 7.3: SAFE-PROGN
(defmacro safe-progn (&rest body)
‘(locally #0f ,@body))
Fast-progn и safe-progn - это простые примеры макросов, которые расширяются в формы, содержащие декларации. Заметьте, что мы использовали неявный progn от locally вместо обычного progn поскольку обычный progn не принимает декларации 3. Эти два макроса используют, ранее определённый, считывающий макрос sharp-f. Мы можем использовать эти формы как разновидности progn, содержащие в себе выражения для оптимизации по скорости (но потенциально опасные) и оптимизацию по безопасности (но потенциально медленные).
3 Поскольку не устанавливает привязки.
* (macroexpand
’(fast-progn
(+ 1 2)))
(LOCALLY
(DECLARE COPTIMIZE (SPEED 3) (SAFETY o)))
(+ 1 2))
T
Мы можем передавать другие декларации в аргументах макроса поскольку их расположение не проверяется и не будет проверено, до тех пор, пока макрос не будет расширен:
* (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
При экспериментировании с расширениями макросов нам может понадобиться выяснить результат встраивания их в различные лексические контексты. Комбинирование макросов, вычисляющихся во время чтения, описано в разделе 4.1, Время-Исполнения и Время-Считывания с помощью переменной * сохраняющей последние результаты REPL и позволяющей убедиться в том, что наша форма вычисляется так, как и было задумано:
* (let ((a 0))
#.*)
И хотя вышеприведённый код вычисляется корректно, декларации, иногда, применимы только для скомпилированного кода. Например, поскольку наше вышеприведённое вычисление рассматривается как код 4, то он, возможно, будет игнорировать декларации безопасности и вернёт переполненный результат в виде bignum. Посмотрим что получится у нас:
4 В большинстве реализаций.
* (let ((a most-positive-fixnum))
# , an)
536870912
Так и есть. CMUCL игнорирует декларации для интерпретируемого кода. Теперь нам нужно продолжать экспериментировать с нашим выражением в ***, но поскольку мы не уверены в том что нужный нам результат будет получен в этот раз, и для того, чтобы не потерять его мы вернёмся к *:
***
(LOCALLY
(DECLARE (OPTIMIZE (SPEED 3) (SAFETY o)))
(DECLARE (TYPE FIXNUM A))
(THE FIXNUM (+ A 1)))
Всё на месте. Теперь у нас есть три попытки запустить этот код. Попробуем скомпилировать этот код и посмотреть как выполняется обёртка fixnum:
* (funcall
(compile nil
‘ (lambda ()
(let ((a most-positive-fixnum))
. *) ) ))
; Warning: This is not a (VALUES FIXNUM &REST T):
; 536870912
536870912
Хм, что у нас получилось? Разве мы не указали лиспу не выполнять проверку? Рассуждения о декларациях усложняются при проведении таких оптимизаций во время компилирования, как свёртка константы (constant folding). Получилось так, что при компиляции формы лисп смог выполнить сложение во время компилирования поскольку мы складываем константы и поэтому он знает что результат также будет константой и его не требуется вычислять во время исполнения. Когда лисп выполнил эти операции, то обнаружил что наша декларация о fixnum определённо неверна. Этим предупреждением лисп говорит нам "Вы дурак, я проигнорирую ваше определение поскольку вам нельзя доверять." Если мы немного перетасуем наше выражение так, чтобы лисп не смог сворачивать константы, то мы наконец увидим эффект от обёртки вокруг fixnum:
* (funcall
(compile nil
‘(lambda (a)
,**))
most-positive-fixnum)
-536870912
Другим важным свойством деклараций является способность затенять (shadow) другие декларации примерно также, как одни лексические переменные затеняют другие лексические переменные. Например, мы можем захотеть написать макрос, выполняющий проверку безопасности, даже будучи встроенным в код с декларированным низким уровнем безопасности:
(defmacro error-checker ()
‘(safe-progn
(declare (type integer var))
do-whatever-other-error-checking))
Обернув ещё один слой, мы можем использовать эти макросы для добавления кода, проверяющего на наличие ошибок некоторый код, для которого важна скорость выполнения, а не безопасность, воспользовавшись вложенным применением другого макроса, fast-progn:
(defun wrapped-operation ()
(safe-progn
do-whatever-error-checking
(fast-progn
but-this-needs-to-go-fast)))
Безопасная проверка параметров с кодом проверки на ошибки, окружающий быструю реализацию некоторой функциональности - это общий шаблон в создании высокопроизводительного лисп кода. Особенно для таких итеративных процедур, как проход по массиву, значительное улучшение производительности может быть достигнуто через выполнение проверок на ошибки в таких случаях как тип и границы в начале операции и в последующем пропуске проверки в тех местах, где это возможно.
COMMON LISP, в первую очередь, спроектирован с упором на мощь в программировании; эффективность находится на втором плане. Однако эти характеристики, мощь и эффективность, не обязательно должны находиться по разную сторону. С помощью макросов мы можем использовать мощь лиспа для решения проблем эффективности. В дополнение к обычным макросам и считывающим макросам - которые сами по себе представляют серьёзную мощь - COMMON LISP позволяет использовать макросы компилятора (compiler macros). Макросы компилятора - это макросы, решающие почти ту же задачу что и обычные макросы: программы, создающие программы. Макросы компилятора не широко описываются в большинстве лисп учебников, что в свою очередь показывает приоритетность производительности для программистов (почти нулевая). Однако, макросы компилятора представляют из себя элегантные решения для определённого класса проблем эффективности и заслуживают своего места в наборе инструментов у каждого лисп профессионала.
Макросы компилятора определяют трансформации, которые будут применены вашим лисп компилятором к вызовам (именованных) функций. Это означает что вы можете взять функцию созданную с помощью defun и сказать лиспу что вместо компилирования вызовов этой функции он должен скомпилировать другой, определённый макросом компилятора, код. Зачем нам нужно использовать функцию в сочетании с макросом компилятора? Ведь проще было бы просто написать макрос с тем же именем? Первая, менее важная причина заключается в том, что такой подход позволяет нам осуществлять больший контроль над устранением накладных расходов компиляции. В частности, COMMON LISP не определяет когда или как часто должен быть расширен макрос. В случае с интерпретируемым кодом вполне возможен вариант когда макрос будет раскрываться при каждом вызове 5. При выполнении оптимизаций во время компиляции нам нужно выполнять (возможно долгие и ресурсоёмкие) вычисления перед выполнением функции, это делается с целью сократить непосредственные вычисления самой функции. Как это и должно быть - компилирующие макросы дают нам возможность выполнять ресурсоёмкие вычисления только единожды, при компиляции кода.
5 Другими словами, кэширование макро расширений не гарантируется при интерпретации.
Но, есть и другая, более важная чем просто однократное вычисление в нужное время, причина - макросы компилятора полезны ещё и тем, что они вводят дуализм синтаксиса в язык. Макросы компилятора позволяют нам добавить второе значение в любую форму, представляющую вызов (именованной) функции. В дополнение к обычному значению слова "макрос", компилирующие макросы добавляют в это значение ещё и компиляцию. Настоятельно рекомендуется убедиться что ваше скомпилированное значение реализует ту же задачу, что и изначальное значение, но, вы вольны сами определять как выполнять это действие (вот в чём изюминка). Преимущество в использовании двойственного синтаксиса заключается в том, что мы можем вносить изменения в эффективность кода без необходимости изменения всего кода. Мы можем взять существующую кодовую базу - которая предположительно использует большое количество вызовов функций - и изменить процесс компиляции кода введя двойственность синтаксиса. Всё что нам нужно - это найти недопустимо дорогостоящие вызовы функций и затем реализовать макросы компилятора, преобразующие их в более дешёвые расширения.
Вызовы каких функций являются наиболее затратными? В качестве первого примера вспомним раздел 4.6, Безопасность Считывателя, в нём упоминается что функции могут выполнять лямбда деструктуризацию и что лямбда деструктуризация - это подмножество более общего множества defmacro деструктуризации 6. Если функции принимают в виде аргументов ключевые слова, то мы передаём их в виде сгруппированных пар символов ключевого слова и их соответствующих значений. Ключевые слова, используемые в качестве аргументов - это очень удобно, но, функции, использующие подобные аргументы, подвержены накладным расходам от большего числа вызовов нежели функции, не использующие подобные аргументы. Деструктуризация не даётся бесплатно. Компилятору приходится компилировать код в функцию, перебирающую список аргументов переменной длины, получающую значения в правильном порядке (включая вставку значений по-умолчанию) и только потом выполняющую функцию. В целом лисп компилирует очень быстрый код для деструктуризации подобных ключевых слов в роли аргументов и мы почти никогда не заметим (или озадачимся) малым падением эффективности. Однако, бывают случаи, когда приходится обратить внимание на падение эффективности, в частности, когда мы вызываем подобную функцию из цикла, в котором критически важна производительность.
6 Лямбда деструктуризация не может деструктурировать списки, переданные как аргументы и не поддерживает таких возможностей, как whole из defmacro.
Fast-keys-strip - это утилита, получающая лямбда деструктурируемый список, состоящий только из обычных аргументов и аргументов ключевых-слов и возвращает список символов, использованных в качестве ссылки на эти аргументы. Другими словами, она вернёт (a b c) если ей передано (a b c) или (a &key b (c 0)), но передача утилите (a &optional b c) запрещена.
Defun-with-fast-keywords используется схожим с defun способом. Как и defun, его первый аргумент - символьное наименование функции, второе - список аргументов, а остальные формы - это формы, исполняемые в теле функции. Однако, в отличие от defun, формы, предназначенные для defun-with-fast-keywords могут содержать в себе только обычные аргументы и аргументы ключевые-слова (нельзя использовать optional, rest и т.д.). Упражнение: Расширьте fast-keywords-strip и добавьте обработку всех лямбда деструктурирующих списков 7.
7 Но, при работе с лиспом не забывайте золотое правило Норвига: никогда не смешивайте аргументы ключевые-слова и optional аргументы.
Листинг 7.4: FAST-KEYWORDS-STRIP
(defun fast-keywords-strip (args)
(if args
(cond
((eq (car args) ’&key)
(fast-keywords-strip (cdr args)))
((consp (car args))
(cons (caar args)
#1=(fast-keywords-strip
(cdr args))))
(1:
(cons (car args) #1#)))))
Листинг 7.5: DEFUN-WITH-FAST-KEYWORDS
(defmacro! defun-with-fast-keywords
(name args &rest body)
‘(progn
(defun ,name ,args ,@body)
(defun ,g!fast-fun
,(fast-keywords-strip args)
,@body)
(compile ’,g!fast-fun)
(define-compiler-macro ,name (&rest ,g!rest)
(destructuring-bind ,args ,g!rest
(list ’,g!fast-fun
,@(fast-keywords-strip args))))))
Листинг 7.6: KEYWORDS-TESTS
(defun
slow-keywords-test (a b &key (c 0) (d 0))
(+ a b c d))
(compile ’s1ow-keywords-test)
(defun-with-fast-keywords
fast-keywords-test (a b &key (c 0) (d 0))
(+ a b c d))
Расширение defun-with-fast-keywords сложно. Defun-with-fast-keywords расширяется в три формы 8. Первая определяет функцию так, как будто мы работаем с обычным defun. Вторая определяет функцию с автоматическим gensym'ом в качестве имени, g!fast-fun. Эта функция аналогична первой с тем исключением, что просто получает в качестве аргументов не-ключевые-слова для каждого аргумента (являющегося ключевым словом или нет). Далее определяется макрос компилятора, преобразующий вызовы нашей первой функции в вызовы второй функции. Таким образом, вместо деструктуризации ключевого слова, осуществляемого первой функцией, мы воспользуемся сведениями из момента компиляции об использованной форме для вызова функции и вставим ключевые слова с правильным расположением совместно с деструктурирующими привязками.
8 Которые рассматриваются как высокоуровневые, поскольку высокоуровневые progn формы рассматриваются по-особому - ценное свойство COMMON LISP.
Теперь у нас есть (почти) двойственный синтаксис с defun. Обычное определение функции с аргументами, содержащими ключевые слова, выглядит как slow-keywords-test. Ниже мы будем компилировать его с целью проведения замеров производительности. Fast-keywords-test написан идентично slow-keywords-test, с тем исключением, что вместо defun используется defun-with-fast-keywords. Благодаря defun-with-fast-keywords нам не нужно компилировать эту функцию, поскольку defun-with-fast-keywords расширяется в вызов компиляции только одного, нужного нам определения - то, которое было названо с помощью автоматического gensym'а g!fast-fun.
Листинг 7.7: KEYWORDS-BENCHMARK
(defun keywords-benchmark (n)
(format t "Slow keys:“%")
(time
(loop for i from 1 to n do
(slow-keywords-test 1 2 :d 3 :c n)))
(format t "Fast keys:'%")
(time
(loop for i from 1 to n do
(fast-keywords-test 1 2 :d 3 :c n))))
(compile ’keywords-benchmark)
Keywords-benchmark - это простая функция, использующая макрос time, для того, чтобы замерять время исполнения эквивалентных серий обеих функций. Следует учесть что мы также компилируем и keywords-benchmark. Тема о замерах производительности будет раскрыта в разделе 7.7, Написание и Замеры Производительности Компиляторов.
* (keywords-benchmark 100000000)
Slow keys:
; Evaluation took:
; 17.68 seconds of real time
Past keys:
; Evaluation took:
; 10.03 seconds of real time
Достаточно 100 миллионов вызовов этой функции для того, чтобы увидеть что хотя обе функции компилируются, но функция определённая с помощью defun-with-fast-keywords исполняется примерно на 40% быстрее благодаря макросу компилятора. Также заметим, что производительность нашего макроса компилятора не зависит от того, являются ли аргументы ключевые-слова постоянным значением, известным во время компиляции. Мы передаём n, произвольную лисп форму, как аргумент ключевого слова :c. Таким образом макрос компилятора расширяет быструю версию в тот же код что и медленная версия, с той разницей, что в быстрой версии нет накладных расходов в виде деструктуризации ключевого слова.
Так почему же COMMON LISP не может выполнять подобную оптимизацию для каждой функции, которая принимает ключевые слова и, таким образом, избежать накладных расходов? Макросы компилятора применяются только во время компиляции, а мы хотим сохранить возможность деструктурировать аргументы во время выполнения. В этом заключается суть макросов компилятора: макросы компилятора предназначены для оптимизации вызовов функции, а не для самих функций. В случае с ключевыми словами, макросы компилятора позволяют нам устранить накладные расходы для скомпилированных вызовов функций, но оставляют без изменения исходную функцию - и её код, деструктурирующий ключевые слова - доступным для использования во время исполнения. Макросы компилятора дают нам двойственный синтаксис для двух различных операций, различимых только по контексту. Другой способ, с помощью которого можно избежать накладных расходов, связанных с ключевыми словами, описан в книге PAIP Норвига [PAIP-P323].
Какую ещё пользу можно извлечь из макросов компилятора для вызовов функций? Мы можем не только уменьшить накладные расходы, связанные с деструктуризацией, но и сократить издержки связанные с самими функциями, предварительно обработав постоянные аргументы. Макрос компилятора может выполнить некоторую подготовку во время компиляции, вследствие чего сокращается время, расходуемое во время выполнения. Одно из наиболее очевидных примеров - это функция format. Рассмотрим как работает format (или, в C, printf). Это функция, которой вы передаёте управляющую строку во время выполнения программы. Format обрабатывает управляющую строку и печатает форматированный вывод в поток (или возвращает вывод в виде строки). В сущности, при использовании format вы выполняете вызов функции интерпретатора, который осуществляет форматирование строки, с управляющей строкой в роли программы. Воспользовавшись макросами компилятора мы можем устранить вызов функции, предварительно обработав управляющую строку, и изменить вызов функции на специализированный код, сращённый с вызывающей стороной, благодаря которому компилятор может выполнять будущие оптимизации. Звучит сложновато, не так-ли? Мы должны знать как конвертировать форматируемые контрольные строки в эквивалентный лисп код. К счастью, как и со многими другими нюансами, COMMON LISP уже позаботился об этом. COMMON LISP правильно выполняет форматирование. Это означает что предметно-ориентированный язык, предназначенный для создания форматированного вывода может макро-компилировать себя в лисп код. Это часть философии лиспа - всё должно компилироваться в лисп. Formatter - это макрос, который компилирует управляющие строки в лисп. Когда вы передаёте управляющую строку formatter'у, то он расширяется в лямбда форму, которая выполняет желаемое форматирование. Например, расширение для простой управляющей строки может выглядеть так 9:
9 Terpi печатает символ новой строки в поток.
* (macroexpand ’(formatter "Hello "a"'/."))
#’ (LAMBDA (STREAM &0PTIONAL
(#:FORMAT-ARG-1783
(ERROR "Missing arg"))
&REST FORMAT: :ARGS)
(BLOCK NIL
(WRITE-STRING "Hello " STREAM)
(PRINC #:FORMAT-ARG-1783 STREAM)
(TERPRI STREAM»
FORMAT::ARGS)
Таким образом formatter расширяется в лямбда форму 10. Она компилирует управляющую строку в лисп форму, пригодную для вычисления или для макро встраивания в другой лисп код, где она будет представлять из себя скомпилированную функцию или будет встроена в скомпилированный код на стороне вызывающего элемента. Также надо учесть что расширению formatter нужно передавать поток и что это расширение не может принимать nil так, как это делает format. Всё это происходит потому, что функции в которые расширяется formatter (такие как write-string и terpi) требуют потоков. Для того, чтобы избежать эту проблему, используйте макрос with-output-to-string.
10 Шарп-закавыченная лямбда форма - если быть более точным.
Fformat - это замечательная невидимая обёртка вокруг format. Благодаря этой обёртке мы можем определить макрос компилятора для форматирования. Нам нужно новое имя, отличающееся от format, поскольку определение макросов компилятора поверх функций определённых в COMMON LISP запрещено [CLTL2-P260]. Наш компилирующий макрос использует свойство defmacro деструктуризации, &whole. Мы применяем его для привязки form к списковой структуре вызова макроса. Сделано это для того, чтобы воспользоваться ещё одной особенностью макросов компилятора: макросы компилятора могут избирательно не раскрывать формы. Если мы вернём form, то лисп увидит что мы просто вернули переданную форму (произведя проверку с помощью eq) и попросит макрос компилятора не выполнять последующие расширения формы - даже если мы раскрываем её для того, чтобы применить функцию совместно с макросом компилятора. При компиляции мы можем решить, что нужно использовать другое значение формы. Это фундаментальное различие между макросом компилятора и обычным макросом. Макрос компилятора может разделить дуализм синтаксиса с функцией, но этого не может сделать обычный макрос. В fformat макрос компилятора не будет производить раскрытие в более эффективный код в случае когда аргумент, управляющая строка, не является константой. В случае с fformat нам нужно чтобы работали вызовы fformat для не строковых управляющих строк (как вызовы функции, возвращающей строки). Другими словами нам нужно сохранить возможность генерировать управляющие строки во время исполнения. Очевидно, что подобные вызовы не могут применять оптимизацию во время компиляции для управляющих строк.
Листинг 7.8: FFORMAT
(defun fformat (&rest all)
(apply #’format a11))
(compile ’fformat)
(define-compiler-macro fformat
(hwhole form
stream fmt &rest args)
(if (constantp fmt)
(if stream
‘(funcall (formatter ,fmt)
,stream ,0args)
(let ((g!stream (gensym "stream")))
‘(with-output-to-string (,g!stream)
(funcall (formatter ,fmt)
,g!stream ,@args))))
form))
Fformat-benchmark - это функция, почти идентичная функции keywords-benchmark, описанной выше. Она использует time, для сравнения времени, затрачиваемого для обработки большого количества операций форматирования с обычным format и новым fformat. Вот результаты, полученные для миллиона итераций:
Листинг 7.9: FFORMAT-BENCHMARK
(defun fformat-benchmark (n)
(format t "Format:'%")
(time
(loop for i from 1 to n do
( format nil "Hello “a "a”%" ’world n)))
(format t "Fformat:'%")
(time
(loop for i from 1 to n do
(fformat nil "Hello "a "a”%" ’world n))))
(compile ’fformat-benchmark)
* (fformat-benchmark 1000000)
Format:
; Evaluation took:
; 37.74 seconds of real time
; [Run times include 4.08 seconds GC run time]
; 1,672,008,896 bytes consed.
Fformat:
; Evaluation took:
; 26.79 seconds of real time
; [Run times include 3.47 seconds GC run time]
; 1,408,007,552 bytes consed.
Увеличение ускорения примерно на 30%. Макрос компилятора не только уменьшил время затрачиваемое на форматирование, но и уменьшил количество cons'ов (что в свою очередь уменьшило время, затрачиваемое на сборку мусора). Макрос компилятора позволил избежать интерпретации форматируемой строки во время исполнения, выполняя вместо этого большинство вычислений только единожды во время компиляции функции - как это и должно быть. К несчастью замеры производительности часто скрывают или устраняют некоторые важные детали. Предварительная компиляция форматируемых строк с помощью fformat устраняет накладные расходы интерпретирования, но за это приходится платить большим размером скомпилированной программы. И даже если памяти в достатке, большой код может выполняться медленнее за счёт уменьшения производительности кэша инструкции.
В этом разделе мы рассмотрели способы изменения производительности кода с помощью обычных макросов, считывающих макросов и специальных типов макросов, предназначенных именно для этой задачи: макросов компилятора. К счастью этот раздел и оставшаяся часть этой главы убедят вас в том, что если вы хотите писать по-настоящему эффективный код, то вам нужен COMMON LISP. А причина, по которой вам нужен COMMON LISP заключается в макросах.
Упражнение: Скачайте CL-PPCRE Эди Вейтза (описано в разделе 4.4, CL-PPCRE) и изучите как api.lisp использует макросы компилятора. Посетите web-сайт Эди и скачайте несколько лисп пакетов, которые покажутся вам интересными.
Упражнение: При написании макроса компилятора для fformat мы были вынуждены явно использовать gensym поскольку у нас нет макроса define-compiler-macro!. Исправьте это положение. Трудное Упражнение: Определите define-compiler-macro! так, чтобы он использовал функциональность defmacro! и сам не вызывал gensym. Подсказка: Думайте за пределами ящика.
7.3 Знакомство с Вашим Дизассемблером
Трудно получить представление о происходящих событиях в лиспе без исследования сырых инструкций, выполняемых вашим процессором в различных лисп формах. Изучение расширения макросов помогает нам в деле создания макросов, аналогично исследование скомпилированных расширений лисп программ - обычно ассемблерных инструкций - также оказывается весьма полезным. Поскольку лисп компиляторы могут и часто являются макро расширителями, то машинный код, генерируемый ими можно рассматривать с некоторой интересной точки зрения как разновидность лисп кода. Поскольку лисп - это не столько язык, а сколько строительный материал и фабрика для создания языков, то можно считать что лисп используется для определения и компиляции языков в язык, состоящий из набора инструкций вашего процессора.
В COMMON LISP есть функция disassemble, предназначенная для просмотра скомпилированных расширений. Disassemble - это аналог CMUCL-овского расширения macroexpand-all описанного в [USEFUL-LISP-ALGOS2]. Передав disasseble функцию или символ для которого существует привязка symbol-function, мы можем увидеть сырые инструкции машинного кода, которые будут выполнены при вызове функции.
Проблема в том, что все эти инструкции сырого машинного кода не выглядят как лисп. Вместо привычных лисповских вложенных скобок эти инструкции представляют из себя странные, мелкие шаги некоторой весьма произвольной машины. Изучение скомпилированного расширения лисп кода подобно рассматриванию плаката с помощью увеличительного стекла. Вы можете разглядеть любой участок картинки с большой детализацией, но представить всю большую картину из малых участков - это сложная, а зачастую и невозможная задача. Но всё становится ещё более сложным когда дело доходит до машинного кода. При такой детализации, порою, невозможно взглянув на участок машинного кода сказать наверняка почему компилятор разместил его здесь.
К сожалению, никто по настоящему не знает как лучше всего реализовать в лиспе функцию compile. Существуют множество макрорасширений, которые можно применить к коду, и можно сказать наверняка что некоторые из них достойны стандартизирования, но поиск наилучшего способа использования таких аппаратных ресурсов как циклы CPU и память остаются (и скорее всего останутся) актуальной темой исследований. Кроме того, улучшения в архитектуре компиляторов зависят от улучшений аппаратного обеспечения. Первоначальные оптимизации впоследствии могут потерять свою актуальность или корректность. Не надо идти далеко за примерами того, как изменение мира влияет на восприятие самого понятия эффективности.
Учёные 11 избегали использование кода, применяющего вычисления с плавающей запятой, и отдавали предпочтение вычислениям, основанным на машинном-слове с фиксированной запятой. Причина заключалась в том, что в компьютерах не было устройства для работы с плавающей запятой и приходилось использовать целочисленные инструкции процессора для симуляции плавающей запятой. А поскольку тогда процессоры не были оптимизированы для работы с плавающей запятой, то вполне естественно что операции с плавающей запятой уступали по производительности операциям с фиксированной запятой. Однако, с течением времени, появились сопроцессоры, предназначенные для работы с плавающей запятой со скоростью света. В течении буквально одной ночи, учёные поставили под сомнение предположение о том, что операции с фиксированной запятой всегда будут быстрее операций с плавающей запятой, и начали производить замеры и исследования своего аппаратного обеспечения. В процессе разработки аппаратного обеспечения изменилась производительность операций с плавающей запятой. Позже в компьютерах появились 2, 4 и более сопроцессоров для работы с плавающей запятой и тут учёные обнаружили что если поддерживать заполненность конвейера (pipeline) обработки операций с плавающей запятой, то производительность операций с плавающей запятой довольно часто оказывается большей чем производительность операций с фиксированной запятой. И если раньше программисты выбирали фиксированную запятую из соображений производительности, то теперь - спустя десятилетие - они отказались от правильной реализации в пользу неправильной реализации.
11 Одни из немногих пользователей компьютеров, для которых требуется эффективный код.
Листинг 7.10: DIS
(defmacro dis (args &rest body)
`(disassemble
(compile nil
(lambda ,(mapcar (lambda (a)
(if (consp a)
(cadr a)
a))
args)
(declare
,@(mapcar
#`(type ,(car a1) ,(cadr a1))
(remove-if-not #'consp args)))
,@body))))
При разработке макросов полезно изучать вывод macroexpand и macroexpand-all, так же полезно изучать вывод disassemble, причём не только со стороны функционирования реализации, но и для того, чтобы убедиться в том, что мы передали лиспу всю требуемую информацию для генерации эффективных расширений. Dis - это макрос, облегчающий проверку вывода disassemble для некоторого участка лисп кода. Его первый аргумент - это список символов или списки типа и символа. Для того, чтобы увидеть как работает dis достаточно просто расширить его. Вот как dis расширяется для простого бинарного сложения:
* (macroexpand
’(dis (a b) (+ a b)))
(DISASSEMBLE
Что здесь делает пустая форма declare? Это место в которое dis может вставить декларации типов, которые могут быть определены в параметрах, например:
* (macroexpand
’(dis ((fixnum a) (integer b))
(+ a b)))
(DISASSEMBLE
Dis во многом работает как лямбда форма, поскольку расширяется в (обёрнутую) лямбда форму. При желании, вы можете добавить дополнительные декларации, и будет возвращено значение (поскольку лямбда формы создают невидимый progn). Загрузите код этой книги и введите следующую форму в вашу лисп среду:
(dis (a b)
(+ a b))
Машинный код должен быть очень коротким, а всё потому, что большинство сложных элементов будут скрыты вызовом предварительно скомпилированной функции - достаточно умной, чтобы предоставить такие возможности лиспа в обработке чисел, как автоматическое приведение числовых типов (type contagion), упрощение рациональных чисел (rational simplification) и т.д.. Такой приём называется косвенностью (indirection), что в свою очередь можно увидеть в выводе вашего дизассемблера:
CALL #x1000148 ; GENERIC-+
А теперь попробуйте применить dis к трём аргументам:
(dis (a b c)
(+ a b c))
Упражнение: Сколько косвенностей вы видите в общей функции сложения? А как насчёт N где (<= 0 N) аргументов?
Теперь попробуем заблокировать тип одной переменной. А теперь сравните этот пример с примером выше, в котором мы не декларировали типы:
(dis ((fixnum a) b)
(+ a b))
Здесь должно появиться некое предупреждение об ошибке OBJECT-NOT-FIXNUM-ERROR. Лисп компилируется с некоторым дополнительным кодом, осуществляющим проверку типа, при косвенном управлении общей функцией сложения поскольку тип b не известен во время компиляции, а это требует наличия всех таких лисповских обработок чисел, как автоматическое приведение числового типа и т.д..
Здесь мы не говорим о том как получить быстрый код. На самом деле этот код может быть чуть менее эффективным, чем предыдущий код. Для быстрого кода мы должны воспользоваться процессом под названием встраивание (inlining). Для некоторых специальных операций, где доступно достаточно информации о типе, лисп компиляторы знают как избежать косвенности и прямо добавляют машинный код в компилируемую функцию для выполнения желаемой операции. В следующем примере не должно быть никаких косвенностей в общей функции сложения:
(dis ((fixnum a) (fixnum b))
(+ a b))
Процесс встраивания может привести к более машинному коду, чем какой-либо из примеров, в котором использовалась косвенность. К этому приводит копирование некоторой (но не всей) функциональности, реализованной в общей функции сложения, в компилируемую функцию. И хотя данный пример может показаться более длинным, этот код будет более производительным за счёт меньшей косвенности.
Но эта мешанина из машинного кода по прежнему менее эффективна чем реализация на C. Сюда прикомпилированы разнообразные функции подсчёта аргументов, типов и проверок на переполнение - их так много, что выгода, получаемая от них оказывается ниже чем накладные расходы. Если же мы используем эту функцию в цикле, то возникающие накладные расходы будут попросту не приемлемыми.
В таких языках как C вы везде определяете типы и нигде не применяете безопасность, поэтому код всегда эффективен, всегда опасен и всегда надоедлив при написании. В большинстве динамических Блаб языках вы нигде не определяете типы и везде применяете безопасность, таким образом, код всегда безопасен, никогда не назойлив, но и в то же время всегда неэффективен. В большинстве строгих, статических Блаб языках вы везде определяете типы и везде применяете безопасность, таким образом код всегда эффективен и всегда безопасен, но всегда надоедлив. Лисп даёт вам право выбора. Поскольку лисп по-умолчанию включён в режим безопасность-и-не-назойливость, то лисп программы часто оказываются немного менее быстрыми чем их C эквиваленты, но, лисп программы почти всегда безопасны. Поскольку лисп предоставляет программистам замечательную систему декларации типов, и превосходную реализацию компиляторов, то лисп программы почти всегда безопасны также, как и динамические Блаб эквиваленты и, в целом, гораздо быстрее их. Что ещё более важно, в лиспе есть макросы, поэтому, если вам что-то не нравится, то просто измените его!
Что же, пойдём дальше и попросим лисп ускорить нашу операцию сложения. Напомним, что шарп-f - это аббревиатура считывающего макроса, предназначенного для декларации высокоскоростного и небезопасного кода.
(dis ((fixnum a) (fixnum b))
#:E
(+ a b))
Эта последовательность инструкций машинного кода должна быть немного короче чем предыдущая. В этой версии удалены проверки типов и подсчёт аргументов. Но этот код - по-прежнему далеко не та короткая опасная инструкция, выполняющая сложение, к которой мы стремились. Для того, чтобы понять что происходит мы должны прочитать замечания компилятора. Посредством замечаний компилятор сообщает нам свои наблюдения: "Похоже, что вы собираетесь сделать что-то эффективное и вы почти у цели, но я хочу внести некоторую ясность в ваши намерения. Вот подсказка, которая поможет прояснить ситуацию..."
Замечания компилятора - это бесценный источник информации. Если вы хотите создать эффективный лисп код, то следует обратить особое внимание на эти замечания. Лисп компиляторы используют системы логического вывода типов (type inference) для обнаружения различных нюансов кода, которые могут остаться незамеченными программистом. В нашем случае компилятор должен дать примерно такое замечание:
; Note: Doing signed word to integer coercion
; (cost 20) to "<return va1ue>".
Лисп никогда не совершит таких глупых поступков, как игнорирование переполнения fixnum, конечно, если мы его сами об этом не попросим 12. Таким образом, для того, чтобы лисп выкинул свои предупреждения на ветер и написал нам очень быструю, но потенциально опасную, функцию, нам нужно заставить лисп игнорировать проверку знаковых слов (fixnum). Нужно сообщить лиспу о том, что переполнение для нас приемлемо, и что мы действительно хотим от него тихого возвращения fixnum:
12 В C программах переполнение fixnum - это класс нарушений безопасности, который часто эксплуатируют злоумышленники.
(dis ((fixnum a) (fixnum b))
#f
(the fixnum (+ a b)))
Очень быстрый код. Примерно эквивалентный C функции, складывающей fixnum-ы: несколько машинных инструкций, складывающих вместе два регистра и возвращающих управление вызвавшему коду. Ваш дизассемблер может послужить толчком для многих идей в области эффективности лиспа, но, он также может научить вас двум навыкам. В этом разделе мы покрыли довольно большую часть первого навыка: как использовать декларации для получения эффективной обработки чисел, особенно внутри циклов. Второй навык - это эффективное использование таких структур данных как массивы/векторы. Этой теме посвящён раздел 7.4, Область Видимости Указателя.
Аналогично техническому прогрессу, изменившему эффективность арифметики с плавающей запятой с техники, которую следует избегать в технику, которую следует использовать, улучшения в технологии лисп компиляторов - в сочетании с правильными системами типов и декларирования безопасности COMMON LISP-а - изменяет способ мышления об эффективности. Благодаря этим инструментам и росту сложности систем программного обеспечения 13, вопрос, посвящённый теме улучшения эффективности лиспа до уровня низко-уровневых языков, меняется на тему, посвящённую улучшению эффективности других языков до уровня лиспа. И конечно, ответ заключён в макросах, используемых для реализации других языков в лиспе.
13 Особенно ярко лисповский оптимизационный потенциал проявляется при использовании макро техник для улучшения производительности больших и сложных приложений.
7.4 Область Видимости Указателя
Уменьшится ли мощь языка при удалении из него указателей? В частности, мешает ли отсутствие явной области видимости указателей в лиспе созданию эффективных алгоритмов, определённых в терминах арифметики указателей? Оказывается, что нет, отсутствие прямой поддержки указателей не является ни теоретической и ни практической преградой. Любые алгоритмы или структуры данных, реализованные с помощью указателей в таком языке как C можно реализовать также или ещё лучше в лиспе.
И всё же, что на самом деле представляет из себя область видимости указателей и почему нам может потребоваться использование области видимости указателей? Область видимости указателей позволяет рассматривать память компьютера (или виртуальную память) как большой, индексируемый массив из которого мы можем загружать и в который мы можем сохранять fixnum значения. Выглядит опасно? Так и есть, на сегодняшний день область видимости указателей - это источник многих сложных ошибок и непосредственная причина возникновения огромных классов проблем безопасности программного обеспечения.
Область видимости указателя - это на самом деле способ определения косвенностей, то есть, получение доступа через различные среды, что собственно и происходит в случае с fixnum арифметикой. Как мы обычно программируем через среды? Мы используем либо динамическую, либо лексическую области видимости, поддерживаемые COMMON LISP-ом, или комбинируем эти две области видимости, или используем новые типы областей видимости, создаваемые с помощью макросов. Макрос pointer-& и функция pointer-* - это примеры-набороски, создающие для нас иллюзию области видимости указателя, что в свою очередь показывает, что потребность в указателях на самом деле может являться простой потребностью в замыкании. Первое и единственное мнение об аналогии между указателями и замыканиями я прочитал в сообщении в новостной группе comp.lang.scheme от Олега Киселёва (Oleg Kiselyov) [POINTERS-AS-CLOSURES]. Он предложил использовать замыкания для эмуляции указателей и написал реализацию для Scheme 14.
14 На web-сайте Олега содержится много материалов посвящённых подобным исследованиям. Настоятельно рекомендую ознакомиться с ними.
Листинг 7.11: POINTER-SCOPING-SKETCH
(defmacro! pointer-& (obj)
`(lambda (&optional (,g!set ',g!temp))
(if (eq ,g!set ',g!temp)
,obj
(setf ,obj ,g!set))))
(defun pointer-* (addr)
(funcall addr))
(defsetf pointer-* (addr) (val)
`(funcall ,addr ,val))
(defsetf pointer-& (addr) (val)
`(setf (pointer-* ,addr) ,val))
Pointer-& и pointer-* показывают возможный способ имитирования косвенности указателя через замыкания. Когда мы используем макрос pointer-& то он расширяется в довольно умную лямбда форму, которая определяет хотите ли вы получить или установить значение и выполняет соответствующее действие. Для этого pointer-& использует gensym-ы. Вместо того, чтобы использовать их в качестве имён для привязок с целью избежать нежелательного захвата переменной во время компиляции, pointer-& использует их для того, чтобы убедиться в отсутствии возможных захватов во время запуска, где мы уже не сможем присвоить значению замыкания некоторое определённое значение, поскольку оно может создавать коллизии с нашей реализацией. Например, мы можем выбрать в качестве значения по-умолчанию лисповский nil, и такой подход, обычно, будет работать, за исключением случая когда мы попытаемся передать nil в качестве аргумента. Gensym-ы удобны для использования во время выполнения, поскольку мы знаем что данному gensym-у не будет никакого eq-абельного значения. В этом их raison-d’etre (смысл жизни).
Pointer-* и его defsetf - это каркас для получения доступа к этим косвенным значениям через обобщённые переменные. Defsetf, относящийся к pointer-&, предназначен для того, чтобы расширение pointer-& знало как присваивать вложенные косвенности. В качестве простого примера мы можем создать замыкание, имитирующее шаблон указатель на указатель (pointer to a pointer) характерный для C создав ссылку, привязывающуюся к let среде.
* (let (CI 0))
(pointer-& (pointer-& x)))
#<Interpreted Function)
Сохраним это замыкание для дальнейшего использования и переместим его со специальной переменной * (сохраним всё, что содержал этот астериск):
* (defvar temp-pointer *)
#<Interpreted Function)
Теперь мы можем разыменовать (dereference) это замыкание:
* (pointer-* temp-pointer)
#<Interpreted Function)
Похоже что у нас есть ещё одно замыкание. Мы разыменовали только одно звено в цепи указателей. Используем специальную переменную * для того, чтобы сослаться на последний результат и продолжим разыменование:
* (pointer-* *)
0
0 - это исходный объект, на который мы ссылались. Кроме того, мы можем использовать этот разыменовывющий синтаксис - который является иллюзией из замыканий - и присвоить ему значение через цепь из указателей:
* (setf (pointer-* (pointer-* temp-pointer)) 5)
5
Конечно же здесь меняется исходная let среда, на которую ссылается указатель, на новое значение 5:
* (pointer-* (pointer-* temp-pointer))
5
При желании, мы можем добавить другой слой косвенности:
* (pointer-& temp-pointer)
#<Interpreted Function>
И теперь потребуются три разыменования:
* (pointer-* (pointer-* (pointer-* *)))
5
И по прежнему можно получать доступ как к обобщённой переменной:
* (setf (pointer-* (pointer-* (pointer-* **))) 9)
9
И хотя они могут находиться в разных уровнях косвенности, все эти замыкания в данной разыменовывающей цепи указывают на исходную let среду:
* (pointer-* (pointer-* temp-pointer))
9
Но, возможно это не то о чём вы подумали, когда мы разговаривали о области видимости указателя. Поскольку большинство компьютерных процессоров рассматривают память как большой массив fixnum-ов, и поскольку C был спроектирован с учётом возможностей существующих процессоров, то область видимости указателей в C неразрывно связана с fixnum арифметикой. В C, при разыменовании указателя вы всегда знаете что происходит: компилятор компилирует в коде индекс в памяти с fixnum-ом и получает или присваивает fixnum значение. Самая большая разница между областью видимости указателя в C и нашей техникой разыменования замыкания в том, что C позволяет нам изменять направление указателя добавив к нему или вычтя из него fixnum-ы, в отличие от статических замыканий скомпилированных с помощью pointer-& и получения доступа с помощью pointer-*. Код получения доступа и присваивания значения - вне зависимости чего-либо - добавлен в косвенную среду во время компиляции. Даже в нашем простом примере, мы использовали по крайней мере два различных разновидностей замыканий, доступ к которым, благодаря обобщённым переменным, осуществляется через унифицированный синтаксис разыменования. Исходная x, к которой мы ссылались, была лексической переменной, а temp-pointer - туннельная переменная, используемая для ссылки - являлась динамической переменной. С помощью раздела 6.7, Пандорические Макросы, мы можем изменять замыкания, а следовательно, можем изменять косвенность так, как только захотим.
Таким образом, оказывается что замыкания более гибки и менее опасны нежели указатели в стиле C. Если вы думаете что вам нужен указатель, то возможно, что на самом деле вам нужно замыкание. И если fixnum можно использовать как адрес, то замыкания - это код, скомпилированный для того, чтобы получать и изменять любые разновидности данных в любых разновидностях сред. И хотя для большинства задач замыкания - это наилучшая конструкция для достижения косвенности, иногда нам может понадобиться функциональность процессора в области адресации с помощью fixnum для достижения чрезвычайно эффективного кода. C позволяет нам достичь этого; COMMON LISP ещё лучше выполняет ту же операцию.
Использовать в лиспе указатели в C - стиле на самом деле очень просто и не требует от нас отказа от обычной лисп техники. Мы просто обеспечим поддержку fixnum массива и используем числовые индексы для индексации в этом массиве - то есть, думаем именно в C стиле. Затем используем декларации для того, чтобы лисп отбросил проверки типов и безопасности, в результате скомпилированный код будет похож на C код. И наконец мы используем макросы для того, чтобы сделать процесс в целом удобным и безопасным.
В целом индексация в массиве - это сложная, медленная процедура. Компилятору нужно проверить что ваш индекс - это числовое значение, что вы пытаетесь индексировать массив и что индекс находится в пределах массива. Кроме того, массивы различных типов могут иметь различный код для доступа к элементам. Загрузив код из этой книги, попробуйте вычислить следующую форму (dis в деталях описан в разделе 7.3, Знакомство с Вашим Дизассемблером):
(dis (arr ind)
(aref arr ind))
Поскольку при не известных типах aref может означать большое множество чего-либо, то, скорее всего, ваш компилятор не будет встраивать код доступа к массиву. В вышеприведённом выводе дизассемблера вы должны обнаружить вызов функции похожей на CMUCL-овский data-vector-ref. Упражнение: Скачайте исходный код вашей лисп среды и изучите эту функцию. В CMUCL этим файлом будет array.lisp. Кроме того, изучите другие функции, содержащиеся в этом файле, включая data-vector-set. Если ваша лисп среда не поставляется с полным исходным кодом или вы не можете выполнить упражнение с имеющимся исходным кодом, то обновите вашу COMMON LISP среду как можно скорее.
COMMON LISP может встраивать функцию + при достаточном объёме информации, аналогично возможно встраивание aref. Воспользуйтесь следующей формой:
(dis (((simp1e-array fixnum) arr)
(fixnum ind))
(aref arr ind))
Вышеприведённый код должен переместить косвенность в функцию ссылки общего массива. Простые массивы - это массивы с одним измерением, где расположение элементов подобно памяти в C стиле. В этом коде мы определили в качестве элемента массива fixnum, но, в вашей COMMON LISP среде возможно представление типа fixnum в другом размере, например: в байтах, в без знаковых байтах, с плавающей запятой, с плавающей запятой двойной точности и многих других. И хотя вышеприведённый код не содержит косвенности, он по прежнему содержит код реализующий проверку типа и безопасности, на которые мы обычно полагаемся при программировании в лиспе. Однако, мы уже использовали считывающий макрос sharp-f из раздела 7.2, Макросы Ускоряют Лисп для того, чтобы сообщить лиспу о необходимости быстрой арифметики, то же самое можно сделать и для ссылок на массив:
(dis (((simple-array fixnum) arr)
(fixnum ind))
#f
(aref arr ind))
В отличие от предыдущих aref-ов в этом коде на первый план выходит не производительность, а проверки типов и безопасности. Этот код предназначен для использования внутри циклов, в которых важна производительность. Заметьте, что здесь мы удалили из кода почти всю безопасность и теперь этот код почти также опасен как и его C эквивалент. В частности он подвержен проблемам переполнения буфера (buffer overflow) 15. В C подобный стиль программирования применяется везде. В лиспе везде применяется безопасное программирование, за исключением горячих точек (hotspots) где вы модифицируете код с целью ускорения программы в целом. Благодаря макросам количество подобных горячих точек может быть очень мало. Отсутствует нужда в компиляции, например, всех функций в быстром/опасном режиме. Макросы позволяют нам оптимизировать узкие, специфичные части выражения. Быстрый код прозрачно сосуществует с безопасным кодом и макросы позволяют сохранить минимальную безопасность вкупе с достижением требуемой производительности.
15 "Переполнение буфера" - общий термин, характеризующий различные возможные проблемы безопасности в C (и иногда даже лисп) программах.
Поскольку вы уже сильно продвинулись в чтении этой книги, то к этому моменту у вас уже должны сформироваться хорошие представления о создании макросов и деклараций, и в отношении области видимости указателей у нас осталось не так уж много тем. Вкратце, C предоставляет очень специфичный предметно-ориентированный язык для контроля ЦПУ на базе целочисленной арифметики, но вы можете написать более лучшие языки если воспользуетесь макросами. Эффективная область видимости указателя (теперь мы можем признать что это означает доступ к массиву - вопреки примерам с замыканиями) - это, в основном, вопрос знания работы макросов, знание работы деклараций и умение читать ваш дизассемблер.
Пример макроса реализующий эффективное получение доступа к массивам with-fast-stack. Этот макрос выбран не случайно - он даёт возможность обсудить амортизацию (amortisation). With-fast-stack реализует стековую структуру данных под названием sym. В отличие от COMMON LISP-овских push и pop стеков использующих cons ячейки для хранения элементов любых типов, эти стеки используют простой массив для хранения элементов фиксированного типа, определённых с помощью ключевого слова :type. Кроме того, размер этого массива фиксирован и определяется с помощью ключевого слова :size. Доступ к стеку осуществляется с помощью нескольких локальных макросов, определённых с помощью macrolet. Если вы назовёте ваш стек как input, то макросы будут привязаны к fast-push-input, fast-pop-input и check-stacks-input. Изучите скомпилированное расширение с помощью dis:
Листинг 7.12: WITH-FAST-STACK
(defmacro! with-fast-stack
((sym &key (type 'fixnum) (size 1000)
(safe-zone 100))
&rest body)
`(let ((,g!index ,safe-zone)
(,g!mem (make-array ,(+ size (* 2 safe-zone))
:element-type ',type)))
(declare (type (simple-array ,type) ,g!mem)
(type fixnum ,g!index))
(macrolet
((,(symb 'fast-push- sym) (val)
`(locally #f
(setf (aref ,',g!mem ,',g!index) ,val)
(incf ,',g!index)))
(,(symb 'fast-pop- sym) ()
`(locally #f
(decf ,',g!index)
(aref ,',g!mem ,',g!index)))
(,(symb 'check-stack- sym) ()
`(progn
(if (<= ,',g!index ,,safe-zone)
(error "Stack underflow: ~a"
',',sym))
(if (<= ,,(- size safe-zone)
,',g!index)
(error "Stack overflow: ~a"
',',sym)))))
,@body)))
* (dis ((fixnum a))
(with-fast-stack (input :size 2000)
(loop for i from 1 to 1000000 do
(fast-push-input a))))
Операция fast-push-input компилируется в очень короткий (и очень небезопасный) машинный код:
;;; [8] (FAST-PUSH-INPUT A)
MOV ECX, [EBP-20]
MOV EDX, [EBP-16]
MOV BAX, [EBP-12]
MOV [ECx+EDX+1], BAX
HOV EAX, [EBP-16]
ADD BAX, 4
MOV [EBP-16], EAX
Но цикл был реализован как обычно, с реализацией проверок на ошибки и косвенность в арифметических функциях, даже несмотря на то, что он находится внутри макроса with-fast-stack.
3 3 3 [7] (LOOP FOR I FROM 1 . . .)
#x1000O1D0 ; #x1000O1D0: GENERIC-+
#x10000468 ; #x10000468: GENERIC->
Очевидно, что этот цикл будет исполняться не так быстро как могло бы быть. Его производительность будет преобладать над накладными расходами выполнения цикла, а не операциями стека. Если нам нужна скорость, то мы должны явно декларировать i как целочисленный тип и добавить отдельные декларации скорости для цикла так, как мы это делали до сих пор. Безопасный код может сосуществовать с быстрым кодом. Конечно, код, который мы только что дизассемблировали - чрезвычайно опасен. Он даже не проверяет размер стека для контроля перехода за нижнюю или верхнюю границы стека. Этим мы расплатились за эффективность. Решение, реализованное в with-fast-stack вдохновлено словом stacks (стеки) из языка программирования forth (форт). С помощью локального макроса checks-stacks-input наш код может проверить находится ли стек в границах и выдаст ошибку в противном случае. Поскольку форт спроектирован с учётом существования на крайне ограниченных платформах, то форт амортизирует цену, которую приходится платить за проверку границ. Вместо того, чтобы выполнять проверку после каждой операции, как это, по-умолчанию, делает лисп, форт выполняет проверку после каждых N операций. Часто в форте это слово вызывается только после вычисления формы в REPL (мы сосредоточимся на форте в главе 8, Лисп, Переходящий в Форт, Переходящий в Лисп). Таким образом, вместо того, чтобы проверять границы после каждой операции, мы запускаем проверку через каждые 10 операций, что позволяет уменьшить цену проверки границ на, примерно, 90% 16. При проверке стека мы знаем, что в худшем случае за пределами границ окажутся 10 элементов. Или что это участок кода с не-критичной-производительностью, допускающей выполнение макроса проверки.
16 Хотя подсчёт каждой выполненной операции вносит свою долю в понижение быстродействия.
Другая особенность with-fast-stack в том, что созданные массивы обладают зонами безопасности (safe zones). То есть, выделяется дополнительная память по обе стороны стека, которая будет использоваться в качестве тормозного пути (run-away lane) при выходе за границы стека. Это не означает что работа в зонах безопасности будет хорошей идеей (особенно при переходе за нижнюю границу), но, данный вариант всё же лучше чем выход в участки памяти, не предназначенные для работы со стеком.
Как было замечено выше - код, который мы только что собрали, - очень опасен и может записать целочисленные значения в не предназначенную для этого память. Никогда не делайте этого. Упражнение: Сделайте это. Вот что у меня получилось:
* (compile nil
‘(lambda (a)
(declare (type fixnum a))
(with-fast-stack (input :size 2000)
#<Function>
Опасный код удачно скомпилирован. Попробуем запустить его:
* (funcall * 31337)
NIL
Ну что же, катастрофы, которой мы боялись, не произошло. Случится ли что-то плохое?
* (compile nil ’(1ambda () t))
; Compilation unit aborted.
Хм, выглядит нехорошо.
* (gc)
Help! 12 nested errors.
KERNEL:*MAXIMUM-ERROR-DEPTH* exceeded.
** Closed the Terminal
NIL
Это определённо выглядит нехорошо. Поскольку лисп - это unix процесс, то, возможно, что вы получите сигнал, обозначающий запись за пределами выделенной вам виртуальной памяти (называется segfault (ошибка сегментации)). CMUCL обрабатывает эти сигналы как исправляемые состояния (хотя в таких случаях вы должны перезагрузить ваш лисп образ):
Error in function UNIX::SIGSEGV-HANDLER:
Segmentation Violation at #x58AB5061.
[Condition of type SIMPLE-ERROR]
Лисп образ в таком состоянии называется повреждённым (hosed). Программы, которые могут стать повреждёнными - это катастрофа безопасности, ждущая своего часа. Разница между C и лиспом выражается в том, что риск повреждения программ на C присутствует практически везде, а риск повреждения лисп программ - практически нигде. Если вы согласны принять подобные риски безопасности для массива, созданного на области видимости указателя, то лисп макросы - это наименее навязчивый и безопасный способ реализации. Конечно, вы практически никогда не согласитесь на такие риски - просто придерживайтесь замыканий.
7.5 Tlist-ы и Cons Пулы
Этот раздел рассказывает об управлении памятью, но, здесь вы можете не найти то, что хотели бы узнать. Я был вынужден включить в книгу этот раздел, поскольку боялся увековечивания одного из неверных мифов о лиспе, утверждающего что cons - это медленная операция. Извините, но это просто неправда; cons на самом деле быстр [GC-IS-FAST]. Конечно, алгоритмы, минимизирующие неопределённо расширяемое хранилище, обычно идеальны, но, большинство алгоритмов можно написать более просто и прямо, если воспользоваться cons-ом. Не бойтесь использовать cons-ы если вам нужна память. На самом деле, иногда самая лучшая оптимизация, которая может быть выполнена в лиспе - это приведение алгоритма в форму, выраженную через cons ячейки, после этого мы можем воспользоваться возможностями настроенного лисповского сборщика мусора. Также, как написание своей собственной хэш-таблицы - это, скорее всего, плохая идея, также и хакание своих собственных процедур распределения памяти - это, скорее всего, тупая идея. Тем не менее, в этом разделе описываются некоторые способы распределения памяти. Сюрприз, мы сделаем это с помощью макросов.
Прежде чем вернуться к распределению памяти, мы поговорим о другой теме. Несмотря на то, что COMMON LISP - это инструмент, который выбирают профессиональные лисп программисты, многие лучшие учебники-о-введении-в-лисп написаны с использованием Scheme. Как правило, наиболее почитаемой является Структура и Интерпретация Компьютерных Программ [SICP] за авторством Харольда Абельсона, Джеральда Сассмана и Джули Сассман. В течение десятилетий SICP 17 изучался первокурсниками МТИ (MIT) и боготворился ими на протяжении десятилетий. Привлекательность Scheme для академических кругов была глубокой и всеобъемлющей. Большинство макро профессионалов начали постигать лисп с помощью Scheme - только тогда, когда они были готовы начать программировать серьёзные макросы, они перешли на язык для хакеров макросов: COMMON LISP.
17 Произносится как сик-пи (sick-pea).
Листинг 7.13: TLISTS
(declaim (inline make-tlist tlist-left
tlist-right tlist-empty-p))
(defun make-tlist () (cons nil nil))
(defun tlist-left (tl) (caar tl))
(defun tlist-right (tl) (cadr tl))
(defun tlist-empty-p (tl) (null (car tl)))
Но при переходе вы всегда берёте с собой некоторые инструменты. Вы не убежите от вашего прошлого - ваших корней. Если ваши корни - это Scheme и вы читали SICP, то, скорее всего, вы помните очереди (queues) (также почитайте [USEFUL-LISP-ALGOS1-CHAPTER3]). Другое описание, которое мы будем использовать, дано в другой книге, посвящённой Scheme - Схемы Вычислений (Schematics of Computation[scm-zwmcs]), в ней очередь называется tlist. Tlist - это структура данных, названная в честь её открывателя, Interlisp хакера Уоррена Тейтелмана (Warren Teitelman). И хотя tlists дан в виде Scheme кода в "Схемы Вычислений", мы будем использовать порт на COMMON LISP.
Как мы можем выяснить из конструктора, make-tlist, tlist - это всего лишь cons ячейка. Но, вместо того, чтобы использовать car в роли элемента, а cdr в роли следующего cons как в обычном списке, tlist использует car для того, чтобы сослаться на первый cons настоящего списка, а cdr - для последнего. Если car tlist-а nil, то tlist считается пустым. В отличие от обычных списков, пустые tlist-ы разнообразны (не eq-абельны). Car tlist-а указывает на cons ячейку, хранящую левый элемент tlist-a. Cdr указывает на cons, хранящий правый элемент.
Функции tlist-left и tlist-right возвращают левый и правый элементы tlist-а без модификации самого tlist. Если tlist будет пустым, то эти функции вернут nil. Если вы будете использовать только эти функции, то вы не сохраните nil в ваш tlist. К счастью вы можете проверить пустоту tlist-а перед тем как использовать его с предикатом tlist-empty-p и тем самым сохранить nil в tlist.
Листинг 7.14: TLIST-ADD
(declaim (inline tlist-add-left
tlist-add-right))
(defun tlist-add-left (tl it)
(let ((x (cons it (car tl))))
(if (tlist-empty-p tl)
(setf (cdr tl) x))
(setf (car tl) x)))
(defun tlist-add-right (tl it)
(let ((x (cons it nil)))
(if (tlist-empty-p tl)
(setf (car tl) x)
(setf (cddr tl) x))
(setf (cdr tl) x)))
Поскольку эти операции выполняются очень просто, то мы решили сообщить компилятору что все эти функции должны быть встроены 18. Это позволит лисп компилятору генерировать более эффективные расширения для функций tlist. В некоторых языках не предоставляющих достаточный контроль компилятора - например C - примитивные макро системы применяются для того, чтобы быть уверенными в том, что такие функции, как наша tlist утилита будут встроенными. В лиспе, где мы полностью контролируем компилятор, нет потребности в использовании макросов для таких нужд. Макросы, о которых идёт речь в этой главе, - это гораздо больше чем простое встраивание.
18 Declaim - это разновидность глобальной версии declare.
Мы можем добавлять элементы с левой стороны tlist с помощью функции tlist-add-left, и с правой стороны с помощью tlist-add-right. Поскольку указатель на конец списка всегда под рукой, то добавление элементов в конец tlist - это операция с постоянной временной сложностью, не зависящей от длины tlist. Однако, в целом, операция добавления к tlist не в полной мере представляет из себя постоянную временную сложность, поскольку сюда добавляются накладные расходы привнесённые cons-ом и связанным с ним выделением памяти. Обычно использование cons обозначает что tlist добавление включает в себя агрегированную побочную нагрузку от сборки мусора.
Данными функциями поддерживается только удаление элемента с левой стороны tlist. Поскольку мы храним указатели только к первому и последнему элементам tlist-а, то единственный способ найти предпоследний элемент - это пройти через весь список начиная с левой стороны tlist.
Листинг 7.15: TLIST-REM-LEFT
(declaim (inline tlist-rem-left))
(defun tlist-rem-left (tl)
(if (tlist-empty-p tl)
(error "Remove from empty tlist")
(let ((x (car tl)))
(setf (car tl) (cdar tl))
(if (tlist-empty-p tl)
(setf (cdr tl) nil)) ;; For gc
(car x))))
Листинг 7.16: TLIST-UPDATE
(declaim (inline tlist-update))
(defun tlist-update (tl)
(setf (cdr tl) (last (car tl))))
Tlist - это абстракция очереди, построенная на основе cons ячеек, особенно удобная из-за прозрачных структур данных. В то время, когда другие структуры данных реализуют tlist функциональность - такие как очереди - предоставляя вам только ограниченный интерфейс к структуре данных, tlist-ы же прямо определены как cons ячейки. Вместо создания некоторого API, которое бы удовлетворяло потребности всех, Тейтелман решил определить спецификацию tlist непосредственно на лисповской cons ячейке. Это архитектурное решение отделяет tlist от других реализаций очереди. При программировании с использованием прозрачных спецификаций, мы не создаём специальные API функции, выполняющие что-либо, нет, сам код - это API.
Если мы решим получить доступ к car tlist-а и модифицировать его содержимое, то нам нужно убедиться в том, что tlist по-прежнему остаётся последовательным. Предполагая что после наших манипуляций желаемый список будет сохранён в car tlist-а, мы можем использовать tlist-update для присваивания соответствующего значения для cdr 19.
19 Часто существует более эффективный способ сохранения последнего элемента списка в cdr tlist-а. Так мы можем избежать использования tlist-update, операции со сложностью, линейно-зависимой-от-длины-списка. Поскольку спецификация tlist прозрачна, то оба способа корректны.
Листинг 7.17: COUNTING-CONS
(defvar number-of-conses 0)
(declaim (inline counting-cons))
(defun counting-cons (a b)
(incf number-of-conses)
(cons a b))
Листинг 7.18: WITH-CONSES-COUNTED
(defmacro! with-conses-counted (&rest body)
`(let ((,g!orig number-of-conses))
,@body
(- number-of-conses ,g!orig)))
Таким образом, главный плюс tlist - это максимально близкая эмуляция лисп списков, с поддержкой операции добавления элементов в концы списка с постоянной сложностью по времени. Поскольку tlist использует cons также, как и обычные списки, то накладные расходы на память остаются теми же самыми.
В COMMON LISP нет достаточной функциональности для отслеживания и контроля выделения памяти. Давайте напишем эту функциональность. Первым делом, вспомним, что в разделе 3.5, Нежелательный Захват, говорится, что не разрешается переопределять или заново привязывать функции, определённые в COMMON LISP. Мы не можем прямо перехватывать cons вызовы, поэтому мы воспользуемся обёрткой (wrapper). Counting-cons - это функция, идентичная cons с тем исключением, что она при каждом вызове инкрементирует переменную number-of-conses.
With-conses-counted - это наш главный интерфейс, предназначенный для проверки значения number-of-conses. Его расширение будет записывать начальное значение, выполнять операции, указанные в теле макроса, и затем возвращать количество вызовов counting-cons.
К несчастью, наша стратегия переименования cons в counting-cons приводит к тому, что для проверки любого кода на потребление памяти нам приходится переписывать применение counting-cons на counting-push. Ниже мы можем увидеть что при каждом вызове counting-push counting-cons вызывается только единожды:
Листинг 7.19: COUNTING-PUSH
(defmacro counting-push (obj stack)
‘(setq ,stack (counting-cons ,obj ,stack)))
* (let (stack)
(with-conses—counted
(loop for i from 1 to 100 do
(counting-push nil stack)
(pop stack))))
100
Вышеприведённый оператор pop удаляет использованные элементы и cons ячейки предназначенные для хранения в стеке. Что происходит с этими cons ячейками? Они становятся мусором. Обычно лисп отбрасывает этот мусор и в дальнейшем никто об этом мусоре не заботится, поскольку в среде COMMON LISP существуют превосходные очищающие программы известные как сборщики мусора (garbage collectors), занимающиеся очисткой хранилища. Однако, сборка мусора не даётся бесплатно - кто-то должен платить за сбор мусора, его транспортировку и переработку в повторно используемый продукт. А что если мы создадим здесь программу мини-переработки? Например, вышеприведённый loop вызывает counting-cons 100 раз, генерируя 100 кусочков мусора, требующих сборки. Однако, беглое чтение кода покажет что в stack'е никогда не находится более одного элемента одновременно. Если мы утилизируем эту cons ячейку, то она снова станет доступна для counting-push, мы можем избежать вызова counting-cons для получения другой cons ячейки. Эта концепция известна под названием cons пула (cons pool). В дополнение к понижению нагрузки на сборщик мусора, cons пулы могут улучшить локализацию часто выделяемых в памяти структур данных.
With-cons-pool - это способ с помощью которого мы можем создавать cons пулы. Заметьте, что этот макрос расширяется в let форму, создающую привязку для cons-pool, cons-pool-count и cons-pool-limit. Эти переменные будут использоваться для хранения cons ячеек, подлежащих переработке. Поскольку такой подход привносит невидимость переменных, то with-cons-pool будет анафорическим макросом. Заметьте, что поскольку COMMON LISP поддерживает двойственный синтаксис для лексических и динамических переменных, то анафорические привязки, созданные расширением этого макроса, могут создавать как динамические, так и лексические привязки, в зависимости от места объявления анафоры: на стороне макроса или на другой стороне.
Листинг 7.20: WITH-CONS-POOL
(defmacro with-cons-pool (&rest body)
‘(let ((cons-pool)
(cons-pool-count 0)
(cons-pool-limit 100))
(declare (ignorable cons-pool
cons-pool-count
cons-pool-1imit))
,0body))
Листинг 7.21: CONS-POOL-CONS
(defmacro! cons-pool-cons (olcar o!cdr)
‘(if (= cons-pool-count 0)
(counting-cons ,g!car ,glcdr)
(let ((,g!ce11 cons-poo1))
(decf cons-pool-count)
(setf cons-pool (cdr cons-poo1))
(setf (car ,g!ce11) ,g!car
(cdr ,g!ce11) ,g!cdr)
,g!ce11)))
Cons-pool-cons расширяется в некоторый код, извлекающий cons ячейки из cons пула. Подразумевается что работа происходит внутри лексической области видимости with-cons-pool, или, если анафора объявлена специальной, то существуют динамические привязки к ним. При пустом пуле cons-pool-cons только вызывает counting-cons. При достижении ограничения cons-pool-limit этот макрос ничего не будет сохранять.
Если мы обнаружим что нам больше не нужна cons ячейка, то мы можем переместить её в cons пул, освобождая с помощью cons-pool-free. Если произошёл такой случай, то код должен пообещать что больше никогда не попытается получить доступ к освобождённой ячейке. Код, в который расширяется cons-pool-free, поместит освобождённую cons ячейку в cons-pool и увеличит cons-pool-count, если же cons-pool-count окажется больше чем cons-pool-limit, то в этом случае ячейка будет оставлена для сборки мусора. Заметьте, если вы решили что вам эти cons ячейки больше не нужны, то не требуется прибегать к cons-pool-free для очистки cons ячеек поскольку сборщик мусора в состоянии определить, когда их следует очистить. Освобождение cons ячеек - это простая и эффективная оптимизация которую можно осуществить, в том случае, если нам доступна некоторая информация, не доступная лиспу.
Листинг 7.22: CONS-POOL-FREE
(defmacro! cons-pool-free (o!ce11)
‘(when (<= cons-pool-count
(- cons-pool-limit 1))
(incf cons-pool-count)
(setf (car ,g!cel1) nil)
(push ,g!ce1l cons-poo1)))
Листинг 7.23: MAKE—CONS-POOL-STACK
(defmacro make-cons-pool-stack ()
‘(let (stack)
(dlambda
(zpush (elem)
(setf stack
(cons-pool-cons elem stack)))
(zpop ()
(if (null stack)
(error "Tried to pop an empty stack"))
(let ((cel1 stack)
(elem (car stack)))
(setf stack (cdr stack))
(cons-pool-free cell)
e1em)))))
Таким образом архитектура cons пулов состоит из двух макросов, один из которых создаёт анафору, невидимо вводящую лексические или специальные привязки, и другой макрос, использующий эту анафору. Обычно для комбинирования этих макросов используется другой макрос. Make-cons-pool-stack - это один из таких примеров. Этот макрос создаёт структуру данных, подобную стеку COMMON LISP, которая, конечно, на самом деле представляет всего лишь список, обновляемый макросами push и pop. Однако, наша структура данных отличается от push и pop по причине не прозрачной спецификации. Детали реализации этих стеков отделены от их использования. Это важно, поскольку мы не хотим чтобы пользователи наших стеков применяли свои собственные методы вставки и извлечения данных, вместо этого мы хотим чтобы пользователи использовали наши, оптимизированные по памяти, версии. Make-cons-pool-stack использует dlambda из раздела 5.7, Dlambda. Вот пример в котором мы создаём лексический cons пул, скрывающий в себе новую стековую структуру данных и затем вставляем в стек и извлекаем из стека один элемент 100 раз подряд:
*(with-cons-pool
(let ((stack (make-cons-pool-stack)))
(with-conses-counted
(loop for i from 1 to 100 do
(funcall stack zpush nil)
(funcall stack :pop)))))
1
Заметьте, что counting-cons - функция, применяемая для размещения в памяти - вызвана только единожды. Потребовалась только одна cons ячейка - она использовалась повторно. Если такой цикл будет использоваться в скомпилированном коде и будет повторён достаточное количество раз, то можно ожидать, что версия с cons пулом будет работать быстрее, просто потому, что не будет вызываться сборка мусора. И что гораздо важнее, наш цикл не будет сталкиваться с неожиданными паузами во время работы сборщика мусора. Конечно, мы почти никогда не столкнёмся с подобными паузами, поскольку лисп достаточно умён и не будет выполнять за раз полную сборку мусора, вместо этого он амортизирует (amortising) операцию техникой, известной как инкрементальная сборка (incremental collection). Сборщики мусора также реализуют оптимизацию на принципе поколений (generational collection), где недавно выделенная память будет очищаться чаще чем давно выделенная память. Удивительно, но такая сборка мусора оказывается разновидностью подсчёта ссылок [UNIFIED-THEORY-OF-GC].
Листинг 7.24: MAKE-SHARED-CONS-POOL-STACK
(with-cons-pool
(defun make-shared-cons-pool-stack ()
(make-cons-pool-stack)))
Листинг 7.25: WITH-DYNAMIC-CONS-POOLS
(defmacro with-dynamic-cons-pools (&rest body)
‘(locally (declare (special cons-pool
cons-pool-count
cons-pool-1imit))
Но, с помощью cons пулов мы выполняем меньше (или вовсе не выполняем) cons операций, а это, в свою очередь, уменьшает (или устраняет) индетерминизм времени, затрачиваемого на сборку мусора. Большинство лисп систем поддерживают временное отключение сборки мусора, так, вы сможете выполнять что-либо без пауз, и допустить более продолжительную паузу в тот момент времени, когда пауза уже не будет иметь значения. Для этих целей в CMUCL вы можете применить функции gc-on и gc-off. Также взгляните на код в signal.lisp. Упражнение: Отключите сборку мусора, а затем с помощью loop сcons-ите большое количество мусора. Используйте юниксовскую программу top для отслеживания потребления памяти.
И хотя вышеприведённая реализация стека требует от вас расположения в одном лексическом контексте с with-cons-pool для обозначения стеков, вам может понадобится поделится cons пулом, благодаря прозрачной архитектуре этих макросов, мы можем скомбинировать их с замыканиями для обозначения локальности так, как нам хочется. Make-shared-cons-pool-stack работает также, как и make-cons-pool-stack с тем исключением, что этот макрос не требует от вас обёртки с with-cons-pool. Эти переменные будут захвачены. Таким образом, все стеки, созданные с помощью make-shared-cons-pool-stack будут разделять между собой один cons пул.
Благодаря двойственности синтаксиса между лексической и специальной переменными, мы можем использовать динамическую среду для хранения наших cons пулов. Макрос with-dynamic-cons-pools преобразовывает ссылки cons пула к лексической области видимости в динамические привязки анафоры. Одна из стратегий заключается в оборачивании всего кода, использующего cons пулы в with-dynamic-cons-pools, после чего, во время исполнения вашей программы, получатся динамические привязки, созданные для cons пула. Поскольку вы можете затенить динамические привязки новыми динамическими привязками, то вы можете сохранить размещение в любой динамической детализации. Для создания динамических привязок, просто оберните wich-dynamic-cons-pools вокруг with-cons-pool.
Листинг 7.26: FILL-CONS-POOL
(defmacro fill-cons-pool ()
‘(let (tp)
(loop for i from cons-pool-count
to cons-pool-limit
do (push
(cons-pool-cons nil nil)
tp))
(loop while tp
do (cons-pool-free (pop tp)))))
Особенно для того, чтобы понизить индетерминизм времени выполнения сборки мусора, может возникнуть необходимость убедиться в том, что cons пул содержит доступные ячейки в пуле, и что программа не будет cons-ить всё (предполагаем что мы не исчерпаем весь пул). Для этого нужно при инициализации сcons-ить необходимое количество ячеек - когда cons ещё допустим - затем добавить их в пул через fill-cons-pool, заполняя cons пул до достижения cons-pool-limit.
Память - это очень сложная тема и эффективность работы с памятью зависит от вашего оборудования, вашей реализации лиспа и особенностей технологий. Если вы не до конца понимаете причины и последствия ваших действий, то попытки улучшить процедуры работы с памятью могут привести к гораздо большим проблемам, чем пользе. Системные программисты постоянно производят тонкие настройки с памятью на протяжении существования всей системы. И, безусловно, эта работа будет продолжаться ещё долгое время. Управление памятью - это тяжёлая работа, и можно быть уверенным в том, что макросы - это лучший инструмент для такой работы.
7.6 Сортирующие Сети
Нет лучшего инструмента для экспериментов с эффективностью или непосредственно реализацией эффективных программ чем лисп. Лисп уникален не только потому, что позволяет нам сконцентрироваться на умных алгоритмах и архитектурах, но и тем, что позволяет нам использовать эти алгоритмы и архитектуры с максимальной эффективностью заложенного потенциала используя мощь компиляторов машинного кода. Этот раздел описывает, с точки зрения лиспа, один из интенсивно изучаемых, но ещё не исчерпанный до конца раздел программирования: сортировку. Большинство людей считают сортировку решённой проблемой, и вы можете удивиться, когда узнаете, что до сих пор существует много важных открытых проблем сортировки.
Нам известно много замечательных алгоритмов сортировки общего назначения. Наиболее распространёнными являются такие алгоритмы, как quick sort (быстрая сортировка), причина этому - эффективная сортировка больших массивов данных. Но, если вместо больших массивов данных нам понадобится сортировать множество маленьких наборов данных, то такие алгоритмы сортировки общего назначения, как quick sort, могут оказаться излишними. Этот раздел посвящён решению подобных проблем, на эти проблемы люди тратят многие десятилетия, а простор для исследований всё ещё очень большой. И что ещё более важно для нас - эти решения дают возможность продемонстрировать расширенные техники оптимизации, простые в лиспе, но достаточно сложные в большинстве других языках программирования. В этом и следующем разделе мы повторно реализуем макрос описанный Грэмом в On Lisp под названием sortf [ON-LISP-P176]. И если sortf Грэма спроектирован для иллюстрации создания макросов, применяющих обобщённые переменные, наш sortf будет создан с упором на производительность. С учётом некоторых обстоятельств, наш sortf сможет достичь производительности, превышающей даже хорошо настроенную системную функцию sort.
Этот раздел посвящён моему учителю и другу Алану Паету (Alan Paeth) обучившему меня многому, и показавшему что даже сортировка может быть интересной. Также я выражаю признательность Джону Гэмблу (John Gamble) за его замечательную Perl программу, Algorithm-Networksort [ALGORITHM-NETWORKSORT]. Эта программа была использована для экспериментов с различными алгоритмами и для генерации ASCII рисунков сетей приводимых в этом разделе.
Сортирующая сеть - это алгоритм, предназначенный, очевидно, для сортировки наборов данных различного фиксированного размера. То есть, в отличие от большинства таких алгоритмов, как quick sort, действие сортирующей сети не зависит от сортируемых наборов данных. Каждый шаг такой сортировки был заранее предрешён ещё на этапе разработки сети. Сортирующая сеть представляет из себя простой список пар, с индексами набора данных. Каждый из этих пар соответствует индексам, которые должны использоваться в операции сравнивания-замены. После выполнения всей последовательности операций сравнивания-замены элементы будут находиться в упорядоченном порядке.
Такие алгоритмы, как quick sort, отлично работающие с большими наборами данных, могут работать с недопустимыми накладными расходами для некоторых разновидностей задач сортировки. Во-первых, обычно реализации quick sort позволяют вам выбрать произвольный оператор сравнения с целью универсализации кода сортировки. Это означает что при каждом сравнении будет происходить вызов функции сравнения что можно было бы, скажем, реализовать как встраиваемый машинный код. Во-вторых, поскольку реализации quick sort являются универсальными, то часто они не могут воспользоваться оптимизациями, которые можно осуществить при работе с наборами данных малых, фиксированных размеров. В-третьих, довольно часто нам не нужно полностью сортировать весь набор данных, а достаточно отсортировать только некоторую часть данных - например, найти серединный элемент. Сортирующие сети, не выполняющие полную сортировку иногда называют выбирающими сетями (selection networks).
Для объяснения того, что такое сортирующая сеть и демонстрации их сложного устройства и неинтуитивности темы мы рассмотрим одну из простейших возможных сетей: сортировка трёх элементов. Большинство программистов знают что для сортировки трёх элементов можно просто воспользоваться тремя сравнениями и не прибегать к использованию quick sort для трёх элементов. Легко убедиться в том, что эти операции сравнения-замены могут быть выполнены в любом порядке и это не влияет на конечный результат. Но не так легко увидеть что одни способы сортировок менее эффективны чем другие.
Сеть bad-3-sn может выглядеть как наиболее очевидная реализация трёхэлементной сети, но - как следует из названия - это не самый оптимальный вариант. ASCII рисунок позволяет визуализировать алгоритм сети описанный с помощью списковой записи в bad-3-sn. Алгоритм производит сравнение элементов под индексами 0 и 1 из набора данных и, если они не расположены по порядку, меняет их местами в правильном порядке. Далее следует выполнение тех же операций для пары индексов (0 2) и наконец для (1 2). После этого процесса элементы будут отсортированы. Если мы реализуем эту сортирующую сеть в виде кода для массива из трёх элементов, назовём этот массив как a, то программа может выглядеть так 20:
20 Rotatef - это лисповский оператор замены.
Листинг 7.27: BAD-3-SN
(defvar bad-3-sn
’((0 1) (0 2) (1 2)))
Листинг 7.28: BAD-3-SN-PIC
o - - - - - - - --o
I I
o--v--I--‘--o
I I
o-----v--V--o
(progn
(if (> (aref a 0) (aref a 1))
(rotatef (aref a 0) (aref a 1)))
(if (> (aref a 0) (aref a 2))
(rotatef (aref a 0) (aref a 2)))
(if (> (aref a 1) (aref a 2))
(rotatef (aref a 1) (aref a 2))))
Bad-3-sn - корректная программа, но не так эффективна как good-3-sn. Изменив порядок первых двух операций сравнения-замены, мы получаем более эффективную сеть. В среднем эта сеть будет производить меньше операций замены, чем bad-3-sn. Для доказательства этого следует воспользоваться условной вероятностью (conditional probability), но, поскольку эта книга повествует о лиспе, а не о сортирующих сетях, то мы уклонимся от этой темы. Вместо этого мы покажем что good-3-sn лучше чем bad-3-sn перебирая все изменения и подсчитывая количество замен, происходящих при интерпретации этих двух сетей. Сейчас мы можем привести следующее интуитивное объяснение: если первой операцией будет произведена длинная связь, то после первой операции по крайней мере один минимальный или максимальный элемент будет находиться на своём окончательном месте. Таким образом, по крайней мере одна последующая операция не будет выполнять замену. Если же первым действием была осуществлена короткая связь, то есть вероятность, что ни один из этих элементов не будет находиться на окончательной позиции и потребуются последующие замены.
Листинг 7.29: GOOD-3-SN
(defvar good-3-sn
’((0 2) (0 1) (1 2)))
Листинг 7.30: GOOD-3-SN-PIC
o - - - - - - - --o
I I
o--I--v--‘--o
I I
o--v-----v--o
Листинг 7.31: INTERPRET-SN
(defvar tracing-interpret-sn nil)
(defun interpret-sn (data an)
(let ((step 0) (swaps 0))
(dolist (i sn)
(if tracing-interpret-sn
(format t "Step "a: 'a”%" step data))
(if (> #1=(nth (car 1) data)
#2=(nth (cadr 1) data))
(progn
(rotatef #1# #23)
(incf swaps)))
(incf step))
(values swaps data)))
Для изучения этого феномена мы реализуем интерпретатор для сортирующих сетей: interpret-sn. Этот интерпретатор будет применять сортирующую сеть sn к набору данных, представленных в виде списка. В качестве первого значения он будет возвращать число выполненных перемещений, а в качестве второго значения - результирующий набор данных. Заметьте, что ссылающиеся сами-на-себя считывающие макросы #= и ## используются для предотвращения повторного набора форм доступа. Также следует отметить применение отслеживающей переменной, и если мы хотим отследить по-шаговое выполнение процесса сортировки, то эту переменную нужно привязать к не-null значению. Для начала рассмотрим уже отсортированный набор данных. Очевидно, что и bad-3-sn и good-3-sn не произведут ни одной операции замены:
* (let ((tracing-interpret-sn t))
(interpret-sn ’(1 2 3) bad-3-sn))
Step 0: (1 2 3)
Step 1: (1 2 3)
Step 2: (1 2 3)
0
(1 2 3)
* (let ((tracing-interpret-sn t))
(interpret-sn ’(1 2 3) good-3-sn))
Step 0: (1 2 3)
Step 1: (1 2 3)
Step 2: (1 2 3)
0
(123)
Далее рассмотрим случай, когда каждый элемент расположен не на своём месте последовательности. И опять, обе сортирующие сети работают одинаково, выполняют необходимые две замены:
* (let ((tracing-interpret-sn t))
(interpret-sn ’(3 1 2) bad-3-sn))
Step 0: (3 1 2)
Step 1: (1 3 2)
Step 2: (1 3 2)
2
(123)
# (let ((tracing-interpret-sn t))
(interpret-sn ’(3 1 2) good-3-sn))
Step 0: (3 1 2)
Step 1: (2 1 3)
Step 2: (1 2 3)
2
(1 2 3)
Однако, в следующем примере результаты bad-3-sn оказываются хуже, что выражается в трёх шагах:
* (let ((tracing-interpret-sn t))
(interpret-sn ’(3 2 1) bad-3-sn))
Step 0: (3 2 1)
Step 1: (2 3 1)
Step 2: (1 3 2)
3
(123)
* (let ((tracing-interpret-sn t))
(interpret-sn ’(3 2 1) good-3-sn))
Step 0: (3 2 1)
Step 1: (1 2 3)
Step 2: (1 2 3)
1
(1 2 3)
Здесь bad-3-sn выполняет три замены, в то время когда оптимальный good-3-sn выполняет только одну замену. Может ли существовать такой симметричный случай, когда good-3-sn будет проигрывать bad-3-sn? Оказывается, такого случая не существует, good-3-sn лучше чем bad-3-sn. Если вы всё ещё не верите в это, то изучите парадокс Монти Холла и тогда вы поймёте насколько не интуитивными могут быть проблемы такого рода. Интуитивно кажется что для достижения результата с меньшим количество шагов элементы нужно менять местами сразу, как только появляется такая возможность
Для количественной оценки превосходства good-3-sn перед bad-3-sn мы представляем утилиту all-sn-perms, генерирующую все возможные перестановки чисел от 1 до n. All-sn-perms включает в себя большое количество лисп шаблонов, включая рекурсивный cons сетей из связанных, временных списков и использует анафорический макрос Грэма alambda. С помощью all-sn-perms мы можем сгенерировать все 6 (факториал 3) перестановок чисел от 1 до 3:
Листинг 7.32: ALL-SN-PERMS
(defun all-sn-perms (n)
(let (perms curr)
(funcall
(alambda (left)
(if left
(loop for i from 0 to (1- (length 1eft)) do
(push (nth i left) curr)
(self (append (subseq left 0 i)
(subseq left (1+ i))))
(pop curr))
(push curr perms)))
(loop for i from 1 to n collect i))
perms))
* (all-sn-perms 3)
((1 2 3) (2 1 3) (1 3 2)
(3 1 2) (2 3 1) (3 2 1))
Поскольку из-за особенности написания all-sn-perms вышеприведённые списки разделяют свою структуру с другими списками, то при использовании их для интерпретации сортирующих сетей (деструктивная операция) нам нужно убедиться в том, что мы будем сортировать их копии, как это реализовано в average-swaps-calc. Для задач такого рода подобное структурирование с разделением структуры - это, в большинстве случаев, хорошая программистская техника, поскольку она позволяет уменьшить общее потребление памяти для ваших структур данных 21.
21 Хотя данный код появился здесь по той причине, что это наиболее простой способ получить требуемый результат.
Используя наш интерпретатор сортирующей сети interpret-sn мы можем выяснить действительное количество перемещений, потребовавшихся для всех возможных комбинаций с помощью average-swaps-calc. Эта функция просто проходит циклом через все комбинации, применяет интерпретатор с заданной сортирующей сетью, суммирует произведённые перемещения и возвращает результат деления этой суммы на число возможных комбинаций. Если мы сделаем предположение о том, что каждая возможная комбинация равнозначна, то данное вычисление покажет среднее число перемещений, для каждой комбинации. Таким образом мы можем увидеть, что результат bad-3-sn в среднем даёт 1.5 перемещения для одной комбинации:
Листинг 7.33: AVERAGE-SWAPS-CALC
(defun average-swaps-calc (n sn)
(/ (loop for i in (all-sn-perms n) sum
(interpret-sn (copy-list i) sn))
(fact n)))
* (average-swaps-calc 3 bad-3-sn)
3/2
Когда результат good-3-sn, в среднем, всего 1.166... перемещений:
* (average-swaps-calc 3 good-3-sn)
7/6
На текущий момент наши сортирующие сети производят сортировку наборов данных размерностью в три элемента. Существуют ли алгоритмы для генерации сортирующих сетей произвольного размера? Да, и эти алгоритмы уже известны. В 1968 году Кен Батчер (Ken Batcher) описал свой гениальный алгоритм [SN-APPLICATIONS], названный Дональдом Кнутом (Donald Knuth) как сортировка перемещением и заменой (merge exchange sort) или алгоритм 5.2.2M из [TAOCP-VOL3-P111]. Алгоритм Батчера - это разновидность комбинации сортировки Шелла (Shell sort) и сортировки перемещением (merge sort), с тем исключением, что известен входной размер, операции сравнения-замены, создаваемые этим алгоритмом, абсолютно не зависят от входных данных - именно то, что нам нужно для сортирующих сетей. Таким образом, для создания сортирующей сети мы запускаем алгоритм Батчера и записываем полученные операции сравнения-замены. Позже мы сможем встроить эти операции в функцию, предназначенную для работы с определённым входным размером. Этот процесс, в отличие от развёртки цикла (loop unrolling), не выполняется полностью, и мы можем в дальнейшем воспользоваться этим.
Листинг 7.34: BUILD-BATCHER-SN
(defun build-batcher-sn (n)
(1et* (network
(tee (ceiling (log n 2)))
(p (ash 1 (- tea 1))))
(loop while (> p 0) do
(let ((q (ash 1 (- tee 1)))
(r 0)
(d p))
(loop while (> d 0) do
(loop for i from 0 to (- n d 1) do
(if (= (logand i p) r)
(push (list i (+ i d))
netvork)))
(setf d (- q p)
q (ash q -1)
r p)))
(setf p (ash p -1)))
(nreverse network)))
Build-batcher-sn - это лисп реализация алгоритма Батчера переведённая с описания Кнута. Благодаря лисповской точности побитовых целочисленных операций эта реализация не подвержена никаким искусственным ограничениям n, скажем, 32 или 64. Мы можем использовать build-batcher-sn для конструирования эффективных сортирующих сетей любого размера. Вот конструкция сети, предназначенной для сортировки массива из трёх элементов - то-же самое, что и вышеприведённый good-3-sn:
* (build-batcher-sn 3)
((0 2) (0 1) (1 2))
А вот конструкция сети, сортирующей массив из 7 элементов:
* (build-batcher-sn 7)
((0 4) (1 5) (2 6) (0 2) (1 3) (4 6) (2 4)
(3 5) (0 1) (2 3) (4 5) (1 4) (3 6) (1 2)
(3 4) (5 6))
Листинг 7.35: BATCHER-7-SN-PIC
A Q
o - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - --o
I I I
o--I--‘-----I--‘--v--------‘--‘-----o
I I I I I I
o--I--I--‘--v--I--‘-----‘--I--v-----o
I I I I I I I
o--I--I--I-----v--I--‘--v--I--‘--‘--o
I I I I I I I I
o--v--I--I--‘-----v--I--‘--v--I--v--o
I I I I I I
o-----v--I--I--------v--v-----I--‘--o
I I I I
o ------ --v--v --------------- --v--v--o
Сети Батчера хороши, но известно, что они не совсем оптимальны для большинства размеров. Нахождение более лучших сетей для различных размеров, процесс их нахождения, а также выяснение их оптимальности - это важная нерешённая задача. В этой области исследований достигнуты значительные успехи с помощью эволюционных алгоритмов (evolutionary algorithms), использующих новые техники искусственного интеллекта для эффективного поиска в супер-экспоненциальных областях проблем сортирующих сетей. Например, известная на данный момент наилучшая сеть размерностью тринадцать была найдена с использованием Развивающегося Не-Детерминированного (Evolving Non-Determinism) алгоритма [END].
Использованные здесь отображения сортирующих сетей в виде ASCII картинок созданы с помощью замечательной Perl программы Джона Гэмбла Algorithm-Networksort. Обратите внимание: в картинке есть несколько связей которые можно выполнять одновременно, такие связи изображены в одной вертикали. Отсюда можно сделать вывод, что алгоритмы сортирующих сетей можно использовать по крайней мере в специализированных устройствах, с целью извлечения выгоды из параллелизма в операциях сравнения-замены. Изучение создания хороших параллельных сортирующих сетей, наряду с распараллеливанием сетей - это также важная и не до конца изученная задача.
Выше мы уже упоминали что одним из недостатков сортирующих функций общего-назначения является то, что они жёстко завязаны на сортировку всего массива. Например, нам может понадобится узнать элемент, находящийся на определённом месте. Обычно нам нужно определить элемент, находящийся по-середине, или медианный (median) элемент. Функции prune-sn-for-median и prune-sn-for-median-aux используют экономный, и, в основном, очевидный алгоритм, открытый мною, который может устранить множество не нужных операций сравнения-замены и может послужить основой для конструирования сетей произвольного выбора.
Листинг 7.36: PRUNE-SN-FOR-MEDIAN
(defun prune-sn-for-median (elems network)
(let ((mid (floor elems 2)))
(nreverse
(if (evenp elems)
(prune-sn-for-median-aux
(reverse network)
(list (1- mid) mid))
(prune-sn-for-median-aux
(reverse network)
(list mid))))))
(defun prune-sn-for-median-aux (network contam)
(if network
(if (intersection (car network) contam)
(cons (car network)
(prune-sn-for-median-aux
(cdr network)
(remove-duplicates
(append (car network) contam))))
(prune-sn-for-median-aux
(cdr network) contam))))
Листинг 7.37: HOYTE-7-MEDIAN-SN-PIC
— — : : : : : x ¢ — : — — — — z : : : : :10
o - - - - - - - - - - - --v - - - - - - - - - - - - - - --o
I I I I I
o--I--I--‘--v--I--‘-----‘--I--------o
I I I I I I I
o"I"I'-I""'V'-I--‘--V--I--‘--‘--0
I I I I I I I I
o--v--l--|-- -----v--I--‘--v--I--v--o
I I I I I
o-----V--I - - - - - - - - --v--v - - - - - - - - --o
Алгоритм начинается с сети Батчера, затем работает в обратном направлении, отслеживая заражённые (contaminated) элементы - элементы, существующие связи которых нельзя удалять, поскольку подобное удаление изменит исход сети для этого элемента. Любые связи, связывающие не заражённые элементы могут быть удалены, поскольку они не играют роли для заражённых элементов. Связь, соединяющая заражённый элемент с не заражённой связью, приводит к заражению не заражённого элемента. Если мы заражаем только средний элемент (или два средних элемента в случае с чётным входным размером), то в этом случае у нас получается сеть для выбора медианы.
Вывод алгоритма для седьмого размера (показано на рисунке) - это модифицированная сеть Батчера, в которой удалены две связи. После запуска этой сети, серединный элемент будет расположен на своём месте, но не гарантируется отсортированный порядок остальных элементов. Ниже, в качестве примера, мы отсортировали список ровно настолько, насколько это требовалось для выяснения серединного элемента (в данном случае 4):
Листинг 7.38: PRUNE-SN-FOR-MEDIAN-CALC
(defun prune-sn-for-median-calc (n)
(loop for i from 2 to n collect
(lett ((sn (build-batcher-sn i))
(snp (prune-sn-for-median i sn)))
(list i
(length sn)
(length snp)))))
* (interpret-sn
’(4 2 3 7 6 1 5)
(prune-sn-for-median
7 (build-batcher-sn 7)))
6
(1 3 2 4 5 7 6)
Для сети с размером семь элементов наша модифицированная серединная сеть Батчера выполняет 12 операций сравнения-замены, в то время, когда обычная сеть Батчера выполнит 14 операций. Prune-sn-for-median-calc даст нам материал, позволяющий сравнить данные классы сетей для различных длин. Он вычисляет сеть Батчера для размера n и группирует его размер с размером связанной серединной сети, созданной нашим алгоритмом.
Вычислены сети с размерами до 49. Заметьте, что для малых размеров, экономится очень мало операций, если они вообще будут экономиться. Но для более значительных величин, мы видим что экономим около 20% операций сравнения-замены. Если нам нужны только серединные значения - то эти сети будут хорошим выбором. Однако, конструирование оптимальных сетей, предназначенных для нахождения серединных элементов, по-прежнему, являются неисследованной областью. Модифицированные сети Батчера, разработанные в этой главе, показывают неплохие результаты, но, они всё ещё не оптимальны. Лучшие сети для нахождения серединного элемента размерностями 9 и 25 (размеры изображений 3x3 и 5x5) были открыты Паетом (Paeth) [GRAPHICS-GEMS-P171-175], они демонстрируются здесь и включены в код книги. Вот длины серединных сетей Паета:
* (length paeth-9-median-sn)
20
* (length paeth-25-median-sn)
99
Листинг 7.39: PRUNED-MEDIAN-DATA
1- (prune -sn-for-median -calc 49)
((2 1 1) (3 3 3) (4 5 5) (5 9 8) (6 12 12)
22) (10 31 29)
48 40) (14 53 47)
74 61) (18 82 72)
(22 114 98)
(7 16 14) (8 19 17) (9 26
37 31) (12 41 35) (13
(11
(15
(19
(23
(27
(31
(35
(39
(43
(47
59 49) (16 63 53) (17
91 75) (20 97 81) (21
122
155
186
232
276
321
361
100)
127)
152)
190)
226)
263)
295)
(24
(28
(32
(36
(40
(44
(48
127
161
191
241
283
329
367
105)
133)
157)
199)
233)
271)
301)
107
(25
(29
(33
(37
(41
(45
(49
88)
138
171
207
255
298
342
383
113)
140)
169)
209)
244)
280)
313))
(26
(30
(34
(38
(42
(46
146
178
219
265
309
351
124)
150)
185)
223)
259)
293)
Листинг 7.40: PAETH-9-MEDIAN-SN
(defvar paeth -9-median - sn
’((0 3) (1 4) (2 5) (0
(3 4) (1 3) (1 6) (4
(3 7) (4 8) (3 8) (3
1)
6)
4)
(0 2) (4 5) (3
(2 6) (2 3) (4
))
5) (
7)
(2
1 2)
4)
Листинг 7.41: PAETH-25-MEDIAN-SN
(defvar paeth -25-median -sn
’((0 1) (3 4) (2 4) (2 3) (6 7) (5 7) (5 6) (9 10)
(8 10) (8 9) (12 13) (11 13) (11 12) (15 16)
(14 16) (14 15) (18 19) (17 19) (17 18) (21 22)
(20 22) (20 21) (23 24) (2 5) (3 6) (0 6) (0 3)
(4 7) (1 7) (1 4) (11 14) (8 14) (8 11) (12 15)
(9 15) (9 12) (13 16) (10 16) (10 13) (20 23)
(17 23) (17 20) (21 24) (18 24) (18 21) (19 22)
(8 17) (9 18) (0 18) (0 9) (10 19) (1 19) (1 10)
(11 20) (2 20) (2 11) (12 21) (3 21) (3 12)
(13 22) (4 22) (4 13) (14 23) (5 23) (5 14)
(15 24) (6 24) (6 15) (7 16) (7 19) (13 21)
(15 23) (7 13) (7 15) (1 9) (3 11) (5 17) (11 17)
(9 17) (4 10) (6 12) (7 14) (4 6) (4 7) (12 14)
(10 14) (6 7) (10 12) (6 10) (6 17) (12 17)
(7 17) (7 10) (12 18) (7 12) (10 18) (12 20)
(10 20) (10 12)))
Для сетей размером 9 полностью сортирующая сеть Батчера выполняет 26 операций. Лучшая, известная на данный момент, сортирующая сеть для девятого размера была открыта Флойдом (Floyd) и выполняет сортировку за 25 операций. Наша обрезанная серединная версия сети Батчера выполняет 22 операции, а серединная сеть Паета - 20 операций. Для сетей размером 25 показатели будут следующими: Батчер: 138, обрезанная версия: 113, Пает: 99. Таким образом наша серединная сеть больше сети Паета (лучшей, на данный момент, сети для этих размеров) примерно на 10%. Как и следовало ожидать, мы не можем обрезать некоторые операции из сетей Паета:
* (length (prune-sn-for-median
9 paeth-9-median-sn))
20
* (length (prune-sn-for-median
25 paeth-25-median-sn))
99
В теории, всё это очень интересно. Но на практике теория достаточно скучна. Мы разработали все эти сортирующие сети для данных в виде списков, некоторые выполняют полную сортировку, используя алгоритм Батчера, некоторые применяют заражающую оптимизацию для алгоритма Батчера с целью нахождения медиан. Затем мы разработали игрушечный интерпретатор для этих сетей, без сомнений работа этого интерпретатора ужасает по сравнению с настоящими сортирующими программами. Что общего между этими программами и эффективностью? Ведь в результате этих экспериментов мы получили теоретические результаты вместо полезного кода 22? В большинстве языков результаты этих экспериментов - наши сортирующие сети - будут отображены в виде некоторых высокоуровневых структур данных и могут быть не достаточно хороши. Но в лиспе эти сети уже чрезвычайно эффективные сортирующие программы; мы не сделали только одно дело: не написали для них компилятор.
22 Нет ничего неправильного в каких-либо теоретических результатах. Некоторые наиболее важные открытия на свете были совершены из-за теории - возможно, что даже и лисп.
Упражнение: модифицируйте алгоритм обрезки (и его подход заражения) таким образом, чтобы он создавал выбирающие сети для квартилей сортируемого массива. Эти сети определяют не только серединное значение всего массива, но и находят серединные значения меньшей и большей половин упорядоченных элементов.
7.7 Написание и Замеры Производительности Компиляторов
Компилятор (compiler) - это страшная концепция для большинства программистов, поскольку большинство языков неудачны в плане написания для них компиляторов. Вот аналогия: разбор сложного log файла - это пугающая и создающая множество ошибок перспектива для программистов знающих только C или Ассемблер, но благодаря Perl'у и регулярным выражениям такая задача не трудна для программистов знающих несколько языков. Аналогично разработка мощного, выразительного языка программирования с последующим созданием компилятора для преобразования программ на этом языке в эффективный машинный код будет устрашающей задачей если мы не знаем лисп. Преимущества лиспа, применённые для написания компиляторов не только делают его лучше по сравнению с остальными языками, - но создают новый уровень выразительности. В целом, это преимущество заключается в разнице между наличием и отсутствием способности к выполнению чего-либо. Лисп программисты используют компиляторы повсюду, такими способами и для таких задач, в существование которых не-лисп программисты иногда даже не верят. Сколько C программистов рассматривали накладные расходы интерпретации функции printf описанные (и решённые) в разделе 7.2, Макросы Делают Лисп Быстрее? Сколько C программистов пытались написать компилятор для printf? В лиспе - это в порядке вещей. Всё должно компилироваться до лиспа.
Что такое компилятор? Если вы пришли из Блаба, то, возможно, ответ будет заключаться в большой стопке книг, посвящённых разбору, трансляции на основе синтаксиса, контекстно-свободных грамматик и т.д. Но не стоит переживать, это лисп и его компилятор прост. Настолько прост, что если вы имели дело с достаточно серьёзным лисп программированием, то вы уже писали его, возможно, даже не осознавая этого. У компилятора есть другое имя - "макрос". Макрос компилирует программы из одного языка в другой. На самом деле Лисп предназначен для написания таких компиляторов - всё остальное вторично. В лиспе единственным нетривиальным моментом в архитектуре программы является сохранение корректности целевой программы с одновременным обнаружением эффективного расширения этого кода. Другими словами - это сущность вашей проблемы компиляции. До сих пор мы рассматривали применение макросов в создании специализированных языков, предназначенных для решения насущных задач, кроме того, мы изучили вопросы касающиеся эффективности лисп кода и применяли определения для удаления двойственностей и проверок безопасности. Создание эффективного компилятора - всего лишь вопрос комбинации этих двух умений.
Листинг 7.42: SN-TO-LAMBDA-FORM-1
(defun sn-to-lambda-form% (sn)
‘(lambda (arr)
#f
(declare (type (simple-array fixnum) arr))
,@(mapcar
#‘(if (> #1=(aref arr ,(car a1))
#2=(aref arr ,(cadr a1)))
(rotatef #1# #2#))
sn)
arr))
Во что расширялся компилятор formatter в разделе 7.2, Макросы Делают Лисп Быстрым, где мы создали компилирующий макрос для обработки format? Это была лямбда форма 23. Иногда имеет смысл производить компилирование в лямбда формы, поскольку в дальнейшем мы можем использовать функцию compile для непосредственной конвертации в машинный код. Возвращаясь к нашим сортирующим сетям из предыдущей главы, sn-to-lambda-form% - это функция, возвращающая лямбда форму. Эта лямбда форма будет содержать инструкции для каждой операции сравнения-замены в списковой сортирующей сети. Каждая инструкция будет (небезопасно) индексироваться в целочисленный массив, для сравнивания и, возможно, применения rotatef для замены элементов. Целочисленный массив будет передан как аргумент (arr) функции, созданной этой лямбда формой. Это всё, что нужно для создания хорошего компилятора машинного кода. Как и со всеми лямбда формами, благодаря макросу lambda мы в состоянии вычислить их для получения функций:
23 Вернее шарп-закавыченная лямбда форма.
* (eval
(sn-to-lambda-formz
(build-batcher-sn 3)))
#<Interpreted Function>
Результат можно преобразовать в скомпилированные функции просто применив к ним compile:
* (compile nil *)
#<Function>
Взглянем на вывод disassemble (скомпилированное расширение):
* (disassemble *)
ii; (> (AREF ARR 0) (AREF ARR 2))
93: NOV EAX, [EDx+1]
A1: MOV ECX, [Enx+9]
A4: cup EAX, ECX
A6: JLE L0
;;; (RDTATEF (AREF ARR 0) (AREF ARR 2))
A8: MOV EAX, [EDx+9]
AB: MOV ECX, [EDx+1]
AE: MOV [EDx+1], EAX
B1: MOV [Enx+9], ECX
;;; (> (AREF ARR 0) (AREF ARR 1))
B4: LO: MOV EAX, [EDx+1]
B7: MOV ECX, [EDx+5]
BA: cup BAX, ECX
BC: JLE L1
333 CROTATEF (AREF ARR 0) (AREF ARR 1))
BE: HOV EAX, [EDX+5]
C1: MOV ECX, [EDx+1]
C4: MOV [EDX+1], EAX
C7: MOV [EDX+5]. ECX
;;; (> (AREF ARR 1) (AREF ARR 2))
CA: L1: MDV EAX, [EDX+5]
CD: MOV ECX, [EDX+9]
no: CMP EAX, ECX
D2: JLE L2
;;; (RUTATEF (AREF ARR 1) (AREF ARR 2))
D4: MOV BAX, [EDX+9]
D7: MOV ECX, [EDX+5]
DA: MDV [EDX+5], BAX
DD: MOV [EDX+9], ECX
E0: L2:
Этот машинный код быстр, но он может быть ещё быстрее. Лисп компиляторы умны - одни из самых умнейших - но они всегда могут быть ещё умнее. В тех редких случаях, когда нам нужно позаботиться о производительности, изучение скомпилированных расширений имеет важное значение, поскольку трудно узнать насколько умна ваша лисп реализация. Если мы внимательно рассмотрим последний дизассемблированный код, мы увидим что он выполняет ненужную операцию чтения перед тем, как выполнить замену. Проблема заключается в том, что rotatef расширяется в избыточный доступ. Более умный компилятор мог бы обнаружить что нужное значение уже содержится в регистре и тем самым не допустил бы выполнения доступа к массиву. Но такого у нас нет, поэтому, я реструктуризовал код так, чтобы он выдавал более эффективное расширение.
Sn-to-lambda-form - это улучшенная версия sn-to-lambda-form%. Она создаёт временные привязки для считанных переменных, поэтому инструкции считывания массива не выполняются для операции замены. Вот улучшенное скомпилированное расширение:
* (disassemble
(compile nil
(sn-to-lambda-form%
(build-batcher-sn 3))))
ii; (LET ((A (AREF ARR 0)) (B (AREF ARR 2))) ...)
2E: MOV BAX, [BDx+1]
31: MOV BCX, [BDx+9]
34: CMP BAX, Box
36: JLE L0
;;; (SETF (AREF ARR 0) B (AREF ARR 2) A)
38: MOV [BDx+1], BCX
3B: MOV [EDX+9], BAX
;;; (LET ((A (AREF ARR 0)) (B (AREF ARR 1))) ...)
3E: L0: MOV BAX, [EDX+1]
41: MOV Bcx, [BDx+5]
44: CMP BAX, Box
46: JLE L1
;;; (SETF (AREF ARR 0) B (AREF ARR 1) A)
48: MOV [BDX+1], Bcx
4B: MOV [EDX+5]. BAX
;;; (LET ((A (AREF ARR 1)) (B (AREF ARR 2))) ...)
4E: L1: MOV BAX, [BDX+5]
51: MDV Bcx, [BDx+9]
54: CMP BAX, Box
56: JLE L2
;;; (SETF (AREF ARR 1) B (AREF ARR 2) A)
58: MOV [BBX+5], Bcx
5B: MOV [EDX+9]. EAX
SE: L2:
Листинг 7.43: SN-TO-LAMBDA-FORM
(defun sn-to-lambda-form (sn)
‘(lambda (arr)
#f
(declare (type (simple-array fixnum) arr))
,@(mapcar
#‘(let ((a #1=(aref arr ,(car a1)))
(b #2=(aref arr ,(cadr a1))))
(if (> a b)
(setf #1# b
#2: a)))
sn)
arr))
Изучая ваш лисп компилятор вы узнаёте в насколько эффективное расширение будет раскрываться ваш макрос, а это очень важно для создания эффективных лисп программ. К сожалению, единственный способ по настоящему развить навыки создания быстрого лисп кода - это disassemble, исходные коды вашей лисп системы и такие инструменты замера производительности, как макрос time.
Расширение в лямбда форму, как это делалось в нашем макросе sn-to-lambda-form, - это наиболее очевидный способ реализовать компилятор в том случае, если вы пришли в лисп из Блаба. Цикл "исходный код -> лямбда форма -> compile -> disassemble" очень похож на Блаб цикл "редактирование -> компиляция -> дизассемблирование". На вход вы подаёте исходный код, а на выходе получаете машинный код. Однако, этот подход может быть более лисповым. В лиспе мы чаще всего делаем наши компиляторы невидимыми - встроенными непосредственно в другие лисп программы. В идеале функция compile должна запускаться только тогда, когда мы хотим осуществить быстрое исполнение кода. Макрос не должен постоянно компилировать всё в машинный код, вместо этого достаточно создать хорошее расширение, такое, чтобы компилятор, вне зависимости от момента запуска, обладал достаточной информацией для создания эффективной программы.
Отдельно отмечу, что нам нет нужды вызывать compile во время-выполнения. Compile - это дорогостоящая операция, поскольку не исключено, что для компиляции одного кода придётся расширить множество уровней макросов. Вместо вызова compile во время-выполнения, вспомним что лисп уже обладает всеми скомпилированными лямбда формами внутри скомпилированной функции. Учитывая это свойство конструирования замыканий в уже скомпилированном во время-выполнения коде, легко убедиться в том, что большинство вычислений во время-компиляции уже выполнено при создании произвольных функций (замыканий) во время-выполнения.
В этой книге мне больше всего нравится макрос sortf. И не только потому что он краткий, элегантный и замечательно демонстрирует большинство приёмов использования макросов, но и потому, что этот макрос - полезный код осуществляющий чрезвычайно быстрые операции сортировки, этот код можно использовать на промышленном уровне. Но что самое лучшее - этот макрос очень просто использовать в других лисп программах, по причине отличной сочетаемости. Поэтому мы не можем пройти мимо такой продвинутой лисп оптимизации. Sortf предназначен для сортирования маленьких наборов данных фиксированного размера. Этот макрос прост для встраивания, иногда даже проще чем функция sort. Вместо расширения в лямбда форму, sortf расширяется в tagbody форму, поскольку tagbody - это канонический progn, возвращающий nil. Вот расширение sortf:
Листинг 7.44: SORTF
(defmacro! sortf (comparator &rest places)
(if places
‘(tagbody
,@(mapcar
#‘(1et ((,g!a #1=,(nth (car a1) p1aces))
(,g!b #2=,(nth (cadr a1) places)))
(if (,comparator ,g!b ,g!a)
(setf #1# ,g!b
#2: ,g!a)))
(build-batcher-sn (length p1aces))))))
* (macroexpand
’(sortf < a b c))
(LET ()
(TAGBDDY
(LET ((#:A1824 A) (#:B1823 c))
(IF (< #:B1823 #:A1824)
(SETF A #:B1823 c #:A1824)))
(LET ((#:A1824 A) (#:B1823 3))
(IF (< #:B1823 #:A1824)
(SETF A #:B1823 B #:A1824)))
(LET ((#:A1824 B) (#:B1823 c))
(IF (< #:B1823 #:A1824)
(SETF B #:B1823 c #:A1824)))))
Архитектура интерфейса sortf пришла из On Lisp, эта архитектура настолько естественна, что почти любой лисп программист реализует её таким способом. Первый аргумент обычно представляет из себя символ, обозначающий оператор сравнения - чаще всего что-то вроде <. Этот аргумент чаще всего функция, но, как отмечает Грэм, первый аргумент может быть и макросом и специальной формой поскольку аргумент помещается непосредственно на позицию функции в списке. А поскольку первый аргумент будет на месте функции, то мы можем передавать в качестве первого оператора лямбда форму 24:
24 Заметьте, что мы не можем передавать шарп-закавыченные лямбда формы. Не используйте шарп-закавычивание для ваших лямбда форм.
* (let ((a -3) (b 2))
(sortf (lambda (a b) (< (abs a) (abs b)))
a b)
(list a b))
(2 -3)
Также, как и макрос Грэма, сортируемые аргументы являются обобщёнными переменными. Это означает, что мы можем использовать sortf для сортировки любых типов переменных, не только представляемых символами, но и вообще всё, к чему можно применить setf. Вот пример:
* (let ((a 2) (b ’(4)) (C #(3 1)))
(sortf < a (car b) (aref c 0) (aref c 1))
(format t "a=”a b=”a c=”a"%" a b c))
a=1 b=(2) c=#(3 4)
NIL
Поскольку sortf Грэма и наш sortf компилирует один исходный язык, то их расширения не будут сильно отличаться. Макрос Грэма, пожалуй, более корректен чем наш макрос, по той причине, что в его макросе код доступа к данным исполняется только один раз. Мы можем передавать макросу Грэма значения с побочными эффектами и, как ожидалось, получим их вычисленными только один раз. Например, sortf Грэма только один раз инкрементирует i при передаче (aref arr (incf i)). Sortf Грэма работает так: копирует каждое сортируемое значение во временную привязку, применяет пузырьковую сортировку для сортирования этих временных привязок, затем использует setf расширения 25 для записи временных переменных в изначальное место, но уже в отсортированном порядке. Вместо этого наш sortf будет вычислять каждое место формы по нескольку раз на протяжении всей сортировки, поэтому вам совет: не используйте места с побочными эффектами. Если вы заботитесь об эффективности, то в следствии этой архитектуры, вам следует убедиться в эффективности доступа к переменным. В частности не используйте методы получения доступа перебирающие весь список, например caddr, поскольку они будут проходить по списку множество раз. В нашей реализации мы сортируем аргументы на месте, без использования временных привязок. Вместо пузырьковой сортировки, с большой "O" (Big-O) сложностью (O (expt N 2)) 26, мы используем гораздо более быструю сортировку Батчера со сложностью (0 (* N (expt (log N) 2))). Есть методы для конструирования сортирующих сетей со сложностью (O (* N (log N))) - то же, что и быстрая сортировка (quick sort) - но большинство из них выполняют больше операций для сортировки малых размеров чем сети Батчера.
25 Подробности в мельчайших деталях описаны в On Lisp.
26 Мы не любим инфиксную запись (Даг перебарщивает).
Поскольку sortf не содержит деклараций типов, то возможно вам захочется использовать sortf совместно с ними. Если вам нужна действительно быстрая сортировка, то убедитесь что компилятор знает типы всех сортируемых обобщённых переменных. Если вы определите типы, всегда убедитесь в том, что все обобщённые переменные определены одним типом. Это обязательное условие, поскольку любой элемент может оказаться в любом месте.
Но как нам узнать выигрывает или проигрывает в производительности наш макрос функции sort? Нам нужно замерить производительность (benchmark). Замеры производительности обсуждались множество раз, особенно среди программистов, поскольку бесконечно страдать ерундой - это очень приятно. К несчастью, результаты почти всех замеров производительности - бесполезны. Более того, я советую вам относиться с недоверием к результатам замеров производительности опубликованных в этой книге. Но, тщательно спланированный, аккуратно проведённый, с точными замерами эксперимент по сравнению быстродействия двух версий кода, запущенных на одном лисп образе, на одной машине, может оказаться очень полезным для понимания и устранения узких мест производительности. Эти замеры полезны не только потому, что могут показать какая техника более эффективна, но и на сколько эффективна. Поскольку макросы пишут код для нас, то макросы - это лучший инструмент для проведения таких экспериментов.
Листинг 7.45: SORT-BENCHMARK-TIME
(defmacro sort-benchmark-time ()
‘(progn
(setq sorter (compile nil sorter))
(let ((arr (make-array
n :e1ement-type ’fixnum)))
(time
(loop for i from 1 to iters do
(loop for j from 0 to (1- n) do
(setf (aref arr j) (random n)))
(funcall sorter arr))))))
Макрос sort-benchmark-time - это компонент нашего эксперимента. Он расширяется в код, который предполагает, что любая лямбда форма или функция является сортировщиком sorter, и эта функция будет использоваться для сортировки целочисленного массива размерности n. После чего компилирует эту функцию и с помощью неё сортирует случайным образом сгенерированный массив в нескольких итерациях iters. Макрос time используется для сбора статистики времени, потраченного на процедуру сортировки.
Do-sort-benchmark - это, непосредственно, интерфейс для осуществления замеров производительности. Заданный набор данных размерности n и число итераций iters будут использоваться как для замера функции COMMON LISP sort, так и для нашего макроса sortf. Он сохраняет состояние генератора случайных чисел и сбрасывает его после выполнения замера sort, но, до запуска sortf, таким образом сортируемые массивы будут идентичными. Важно, чтобы do-sort-benchmark был скомпилирован при запуске, таким образом мы как можно больше сокращаем возможные помехи замеров.
После запуска do-sort-benchmark покажет нам не только то, что sortf мало того эффективнее, но и что сортирующие алгоритмы общего назначения не то-же самое, что и сортирующие сети по отношению к производительности при работе с малыми, фиксированными наборами данных. Также, можно заметить, что sortf не потребляет память, что в свою очередь выливается в меньшее время сборки мусора и в повышение производительности. Вот результаты для наборов данных размерностями 2, 3, 6, 9, 25, 49:
* (do-sort-benchmark 2 1000000)
CL sort:
; Evaluation took:
; 1.65 seconds of real time
; 8,000,064 bytes consed.
sortf:
; Evaluation took:
; 0.36 seconds of real time
; 0 bytes consed.
* (do-sort-benchmark 3 1000000)
CL sort:
; Evaluation took:
; 3.65 seconds of real time
; 24,000,128 bytes consed.
sortf:
; Evaluation took:
; 0.46 seconds of real time
; 0 bytes consed.
(do-sort-benchmark 6 1000000)
CL sort:
; Evaluation took:
; 10.37 seconds of real time
; 124,186,832 bytes consed.
sortf:
; Evaluation took:
; 0.8 seconds of real time
; 0 bytes consed.
* (do-sort-benchmark 9 1000000)
CL sort:
; Evaluation took:
; 19.45 seconds of real time
; 265,748,544 bytes consed.
sortf:
; Evaluation took:
; 1.17 seconds of real time
; 0 bytes consed.
CL sort:
; Evaluation took:
; 79.53 seconds of real time
; 1,279,755,832 bytes consed.
sortf:
; Evaluation took:
; 3.41 seconds of real time
; 0 bytes consed.
* (do-sort-benchmark 49 1000000)
CL sort:
; Evaluation took:
; 183.16 seconds of real time
; 3,245,024,984 bytes consed.
sortf:
; Evaluation took:
; 8.11 seconds of real time
; 0 bytes consed.
Листинг 7.46: DO-SORT-BENCHMARK
(defun do-sort-benchmark (n iters)
(let ((rs (make-random-state *random-state#)))
(format t "CL sort:"%")
(let ((sorter
’(1ambda (arr)
#f
(declare (type (simple-array fixnum)
arr))
(sort arr #’<))))
(sort-benchmark-time))
(setf trandom-state* rs)
(format t "sortf:"%")
(let ((sorter
‘(lambda (arr)
#f
(declare (type (simple-array fixnum)
arr))
(sortf <
,@(loop for i from 0 to (1- n)
collect ‘(aref arr ,i)))
arr)))
(sort-benchmark-time))))
(compile ’do-sort-benchmark)
Таким образом для общих задач, где важно упорядочивание и производительность мы можем использовать сортирующие сети. Эти измерения делались не для дискредитации реализации sort (на самом деле это замечательная сортирующая процедура), но, для того, чтобы показать реалистичный пример того, как умное программирование с макросами может дать значительное повышение производительности. Лисп макросы дали нам возможность писать умные программы простым и переносимым способом. Но, для того чтобы писать умные программы на Блаб языках, приходится тратить столько усилий, что в результате Блаб программисты почти всегда довольствуются примитивным программированием. В лиспе всё компилируется в лисп и поэтому нет никаких барьеров для оптимизаций. Если что-то оказывается неприемлемо медленным, то измените эту вещь и сделайте эту вещь быстрее. Нам почти никогда не требуется быстрое исполнение чего-либо, но когда нам требуется скорость, то решением будет лисп.
Листинг 7.47: MEDIANF
(defun medianf-get-best-sn (n)
(case n
((0) (error "Need more places for medianf"))
((9) paeth-9-median-sn)
((25) paeth-25-median-sn)
(t (prune-sn-for-median n
(build-batcher-sn n)))))
(defmacro! medianf (&rest places)
‘(progn
,@(mapcar
#‘(1et ((,g!a #1=,(nth (car a1) p1aces))
(,g!b #2=,(nth (cadr a1) places)))
(if (< ,g!b ,g!a)
(setf #1# ,g!b
#2:: ,g!a)))
(medianf-get-best-sn (length p1aces)))
,(nth (floor (1- (length places)) 2) ; lower
p1aces)))
Другой макрос похожий на sortf - это medianf, использующий нашу урезанную сеть нахождения медианы или вручную написанные Паетовские сети нахождения медианы для неполной сортировки. Предназначение medianf - убедиться в том, что серединный элемент расположен на правильной позиции. В случае чётных размеров сети и нижняя и верхняя медиана будут находиться на правильном месте. В отличие от sortf, который всегда возвращает nil, medianf вернёт значение нижней медианы (то же самое, что верхняя медиана для сетей нечётных размеров).
Как мы сказали ранее, sortf и medianf сортируют любые разновидности объектов, к которым можно применить setf. В случае с переменными, сохраняемыми в регистрах, такой подход даёт возможность создавать сортирующий код, которому даже не нужен доступ к памяти. Например, вот скомпилированное расширение для medianf на трёх fixnum переменных:
* (dis ((fixnum a) (fixnum b) (fixnum c))
#f
(medianf a b c))
;;; (MBDIANF A B c)
34: HOV BBX, BAX
36: CMP BDX, BAX
38: JL L4
3A: L0: MOV EBX, BAX
3C: CMP BCX, BAX
3B: JL L3
40: L1: MOV BAX, BCX
42: CMP BDX, BCX
44: JNL L2
46: MOV BCX, BDX
48: MOV BDX, BAX
4A: L2:
5B: L3: MOV BAX, BCX
5D: MOV BCX, BBX
5F: JMP L1
61: L4: MDV BAX, EDX
63: MOV BDX, BBX
65: JMP L0
Лисп обладает гораздо большим потенциалом для создания эффективного кода чем другие языки и всё это - благодаря макросам. Макросы очень хороши в плане создания контролируемых экспериментов по некоторым замерам, но, кроме того, макросы - это решение позволяющее определить и сравнить эффективность различных техник. Компиляторы - это программы, которые пишут другие программы, и ничто так хорошо не подходит под эту задачу, как макросы.
Переведено на Нотабеноиде
http://notabenoid.org/book/40014/206477
Переводчики: Charlz_Klug, snakeduse
Настройки
Готово:
100.00%
КП = 1.2