为什么Lisp中的消耗很慢？

Question

我在"On Lisp"一书中读到,应该避免cons在扩展宏的主体中过度使用.为什么被cons认为是效率低下的操作？Lisp不与cons细胞共享结构吗？

Answer 1

你需要先了解行话.

CONS是一种创造新的利弊细胞的原始手法.

Consing意味着通常在堆上分配内存,而不仅仅是cons单元:数字的构成,数组的构造,CLOS对象的构造,......

"内存管理术语表"中的定义是:

1. cons(1)在Lisp中,cons是一个创建列表元素的原始操作(来自英语"CONStruct").通过扩展,缺点是创建的元素.
2. cons(2)(有关详细信息,请参阅allocate)分配是分配资源的过程.当程序请求时,应用程序存储器管理器或分配器为程序分配存储器块(2)以存储其数据.分配也称为consing,来自cons(1).

所以,格雷厄姆使用了第二个含义.

如果格雷厄姆说'避免特别消费.一种不必要地使用的实用程序可能破坏其他有效程序的性能. - 这意味着:避免堆上不必要的内存分配.但对于任何代码 - 宏,函数等都是如此.

当计算机具有较少的内存并且垃圾收集成本较高时(特别是当它需要扫描虚拟内存系统中的交换内存时,物理内存小于虚拟内存),这一点尤为突出.

今天的问题不是一个问题,但仍然具有相关性.

以函数READ-LINE为例,它从流中读取一行并"汇集"一个新字符串.请注意,字符串不是由conses构建的,而是一个向量.我们的意思是'在堆上分配一个字符串'.如果你有一个包含大量行的大文件,那么使用一个获取缓冲区的例程并使用行字符填充缓冲区可能会更快(Common Lisp中有一些带有填充指针的向量).这样,行缓冲区只是一个对象,可以重用于此行读取函数的调用.

请参阅Allegro CL文档中的此示例:在处理非常大的文本文件时减少耗尽的一些技巧.

Answer 2

我不认为利弊很慢.它不会创建整个列表的新副本,只是将新元素附加到链接列表的前面.

如果任何事情都很慢,那就是必须为新节点分配一些内存.如果你要创建大量的节点,最好一次创建它们而不是一个一个.

Answer 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

所以:是的,避免收费可以提高性能,但是如果你知道自己在做什么,那么你应该只使用破坏性修改.我不会说消费本身是"缓慢的",但尽管如此,避免它可能是有益的.如果比较分配内存的差异(花费时间),应该清楚为什么第二个版本比第一个版本快.