[m-dev.] for review: performance improvements to moose.

[Thomas Conway]

Hi

The following changes to moose were made in response to using
deep profiling. It took about 5 minutes to find each of the two
issues that are addressed and then about 15 or 20 to then fix them.

-- 
 Thomas Conway              Unicode for terrorists: U+0001 300C
 <conway at cs.mu.oz.au>         "Tie his hands behind his back"
 Mercurian )O+  

extras/moose/grammar.m:
extras/moose/lalr.m:
	Changed a couple of places where list_to_set is called so that
	we construct the list in sorted order and can call
	sorted_list_to_set instead which give about a 10% performance
	improvement.

	Change a place where we call set_to_sorted_list and then iterate
	over the list calling set__insert. Instead we now reverse the
	list first so that the insertions happen at the start of the list
	not the end. Results in about 5% performance improvement.

Index: grammar.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/extras/moose/grammar.m,v
retrieving revision 1.1
diff -u -r1.1 grammar.m
--- grammar.m	2000/05/22 05:22:03	1.1
+++ grammar.m	2000/08/23 04:50:32
@@ -229,7 +229,15 @@
 		First0, Follow0),
 	foldl(transform_clause_list, ClauseList, Grammar0, Grammar1),
 	compute_first0(Grammar1, Grammar2),
-	compute_follow0(Grammar2, Grammar).
+	compute_follow0(Grammar2, Grammar3),
+	Grammar3 = grammar(Rules3, AllClauses3, XForms3, Nont3, ClauseIndex3,
+		First3, Follow3),
+	map__map_values((pred(_K::in, V0::in, V::out) is det :-
+	    sort(V0, V1),
+	    reverse(V1, V)
+	), ClauseIndex3, ClauseIndex4),
+	Grammar = grammar(Rules3, AllClauses3, XForms3, Nont3, ClauseIndex4,
+		First3, Follow3).
 
 :- pred start_rule(nonterminal, rule).
 :- mode start_rule(in, out) is det.
Index: lalr.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/extras/moose/lalr.m,v
retrieving revision 1.1
diff -u -r1.1 lalr.m
--- lalr.m	2000/05/22 05:22:04	1.1
+++ lalr.m	2000/08/23 05:38:01
@@ -301,7 +301,11 @@
 	BItem = item(Bp, Bd),
 	BItem0 = item(Bp, Bd, (*)),
 	J0 = closure({ BItem0 }, Rules, First, Index),
-	set__to_sorted_list(J0, JList),
+	set__to_sorted_list(J0, JList0),
+	    % Reverse the list so that in add_spontaneous, the 
+	    % set insertions are in reverse sorted order not
+	    % sorted order thereby taking to cost from O(n) to O(1).
+	reverse(JList0, JList),
 	lookaheads2(JList, BItem, I, Gotos, Rules, Lookaheads0, Lookaheads1),
 	lookaheads1(BItems, I, Gotos, Rules, First, Index,
 		Lookaheads1, Lookaheads).
@@ -344,10 +348,17 @@
 			;
 				Bf = Bf0
 			),
-			set__to_sorted_list(Bf, BfList),
+			set__to_sorted_list(Bf, BfList0),
+			    % Reverse the list so that we construct
+			    % the new items in reverse sorted order
+			    % so that the accumulated list is in
+			    % sorted order. Thus we don't have to
+			    % sort the list to turn it into a set.
+			    % Reduces running time by > 10%
+			reverse(BfList0, BfList),
 			lookup(Index, Bn, Bps),
 			make_items(Bps, BfList, [], NList),
-			set__list_to_set(NList, N),
+			set__sorted_list_to_set(NList, N),
 			I1 = [N|I0]
 		;
 			I1 = I0
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------