lists,vectors,arrays in SML/NJ and MLton

Matthew Fluet
Wed, 9 Aug 2000 10:26:45 -0400 (EDT)

> I would guess that the slowness of the array-of-array choice is because
> of the generational GC.   In general this makes mutation more expensive
> since you have to mark a card to indicate that the written to object may
> contain a pointer to a younger generation.

Probably, although I'm surprised that the record-of-refs choice doesn't
exhibit the same problems.

Unfortunately, the self-compile last night showed that the record-of-refs
wasn't really that great.  The allocate-registers pass took 3126 seconds
(up from 1403 seconds with the vector-of-lists).

> The right thing to expose may be a fold procedure.  Then you never cons up the
> initial list when you filter or map.

Well, the map never cons up the list -- it's one of the functions
specialized to the representation.  Filter has to dump a list at the end,
so there is some consing.