[m-dev.] An optimization worth doing.

[Lee Naish]

In message <199702092222.JAA07893 at fengshui.cs.mu.oz.au>Tom wrote:

>:- type hufftree	--->
>		node(frequency, item)
>	;	tree(frequency, hufftree, hufftree)
>	.

>get_frequency(node(Freq, _), Freq).
>get_frequency(tree(Freq, _, _), Freq).

>Now, because in both cases we want the first field (irrespective
>of the tag), it would be cheaper to simply mask off the tag at

I also think its worth doing this.  I have come across similar instances
(in Prolog, of course) where I have been tempted to use arg/3 to save
time and code.  This issue is closely linked to data structuire design,
which can be a bit subtle.

The general DS design rule is "if there are N cases invent N different
functors, each with the appropriate number of arguments".  Eg

:- type mylist ---> my_empty_list; my_nonempty_list(data, mylist).
:- type mytree ---> nil; t(mytree, data, mytree).

Very simple!  Now 2-3 trees:

:- type my23tree --->
	nil;
	t2(my23tree, data, my23tree);
	t3(my23tree, data, my23tree, data, my23tree).

Now red-black trees.  Following on from above there is the obvious:

:- type myrbtree --->
        nil;
        tr(myrbtree, data, myrbtree);
        tb(myrbtree, data, myrbtree).

But if you think at a lower(?) level you might come up with something
different:

:- type myrbtree1 --->
        nil;
        rbt(colour, myrbtree1, data, myrbtree1).
:- type colour ---> red ; black.

I think its hard to argue that one of these is more natural than the
other.  In a similar vein (but I think less natural) 23 trees can be
done as follows:

:- type my23tree1 --->
        nil;
        non_empty23t(my23tree1, data, maybe_empty23tree).
:- type maybe_empty23tree --->
	yes_its_empty;
	no_its_not_empty(my23tree1, data, my23tree1).

We can also redefine hufftree in a similar way.

What general things can we say about all this?

1) If different cases for the DS share data then we have a choice to
make.

2) If we choose to combine the cases we need to introduce more types and
the DS representation generally becomes less space efficient.

3) If we choose to separate the cases (and duplicate the same data in
different cases) this tends to lead to code duplication.  See, for
example, the code for searching with the two different RB-tree examples
or get_frequency with the huffman DS.  The source code duplication will
result in object code duplication with switches to select between the
different copies of equivalent code, unless the compiler is smart.

Tom's suggested optimisation addresses the object code inefficiency in
3).   This is a good thing, though the duplicated source code is still
rather a pain.

An alternative would be more flexible data representation.  We all know
that terms in LP are just like (pointers to) Pascal's variant records.
A litle known fact (even I didn't know it until just now) it that Pascal
variant records are significantly more flexible.  For example (in my best
approximation to Pascal syntax, which I have almost totally forgotten):

type my23tree1node =
	record
		left : my23tree1;
		data1: data;
		case nodekind: twoThree of
			two : (right : my23tree1);
			three : (mid : my23tree1;
				 data2: data;
				 right1: my23tree1)
		end

The variant part is contiguous with the invariant part.  In Prolog and
Mercury you can't get a variant part unless you have a pointer to it.
In Pascal you can have invariant parts followed by variant parts (even
nested variant parts) without additional pointers.

I had a nagging suspicion that 2) was the "right" alternative since it
avoids duplicating (source) code.  With a suitable language and (/or?)
implementation it can also be as efficient as 3) + Tom's optimisation.
For untyped unmoded languages like Prolog you expect to pay an efficiency
penalty.  For Mercury you should not have to.  However, I think Mercury has
not moved quite far enough away from the Prolog data structures.  This may
take a fair bit of work to fix.  At least Tom's optimisation allows you
to get the "right" space and time efficiency, even if its with the
"wrong" source code.

Enough of my day wasted...

	lee