Intereting Posts
Использование макроса приводит к некорректному выводу при использовании в качестве части более крупного математического выражения – почему это происходит? Является ли законным принимать адрес параметра функции? Является ли звездочка необязательной в указателе функции? измерять время для выполнения одной инструкции Как отлаживать дочерний процесс после fork () в gdb? Изменение указателя головы в связанном списке NUL uneclared – сначала использовать в этой функции Вычислить площадь поверхности трехмерной сетки Является ли операция «++» атомой в C? C – Какую опцию я использую для создания файла листинга? Странная формулировка в стандарте, касающаяся сравнения указателей Понимание базовых указателей и указателей стека: в контексте с выходом gcc Почему log (1000) / log (10) не совпадает с log10 (1000)? Статические переменные C и инициализация Вычислить произведение двойного слова (подписанное) из двух слов, учитывая нижнее словосочетание

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

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

Для gcc под Linux отсутствует опция сравнения размера стека. Однако в этом тексте обсуждается, как установить размер стека в Linux. используя команду ulimit .

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

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

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

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


Пример:

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

 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); } 

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

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

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

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

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

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

 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 , который обрабатывает некоторые детали для вас, чтобы защитить вас от утечек памяти и переполнения буфера (и, для записи, хранит данные в куче [см. Сноску], что означает, что она, скорее всего, будет использоваться меньше пространства стека).

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

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


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

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

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

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