Про потоки (не мыслей)

[lomeo]

Из дискуссии с sassa_nf.

В java локальные переменные метода не собираются сборщиком мусора, пока мы не выйдем из метода (наверх, разумеется, а не глубже). Это важно, потому что Scala'вские Stream из-за этого часто становятся бесполезны.

Вот имеем мы некий Stream, который любят сравнивать с Haskell'евским списком. И начинаем его обрабатывать. А обработка через некоторое время завешается с OutOfMemoryError:

val messages = Stream continually nextMessage
for (message <- messages) doSomething(message)

А теперь перепишем это так:

for (message <- Stream continually nextMessage) doSomething(message)

и обработка у нас будет вестись вечно.

А всё потому, что первый способ генерит astore, который создаёт локальную переменную. А второй — нет.

UPD: sassa_nf всё же заставил java работать правильно. За что ему отдельное спасибо!

Comments

[metaclass.livejournal.com]

В локальной переменной, которая не собирается gc, что хранится?

[lomeo.livejournal.com]

В данном случае? messages, со всеми уже выведенными хвостами, жадно пожирающими память.

Т.е. в первом примере сгенерится astore и в нужном месте (где foreach, если знаешь Scala, или где <-, если не знаешь) будет вызван aload.

Во втором примере в том месте, где в первом был aload будет сделан непосредственный вызов — создание Stream-а. И вот он уже будет собираться gc.

[tonsky.livejournal.com]

Stream хранит ссылку на голову последовательности? Нафига?

[thedeemon.livejournal.com]

Нет же, ссылка в стеке оказывается, из-за нее голова потока не считается мусором, а за ней и другие элементы.

[lomeo.livejournal.com]

Ну Stream это же head и tail, только tail ленивый. Так вот даже когда нам не нужны предыдущие вычисления они будут храниться. Обязаны, пока они являются локальными переменными.

[tonsky.livejournal.com]

Да, точно, иммутабельность же.

[lomeo.livejournal.com]

Кстати, а как с этим в clojure?

[mr-aleph.livejournal.com]

что-то как-то непонятно, можно байткод обоих случаев в студию?

вообще любоей вменяемый компилятор делает анализ живости, поэтому если локальная переменная с какого-то момента не используется, то ее GC и не должен видеть.

[jakobz.livejournal.com]

В дотнете делает только в релизе - чтобы не печалить индусов в дебаггере.

[mr-aleph.livejournal.com]

ну на jvm интерпретатор такого тоже не делает.

[lomeo.livejournal.com]

Это старая фишка, нарывался много лет назад, поэтому помню хорошо.

Ну вот для этого:

object X {

    def main(xs: Array[String]) = {
        for (x <- Stream.continually(1)) {}  // первый случай

        val xs = Stream.continually(1)  // второй случай
        for (x <- xs) {}
    }

}

байткод будет

public final class X$ extends java.lang.Object implements scala.ScalaObject{
public static final X$ MODULE$;

public static {};
  Code:
   0:	new	#9; //class X$
   3:	invokespecial	#12; //Method "":()V
   6:	return

public void main(java.lang.String[]);
  Code:
   0:	getstatic	#19; //Field scala/package$.MODULE$:Lscala/package$;
   3:	invokevirtual	#24; //Method scala/package$.Stream:()Lscala/collection/immutable/Stream$;
   6:	new	#26; //class X$$anonfun$main$1
   9:	dup
   10:	invokespecial	#27; //Method X$$anonfun$main$1."":()V
   13:	invokevirtual	#33; //Method scala/collection/immutable/Stream$.continually:(Lscala/Function0;)Lscala/collection/immutable/Stream;
   16:	new	#35; //class X$$anonfun$main$2
   19:	dup
   20:	invokespecial	#36; //Method X$$anonfun$main$2."":()V
   23:	invokevirtual	#42; //Method scala/collection/immutable/Stream.foreach:(Lscala/Function1;)V
   26:	getstatic	#19; //Field scala/package$.MODULE$:Lscala/package$;
   29:	invokevirtual	#24; //Method scala/package$.Stream:()Lscala/collection/immutable/Stream$;
   32:	new	#44; //class X$$anonfun$1
   35:	dup
   36:	invokespecial	#45; //Method X$$anonfun$1."":()V
   39:	invokevirtual	#33; //Method scala/collection/immutable/Stream$.continually:(Lscala/Function0;)Lscala/collection/immutable/Stream;
   42:	astore_2
   43:	aload_2
   44:	new	#47; //class X$$anonfun$main$3
   47:	dup
   48:	invokespecial	#48; //Method X$$anonfun$main$3."":()V
   51:	invokevirtual	#42; //Method scala/collection/immutable/Stream.foreach:(Lscala/Function1;)V
   54:	return

}

