如何让更多的内存和避免堆栈溢出大量的recursion?

我正在testing执行大量recursion调用的algorithm的时间。 我的程序在约128k的recursion调用中死亡,这只需要0.05秒。 我想让更多的记忆在我的分析中有更长的时间。 我正在运行Linux和使用gcc。 是否有一个系统调用,或环境variables,或gcc标志,或包装,或什么?

Solutions Collecting From Web of "如何让更多的内存和避免堆栈溢出大量的recursion?"

在Linux下gcc没有堆栈大小编译器选项。 但是本文讨论了如何在Linux上设置堆栈大小。 使用ulimit命令。

尝试组织你的递归函数来进行尾递归 。

也就是说,确保递归函数的最后一个操作是递归调用。 通过这样做,编译器可以将其优化为简单的迭代。

尾递归将帮助你,因为迭代将大大减少使用的堆栈空间。

通过尾递归,你通常一直将你的值递增,一次计算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); } 

你有三个选择:

  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的值),我会假设有人提出有关编程的问题要么知道如何做到这一点,要么足够聪明以找出答案。

这里重要的一点是,每次recursive_function()时, scratchpad占用堆栈的400字节(在32位机器上,在64位机器上是800字节recursive_function() ,所以如果recursive_function()被递归调用100次,那么堆栈空间的40,000字节(或64位计算机上的80,000字节)正被用于缓冲区,并且很可能您可以修改该函数以在每次调用时重用相同的缓冲区:

 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
这是初始线程堆栈的最大大小(以字节为单位)。 该实现不会自动增加超出此限制的堆栈。 如果超过这个限制, SIGSEGV应该为线程生成。 如果线程阻塞了SIGSEGV ,或者进程正在忽略或捕获SIGSEGV ,并且没有安排使用备用堆栈,那么SIGSEGV的配置在生成之前必须设置为SIG_DFL