замыкания

[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

[n16bs.livejournal.com]

В C# переменные, на которые происходит замыкание, становятся полями специального класса, генерируемого компилятором. А сами лямбды с замыканием - его методами.
При входе в метод создаётся экземпляр этого класса, в вызовы ФВП передаются ссылки на его методы.
Т.е. замыкание на самом деле превращается в объект.

А scope модификатор - хорошая штука.

[neatfires.livejournal.com]

А компайлер проверяет соблюдение кодом гарантий scope? (Предполагаю, что нет, т.к. если да, то scope не нужен).

[thedeemon.livejournal.com]

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

[grey-demonstr.livejournal.com]

Судя по рассказу Майерса, C++11/14 делает примерно то же самое.

[thedeemon.livejournal.com]

Мне казалось, там по отдельному объекту на каждое замыкание делается...

[grey-demonstr.livejournal.com]

А, я понял, о чем ты. Да, на каждый из трех вызовов будет создано по объекту размером в 4 байта. На переменные, если передавать по ссылке, лишняя память выделяться не будет.

[thedeemon.livejournal.com]

Тут в примере 3 лямбды передаются по 3 раза, всего 9 вызовов. Сколько конструкторов будет выполнено в С++?

[some41.livejournal.com]

В С++ все вручную. Если писать лямбды, то каждый раз вызовется конструктор. Но объект выделяется на стеке, а не в куче, так что это довольно дешево. Можно вручную создать std::function. Сколько раз создашь, столько и будет.
То, что замыкание поймало, либо копируется в него, либо используется по ссылке -- нужно указывать вручную. Если ни копирование ни стек не подходят, выделять в куче и класть в shared_ptr нужно вручную. Сколько раз сделаешь, столько и будет.

[http://users.livejournal.com/_winnie/]

Предположим, что ссылки копировать нельзя.

В С++ каждая lambda - будет отдельным объектом, в каждую будет скопирован массив. Если переложить в std::function (чего часто можно избежать), то будет аллокация в 40+4 байта (проверил).

Ещё удивлён, что при копировании std::function непонятно зачем выделяется 16 байт.

Если сделать shared_ptr на указываемые объекты, то добавится ещё 24 байта.

x64, код - http://pastebin.com/pL9hutNH

[http://users.livejournal.com/_winnie/]

Ожидал в std::function увидеть оптимизацию для маленьких лямбд, не оказалось. В boost::function - оптимизация в наличии, вместил в себя три раза восьмибайтовый size_t (24 байта).э

[some41.livejournal.com]

Это ты в каком STL смотришь? У g++ 4.8 вроде есть оптимизация на два слова. Хотя я очень бегло смотрел. Больше удивило, что требуется копирование environment, так что нельзя поймать unique_ptr.

[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.

[some41.livejournal.com]

Выделять один environment на функцию -- это стандартная техника, так много кто делает. На вскидку, V8. Даже gnu C nested functions так делают, хотя им проще, потому что environment всегда живет на стеке.
Делать один env на всех -- это trade-off. С одной стороны меньше аллокаций, с другой -- возможный memory leak:

myfn makefn() {
    int x; int y[1000];
    non_capturing_call(n => y[n]);
    return (n => n+x);
}

Получилось, что функция вместо одного int держит в памяти еще и большой массив. Думаю, из-за этого CPython заворачивает отдельно каждую пойманную переменную, а не один env. В питоне еще функция -- mutable object, так что компилятор не может переиспользовать одну и ту же в цикле.

[lispnik.livejournal.com]

Плюсую. Ничего хитрого тут нет. lambda lifting, всего-то :)

[thedeemon.livejournal.com]

педивикия не согласна:
Lambda lifting is not the same as closure conversion. Lambda lifting requires all call sites to be adjusted (adding extra arguments to calls) and does not introduce a closure for the lifted lambda expression. In contrast, closure conversion does not require call sites to be adjusted but does introduce a closure for the lambda expression mapping free variables to values.

[lispnik.livejournal.com]

Спасибо, ценное замечание.

[109.livejournal.com]

C#, по-моему, захватывает переменные один раз, вне зависимости от количества лямбд. именно это является причиной раздражающего ворнинга "implicitly captured closure". всегда хочется ответить "so fucking what?"

[some41.livejournal.com]

> so fucking what?
Может быть resource leak.

[109.livejournal.com]

прикол защитан.

[valentin budaev (from livejournal.com)]

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

Непонятно удивление - это же стандартное поведение (спагетти-стек, замыкание принимает неявный аргумент-ссылку на стек-фрейм своего скопа). Как по-другому сделать, если, следуя семантике, замыкание может захватывать мутабельную переменную, которая, очевидно, должна быть разделена (одна и та же) между всеми замыканиями скопа?

[thedeemon.livejournal.com]

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

[valentin budaev (from livejournal.com)]

А если замыкания немутабельны и есть джит, то можно вообще бодро инлайнить захваченные переменные при компиляции :)
Для value-типов, по крайней мере.