CLR中的尾调用优化

Question

我偶然发现（通过意外），最后一个CLR进行了尾调用优化。我已经使用一段代码进行了测试，但实际上它的行为并不像我预期的那样。我认为尾调用优化可能会在函数中的最后一件事是函数调用时发生。

我正在尝试“破坏”这段代码以防止尾调用优化。

class Program
{
    static void Foo(int counter, int limit)
    {
        try
        {
            if (counter == limit)
            {
                return;
            }
            Foo(++counter, limit);

            int d = 1;
            d = Bar(d);
            //Console.Write(d);
            //Thread.Sleep(1);
            int baz = 0;
            var z = baz + d;
            StringBuilder b = new StringBuilder();
            b.Append("D");
        }
        catch (Exception)
        {
            throw;
        }
    }

    static int Sum(int s)
    {
        if (s == 1)
        {
            return s;
        }
        return s + Sum(s - 1);
    }

    static int Bar(int d)
    {
      return  d = 10 + d;
    }

    static void Main(string[] args)
    {
        int i = 0;

        Foo(i, 10000); // jitter 
        Sum(10000);

        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();
        Foo(i, 10000);
        stopwatch.Stop();
        Console.WriteLine(string.Format("time of execution = {0}ms",stopwatch.ElapsedMilliseconds));

        stopwatch = new Stopwatch();
        stopwatch.Start();
        Sum(10000);
        stopwatch.Stop();
        Console.WriteLine(string.Format("time of execution = {0}ms", stopwatch.ElapsedMilliseconds));

        Console.ReadKey();
    }
}

但是Foo仍然被优化了。为什么呢？

- Lukasz Madon

---

@Mike：可能是基于非爆炸式堆栈使用，尽管当函数如此简单时，10000深度可能不足以溢出默认堆栈。 - Ben Voigt

@Ben，我不知道。 baz 没有被用于任何有意义的事情，所以我可以看到编译器完全省略它，而且我怀疑 JITter 会使用与 d 相同的存储来存储 z，因此每个帧仅为8字节，这远远不足以使默认的1兆栈溢出。不过，最好的方法是查看 IL ;) - Mike Caron

@Ben，是的，那就是你说的。无论如何，寄存器和返回地址都是JITter需要担心的问题。无论如何，我正在查看OP代码的IL，并使用/o进行编译，我没有看到任何真正的尾调用（即tail后跟call、calli或callvirt）。也许我没有正确地阅读ILDASM... - Mike Caron

两者都没有在主流抖动中进行优化。只需添加一个0即可使其在SO上崩溃。 - Hans Passant

.NET 目前对尾递归函数的处理相当糟糕。这就是为什么 F# 编译器将其优化为 while(true) 循环的原因。 - vcsjones

Answer 1

在调用 Foo 递归后，您没有使用任何副作用。我假设您尝试了注释掉的代码，并且它确实防止了优化。那么问题是什么？

您还可以写入类成员，这将是一个无法丢弃的副作用。

private static int dummy;
static void Foo(int counter, int limit)
{
    if (counter == limit) return;
    Foo(++counter, limit);
    dummy++;
}

然后在Main的结尾读取dummy。

- Ben Voigt

---

实际上并没有。10,000次Thread.Sleep(1)的运行时间为10,032毫秒。我认为如果我防止优化，堆栈会崩溃。 - Lukasz Madon

@lucas：这个函数不会使用太多的堆栈。即使有10000个嵌套调用，也不会耗尽线程的默认堆栈大小。 - Ben Voigt

我在Foo中添加了dummy += z;，但时间仍为0ms。 - Lukasz Madon

JIT 不应该聪明到删除 StringBuilder 的内容。只有当所有内容都被内联时，它才能得出这是无副作用的结论。此外，JIT 目前不会删除分配。 - usr

抱歉，在一个老帖子上评论了。我真的很讨厌过时的问题被顶起来。对我来说从来没有什么用处。 - usr