logo标签列表

Mono下的堆栈大小

.netrecursionf#mono
10

我编写了一小段递归的F#代码，用来测试在.NET/Mono下堆栈可以承受多少级递归。它只在递归深度是2的幂时打印递归深度，所以我可以找出最大深度，精确到2的因子。

我使用 System.Threading.Thread (ThreadStart, int) 在一个有定义的堆栈空间的线程中启动代码。在.Net下，它似乎每个递归级别需要约100字节，我可以在2G的堆栈上获得约1600万级别。在Mono下，内存使用情况差不多，但我只能获得约3万级别。将传递给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)
默认的.NET应用程序堆栈大小为1 MB。请参阅C#中的堆栈容量。此外，还有一篇详细的文章介绍如何更改堆栈大小。 - Palec
4个回答
9

选项1：更改Mono堆栈大小

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

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

public Thread (ThreadStart start, int maxStackSize)
{
    if (start == null)
        throw new ArgumentNullException ("start");
threadstart = start;
    Internal.stack_size = CheckStackSize (maxStackSize);
}
static int CheckStackSize (int maxStackSize)
{
    if (maxStackSize < 0)
        throw new ArgumentOutOfRangeException ("less than zero", "maxStackSize");
if (maxStackSize < 131072) // make sure stack is at least 128k big
        return 131072;
int page_size = Environment.GetPageSize ();
if ((maxStackSize % page_size) != 0) // round up to a divisible of page size
        maxStackSize = (maxStackSize / (page_size - 1)) * page_size;

    int default_stack_size = (IntPtr.Size / 4) * 1024 * 1024; // from wthreads.c
    if (maxStackSize > default_stack_size)
        return default_stack_size;

    return maxStackSize; 
}

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

您可以理论上更改上述函数中的一个或两个函数中的代码（粗体行），以便分配更大的堆栈大小。一旦您这样做，您将不得不构建Mono运行时，然后运行您的函数以查看更改是否有所作为。

我应该强调，我不了解Mono是否足够了解在您的特定情况下分配更大的堆栈是否有所帮助。如果我的其他答案都不起作用，我只会在万不得已时这样做。

非常感谢。我猜原因是如果堆栈增长太多，垃圾收集器的复杂性会出现问题，尽管这并不能解释一个可笑地小的硬编码限制。 - Joe Huha
@JoeHuha - 我发现了这个代码提交，其中添加了函数CheckStackSize，但没有提到为什么。 - chue x
我猜为什么有这样一个小的限制：为了与.Net保持一致的行为：“只有完全信任的代码才能将maxStackSize设置为大于默认堆栈大小（1兆字节）的值。如果在部分信任下运行代码时指定了更大的maxStackSize值，则maxStackSize将被忽略”。 - chue x
Mono中的一些评论表明，限制只是一个临时解决方案。虽然不清楚限制是为了什么，但可以创建的线程数量可能与其有关。无论如何，从C#代码中删除限制似乎对我有效。内存分配器会有一些抱怨（可能与其他原因无关），但它仍然运行得足够快。非常感谢您的帮助。 - Joe Huha
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 - 仅是递归调用的次数 为什么你的示例代码不是尾递归？ 重新表述维基百科文章中的如何编写尾递归函数部分，我们可以重写您代码的这一行:
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

非常明确的定义了尾递归，它指出在递归调用之后不能有其他操作。正如我们在重写代码的版本中所看到的那样，需要执行其他操作才能产生结果。

资源

非常感谢。然而，问题（正如您所观察到的）是Mono不总是在应该时执行尾调用。我的代码已经是尾递归的，在.net下运行得很好。但是在相同的代码下，Mono很快就会耗尽堆栈，只有30k递归层数可供使用，我无法解决这个问题。（我已经为您的其他答案投了赞成票，因为它非常接近我想知道的内容，即使它只是解释了Mono如何限制堆栈大小而不是为什么以及如何避免它-但这是值得奖励的进步。谢谢。） - Joe Huha
这里有一个关于该主题的旧问题：Mono中的尾调用消除。 - Palec
2

选项三：使其迭代

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

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 - 仅是迭代调用的次数（循环次数）

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

0
这段代码绕过了mono的限制。在竞赛编程中进行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();
        }
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接