A tale of recursion

You spend a lot of time learning about tail recursion, and how it is a way of writing loops while keeping the code in a functional style. So it’s a shame that the .NET platform doesn’t always guarantee tail call optimisation, in particular for self tail calls. The problem is, of course, that you’ll write something and it will work on all sorts of simple tests and then fail on large customer examples owing to a greater depth in the recursion at runtime. There are no end of examples of C# code which manipulates binary trees, and which would fall prey to this trap.

Take, for example, the following program:

    class Program
    {
        static void Main(string[] args)
        {
            TailMe(1000000, 0);
        }

        static int TailMe(int x, int y)
        {
            if (x == 0)
                return y;
            Console.WriteLine(x);
            return TailMe(x – 1, y + 1);
        }
    }

Compile it in debug mode, and you get the following output:

….
984112
984111

Process is terminated due to StackOverflowException.

Compile for “Any Cpu” release mode and run on an x64 machine:

3
2
1

Compile it for “x86” release mode:

871186
871185
871184

Process is terminated due to StackOverflowException.

What is interesting is that even though the IL doesn’t use a tail prefix on any of the IL instructions (which is a hint to the jit that it would be good to tail call in this particular case)

  .method private hidebysig static int32
          TailMe(int32 x,
                 int32 y) cil managed
  {
    // Code size       23 (0x17)
    .maxstack  8
    IL_0000:  ldarg.0
    IL_0001:  brtrue.s   IL_0005

    IL_0003:  ldarg.1
    IL_0004:  ret

    IL_0005:  ldarg.0
    IL_0006:  call       void [mscorlib]System.Console::WriteLine(int32)
    IL_000b:  ldarg.0
    IL_000c:  ldc.i4.1
    IL_000d:  sub
    IL_000e:  ldarg.1
    IL_000f:  ldc.i4.1
    IL_0010:  add
    IL_0011:  call       int32 TailMe.Program::TailMe(int32,
                                                      int32)
    IL_0016:  ret
  } // end of method Program::TailMe

in the x64 release case, the code has been jitted to have a jmp to implement the self tail call.

0:004> u 000007ff00140160
000007ff`00140160 53              push    rbx
000007ff`00140161 57              push    rdi
000007ff`00140162 4883ec28        sub     rsp,28h
000007ff`00140166 8bfa            mov     edi,edx
000007ff`00140168 8bd9            mov     ebx,ecx
000007ff`0014016a 660f1f440000    nop     word ptr [rax+rax]
000007ff`00140170 85db            test    ebx,ebx
000007ff`00140172 750c            jne     000007ff`00140180
000007ff`00140174 8bc7            mov     eax,edi
000007ff`00140176 eb4b            jmp     000007ff`001401c3
000007ff`00140178 0f1f840000000000 nop     dword ptr [rax+rax]
000007ff`00140180 48b8f010de1200000000 mov rax,12DE10F0h
000007ff`0014018a 488b00          mov     rax,qword ptr [rax]
000007ff`0014018d 4885c0          test    rax,rax
000007ff`00140190 750e            jne     000007ff`001401a0
000007ff`00140192 b101            mov     cl,1
000007ff`00140194 e8e7b79fe5      call    mscorlib_ni+0x3db980 (000007fe`e5b3b980)
000007ff`00140199 0f1f8000000000  nop     dword ptr [rax]
000007ff`001401a0 49bbf010de1200000000 mov r11,12DE10F0h
000007ff`001401aa 4d8b1b          mov     r11,qword ptr [r11]
000007ff`001401ad 498b03          mov     rax,qword ptr [r11]
000007ff`001401b0 4c8b4060        mov     r8,qword ptr [rax+60h]
000007ff`001401b4 8bd3            mov     edx,ebx
000007ff`001401b6 498bcb          mov     rcx,r11
000007ff`001401b9 41ff5028        call    qword ptr [r8+28h]
000007ff`001401bd ffcb            dec     ebx
000007ff`001401bf ffc7            inc     edi
000007ff`001401c1 ebad            jmp     000007ff`00140170   <<<<< self tail call
000007ff`001401c3 4883c428        add     rsp,28h
000007ff`001401c7 5f              pop     rdi
000007ff`001401c8 5b              pop     rbx
000007ff`001401c9 c3              ret

Advertisements
This entry was posted in Computers and Internet. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s