cvs diff: tree234.m

[Christopher Rodd SPEIRS]

Tom, could you please review this change to tree234.m
While looking at the code in tree234, i noticed that tree234__set and
tree234__insert were not making balanced 234 trees.  Instead, they were
essentially making unbalanced binary trees.  After making these changes,
and doing some quick timing checks, it seems that using balanced 234
trees are slower than unbalanced binary trees in the compiler.  The
compile time slowed down by about 3%.  I think that perhaps the reason
for this is that it is 11% slower to do the key comparisons on a 3 node,
in comparison to a 2 node.  ( this is because on average it takes 1.66
comparisons to select the correct subtree, and by selecting the correct
subtree, the search space is 1/3 what it was.  This is in comparison to
1 comparison to halve the search space for a 2 node).

Cvs log message starts here:

Changed tree234__search to use a more efficient algorithm when searching
4 nodes. (compare against the middle key first)
Changed tree234__set so that it builds a balanced 234tree.  The old
implementation of 234trees split 4 nodes into 3 2nodes whenever a 4 node
was created, instead of pushing the 4 nodes up to the root node before
it was split.  

compiler/tree234.m:

Index: tree234.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/library/tree234.m,v
retrieving revision 1.16
diff -u -r1.16 tree234.m
--- tree234.m	1997/04/01 10:04:48	1.16
+++ tree234.m	1997/04/04 01:44:36
@@ -208,45 +208,45 @@
 			)
 		)
 	;
-		T = four(K0, _, _, _, _, _, _, _, _, _),
-		compare(Result0, K, K0),
+		T = four(_, _, K1, _, _, _, _, _, _, _),
+		compare(Result0, K, K1),
 		(
 			Result0 = (<),
-			T = four(_, _, _, _, _, _, T0, _, _, _),
-			tree234__search(T0, K, V)
+			T = four(K0, _, _, _, _, _, _, _, _, _),
+			compare(Result1, K, K0),
+			(
+				Result1 = (<),
+				T = four(_, _, _, _, _, _, T0, _, _, _),
+				tree234__search(T0, K, V)
+			;
+				Result1 = (=),
+				T = four(_, V0, _, _, _, _, _, _, _, _),
+				V = V0
+			;
+				Result1 = (>),
+				T = four(_, _, _, _, _, _, _, T1, _, _),
+				tree234__search(T1, K, V)
+			)
 		;
 			Result0 = (=),
-			T = four(_, V0, _, _, _, _, _, _, _, _),
-			V = V0
+			T = four(_, _, _, V1, _, _, _, _, _, _),
+			V = V1
 		;
 			Result0 = (>),
-			T = four(_, _, K1, _, _, _, _, _, _, _),
-			compare(Result1, K, K1),
+			T = four(_, _, _, _, K2, _, _, _, _, _),
+			compare(Result1, K, K2),
 			(
 				Result1 = (<),
-				T = four(_, _, _, _, _, _, _, T1, _, _),
-				tree234__search(T1, K, V)
+				T = four(_, _, _, _, _, _, _, _, T2, _),
+				tree234__search(T2, K, V)
 			;
 				Result1 = (=),
-				T = four(_, _, _, V1, _, _, _, _, _, _),
-				V = V1
+				T = four(_, _, _, _, _, V2, _, _, _, _),
+				V = V2
 			;
 				Result1 = (>),
-				T = four(_, _, _, _, K2, _, _, _, _, _),
-				compare(Result2, K, K2),
-				(
-					Result2 = (<),
-					T = four(_, _, _, _, _, _, _, _, T2, _),
-					tree234__search(T2, K, V)
-				;
-					Result2 = (=),
-					T = four(_, _, _, _, _, V2, _, _, _, _),
-					V = V2
-				;
-					Result2 = (>),
-					T = four(_, _, _, _, _, _, _, _, _, T3),
-					tree234__search(T3, K, V)
-				)
+				T = four(_, _, _, _, _, _, _, _, _, T3),
+				tree234__search(T3, K, V)
 			)
 		)
 	).
@@ -590,9 +590,22 @@
 				T0 = four(_, _, _, _, _, _, _, _, _, _)
 			->
 				tree234__four(T0, K2, V2, T3, T4),
-				T5 = four(K2, V2, K0, V0, K1, V1,
-					T3, T4, T1, T2),
-				tree234__set(T5, K, V, Tree)
+				compare(Result1, K, K2),
+				(
+					Result1 = (<),
+					tree234__set(T3, K, V, NewT0),
+					Tree = four(K2, V2, K0, V0, K1, V1,
+						NewT0, T4, T1, T2)
+				;
+					Result1 = (=),
+					Tree = four(K2, V, K0, V0, K1, V1,
+						T3, T4, T1, T2)
+				;
+					Result1 = (>),
+					tree234__set(T4, K, V, NewT1),
+					Tree = four(K2, V2, K0, V0, K1, V1,
+						T3, NewT1, T1, T2)
+				)
 			;
 				tree234__set(T0, K, V, T3),
 				Tree = three(K0, V0, K1, V1, T3, T1, T2)
@@ -609,9 +622,22 @@
 					T1 = four(_, _, _, _, _, _, _, _, _, _)
 				->
 					tree234__four(T1, K2, V2, T3, T4),
-					T5 = four(K0, V0, K2, V2, K1, V1,
-						T0, T3, T4, T2),
-					tree234__set(T5, K, V, Tree)
+					compare(Result2, K, K2),
+					(
+					    Result2 = (<),
+					    tree234__set(T3, K, V, NewT1),
+					    Tree = four(K0, V0, K2, V2, K1, V1,
+					    	T0, NewT1, T4, T2)
+					;
+					    Result2 = (=),
+					    Tree = four(K0, V0, K2, V, K1, V1,
+					    	T0, T3, T4, T2)
+					;
+					    Result2 = (>),
+					    tree234__set(T4, K, V, NewT2),
+					    Tree = four(K0, V0, K2, V2, K1, V1,
+					    	T0, T3, NewT2, T2)
+					)
 				;
 					tree234__set(T1, K, V, T3),
 					Tree = three(K0, V0, K1, V1, T0, T3, T2)
@@ -625,9 +651,22 @@
 					T2 = four(_, _, _, _, _, _, _, _, _, _)
 				->
 					tree234__four(T2, K2, V2, T3, T4),
-					T5 = four(K0, V0, K1, V1, K2, V2,
-						T0, T1, T3, T4),
-					tree234__set(T5, K, V, Tree)
+					compare(Result2, K, K2),
+					(
+					    Result2 = (<),
+					    tree234__set(T3, K, V, NewT2),
+					    Tree = four(K0, V0, K1, V1, K2, V2,
+					    	T0, T1, NewT2, T4)
+					;
+					    Result2 = (=),
+					    Tree = four(K0, V0, K1, V1, K2, V,
+					    	T0, T1, T3, T4)
+					;
+					    Result2 = (>),
+					    tree234__set(T4, K, V, NewT3),
+					    Tree = four(K0, V0, K1, V1, K2, V2,
+					    	T0, T1, T3, NewT3)
+					)
 				;
 					tree234__set(T2, K, V, T3),
 					Tree = three(K0, V0, K1, V1, T0, T1, T3)