lists,vectors,arrays in SML/NJ and MLton

[Matthew Fluet]

> I glanced at what you have and I think the best representation for
> RegisterAllocation.t would be a record with mutable fields 
>   type t = {eax: entry, ebx: entry, ..., esp: entry, 
>             reserved: Register.t list}
> (where entry is modified to be mutable)

Using a record of list refs is working about as well as a vector of lists.
I changed a few of the functions so that all of the accesses of the
registerAllocation.t type go through a small set of functions, so it's
been fairly easy to try out different representations.  Another suprise
was that a record of record of option refs (i.e., give each part a slot)
was pretty bad, although not as bad as array of array.  I suspect part of
this might be tradeoffs between places where I really want to update a
single element quickly and other places where I want to filter or map over
the whole structure.  Creating a list out of the individual pieces is
more costly than simply returning the list that's right there.

I'm curious to see how this works on a self-compile and with a
MLton-compiled version of MLton.  I think it will be a little bit better.
I remember from self-compiles I was doing last week that peak memory usage
was during allocate-registers, but it always fell off when it came close
to using 100%; I suspect that's from the fact that all of these little
vector copies filled the heap, but at a GC all but the current version
could be collected.  This version hopefully will have slightly better
results, since the whole register file won't be copied every time.

> The only thing I can think of is the fact that they have a generational
> collector and so assignments cost them.
> 
> > Would
> > this same behavior appear using the MLton compiled version of MLton? 
> 
> I would be surprised.  In fact, there will be no difference between arrays and
> vectors, and I would bet that mutable arrays are faster than copied lists.  But
> again, I would rather see record types wherever possible.

Well, I'll check it out after getting a self-compile to go through.