Как разрешить больше памяти и избежать переполнения стека при большом количестве рекурсии?

Question

Я проверяю время работы алгоритма, который выполняет множество рекурсивных вызовов. Моя программа умирает при рекурсивных вызовах 128k, и это занимает всего 0,05 секунды. Я бы хотел, чтобы в моем анализе было больше памяти, чтобы иметь больше времени. Я использую Linux и использую gcc. Есть ли системный вызов, или переменная окружения, или флаг gcc, или оболочка, или что-то?

Answer 1

Попробуйте организовать свою рекурсивную функцию так, чтобы хвостовая рекурсия .

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

Хвостовая рекурсия поможет вам, потому что итерации значительно уменьшат используемое пространство стека.

При использовании хвостовой рекурсии вы обычно передаете значение UP полностью, вычисляя 1 шаг за раз. Поэтому, когда рекурсия завершена, все, что нужно сделать, это вернуться.

---

Пример:

Преобразовать следующий код:

unsigned fact(unsigned x)
{
  if(x == 1)
    return 1;

   //--> Not tail recursive, multiply operation after the recursive call
   return fact(x-1) * x;
}

К этому:

unsigned fact(unsigned x)
{
    return tail_fact(x, 1);
}

unsigned tail_fact(unsigned x, unsigned cur_val)
{
  if(x == 1)
    return cur_val;  

  return tail_fact(x-1, x * cur_val);  
}

Answer 2

В Linux нет опции компилятора размера стека для gcc. Однако этот текст описывает, как установить размер стека в Linux. с помощью команды ulimit.

Answer 3

Хотя другие ответы говорят о том, как вообще избежать рекурсии, или как использовать хвостовую рекурсию, или как просто установить больший размер стека, для полноты картины я думаю, что стоит рассмотреть шаблоны использования памяти (чтобы ответить «как позволить больше памяти ... на много рекурсии ").

По привычке многие программисты размещают буферы внутри рекурсивной функции и перераспределяют новые буферы, когда функция вызывается рекурсивно:

int recursive_function(int x)
{
    if (1 == x)
        return 1;
    int scratchpad[100];
    ... // use scratchpad
    return recursive_function(x-1) + scratchpad[x-1];
}

Поскольку это одноразовый образец, я не буду беспокоиться о неправильном вводе (отрицательные значения, значения больше 100), и я предполагаю, что кто-то задает вопрос о программировании, либо знает, как это сделать, либо умен достаточно, чтобы узнать.

Важным моментом здесь является то, что scratchpad занимает 400 байтов (на 32-битной машине, 800 байтов на 64-битной машине) стека каждый раз, когда вызывается recursive_function(), поэтому, если recursive_function() вызывается рекурсивно 100 раз, затем 40 000 байт (или 80 000 байт на 64-битной машине) стекового пространства используются для буферов, и очень вероятно, что вы можете изменить функцию для повторного использования одного и того же буфера при каждом вызове:

int recursive_function(int x, int* buffer, int buffer_length)
{
    if (1 == x)
        return 1;
    ... // use buffer (and buffer_length to avoid overflow)
    int temp_value = buffer[x-1];
    return recursive_function(x-1, buffer, buffer_length) + temp_value;
}

Конечно, вы могли бы вместо этого использовать std::vector, который обрабатывает некоторые детали для вас, чтобы защитить вас от утечек памяти и переполнения буфера (и, для записи, сохраняет данные в куче [см. Сноску], то есть скорее всего использовать меньше места в стеке).

40 тыс. Или даже 80 тыс. Может показаться не таким уж большим, но все может сложиться. Если функция не имеет много других переменных, выделенных стеком, то это может доминировать в пространстве стека (то есть, если бы не дополнительное пространство, занимаемое буферами, вы можете вызывать функцию гораздо чаще).

Это может показаться очевидным, , но оно появляется , даже в нерекурсивных функциях. Кроме того, буферы не всегда очевидны как массивы. Например, это могут быть строки или объекты.

---

Сноска : контейнеры STL, такие как массивы, не обязательно помещают все свои данные в кучу. Они фактически принимают аргумент шаблона, чтобы указать используемое распределение памяти; просто используемый ими по умолчанию распределитель помещает данные в кучу. Очевидно, что если вы не укажете распределитель, который каким-то образом помещает данные в стек, конечный результат будет таким же: использование контейнеров STL, вероятно, будет использовать меньше памяти, чем использование выделенных в стеке массивов или объектов.

Я говорю «вероятно», потому что, хотя данные хранятся в куче (или где-то еще), контейнер может получить доступ к этим данным только через указатели, которые он хранит внутри, если контейнер находится в стеке, то эти указатели будут находиться на стек, и эти указатели занимают место. Таким образом, один или два элемента std::vector могут фактически занимать больше места в стеке, чем соответствующий массив.

Answer 4

У вас есть три варианта:

1. Перепишите программу, чтобы сделать ее нерекурсивной. Это лучшее, но не всегда возможно.

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

3. Настроить окружающую среду, чтобы отложить неизбежное. Visual C ++ имеет настройку компоновщика для размера стека. Почти наверняка у gcc тоже есть.

Answer 5

Взгляните на setrlimit():

RLIMIT_STACK
Это максимальный размер стека исходного потока в байтах. Реализация не увеличивает стек автоматически за этот предел. Если этот предел превышен, для потока должно быть сгенерировано SIGSEGV. Если поток блокирует SIGSEGV, или процесс игнорирует или перехватывает SIGSEGV и не принял меры для использования альтернативного стека, расположение SIGSEGV должно быть установлено на SIG_DFL до его генерации. *