Обрати внимание на 42-43 строчки.

[mr-aleph.livejournal.com]

так на строчках 13 и 51 поток используется как ресивер виртуального вызова Stream.foreach

до того как этот foreach вернется поток точно не помрет в обоих случаях, а после того как вернется... ну в интерпретаторе он допустим застрянет в локале ненадолго, но я более чем уверен, что для C1/C2 локал мертв после 43й строчки.

[lomeo.livejournal.com]

Проверь!

Закомментируй первый случай, скомпиль, запусти. Убедись, что падает.
Раскомментируй, скомпиль, запусти. Убедись, что вертится.

[mr-aleph.livejournal.com]

да, действительно застревает.

чудеса! совершенно непонятно зачем и где они его удерживают. я бы не стал.

ради интереса хотел посмотреть ассемблерный код, но на маке это надо через скакалочку прыгать, оказывается...

(а Stream.foreach оказывается свой this перезаписывает. поэтому он там и не застревает как я ожидал).

[lomeo.livejournal.com]

Угу, чудеса, причём в спеке об этом как-то мимоходом сказано (сейчас даже найти не смог). А нарвался я на это много лет назад, разбираясь почему память течёт.

foreach — тоже угу, хвостато-рекурсивный.

[mr-aleph.livejournal.com]

по поводу UPD будут какие-нибудь детали? :-)

[lomeo.livejournal.com]

Упс. Ссылку криво вписал, поправил.

Смысл такой, что на некоторых jvm да с некоторыми ключами jit оптимизирует хранение переменной (регистр, параметр следующей функции, х.з.). И gc её всё-таки убивает.

[mr-aleph.livejournal.com]

я кстати с -Xcomp первым делом попробовал... не помогает мне на моей 1.7.0 :-)

ну хоть где-то починили, хотя я прямо так скажем ожидал, что с версии 0 должно нормально это работать :-)

[хорошо хоть мое шестое чувство меня не подвело :-)]

[lomeo.livejournal.com]

Да, поведение совершенно противоестественное.

[andy legkiy (from livejournal.com)]

Где-то на stackoverflow alexrom советовал пробовать ephemeral stream, из scalaz. Оно память не жрет.
https://github.com/scalaz/scalaz/blob/master/core/src/main/scala/scalaz/EphemeralStream.scala

> import scalaz.EphemeralStream
> val stream = EphemeralStream.range(0, 100000000)
> stream.length
  res0: Int = 100000000

Советы использовать tailrec, чтобы head не сохранялся, мне не особо понравились.

[lomeo.livejournal.com]

Спасибо, глянул реализацию.

Так там weak reference! У этого-то, конечно, будут чиститься все tail (кроме самого первого Stream, разумеется).

[lomeo.livejournal.com]

Кстати, также очень не нравится, что из-за этого нельзя описывать рекурсивные фишки, типа

val fibs: Stream[Int] = 0 #:: 1 #:: (fibs, fibs.tail).zipped.map(_ + _)

Опять локальные переменные, опять out-of-memory.

[andy legkiy (from livejournal.com)]

Видимо для выбранных нужд коллекции с memoization и правда не очень подходят.
Прийдется возращаться к рекурсии ;)

[potan.livejournal.com]

В Heskell подобное тоже случается. Правда, хвостовая рекурсия и умный оптимизатор делают это событие сравнительно редким.

[thesz.livejournal.com]

Слабо пример случившегося привести?

[potan.livejournal.com]

Prelude> let n=[1..] ; m = n !! (2 ^ 30) ; k = m + if m == 0 then head n else 1 in k

[lomeo.livejournal.com]

Нечестно! Читер! Читер! :-)

У тебя два использования n. Он просто обязан хранить весь список.

[thesz.livejournal.com]

Это не совсем другое, но заметно другой пример. В вычислении k используется n, хотя человеку понятно, что происходит, а компилятору нет. Здесь нужен умный компилятор. В вычислении foreach (x : s) { } переменная s не используется, она может быть заменена прямой подстановкой, компилятор и RTS могут быть заметно тупей.

[potan.livejournal.com]

Мог бы. Тем более там val, а не var. Но тягаться по интеллекту с ghc компиляторы еще долго не смогут.

[lomeo.livejournal.com]

Там же вроде не хвостовая рекурсия, там и стека-то толком нет.

[potan.livejournal.com]

Ленивость в некотором смысле ей эквивалентна. Но по моему он хвостовой вызов умеет оптимизировать - раз до туда управление дошло, значит результат вызова понадобился и возвращать недовыполненное значение смысла не имеет.