замыкания

[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

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