[mercury-users] Exceptions and unique modes

[Thomas Conway]

On Thu, Feb 22, 2001 at 10:45:32PM EST, Ralph Becket wrote:
> >From Peter Ross on 22/02/2001 11:41:32
> > > 
> > You would think that the best canditate for reuse of that memory is the
> > next state.  Unfortunately it is not quite that easy as the following
> > type indicates.
> > 
> > :- type t
> >     --->    f(int)
> >     ;       g(int, int).
> > 
> > No matter what you initialise this type to you need to make sure that
> > you allocate 2 words so that you can possibly hold the g constructor at
> > some later date.
> 
> I don't think di/uo guarantees structure reuse, just that SR may happen,
> in which case you have to take the conservative line.  It would certainly
> be good if the compiler did perform this optimization for unique objects,
> though.

That's all well and good for the type `t' above, but for 234 trees
it is less clear whether this is a good idea:

:- type tree234
	--->	empty
	;	two(K, V, tree234, tree234)
	;	three(K, V, K, V, tree234, tree234, tree234)
	;	four(K, V, K, V, K, V, tree234, tree234, tree234, tree234)
	.

If we allocate 10 words for every two/4 cell in stead of allocating
4 words, depending on the distribution of nodes we may pay quite a
high memory overhead, and it becomes less clear that it is a win to
do reserve the extra memory (in this specific case, perhaps red-black
trees would be a win, Pete! ;-)).

Here is some actual data. I just whipped up a little program that
inserts N random keys into a tree234, then counts the number of
each kind of node:

       1 key:
		       1 two nodes
		       0 three nodes
		       0 four nodes

      10 keys:
		       2 two nodes
		       1 three nodes
		       2 four nodes

     100 keys:
		      26 two nodes
		      22 three nodes
		      10 four nodes

    1000 keys:
		     251 two nodes
		     223 three nodes
		     101 four nodes

   10000 keys:
		    2403 two nodes
		    2321 three nodes
		     985 four nodes

  100000 keys:
		   24031 two nodes
		   22752 three nodes
		   10155 four nodes

What this suggests is that the memory overhead in this case isn't
too bad - somewhere between 25% and 30% for maps with lots of keys,
and less for most small maps (we don't care about wasting 6 words
for singleton maps).

However, such an allocation strategy would need a heuristic because
if I have a type that is more unbalanced that tree234, then the effect
could be much worse (eg
:- type matrix
	--->	id
	;	mat(float, float, float, float,
		    float, float, float, float,
		    float, float, float, float,
		    float, float, float, float).

where most of the time I will be using `id').

-- 
  Thomas Conway )O+
 <conway at cs.mu.oz.au>       499 User error! Replace user, and press any key.
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------