Почему задержка в Lisp медленная?

Ответ 1

Сначала вам нужно понять жаргон.

CONS - это примитивная операция для создания свежей ячейки cons.

Consing означает выделение памяти в куче вообще, а не только cons cells: Consing of numbers, Consing of arrays, Consing of CLOS objects,...

В определении из "глоссария управления памятью" говорится:

• cons (1) В Lisp cons - это примитивная операция, создающая элемент списка (из английского "CONStruct" ). Посредством расширения создается элемент cons.
• cons (2) (для получения полной информации см. раздел "Распределение" ). Распределение - это процесс назначения ресурсов. когда запрошенных программой, диспетчер памяти приложений или распределитель выделяет блок памяти (2) для сохранения программы его данные в. Распределение также известный как consing, от минус (1).

Итак, Грэм использует второй смысл.

Если Грэм говорит: "Избегайте особого внимания. Утилита, которая без сомнения оправдывает себя, может испортить производительность другой эффективной программы". - это означает: избегать ненужного выделения памяти в куче. Но это может быть справедливо для любого кода - макроса, функции и т.д.

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

Сегодня consing менее проблематичен, но может быть актуальным.

Возьмем, например, функцию READ-LINE, она читает строку из потока и "соглашается" с новой строкой. Обратите внимание, что строка не построена из conses, но это вектор. Мы имеем в виду здесь "выделяет строку в куче". Если у вас большой файл с большим количеством строк, может быть быстрее иметь подпрограмму, которая получает буфер и заполняет буфер символами строки (в этом есть векторы в Common Lisp с указателем заполнения). Таким образом, буфер строки является всего лишь одним объектом и потенциально может быть повторно использован для вызовов этой функции чтения строки.

См. этот пример в документации Allegro CL: Некоторые методы сокращения consing при обработке очень больших текстовых файлов.

Ответ 2

Я не думаю, что cons работает медленно. Он не создает новую копию всего списка, он просто добавляет новый элемент в начало связанного списка.

Если что-то медленное, то ему нужно выделить некоторую память для нового node. Если вы создаете много и много узлов, возможно, лучше создать их все за один раз, а не один за другим.

Ответ 3

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

CL-USER> (defun non-destructive ()
           (progn
             (reverse (loop for x from 1 to 100000 collecting x))
             nil))
NON-DESTRUCTIVE
CL-USER> (defun destructive ()
           (progn
             (nreverse (loop for x from 1 to 100000 collecting x))
             nil))
DESTRUCTIVE
CL-USER> (time (non-destructive))
(NON-DESTRUCTIVE) took 140 milliseconds (0.140 seconds) to run 
                    with 2 available CPU cores.
During that period, 156 milliseconds (0.156 seconds) were spent in user mode
                    0 milliseconds (0.000 seconds) were spent in system mode
94 milliseconds (0.094 seconds) was spent in GC.
 1,600,024 bytes of memory allocated.
NIL
CL-USER> (time (destructive))
(DESTRUCTIVE) took 93 milliseconds (0.093 seconds) to run 
                    with 2 available CPU cores.
During that period, 93 milliseconds (0.093 seconds) were spent in user mode
                    0 milliseconds (0.000 seconds) were spent in system mode
63 milliseconds (0.063 seconds) was spent in GC.
 800,024 bytes of memory allocated.
NIL

Итак: Да, избегая consing, можно повысить производительность, но вы должны использовать только деструктивную модификацию, если знаете, что делаете. Я бы не сказал, что consing является "медленным" как таковым, но, тем не менее, избегать его может быть полезным. Если вы сравниваете разницу в выделенной памяти (которая занимает свое время), должно быть понятно, почему вторая версия быстрее первой.

Ответ 4

Заключение, которое является Lisp жаргоном для динамического распределения памяти, не замедляется. Но он добавляет накладные расходы на программу. Вы не можете просто посмотреть на стоимость выделения объекта, но при полной стоимости жизненного цикла, от создания объекта до его восстановления, когда он стал мусором.

Ненужное поглощение "оказывает давление" на сборщик мусора; это делает сбор мусора более часто.

(Это не проблема Lisp. Например, C-программы, которые делают много вызовов malloc и free, или программ на С++, которые используют new и delete много, также не будут выполняться как а также аналогичные программы, которые лучше организованы, чтобы избежать многих из этих вызовов.)

Вам не нужно быть параноидальным, чтобы избежать необходимости в Lisp, потому что это сделает программирование неудобным, а некоторые из трюков для избежания consing, связанные с разрушительным повторным использованием существующих объектов, подвержены ошибкам.

Но он может заплатить, чтобы следить за тем, что происходит во внутренних циклах, которые выполняются много раз, и в низкоуровневом коде, таком как служебные функции, предназначенные для широкого повторного использования. Например, предположим, что mapcar внутренне построил список результатов в обратном порядке, а затем поместил его в правильном порядке, вызвав reverse вместо nreverse. Тогда все, что называет mapcar, будет страдать от ненужных запросов.