замыкания

[thedeemon]

Некоторое время назад сделал себе трекер аллокаций в D и обнаружил, что замыкания там реализованы несколько не так, как я ожидал, а довольно остроумным способом. Давайте для примера опишем простую ФВП и попередаем ей из одной функции всякие лямбды, захватывающие разные переменные из окружения, да по нескольку раз :

int twice(int delegate(int) f, int x) { return f(f(x)); } 

void fun() 
{
    int x = 10, y = 100;
    byte[40] arr;
    double z = 55;
    foreach(i; 0..3)
        twice(n => n + arr[8] + x, i).writeln;
    foreach(i; 10..13)
        twice(n => n + y++, i).writeln;
    foreach(i; 20..23)
        twice(n => n + y + arr[2], i).writeln;
}

Теперь вызовем fun(). Как думаете, сколько тут будет сделано аллокаций и сколько всего памяти под них будет запрошено? (компиляем в 32 бита)

Ответ: одна единственная аллокация в 52 байта (40 байт на массив arr, по 4 байта на x и y, плюс 4 байта служебных). Она происходит при входе в fun(), при этом упоминаемые в замыканиях x, y и arr сразу размещаются в этом выделенном на куче фрагменте, а остальные локальные переменные живут на стеке. Все замыкания внутри fun ссылаются на этот один кусочек памяти, и сколько бы их ни было разных, сколько бы раз они не создавались/передавались, никаких новых аллокаций не происходит. И даже никакого копирования данных не делается. Помните высказывания о том, что замыкания - это объекты для бедных и наоборот? Тут, по сути, как раз получился объект: его данные - это тот фрагмент выделенной на куче памяти, где лежат захватываемые переменные, а его методы - это все те замыкания, которые какие-то из этих переменных захватывают. По-моему, красиво.

Еще один момент: если добавить в тип ФВП одно слово

int twice(scope int delegate(int) f, int x) { return f(f(x)); } 

то при вызове fun() не произойдет ни одной аллокации вообще. Это волшебное слово означает, что ФВП не будет нигде сохранять ссылки на переданное замыкание и его данные, а значит им не нужно жить дольше, чем работает fun(), и их можно оставить на стеке. Тогда все замыкания просто ссылаются на ее фрейм на стеке, аллоцировать на куче ничего не надо.

А сколько и каких аллокаций сделает аналогичный код на вашем любимом языке?

Comments

[chaource.livejournal.com]

I don't quite understand the semantics of this code:

 foreach(i; 10..13)
        twice(n => n + y++, i).writeln;;

We create four closures that capture values of "y", and at the same time we modify the values of "y". Or are the values of "y" modified only when the closures are actually executed?

If "y" is modified at the time of creating the closures, it would appear that these four closures should capture four different values of "y". Isn't a closure supposed to keep all values it captures as constants? I would expect that each closure should have its own separate copy of "y". Why is it correct that only one instance of "y" is ever allocated?

[some41.livejournal.com]

1) In most languages closures do not capture values. They capture variables. That is, they access the same variable as the outer function. If that variable is modified, closures see the new value. If closures modify the variable, the outer function and other closures see the change.

2) Of course the closure's code is only run when the closure is invoked, not when it is created. So y is modified inside twice().

[thedeemon.livejournal.com]

some41 got it right.
In all this code all mentions of "y" refer to the same location in memory.

n => n + y++
becomes
int f(int n) { return n + y++; }
and inside "twice" this function is called twice (f(f(x)).

foreach(i; 10..13)
makes three iterations: i=10, i=11 and i=12,
so "y" will be incremented 6 times and in the end of fun() "y" is 106.