Clojure удержание головы

Я читаю Clojure книгу программирования О'Рейли..

Я придумал пример удержания головы. В первом примере сохраняется ссылка на 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) во-первых, как это будет быстрее/больше памяти, тогда, если я вообще не верну его? И что и зачем в этом случае сохраняется?

Ответ 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.

Сам входной ввод полностью реализуется (count d), который должен реализовать d, и, следовательно, исходный ввод seq.

Переходим к тому, почему t сохраняется:

В первом случае это происходит потому, что (count d) оценивается до (count t). Поскольку Clojure оценивает эти выражения слева направо, локальный t должен зависать для второго вызова для подсчета, и поскольку он происходит, чтобы удерживаться на огромном seq (как объяснялось выше), это приводит к OOME.

Последний пример, когда возвращается только (count d), в идеале не должен оставаться на t; причина, по которой это не так, несколько тонкая и лучше всего объясняется ссылкой на второй пример.

Второй пример работает нормально, потому что после (count t) оценивается t больше не требуется. Компилятор Clojure замечает это и использует умный трюк, чтобы локальный reset to nil одновременно с созданным вызовом count. Ключевая часть кода Java делает что-то вроде f(t, t=null), так что текущее значение t передается соответствующей функции, но локаль очищается до того, как управление передается на f, так как это происходит как сторона эффект выражения t=null, который является аргументом для f; Очевидно, что здесь используются семантика Java слева направо.

В последнем примере это не работает, потому что t фактически не используется нигде, а неиспользуемые локали не обрабатываются процессом очистки локальных сетей. (Очистка происходит в момент последнего использования, при отсутствии такой точки в программе нет клиринга.)

Что касается count реализации ленивых последовательностей: он должен это делать, поскольку нет общего способа предсказать длину ленивого seq, не осознавая этого.

Ответ 2

Ответа на этот вопрос @Michał Marczyk, правда, немного сложно понять. Я нахожу этот пост в Google Groups легче понять.

Вот как я это понимаю:

Шаг 1 Создайте ленивую последовательность: (range 1e8). Значения еще не реализованы, я обозначил их как астерикс (*):

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

Шаг 2 Создайте еще две ленивые последовательности, которые являются "окнами", через которые вы смотрите на оригинальную, огромную ленивую последовательность. Первое окно содержит только 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)]. Поэтому мы сначала хотим подсчитать элементы в более мелкой последовательности head:

! * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ... * * *
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 больше не нужны, компилятор смог очистить память, когда она прошла через большую последовательность.