OCaml From the Ground Up声明。。。
在机器级别，链表是一对头值和一个指向尾的指针。
我听说链表(在命令式语言中(往往很慢，因为缓存未命中、内存开销和指针追逐。我很好奇OCaml的垃圾收集器或内存管理系统是否避免了这些问题，以及它们是否在内部使用了与其他语言中的链表不同的技术或优化。
OCaml管理自己的内存，它以自己的方式调用系统级内存分配和释放原语(例如，它可以在程序启动期间分配一大块堆内存，并管理上面的OCaml值(，因此，如果编译器和/或运行时知道您正在分配一个固定大小的列表，它可以安排单元在存储器中彼此靠近。由于语言本身没有指针类型，它可以在垃圾收集期间移动值，以避免内存碎片，这是像C或C++这样的语言无法做到的(或者在允许移动的同时努力维护抽象(。
这些是关于垃圾回收语言(命令式或非命令式(如何优化内存管理的一般指针，但了解垃圾回收器可以了解更多关于垃圾回收器如何在OCaml中实际工作的详细信息。
链表确实是一个很难迭代的结构。
但OCaml分配内存的方式以及大多数情况下创建列表的方式大大缓解了这种情况。
在OCaml中，GC将一大块内存分配为它的(小(堆，并维护一个指向已使用部分末尾的指针。分配只是将指针增加所需的内存量。
再加上大多数时间列表都是在很短的时间内构建的。通常，创建列表是唯一分配内存的事情。以List.map或List.rev为例。这将生成一个列表，其中列表的节点在内存中是连续的。因此，链表并不是在地址空间中跳跃，而是包含在一个小区块中。这使得缓存的工作效果比您对链表的预期要好得多。重复列表实际上会按顺序访问内存。
上面的意思是，许多列表比其他语言的列表要有序得多。而且很多时间列表都是临时的，并且将完全在缓存中。它的表现比它应该做的要好得多
这还有另一层。在OCaml中，垃圾收集器是一代GC。在频繁扫描的小堆上创建新值。因此，临时值被迅速回收。在次要堆上保持活动状态的值被复制到主要堆，而主要堆的扫描频率较低。复制操作压缩值，从而消除由不再活动的值引起的任何漏洞。如果列表节点一开始就有间隙，这将使列表节点再次紧密相连。当扫描主堆时，也会发生同样的事情，压缩内存，使分配的值在时间上更接近。
虽然这些都不能保证列表在内存中是连续的，但似乎可以避免其他语言中与链表相关的许多不良影响。尽管如此，当您需要对数据进行迭代，或者更糟的是频繁访问第n个节点时，您不应该使用列表。请改用数组。除非你的列表很小，否则追加也很糟糕(对于大列表，会溢出堆栈(。由于时间较晚，您通常会反向构建列表，将项目添加到前面而不是末尾，然后将列表反向作为最后一步。最后的List.rev会给你一个完全连续的列表。