13.4. Обходимся без мусора |
229 |
13.4. Обходимся без мусора
Лисп позволяет отложить решения касательно не только типов пере менных, но и выделения памяти. На ранних стадиях создания програм мы возможность не думать о таких вещах дает больше свободы вообра жению. Но по мере того как программа становится зрелой, она может стать быстрее, меньше полагаясь на динамическое выделение памяти.
Однако уменьшение консинга (consing) не обязательно приведет к уско рению программы. В реализациях Лиспа с плохими сборщиками мусо ра такие программы обычно работают медленно. До недавнего времени большинство реализаций имели не самые удачные сборщики мусора, поэтому бытовало мнение, что эффективные программы должны по возможности избегать выделения памяти. Но последние усовершенст вования перевернули ситуацию с ног на голову. Некоторые реализации теперь имеют настолько изощренные сборщики мусора, что выделять память под объекты и выбрасывать их за ненадобностью оказывается быстрее, чем использовать эту память повторно.
В этом разделе показаны основные методы экономии памяти. Скажется ли это на производительности, зависит от используемой реализации. Как всегда, лучший совет: попробуйте сами – и все увидите.
Существует множество приемов, позволяющих избежать выделения па мяти. Некоторые из них практически не изменяют вид вашей програм мы. Например, одним из наиболее простых методов является использо вание деструктивных функций. В следующей таблице приводятся не которые часто употребляемые функции и их деструктивные аналоги:
Безопасные |
Деструктивные |
append |
nconc |
reverse |
nreverse |
remove |
delete |
remove-if |
delete-if |
remove-duplicates |
delete-duplicates |
subst |
nsubst |
subst-if |
nsubst-if |
union |
nunion |
intersection |
nintersection |
set-difference |
nset-difference |
|
|
Если вам известно, что модификация списка безопасна, используйте delete вместо remove, nreverse вместо reverse и т. д.
Если вы желаете полностью исключить выделение памяти, это еще не значит, что придется забыть о возможности создания объектов на лету. Чего следует избегать, так это выделения памяти под объекты на лету
230 |
Глава 13. Скорость |
и ее последующего сбора. Общим решением является заблаговременное выделение блоков памяти и их дальнейшее повторное использование «вручную». Заблаговременно означает в момент компиляции или неко торой процедуры инициализации. Когда скорость начинает играть роль, зависит от приложения.
Например, если обстоятельства позволяют нам ограничить размер стоп ки, то вместо ее создания из отдельных ячеек можно сделать так, что стопка будет расти и уменьшаться в рамках заранее выделенного векто ра. Common Lisp имеет встроенную поддержку использования вектора
вкачестве стопки. Для этого есть необязательный параметр fill-pointer
вmake-array. Первый аргумент make-array задает количество памяти, вы деляемой под вектор, а fill-pointer, если задан, определяет его исход ную фактическую длину:
>(setf *print-array* t)
T
>(setf vec (make-array 10 :fill-pointer 2
:initial-element nil))
#(NIL NIL)
Функции работы с последовательностями будут рассматривать его как вектор из двух элементов:
> (length vec) 2
но его размер может вырасти до 10. Поскольку этот вектор имеет указа тель заполнения, к нему можно применять функции vector-push и vectorpop, аналогичные push и pop для списков:
>(vector-push ’a vec)
2
>vec
#(NIL NIL A)
>(vector-pop vec)
A
>vec
#(NIL NIL)
Вызов vector-push увеличил указатель заполнения и вернул его старое значение. Мы можем записывать в такой вектор новые значения до тех пор, пока указатель заполнения меньше начального размера вектора, заданного первым аргументом make-array. Когда свободное место закон чится, vector-push вернет nil. В наш вектор vec мы можем поместить до 8 новых элементов.
Векторы с указателем заполнения имеют один недостаток – они более не принадлежат типу simple-vector, и вместо svref нам приходится ис пользовать aref. Эти дополнительные затраты стоит учесть при выборе подходящего решения.
13.4. Обходимся без мусора |
231 |
Некоторые приложения могут производить очень длинные последова тельности. В таком случае вам поможет использование map-into вместо map. В качестве первого аргумента она получает не тип новой последова тельности, а саму последовательность, в которую будут записаны ре зультаты. Из этой же последовательности могут браться и аргументы для функции, которая производит отображение. Для примера увеличим на единицу все элементы вектора:
(setf v (map-into v #’1+ v))
На рис. 13.3 показан пример приложения, работающего с длинными векторами. Это программа, генерирующая несложный словарь рифм (точнее, словарь ранее увиденных рифм).
(defconstant dict (make-array 25000 :fill-pointer 0))
(defun read-words (from)
(setf (fill-pointer dict) 0) (with-open-file (in from :direction :input)
(do ((w (read-line in nil :eof) (read-line in nil :eof)))
((eql w :eof)) (vector-push w dict))))
(defun xform (fn seq) (map-into seq fn seq))
(defun write-words (to)
(with-open-file (out to :direction :output :if-exists :supersede)
(map nil #’(lambda (x) (fresh-line out) (princ x out))
(xform #’nreverse
(sort (xform #’nreverse dict) #’string<)))))
Рис. 13.3. Генерация словаря рифм
Функция read-words читает слова из файла, содержащего по слову на строке,° а write-words печатает их в обратном алфавитном порядке. Ее вывод может начинаться так:
a amoeba alba samba marimba ...
и завершаться так:
... megahertz gigahertz jazz buzz fuzz
Используя преимущества векторов с указателем заполнения и map-into, мы сможем легко и эффективно написать эту программу.
232 |
Глава 13. Скорость |
В расчетных приложениях будьте аккуратны с типами bignum. Опера ции с bignum требуют выделения памяти и работают существенно мед леннее. Но даже если ваша программа должна в конце возвращать зна чения bignum, ее можно сделать эффективнее, организовав промежуточ ные результаты как значения fixnum.
Другой способ избежать выделения памяти – заставить компилятор размещать объекты не в куче, а на стеке. Если вам известно, что какой- либо объект будет использоваться временно, вы можете избежать выде ления для него памяти в куче с помощью декларации dynamic extent.
Декларируя dynamic-extent для переменной, вы утверждаете, что ее зна чение не будет жить дольше, чем сама переменная. Как может значение существовать дольше переменной? Вот пример:
(defun our-reverse (lst) (let ((rev nil))
(dolist (x lst) (push x rev))
rev))
Функция our-reverse аккумулирует переданный ей список в обратном порядке в rev и по завершении возвращает ее значение. Сама перемен ная исчезает, а список, который в ней находился, продолжает сущест вовать и возвращается назад вызвавшей функции. Дальнейшая его судьба непредсказуема.
Для контраста рассмотрим следующую реализацию adjoin:
(defun our-adjoin (obj lst &rest args) (if (apply #’member obj lst args)
lst
(cons obj lst)))
Из этого определения функции видно, что список args никуда не пере дается. Он нужен не дольше, чем сама переменная. Значит, в этой си туации имеет смысл сделать декларацию dynamic-extent:
(defun our-adjoin (obj lst &rest args) (declare (dynamic-extent args))
(if (apply #’member obj lst args) lst
(cons obj lst)))
Теперь компилятор может (но не обязан) размещать args на стеке, то есть это значение будет автоматически отброшено по выходу из our-adjoin.
13.5. Пример: заранее выделенные наборы
Чтобы избежать динамического выделения памяти в приложении, кото рое использует структуры данных, вы можете заранее разместить кон кретное их количество в пуле (pool). Когда вам необходима структура,
13.5. Пример: заранее выделенные наборы |
233 |
вы берете ее из пула, а по завершении работы с ней возвращаете струк туру назад в пул.° Чтобы проиллюстрировать эту идею, напишем прото тип программы, контролирующей перемещение кораблей в гавани, а затем перепишем этот прототип с использованием пула.
На рис. 13.4 показана первая версия. Глобальная переменная *harbour* содержит список кораблей, каждый из которых представлен в виде структуры ship. Функция enter вызывается при заходе корабля в порт; find-ship находит корабль с заданным именем (если он существует); leave вызывается, когда корабль покидает гавань.
(defparameter *harbor* nil)
(defstruct ship name flag tons)
(defun enter (n f d)
(push (make-ship :name n :flag f :tons d) *harbor*))
(defun find-ship (n)
(find n *harbor* :key #’ship-name))
(defun leave (n) (setf *harbor*
(delete (find-ship n) *harbor*)))
Рис. 13.4. Порт
Отличный подход для написания первой версии программы, но такая реализация производит достаточно много мусора. При выполнении про граммы память выделяется двумя путями: при заходе кораблей в га вань будут производиться новые структуры, а с ростом списка *harbour* будут выделяться новые ячейки.
Мы можем избавиться от обоих источников мусора, выделяя память в момент компиляции. На рис. 13.5 приведена вторая версия програм мы, которая не производит никакого мусора.
Строго говоря, выделение памяти все же происходит, но не в момент вы полнения. Во второй версии *harbour* является хеш-таблицей, а не спи ском, и пространство под нее выделяется при компиляции. Тысяча структур ship также создается во время компиляции и сохраняется в векторе pool. (Если параметр :fill-pointer имеет значение t, указатель заполнения размещается в конце вектора.) Теперь при вызове enter нам не нужно создавать новую структуру, достаточно получить одну из уже существующих в пуле с помощью make-ship. А когда leave удаляет ко рабль из гавани, соответствующая структура не становится мусором, а возвращается назад в пул.