10

我编写了一小段递归 F# 代码，以查看在 .NET/Mono 下可以将多少级递归放入堆栈中。只要它是 2 的精确幂，它就会打印递归深度，所以我找出最大深度在 2 倍以内。

我在一个具有定义数量堆栈空间的线程中使用System.Threading.Thread (ThreadStart, int). 在 .Net 下，每级递归似乎需要大约 100 个字节，而我可以在 2G 堆栈上获得大约 1600 万级。Mono 下的内存使用大致相似，但是我只能获得大约 30,000 个级别。增加传递给Thread过去的堆栈大小值大约600000不会增加递归深度。

ulimit报告堆栈大小限制为 1G。

一个明显的解释是，如果 Mono 太大，它将不服从第二个参数Thread。请问有人知道如何说服 Mono 分配一个大堆栈吗？

该代码是微不足道的，但它在下面以防万一有人关心：

let rec f i =
    if popcount i = 1 then // population count is one on exact powers of 2
        printf "Got up to %d\n" i
        stdout.Flush ()
    if i = 1000000000 then 0 else 1 + f (i+1)
4

4 回答 4

8

选项 1：更改 Mono 堆栈大小

一个明显的解释是，如果 Mono 太大，它将不服从第二个参数Thread。请问有人知道如何说服 Mono 分配一个大堆栈吗？

你是对的，即使你传入一个很大的值，Mono 也会限制堆栈大小。例如，在我的 Cent OS 64 位测试机器上，Mono 将分配的最大堆栈大小为 2 兆字节。Mono C# 源文件 Thread.cs向我们展示了创建Mono线程时会发生什么：

公共线程（ThreadStart 开始，int maxStackSize）
{
    如果（开始 == 空）
        抛出新的 ArgumentNullException（“开始”）；

    线程启动 = 开始；
    Internal.stack_size = CheckStackSize (maxStackSize);
}

静态 int CheckStackSize (int maxStackSize)
{
    如果 (maxStackSize < 0)
        throw new ArgumentOutOfRangeException ("小于零", "maxStackSize");

    if (maxStackSize < 131072) // 确保栈至少有 128k 大
        返回 131072；

    int page_size = Environment.GetPageSize ();

    if ((maxStackSize % page_size) != 0) // 向上舍入到页面大小的整除
        maxStackSize = (maxStackSize / (page_size - 1)) * page_size;

    int default_stack_size = (IntPtr.Size / 4) * 1024 * 1024; // 来自 wthreads.c
    if (maxStackSize > default_stack_size)
        返回默认堆栈大小；

    返回最大堆栈大小；
}

上面的代码对堆栈大小设置了硬性限制。

理论上，您可以更改上述一个或两个函数（粗线）中的代码，以便分配更大的堆栈大小。完成此操作后，您必须构建 Mono 运行时，然后运行您的函数以查看更改是否会产生影响。

我应该强调，我对 Mono 的了解不够，无法理解分配更大的堆栈是否会对您的特定情况有所帮助。我只会将此作为最后的手段（如果我的其他答案都不起作用）。

于 2013-11-11T15:03:22.137 回答
4

选项 2：F# 尾调用

一种选择是重写您的方法，以便使用递归尾调用。从之前的（维基百科）链接：

尾递归函数是递归的一种特殊情况，其中方法中执行的最后一条指令是递归调用。F#等许多函数式语言可以优化尾递归函数；因为在递归调用之后没有执行额外的工作，所以函数不需要记住它来自哪里，因此没有理由在堆栈上分配额外的内存。

F# 通过告诉 CLR 在执行目标函数之前删除当前堆栈帧来优化尾递归函数。因此，尾递归函数可以无限递归而不会消耗堆栈空间。

有一个警告 - Mono 不完全支持尾递归调用- 你应该首先在 .Net 运行时进行测试，然后查看代码是否会在 Mono 中运行。

这是使用尾递归调用重写的示例函数 - 它在 .NET（使用 Visual Studio 2010）和 Mono（Mono 版本 3.2.0，F# 3.0）中都有效：

let f i =
    let rec loop acc counter =
        // display progress every 10k iterations
        let j = counter % 10000
        if j = 0 then
            printf "Got up to %d\n" counter
            stdout.Flush ()

        if counter < 1000000000 then
            // tail recursive
            loop (acc + 1) (counter + 1)
        else
            acc

    loop 0 i

对于输入值 1：

let result = f 1
printf "result %d\n" result

输出：

Got up to 10000
Got up to 20000
Got up to 30000
...
Got up to 999980000
Got up to 999990000
Got up to 1000000000
result 999999999

对于输入值 999,999,998：

let result = f 999999998
printf "result %d\n" result

输出：

Got up to 1000000000
result 2

上面的代码使用两个变量来跟踪进度：

acc- 累加器，存储计算结果

counter- 只是递归调用的次数

为什么您的示例代码不是尾递归的？

解释 Wikipedia 文章的如何编写尾递归函数部分，我们可以重写这行代码：

if i = 1000000000 then 0 else 1 + f (i+1)

作为

if i = 1000000000 then 0
else
    let intermediate = f (i+1) // recursion
    let result = 1 + intermediate // additional operations
    result

尾递归的定义是在递归调用之后不能有额外的操作。正如我们在代码的重写版本中看到的那样，产生结果需要额外的操作。

资源

于 2013-11-11T15:05:45.650 回答
2

选项 3：使其迭代

一种选择是重写您的方法，使其不是递归的，而是迭代的。也就是说，您更改方法，使其成为计算结果的循环：

let f i =
    let mutable acc = 0
    for counter in i .. 1000000000 do
        // display progress every 10k iterations
        let j = counter % 10000
        if j = 0 then
            printf "Got up to %d\n" counter
            stdout.Flush ()

        if counter < 1000000000 then
            acc <- acc + 1
    acc

对于输入值 1：

let result = f 1
printf "result %d\n" result

输出：

Got up to 10000
Got up to 20000
Got up to 30000
...
Got up to 999980000
Got up to 999990000
Got up to 1000000000
result 999999999

对于输入值 999,999,998：

let result = f 999999998
printf "result %d\n" result

输出：

Got up to 1000000000
result 2

上面的代码使用两个变量来跟踪进度：

acc- 累加器，存储计算结果

counter- 只是迭代调用的次数（循环数）

由于我们使用循环来计算结果，因此没有分配任何额外的堆栈。

于 2013-11-11T15:06:57.157 回答
0

此代码绕过单声道限制。它对 dfs 在竞争性编程中很有用。

        public static void IncreaseStack(ThreadStart action, int stackSize = 16000000)
        {
            var thread = new Thread(action, stackSize);
#if __MonoCS__
        const BindingFlags bf = BindingFlags.NonPublic | BindingFlags.Instance;
        var it = typeof(Thread).GetField("internal_thread", bf).GetValue(thread);
        it.GetType().GetField("stack_size", bf).SetValue(it, stackSize);
#endif
            thread.Start();
            thread.Join();
        }
于 2017-12-28T07:27:32.030 回答