[MLton-user] Why is recursion slower than C?

[Wesley W. Terpstra]

On Apr 25, 2007, at 5:44 PM, Neal Glew wrote:
> Intel hardware (probably AMD as well) has a return address stack as
> part of the branch prediction logic.  This stack stores the most
> recent n (for some n) addresses pushed by call instructions.  At a ret
> instruction the top of this stack is used to predict where the return
> will return to (and the stack is popped).  Not using these
> instructions means not using this part of the branch prediction logic
> and generally results in very poor branch prediction for returns, and
> thus much stalling.  I suspect that this accounts for most of the
> performance difference you are experiencing.

Yeah. It sounds like we're all in agreement about why C is faster  
here. It's a shame because one would really like SML to be fast at  
recursion. As long as
>> Also, it seems MLton is using %ebp for the stack pointer, instead  
>> of %esp. Why is this? I gather this is why call/return are out
> In a MLton compiled program, there are effectively two stacks: the  
> system C stack and the ML stack (allocated in the ML heap, which in  
> turn is allocated in the system C heap).
this remains true, it seems unlikely that MLton will ever be able to  
compete with C on recursion with two non-tail branches.