[MLton] native vs. C code generation

[Matthew Fluet]

> I've computed an average of native vs. C code speed. It turned out that C
> code is 35% slower than native on average (ok this is not a real average).
> Considering code size it's about 10%. My question is then: does it make
> sense to write native codegenerator for a new platform? And, how much effort
> would it be? 

Well, there are a number of individuals using MLton on Sparc and PowerPC 
using only the C codegen.

"Does it make sense to write a native codegen?"  If you re-phrase the
question as "Will a highly tuned native codegen be better than the C
codegen and gcc?", then the answer is almost certainly "yes".  There is a
lot of semantic meaning that we can't convey to gcc through the C
language.  Likewise, the fact that the C codegen is %35 slower than the
native codegen should not be taken as an upper bound on the performance of
a native codegen, as the x86 codegen is the product of my early
association with MLton;  the native backend hasn't received much of an
overhaul since it was originally written (and virtually every other part
of the compiler has since then).  For example, the register allocator is 
notoriously bad:

http://mlton.org/pipermail/mlton/2004-June/025511.html
http://mlton.org/pipermail/mlton/2004-July/025519.html

And, a choice quote from that thread:

   There are some nagging questions, like what could the native codegen
   possibly be doing that improves over gcc? I've conjectured that the 
   native codegen makes better use of alias information than gcc does. (In
   particular, from gcc's perspective both the ML stack and the ML heap
   alias, so every stack-slot operation conflicts with every heap cell
   manipulation.) I wrote up some experiments, with some surprising
   results, at:

     http://www.mlton.org/pipermail/mlton/2002-November/013253.html

   The whole thread there has some other interesting points.

There appear to be definite gains available in the native codegen, but it 
isn't clear that more tuning of the C codegen wouldn't also close the gap.

Other ways of rephrasing the question:
 * "Are there likely to be interesting research questions raised by 
    writing a new native codegen?"  -- answer: probably not
 * "Would writing a new native codegen be an appropriate undergrad 
    or early gard project?"  -- answer: possibly; note, there are 
         ancillary benefits to working on MLton (I've gotten one nice 
         research paper out of it, ideas for future papers, all out of my 
         initial association writing a native backend).


"How much effort would it be?"  The x86 native codegen is the product of 
one full-time summer internship (2000), one half-time summer internship 
(2001), and steady part-time work (since fall 2000).  And the x86 native 
codegen is by no means a highly tuned beast.  We've revised the lowest 
level ILs since the x86 native codegen was started (for the better, making 
future native codegens likely to be slightly easier), but I would still 
estimate a good 4 to 6 months of full-time work to get something in the 
ballpark (i.e., with the C-codgen about 25% slower).

So, probably the best answer is what one thinks of that trade off:
say, 6 months of work for 1.3X speedup.


I'll conclude with the fact that I started down the MLton/C-- experiment 
(the thread I referred to in the previous message) both to foster some 
exchange with a project whose reasearchers I've spent a lot of time with, 
but also as a means of exploring ways of getting out of the native-codegen 
game.  Between MLRISC, C--, LLVM, etc., there appear to be a number of 
projects that are aiming at providing a simpler means of targetting 
multiple platforms without the downside of emitting portable C and without 
the cost of writing multiple codegens.