замыкания

[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 не нужен).

[grey-demonstr.livejournal.com]

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

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

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

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

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

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

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

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

Выделять один 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, так что компилятор не может переиспользовать одну и ту же в цикле.

[109.livejournal.com]

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

[valentin budaev (from livejournal.com)]

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

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