lomeo: (лямбда)
[personal profile] lomeo
Из дискуссии с [livejournal.com profile] 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: [livejournal.com profile] sassa_nf всё же заставил java работать правильно. За что ему отдельное спасибо!

Date: 2012-12-01 11:56 am (UTC)
From: [identity profile] metaclass.livejournal.com
В локальной переменной, которая не собирается gc, что хранится?

Date: 2012-12-01 12:07 pm (UTC)
From: [identity profile] lomeo.livejournal.com
В данном случае? messages, со всеми уже выведенными хвостами, жадно пожирающими память.

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

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

Date: 2012-12-01 12:47 pm (UTC)
From: [identity profile] tonsky.livejournal.com
Stream хранит ссылку на голову последовательности? Нафига?

Date: 2012-12-01 01:07 pm (UTC)
From: [identity profile] thedeemon.livejournal.com
Нет же, ссылка в стеке оказывается, из-за нее голова потока не считается мусором, а за ней и другие элементы.

Date: 2012-12-01 05:28 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Ну Stream это же head и tail, только tail ленивый. Так вот даже когда нам не нужны предыдущие вычисления они будут храниться. Обязаны, пока они являются локальными переменными.

Date: 2012-12-01 05:40 pm (UTC)
From: [identity profile] tonsky.livejournal.com
Да, точно, иммутабельность же.

Date: 2012-12-01 05:45 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Кстати, а как с этим в clojure?

Date: 2012-12-01 01:00 pm (UTC)
From: [identity profile] mr-aleph.livejournal.com
что-то как-то непонятно, можно байткод обоих случаев в студию?

вообще любоей вменяемый компилятор делает анализ живости, поэтому если локальная переменная с какого-то момента не используется, то ее GC и не должен видеть.
Edited Date: 2012-12-01 01:04 pm (UTC)

Date: 2012-12-01 02:45 pm (UTC)
From: [identity profile] jakobz.livejournal.com
В дотнете делает только в релизе - чтобы не печалить индусов в дебаггере.

Date: 2012-12-01 04:26 pm (UTC)
From: [identity profile] mr-aleph.livejournal.com
ну на jvm интерпретатор такого тоже не делает.

Date: 2012-12-01 05:26 pm (UTC)
From: [identity profile] 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 строчки.

Date: 2012-12-01 05:47 pm (UTC)
From: [identity profile] mr-aleph.livejournal.com
так на строчках 13 и 51 поток используется как ресивер виртуального вызова Stream.foreach

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

Date: 2012-12-01 05:59 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Проверь!

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

Date: 2012-12-01 06:39 pm (UTC)
From: [identity profile] mr-aleph.livejournal.com
да, действительно застревает.

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

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

(а Stream.foreach оказывается свой this перезаписывает. поэтому он там и не застревает как я ожидал).
Edited Date: 2012-12-01 06:39 pm (UTC)

Date: 2012-12-01 06:47 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Угу, чудеса, причём в спеке об этом как-то мимоходом сказано (сейчас даже найти не смог). А нарвался я на это много лет назад, разбираясь почему память течёт.

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

Date: 2012-12-03 08:59 am (UTC)
From: [identity profile] mr-aleph.livejournal.com
по поводу UPD будут какие-нибудь детали? :-)

Date: 2012-12-03 09:28 am (UTC)
From: [identity profile] lomeo.livejournal.com
Упс. Ссылку криво вписал, поправил.

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

Date: 2012-12-03 09:51 am (UTC)
From: [identity profile] mr-aleph.livejournal.com
я кстати с -Xcomp первым делом попробовал... не помогает мне на моей 1.7.0 :-)

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

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

Date: 2012-12-03 12:00 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Да, поведение совершенно противоестественное.

Date: 2012-12-01 05:54 pm (UTC)
From: [identity profile] 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 не сохранялся, мне не особо понравились.

Date: 2012-12-01 06:05 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Спасибо, глянул реализацию.

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

Date: 2012-12-01 06:17 pm (UTC)
From: [identity profile] lomeo.livejournal.com
Кстати, также очень не нравится, что из-за этого нельзя описывать рекурсивные фишки, типа
val fibs: Stream[Int] = 0 #:: 1 #:: (fibs, fibs.tail).zipped.map(_ + _)

Опять локальные переменные, опять out-of-memory.
Edited Date: 2012-12-01 06:18 pm (UTC)

Date: 2012-12-01 06:53 pm (UTC)
From: [identity profile] andy legkiy (from livejournal.com)
Видимо для выбранных нужд коллекции с memoization и правда не очень подходят.
Прийдется возращаться к рекурсии ;)

Date: 2012-12-01 06:46 pm (UTC)
From: [identity profile] potan.livejournal.com
В Heskell подобное тоже случается. Правда, хвостовая рекурсия и умный оптимизатор делают это событие сравнительно редким.

Date: 2012-12-01 10:21 pm (UTC)
From: [identity profile] thesz.livejournal.com
Слабо пример случившегося привести?

Date: 2012-12-02 09:29 am (UTC)
From: [identity profile] potan.livejournal.com
Prelude> let n=[1..] ; m = n !! (2 ^ 30) ; k = m + if m == 0 then head n else 1 in k

Date: 2012-12-02 09:38 am (UTC)
From: [identity profile] lomeo.livejournal.com
Нечестно! Читер! Читер! :-)

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

Date: 2012-12-02 09:38 am (UTC)
From: [identity profile] thesz.livejournal.com
Это не совсем другое, но заметно другой пример. В вычислении k используется n, хотя человеку понятно, что происходит, а компилятору нет. Здесь нужен умный компилятор. В вычислении foreach (x : s) { } переменная s не используется, она может быть заменена прямой подстановкой, компилятор и RTS могут быть заметно тупей.

Date: 2012-12-02 09:48 am (UTC)
From: [identity profile] potan.livejournal.com
Мог бы. Тем более там val, а не var. Но тягаться по интеллекту с ghc компиляторы еще долго не смогут.

Date: 2012-12-02 04:06 am (UTC)
From: [identity profile] lomeo.livejournal.com
Там же вроде не хвостовая рекурсия, там и стека-то толком нет.

Date: 2012-12-02 09:33 am (UTC)
From: [identity profile] potan.livejournal.com
Ленивость в некотором смысле ей эквивалентна. Но по моему он хвостовой вызов умеет оптимизировать - раз до туда управление дошло, значит результат вызова понадобился и возвращать недовыполненное значение смысла не имеет.

Profile

lomeo: (Default)
Dmitry Antonyuk

December 2015

S M T W T F S
  12345
6789101112
131415 16171819
20212223242526
2728293031  

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 24th, 2017 03:50 pm
Powered by Dreamwidth Studios