C# has no Tail Call Optimization; Or how I spent too much time reading CIL.

Hello!

Background: During the last year, a friend and I started working on a Stock-Exchange analysis tool.  Working on this project taught me a lot about the Task Parallel Library (and Multi-Threading in general), especially when I tried to speed the code up and have it take less than ~3 hours to go over ~10,000 stock symbols. In addition, I've started working on my Final-Project for my BSc in CompSci with another friend. That project involves Machine Learning and a specific class of Regular Languages (DFA). My thoughts on both projects converged around performance questions and the idea that utilizing F# (Oh yeah, I failed to note that both projects are written in C#.net) might speed up coding and/or runtime performance. I bring to you, a (not so) brief account of some of the things I've learned:

Preliminaries [Stuff it might be nice to know while reading this Post]:

• .Net Languages: C#, F#, CIL (aka MSIL)
• The Ackermann Function
• Tail Call, Tail Call Optimization

First of all: An Experiment or the ACK!(ermann) function.
So there I was, thinking of a way to compare between C# and F# when I remembered a certain function that can utilize F#'s Pattern-Matching abilities. [Full Disclosure: Now when I think about it, Ackermann only really tests heavy stack use and not much else, so I guess I'll have to do another benchmark when I'm done with this one.] So, without further ado, I present to you the code I wrote:

C#:

F#:


At first, I ran the code in Debug mode and then averaged the time it took to run the method 5 times. The results:

	ack(3, 9)	ack(3, 10)
C#	~300ms	~1300ms
F#	~720ms	~4500ms
%	240%	346%

Now this looked a bit excessive. I could understand how F# would be less optimized than C#, but I would not expect the difference to be this large. I then changed the mode to Release (:P) and ran the code. Again, I was surprised to see the following results:

	ack(3, 9)	ack(3, 10)
C#	~110ms	~480ms
F#	~50ms	~200ms
%	45%	42%

A 63% decrease in running time due to removal of debug information I could accept. But, 93% was too big of an improvement for me to just leave it at that.

So I did what any student taking a Compilation class would do; I used RedGate’s Reflector to view the CIL code of the functions. There were several differences in the code that could be attributed to common cases the compiler was optimized to handle [I will probably go over those differences in my next post], but one difference stood out above all else. The C# CIL had 3 recursive calls to Ackermann where the F# CIL had only 1. This could only mean one thing! The F# compiler was optimizing out any Tail Call Recursions. So I wrote my own pre optimized version in C#:

The hand-optimized code yielded a 10% reduction in runtime compare to the F# version.

Conclusions

1. C# Does not perform the Tail Call Optimization.
2. C# and F# compilers generate different CIL for the same code.
3. F#’s Debug mode has an insane amount of overhead.
4. C# code optimized by hand (for TCO) runs better than F# code (Which I don’t see any way of optimizing further).

Q and A (from user comments)

Q: Is F# so slow in debug only because it doesn't do tail-call optimization?
A: The F# compiler performs the TCO in debug as well. However, it instanciates Heap-Heavy objects instead of primitives.

Q: What were the differences in the compiled MSIL between the optimized F# and the hand-optimized C#?
A: Probably going to be in my next post.

Q: [Rephrased] Whereas the C# Method is restricted to operation on Integer values, the F# implementation looks polymorphic. Is it possible that the F# code assumes a different numeric type (i.e. bignum) and this is the cause for the relative slowness compared to the optimized C# code?
A: Actually - for reasons I do not yet know - F# guessed correctly that I'm dealing with Int32 types (Excatly as in C#). Therefore I assume that some other compilational difference is the culprit. More of that in next post.

Hope you enjoyed this post.
Please let me know if / how I can improve.

Nathan Dortman
P.S. Special Thanks to my Professor of Compilation Mayer Goldberg.
P.P.S. This is a reconstruction of my previous post from an early backup (due to the crashing of my previous host's DB). Please be patient while I bring it back to 100% quality.

Edit 13.01.12 - Fixed grammar [Thanks Avi] + Added QnA

Introduction - Take Two

Hello!

This is my second attempt at opening a blog. The first one crashed along with my previous host. So here I am, trying my luck with the google-hosted-blogspot instead of somehow-hosted-wordpress.

While I'm getting a hang on blogspot and adapting my style and layout to it, I've decided to upload a small introduction post.

About me:

1. 3rd year CompSci student.
2. Many years of experience developing .Net applications (mainly C#).
3. Avid Gamer.
4. Newly sparked interest in Compilation and Programming languages.

About this blog:

In this blog i will write about topics that interest me. Among these are Programming Language features, Frameworks, Compilers or Game Design concepts, interesting mechanics or system discussions. I will, perhaps, discuss other subjects as well, which I cannot categorize at present.

Now bear with me while I get my first actual post ready.
Cheers!

Edit 13.01.12 - Rephrased awkward phrasing. [Thanks Avi]