Что касается повторного использования стека функции, вызывающей себя? - PullRequest
Новая
       21

Что касается повторного использования стека функции, вызывающей себя?

7 голосов
/ 12 февраля 2010

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

void funcnew(void)
{
   int a=10;
   int b=20;
   funcnew();
   return ;
 }

Может ли функция повторно использовать кадр стека, который использовала ранее? Какой вариант в gcc повторно использовать тот же фрейм в хвостовой рекурсии ??

Ответы [ 6 ]

5 голосов
/ 12 февраля 2010

Да. См

-foptimize-одноуровневых-звонки

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

Включено на уровнях -O2, -O3, -Os.

Ваша функция скомпилирована в: 

funcstack:
.LFB0:
    .cfi_startproc
    xorl    %eax, %eax
    jmp func
    .cfi_endproc

(обратите внимание на переход к функции)

Повторное использование стекового фрейма, когда функция завершается вызовом - это включает в себя всеобщую манипуляцию стеком, чтобы поместить параметры в правильное место, и замену вызова функции переходом к началу функции - хорошо известная оптимизация, называемая [i] удалением хвостовых вызовов [/ i]. Это предписано некоторыми языками (например, схемой) для рекурсивных вызовов (рекурсивный вызов является естественным способом выразить цикл в этих языках). Как указано выше, в gcc реализована оптимизация для C, но я не уверен, какой другой компилятор имеет ее, я бы не зависел от нее для переносимого кода. И обратите внимание, что я не знаю, какие ограничения существуют на нем - я не уверен, например, что gcc будет манипулировать стеком, если типы параметров различаются.

3 голосов
/ 12 февраля 2010

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

Вполне возможно (я узнал об этом недавно), что компилятор оптимизирует ваш цикл в хвостовую рекурсию (что делает стек вообще не увеличивающимся). Ссылка на вопрос о хвостовой рекурсии на SO

0 голосов
/ 13 мая 2011

Как уже отмечали другие, это возможно только в том случае, если (1) ваш компилятор поддерживает оптимизацию хвостового вызова, и (2) если ваша функция подходит для такой оптимизации. Оптимизация заключается в повторном использовании существующего стека и выполнении JMP (т.е. GOTO в сборке) вместо CALL.

На самом деле, ваша примерная функция действительно подходит для такой оптимизации. Причина в том, что последнее, что ваша функция делает перед возвратом, это сам вызов; он не должен ничего делать после последнего вызова funcnew(). Однако, только некоторые компиляторы будут выполнять такую ​​оптимизацию. GCC, например, сделает это. Для получения дополнительной информации см. Какие, если таковые имеются, компиляторы C ++ выполняют оптимизацию хвостовой рекурсии?

Классическим материалом для этого является факториальная функция. Давайте создадим рекурсивную факториальную функцию, которая не подходит для оптимизации хвостового вызова (TCO). 

int fact(int n)
{
  if ( n == 1 ) return 1;
  return n*fact(n-1);
}

Последнее, что он делает, это умножает n на результат из fact(n-1). Каким-то образом исключив эту последнюю операцию, мы сможем повторно использовать стек. Давайте введем переменную-аккумулятор, которая вычислит ответ для нас: 

int fact_helper(int n, int acc)
{
  if ( n == 1 ) return acc;
  return fact_helper(n-1, n*acc);
}

int fact_acc(int n)
{
  return fact_helper(n, 1);
}

Функция fact_helper выполняет свою работу, тогда как fact_acc - это просто вспомогательная функция для инициализации переменной аккумулятора.

Заметьте, как последняя вещь, которую fact_helper делает, это вызывает себя. Этот CALL может быть преобразован в JMP путем повторного использования существующего стека для переменных.

С помощью GCC вы можете убедиться, что он оптимизирован для перехода, просмотрев сгенерированную сборку, например gcc -c -O3 -Wa,-a,-ad fact.c: 

  ...
  37                    L12:
  38 0040 0FAFC2                imull   %edx, %eax
  39 0043 83EA01                subl    $1, %edx
  40 0046 83FA01                cmpl    $1, %edx
  41 0049 75F5                  jne     L12
  ...

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

0 голосов
/ 12 февраля 2010

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

0 голосов
/ 12 февраля 2010

Да, в некоторых случаях компилятор может выполнить то, что называется оптимизация хвостового вызова . Вы должны проверить с вашим руководством компилятора. (Кажется, AProgrammer цитировал руководство GCC в своем ответе.)

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

0 голосов
/ 12 февраля 2010

Нет, каждая рекурсия - это новый кадр стека. Если рекурсия бесконечно глубока, то необходимый стек также бесконечен, поэтому вы получаете переполнение стека.

...