[MLton-devel] size of closures

Stephen Weeks MLton@mlton.org
Mon, 20 Jan 2003 17:42:27 -0800

> I reworked the StreamIO functor to cut down on allocation.  I finally got
> it on par with the existing IO (yeah!), but then I went back to clean up
> some code, and I ended up blowing up the size by quite a bit.
> Now, at first I had this version of input1:
> 	    let
> 	      val (k, next) = if pos + 1 < V.length inp
> 				then (pos + 1, state)
> 				else (0, next)
> 	    in
> 	      SOME (V.sub (inp, pos), update (is, k, next))
> 	    end
> And I get:
> 55,632,880 bytes allocated (2,336 bytes by GC)
> Now, I change input1 to the following, which I thought was a little
> cleaner:
> 	    let
> 	      val update = if pos + 1 < V.length inp
> 			     then fn () => updatePos (is, pos + 1)
> 			     else fn () => updateState (is, next)
> 	    in
> 	      SOME (V.sub (inp, pos), update ())
> 	    end
> And now I get:
> 1,015,633,360 bytes allocated (13,872 bytes by GC)
> I guess it is obvious to me that the two versions are semantically
> equivalent.  I suppose that MLton is unable to compare the two anonymous
> functions to determine that a common closure of just an instream * int * state
> dispatching to update could be used.

Right.  The flow analysis sees the two different lambdas at the one
call site, so the closure converter builds a datatype with two
variants, Env1 and Env2 and a case dispatch at the call to update.
There is no analysis in MLton that tries to notice redundancies across
datatype variants, so the only hope is some other local
simplification.  When I first saw the code, I thought we would be OK,
because known-case would see the dispatch at update, and the two
control-flow paths that construct a closure and go to the dispatch.
Unfortunately, known-case doesn't kick in because of the intervening
V.sub (inp, pos).  It would be nice if known-case were better, but
it's certainly a hard problem to decide how much intervening code to
duplicate in order to simplify a case.

To test this, you can use the following code, which will allow
known-case to kick in, and give the 55M allocation total.

		      val z = V.sub (inp, pos)
		      val update = if pos + 1 < V.length inp
				      then fn () => updatePos (is, pos + 1)
				   else fn () => updateState (is, next)
		      SOME (z, update ())

Of course, this makes it clear that the following code will also have
the 55M total.

		   SOME (V.sub (inp, pos),
			 if pos + 1 < V.length inp
			    then updatePos (is, pos + 1)
			 else updateState (is, next))

And I find that code clearest of all.

This SF.NET email is sponsored by:
SourceForge Enterprise Edition + IBM + LinuxWorld = Something 2 See!
MLton-devel mailing list