[MLton-devel] Minimizing space usage in ML (fwd)

[Joe Hurd]

Hi,

I thought you might be interested in the following optimization that I
passed on to Peter Sestoft a couple of months ago. He responded that
although promising it didn't make much difference in Moscow ML, but
perhaps it will in MLton...

Regards,

Joe


---------- Forwarded message ----------
Date: Thu, 29 Aug 2002 00:06:06 +0100 (BST)
From: Joe Hurd <joe.hurd@cl.cam.ac.uk>
To: Peter Sestoft <sestoft@dina.kvl.dk>
Cc: Ken Friis Larsen <kfl@it.edu>
Subject: Minimizing space usage in ML

Hi Peter,

I've just been to TPHOLs, where I discussed with Carl Witty the issue
of minimizing space usage during execution of ML. He came up with
(what seemed to me) a rather good idea, so thought I'd pass it on.

The idea is that if you compare the following two terms for equality

CON subterm1 = CON subterm2

and the test succeeds, then it's fine to swing the pointer from
subterm1 to subterm2 (correcting the reference counts as you do it).
subterm1 might then be left with no references, allowing it to be
garbage collected. Refinements that suggest themselves are swinging
the pointer from the least-referenced object to the most-referenced,
or favouring objects living in more permanent generations with respect
to the garbage collector.

Over time, this may well shrink the heap size to its optimal size,
with only a small overhead on each nontrivial successful equality
test.

Has this been tried before? Can you see any flaws with the scheme?

Regards,

Joe


On Mon, 2 Sep 2002, Peter Sestoft wrote:

> I've experimentally implemented sharing-on-equality in the runtime,
> but alas, the effect is negligible except in artificial example
> programs.  In particular, my version of Michael's Omega is completely
> unaffected.  Probably the reason is that the equality predicate by
> design does a little work as possible.  So if the first components of
> two tuples are found unequal, no comparison and hence no sharing is
> done one the second, third, etc. components.

> I'll probably not make it a standard part of the runtime unless it can
> be further improved.  One problem is that it makes the equality
> function more non-tailrecursive, so comparison of very long (and equal
> or almost-equal) lists could cause a C stack overflow.






-------------------------------------------------------
This sf.net emial is sponsored by: Influence the future 
of  Java(TM) technology. Join the Java Community 
Process(SM) (JCP(SM)) program now. 
http://ad.doubleclick.net/clk;4699841;7576298;k?http://www.sun.com/javavote
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel