[MLton-user] Destructive update

Stephen Weeks MLton-user@mlton.org
Thu, 9 Feb 2006 10:05:37 -0800


> Following the discussion of mutable vs immutable data structures, I'm
> still a little unsure whether they should be comparison based or hash
> function based. Using comparisons avoids the pathological cases of
> colliding hashes and allows a simpler implementation of immutable data
> structures (especially in-order traversal), but using hash functions
> seems like it might be more efficient and allows a simpler
> implementation of mutable data structures. Hmm.

I bet that HashSet is faster, and haven't personally run into
pathological behavior.  There is the stats printing stuff in HashSet
-- we have measured its behavior in the past to make sure there was no
problem with collisions, and you could easily check in your situation.

If you do benchmarks comparing HashSet to some immutable data
structure(s), please send the results to the list, as I'm sure there
would be interest.

> FYI I am running my programs on a 4Gb machine, so 40% corresponds to
> 1.6Gb, which is how much memory is consumed by the program with
> ram-slop set to 80%. 

At that size the problem is almost certainly address space
fragmentation.  You are probably seeing a single space that is
mark-compacted (which you can confirm with @MLton gc-messages --).