[MLton] stack-allocated references

Jake Donham jdonham at cs.cmu.edu
Wed Feb 28 18:09:26 PST 2007


Over on mlton-user, Matthew Fluet wrote:

> MLton will eliminate a reference cell that doesn't outlive its
> scope.  A common idiom that is picked up is the following:

> fun mapAndLength f l =
>    let val r = ref 0
>        val l' = map (fn x => (r := !r + 1; f x) l
>    in
>      (l', !r)
>    end

> The use of the reference is completely local to the function (after 
> inlining the code for map) and MLton will eliminate heap allocated 
> reference cell in favor of a stack local integer holding the length.

Does this happen if the ref is passed into another non-inlined
function? Or only if it is used solely in the function in which it is
declared (after inlining, as you mention).

I ask because I am looking at implementing "stacklets" as part of the
Cheng-Blelloch collector. The idea is that the stack is a list of
stacklets (of bounded size) linked together, and only the topmost one
is mutable. Immutable stacklets can be processed during the
collection, without a write barrier, and the topmost stacklet can be
processed in bounded time when the collector is turned off (see
Cheng's thesis for a fuller description).

If a stack-allocated ref can be passed into a function, then
non-topmost stacklets are not immutable and this scheme doesn't work.



More information about the MLton mailing list