garbage-collection - 在函数式语言中使用大型数据结构时减少垃圾收集时间

Question

如何在函数式语言中使用大型数据结构时减少垃圾回收时间？

(我使用的是 Racket，但这个问题适用于任何带有垃圾收集器的面向功能的语言。)

函数式编程的核心习语是您设计函数来处理数据副本，并返回处理后的数据作为结果，而不是从远处改变数据结构。您不必担心额外的复制，因为垃圾收集器会过来回收不再使用的内存。

就目前而言，这很棒。但是当我开始编写处理更大数据结构的程序时，我发现更多的总运行时间被垃圾收集占用(25-35%，而不是我发现的典型小结构的 10-15% ).

这并不奇怪，因为每次函数调用都会复制更多数据，因此需要收集更多垃圾。

但这也使速度提高变得更加困难，因为垃圾收集器占用了更多的运行时间，这基本上是您无法控制的。

显而易见的解决方案是完全避免复制数据。但这会让你从远处回到变异数据，这与函数习语相矛盾。 (虽然我知道这可以在 Racket 中通过使用装箱值甚至参数来在某种程度上完成。)

除此之外，我想到了三个选项:

1. 设计您的数据结构，使其对信息进行更紧凑的编码。
2. 与其将整个数据结构传递给函数，不如提取您需要处理的数据子集(当然，假设分离和重新加入数据子集的成本节省了足够的垃圾收集时间是值得的)。
3. 在可能的情况下，将多个函数(通常将大型数据结构从一个传递到另一个，每次复制它)组合成一个尾递归函数(不会)。

这些方法有效吗？我忽略了其他人吗？

Answer 1

有一些功能性数据结构旨在降低复制成本 - 例如，如果一个函数改变树的一个分支，那么新树将共享未受影响分支的节点，并且只有变异的分支需要被复制。

克里斯冈崎的 Purely Functional Data Structures是我所知道的关于这方面最好的论文，但可能还有更多我不知道的最新研究(例如，我只通过维基百科知道的 ctrie)。