Clojure头部保留

Question

我正在读O'Reilly的Clojure Programming book.

我找到了头部保留的例子.第一个例子保留对d(我推测)的引用,因此它不会收集垃圾:

(let [[t d] (split-with #(< % 12) (range 1e8))]
    [(count d) (count t)])
;= #<OutOfMemoryError java.lang.OutOfMemoryError: Java heap space>

虽然第二个例子不保留它,但它没有问题:

(let [[t d] (split-with #(< % 12) (range 1e8))]
    [(count t) (count d)])
;= [12 99999988]

我没有得到的是在哪种情况下保留了什么以及为什么.如果我试着回来[(count d)],就像这样:

(let [[t d] (split-with #(< % 12) (range 1e8))]
    [(count d)])

它似乎创造了相同的内存问题.

此外,我记得count在每种情况下都会实现/评估一个序列.所以,我需要澄清一下.

如果我(count t)首先尝试返回,那么如果我根本不返回它会如何更快/更高效？在哪种情况下保留了什么？为什么？

Answer 1

在第一个和最后一个例子中,split-with保留原始序列,同时在内存中完全实现; 因此,OOME.这种情况发生的方式是间接的; 直接保留的是t,当原始序列被保持t为懒惰的seq时,处于未实现的状态.

该方式t导致要保存的原始顺序如下.在实现之前,t是一个LazySeq存储thunk 的对象,可以在某个时刻调用以实现t; 这个thunk需要存储一个指向原始序列参数的指针,split-with然后才能实现将其传递给take-while- 请参阅实现split-with.一旦t实现,thunk就有资格获得GC(将LazySeq对象中保存它的字段设置为null),t不再保留巨大输入seq的头部.

输入seq本身正在完全(count d)实现d,需要实现,因而原始输入seq.

继续讨论为什么t被保留:

在第一种情况下,这是因为(count d)之前得到了评估(count t).由于Clojure的评估这些表达式从左到右,当地t需求流连第二个电话来算,并且由于它恰好留住了巨大的序列(如上所述),通向OOME.

只(count d)返回的最后一个例子理想情况下不应该坚持t; 不是这种情况的原因有点微妙,最好通过参考第二个例子来解释.

第二个例子恰好工作正常,因为在(count t)评估之后,t不再需要.Clojure编译器注意到这一点并使用一个聪明的技巧使本地重置nil与count正在进行的调用同时进行.Java代码的关键部分做类似的东西f(t, t=null),这样的电流值t传递给相应的功能,但当地被移交之前,控制权交给被清除f,因为这种情况作为表达的副作用,t=null这是一个参数f; 显然,Java的从左到右的语义是这项工作的关键.

回到最后一个例子,这不起作用,因为t实际上并没有在任何地方使用,并且当地人清算过程不处理未使用的本地人.(清算发生在最后一次使用时;如果程序中没有这样的一点,则没有清算.)

至于count实现延迟序列:它必须这样做,因为没有一般的方法来预测懒惰seq的长度而没有意识到它.

Answer 2

回答@MichałMarczyk,虽然正确,但有点难以理解.我发现Google网上论坛上的这篇文章更容易掌握.

这是我理解的方式:

步骤1创建延迟序列:(range 1e8).值尚未实现,我将它们标记为asterixes(*):

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ... * * *

步骤2创建两个更加懒惰的seqences,它们是"窗口",您可以通过它查看原始的,巨大的懒惰序列.第一个窗口只包含12个元素(t),另一个包含其余元素(d):

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ... * * *
t t t t t t t t t t t t t d d d d d d d d d d d d d d d d d ... d d d 

第3步 - 内存不足的情况 - 您评估[(count d) (count t)].所以,首先你计算元素d,然后在t.将要发生的是,您将通过从第一个元素开始的所有值d并实现它们(标记为!):

* * * * * * * * * * * * * ! * * * * * * * * * * * * * * * * ... * * *
t t t t t t t t t t t t t d d d d d d d d d d d d d d d d d ... d d d 
                          ^
                         start here and move right ->

* * * * * * * * * * * * * ! ! * * * * * * * * * * * * * * * ... * * *
t t t t t t t t t t t t t d d d d d d d d d d d d d d d d d ... d d d 
                            ^

* * * * * * * * * * * * * ! ! ! * * * * * * * * * * * * * * ... * * *
t t t t t t t t t t t t t d d d d d d d d d d d d d d d d d ... d d d 
                              ^

                     ...

; this is theoretical end of counting process which will never happen
; because of OutOfMemoryError
* * * * * * * * * * * * * ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ... ! ! !
t t t t t t t t t t t t t d d d d d d d d d d d d d d d d d ... d d d 
                                                                    ^

问题是所有已实现的值(!)都被保留,因为仍然需要集合的头部(前12个元素) - 我们仍然需要进行评估(count t).这会消耗大量内存导致JVM崩溃.

第3步 - 有效场景 - 这次你评估[(count t) (count d)].所以我们首先想要计算较小的头部序列中的元素:

! * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ... * * *
t t t t t t t t t t t t t d d d d d d d d d d d d d d d d d ... d d d 
^
start here and move right ->

                        ! * * * * * * * * * * * * * * * * * ... * * *
t t t t t t t t t t t t t d d d d d d d d d d d d d d d d d ... d d d 
                        ^

然后,我们按d顺序计算元素.编译器知道t不再需要来自的元素,所以它可以垃圾收集它们释放内存:

                          ! * * * * * * * * * * * * * * * * ... * * *
t t t t t t t t t t t t t d d d d d d d d d d d d d d d d d ... d d d 
                          ^

                            ! * * * * * * * * * * * * * * * ... * * *
t t t t t t t t t t t t t d d d d d d d d d d d d d d d d d ... d d d 
                            ^

                     ...

                                                            ...     !
t t t t t t t t t t t t t d d d d d d d d d d d d d d d d d ... d d d 
                                                                    ^

现在我们可以看到,因为t不再需要来自元素,编译器能够在通过大序列时清除内存.