Почему сборка мусора необходима для оптимизации вызовов?

Question

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

Answer 1

Как и в большинстве мифов, в этом может быть доля правды. Хотя для оптимизации хвостового вызова GC не требуется , в некоторых случаях, безусловно, помогает . Допустим, у вас есть что-то вроде этого в C ++:

int foo(int arg) {
    // Base case.

    vector<double> bar(10);
    // Populate bar, do other stuff.

    return foo(someNumber);
}

В этом случае вернуть foo (someNumber); выглядит как хвостовой вызов, но поскольку вы используете управление памятью RAII и вам нужно освободить бар, эта строка будет переведена на более низкий уровень следующим образом (в неформальном псевдокоде):

ret = foo(someNumber);
free(bar);
return ret;

Если у вас есть GC, компилятору не обязательно вставлять инструкции в свободную строку. Следовательно, эта функция может быть оптимизирована для хвостового вызова.

Answer 2

Где ты это услышал?

Даже компиляторы C без какого-либо сборщика мусора способны оптимизировать хвостовые рекурсивные вызовы до их итеративного эквивалента.

Answer 3

Сборка мусора не требуется для оптимизации хвостового вызова.

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

Любые локальные переменные, размещенные в куче и не освобожденные до хвостового вызова, будут пропускать память независимо от того, используется оптимизация хвостового вызова или нет. Локальные переменные, выделенные в куче и освобожденные до хвостового вызова, не будут пропускать память независимо от того, используется ли оптимизация хвостового вызова.

Answer 4

Это правда, сборка мусора на самом деле не требуется для оптимизации хвостового вызова.

Однако, допустим, у вас есть 1 ГБ ОЗУ и вы хотите отфильтровать список целых 900 МБ, чтобы оставить только положительные. Предположим, около половины положительные, половина отрицательные.

На языке с GC вы просто пишете функцию. GC будет происходить несколько раз, и вы получите список 450 МБ. Код будет выглядеть так:

list *result = filter(make900MBlist(), funcptr);

make900MBlist будет постепенно увеличиваться до GCd, так как фильтр деталей больше не упоминается.

На языке без GC, чтобы сохранить хвостовую рекурсию, вы должны сделать что-то вроде этого:

list *srclist = make900MBlist();
list *result = filter(srclist, funcptr);
freelist(srclist);

Это приведет к необходимости использовать 900 МБ + 450 МБ, прежде чем окончательно освободить srclist, поэтому программе не хватит памяти и произойдет сбой.

Если вы напишите свой собственный filter_reclaim, это освободит список ввода, так как он больше не нужен:

list *result = filter_reclaim(make900MBlist(), funcptr);

Он больше не будет хвост-рекурсивным, и вы, вероятно, переполните свой стек.