为什么在Haskell中，[x|x<-[1..10]]方法如此缓慢？

Question

为什么像这样的东西在Haskell中运行非常缓慢？

test = [x|a<-[1..100],b<-[1..100],c<-[1..100],d<-[1..100],let x = a]

print $ length test

只需要运行约10^8个数字，本应在瞬间完成，但看起来却像是永远运行下去，并且几乎崩溃。

- CYC

---

虽然这并不回答“为什么”的问题，但是可以通过进行优化编译来改善情况。我在ghci中观察到25秒的运行时间；使用“-O0”编译后为20秒；但是如果使用“-O2”编译，则只需要0.3秒。 - Daniel Wagner

为什么最终答案是10的8次方而不是100，因为有一条赋值语句 let x = a？ - Kamel

@Kamel let x = a 在所有绑定之后，因此 x 必须被复制 10^8 次。 - András Kovács

@AndrásKovács那么，如果let x = a对最终的test结果没有影响，那它是什么意思呢？ - Kamel

@Kamel 这意味着 x 现在绑定到了 a。问题在于，由于列表中 (>>=) 的定义，a（因此 x）的值取决于所有绑定。例如，为了真正展示仅具有绑定如何影响结果的效果：[5| _ <- [1..10]] 输出 [5,5,5,5,5,5,5,5,5,5]。 - MasterMastic

@MasterMastic 很棒的示例和信息，谢谢！ - Kamel

Answer 1

您是在ghci中运行还是在编译后的程序中运行？这将产生很大的区别。

如果在ghci中运行，那么ghci会保留计算出的test值，以便稍后使用。通常这是个好主意，但在这种情况下不是，因为test是一个巨大的值，而重新计算它的成本很低。有多巨大呢？首先，它是一个包含10^8个元素的列表，在64位系统上，一个列表的成本是每个元素24字节，所以已经有了2.4G的空间成本。然后是值本身的空间使用。人们可能认为这些值都来自于[1..100]，所以它们应该是共享的，并且总体上使用的空间量可以忽略不计。但是列表中的值实际上是x的形式，它可能取决于a、b、c和d，并且length在遍历列表时不会检查列表中的值。因此，每个元素将被表示为一个闭包，引用a、b、c和d，这至少需要40个字节（8 *（4 + 1）），这使得总计达到了6.4G。

这相当多，当您分配6.4G的数据时，垃圾收集器必须进行大量复制。这就是需要花费很长时间的原因，而不是实际计算列表或其长度。

如果您编译程序

test = [x|a<-[1..100],b<-[1..100],c<-[1..100],d<-[1..100],let x = a]

main = print $ length test

那么由于计算长度时没有使用test，它不必保持活动状态，显然它永远不会再被使用。因此，现在垃圾收集器几乎没有工作要做，程序在几秒钟内运行（对于大约10^8个列表节点分配和Integer上的计算是合理的）。

- Reid Barton

Answer 2

你不仅仅是循环运行了10^8次，而且还创建了一个有10^8个元素的列表。由于你使用了length函数，Haskell必须实际评估整个列表才能返回它的长度。列表中的每个元素占用一个字，可能是32位或64位。在乐观的假设下，它是32位（4字节），你刚刚分配了400 MB（约381.5 MiB）的内存。如果是64位，则刚刚分配了800 MB（约763 MiB）的内存。根据您的系统上正在进行的其他操作，您可能刚刚通过一次性分配如此多的RAM而达到了交换文件/交换分区的限制。

如果还有其他微妙之处，我不知道，但内存使用是我首先怀疑为什么速度这么慢的原因。

- rmunn

---

你可能低估了最终为此分配的总内存量。但我真的不认为这是问题所在：在现代系统上，1GB不会强制你进行交换；即使如此，在任何给定时间，我们只需要在内存中保留最多10^6个元素。 GHC的分配器可以轻松处理100万次分配；等到你看到即使是简单的、短期运行的程序在剖析输出中出现多少GB的分配/释放时，你就会明白了。 - Daniel Wagner

毫无疑问，我不是Haskell专家（我更了解F#，但即使在那里我也只是涉猎）。@CYC，如果Daniel Wagner说的任何话与我相矛盾，请听他的，而不是我。我大多数只是猜测。 - rmunn

@DanielWagner 为什么它只需要在任何给定时间保留10^6个元素的内存？ - user253751

@immibis 它不需要保留那么多，但由于 GC 不会在每个元素被消耗后执行，因此它可能会同时收集那么多。 - Thomas M. DuBuisson