Почему медлительность в Лиспе медленная?

Я прочитал в книге "На Лиспе", что следует избегать чрезмерного использования cons в теле развернутых макросов. Почему cons считается неэффективной операцией? Разве Лисп не делит структуру совместного использования с клетками "против"?

Источник

4 ответа

Решение

Вы должны сначала понять жаргон.

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

Объединение означает выделение памяти в куче в целом, а не только в ячейках объединения: Объединение чисел, Объединение массивов, Объединение объектов CLOS, ...

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

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

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

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

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

Сегодня консинг не является проблемой, но все еще может быть актуальным.

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

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

Источник

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

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

Источник

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

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

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

Источник

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

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

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

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

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

Источник
Другие вопросы по тегам