Почему в Лиспе медленно?

Question

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

Answer 1

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

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

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

определение от «управления глоссарии памяти говорит:

1. против (1) В Лиспе минусы это примитивная операция создания списка элементов (от английского „конструкта“). Посредством расширения создается элемент cons.
2. cons (2) (подробнее см. В разделе «Распределение»). Распределение - это процесс назначения ресурсов. Когда предложено программой, менеджер памяти приложение или Распределитель выделяет блок памяти (2) для программы, чтобы хранить свои данные в. Выделение также известный как consing, от против (1) ,

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

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

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

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

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

См. Этот пример в документации Allegro CL: Some techniques for reducing consing when processing very large text files.

Answer 2

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

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

Answer 3

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

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 является «медленным» как таковым, но, тем не менее, избегать его может быть полезным. Если вы сравниваете разницу в выделенной памяти (которая занимает свое время), должно быть понятно, почему вторая версия быстрее первой.

Answer 4

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

Ненужные соображения «оказывают давление» на сборщик мусора; он чаще работает сбор мусора.

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

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

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