clojure 中内存不足 - 惰性序列上的嵌套缩减

Question

像添加3个嵌套reduce这样简单的事情就会给我一个内存不足的错误。

Execution error (OutOfMemoryError) at .../my-large-lazy$iter$fn$fn$iter$fn$fn$iter$fn$fn (serial_write.clj:39).
Java heap space: failed reallocation of scalar replaced objects

当我评估

(add-cords 1000)

我正在运行时出现问题

java -Xmx1G ...

(defn my-large-lazy
  [size]
  (for [x (range size)]
    (for [y (range size)]
      (for [z (range size)]
        {:x x :y y :z z}))))

(defn add-coords 
  [size]
  (reduce (fn [sum-1 x-1]
            (reduce (fn [sum-2 x-2]
                      (reduce (fn [sum-3 x-3]
                                (+ sum-3 (:x x-3) (:y x-3) (:z x-3)))
                              sum-2 x-2))
                    sum-1 x-1))
          0 (my-large-lazy size)))

我希望它计算出的总和可能是几KB的内存，而不是1GB的错误。理想情况下，内存需求应该是 O(1)。尺寸越大，占用的内存越大。在

{:x x :y y :z z}

中避免使用字典会有所帮助，但在原始程序中这是不可避免的。我正在研究如何有效地实施

add-cords

。

我知道持有序列头和其他常见问题。但这似乎在逃避我。我尝试了一个测量分配的探查器，但我不明白为什么它们没有被释放。我尝试了几种实现此功能的变体，但都遇到了相同的 OOM 问题。我还尝试了各种 JVM，总体内存略有差异，但它们都失败了。

Answer 1

这是一个非常有趣的问题。确实reduce过程中没有保留序列的head，但是什么原因导致OOM错误呢？

即使原始惰性序列的头部在归约过程中没有保留，当前的 LazySeq 对象仍保留在内存中，因为它保存了对序列其余部分的引用。并且由于当前的 LazySeq 实例被保留，因此它的头元素也被保留。

并且由于您有惰性序列的嵌套结构，因此最外面的当前序列元素中引用的所有内容也会保留，即使这些元素已经被处理，直到最外面的当前序列移动到下一个元素。

对于您的示例，当我们处理

x=9,y=9,z=9

时，持有

x=9

的外部惰性 seq 仍在内存中，这意味着

x=9,y=0,z=0

、

x=9,y=0,z=1

、...

x=9,y=9,z=9

也在那里。这些将被保留，直到我们移动到最外层序列中的

x=10

。

---

解决方案是稍微重新组织代码：代替惰性序列的嵌套结构，将其展平为单个惰性序列：

(defn my-large-lazy' [size]
  (for [x (range size)
        y (range size)
        z (range size)]
    {:x x :y y :z z}))

(defn internal-sum [sum-3 x-3] (+ sum-3 (:x x-3) (:y x-3) (:z x-3)))

(println (reduce internal-sum 0 (my-large-lazy' 100)))