[mercury-users] Set performance

[Thomas Conway]

Hi

I thought the following observation might be interesting to the readers
of mercury-users.

Over the weekend I was finishing off a Mercury yacc clone. On the C
grammar it was taking about 35-40 seconds just to compute the LALR
lookaheads (see Aho, Seti and Ullman for details of the algorithm).
Profiling showed that the majority of the time was spent doing set
unions. The following pseudo code describes the code as it stood:

closure(OldItems, Items) :-
	compute_some_new_lr1_items(ComputedItemSet),
	NewItems = ComputedItemSet - OldItems, % set difference
	if (not empty(NewItems))
		Items1 = OldItems \/ NewItems, % union
		closure(Items1, Items)
	else
		Items = OldItems

compute_some_new_lr1_items(ComputedItemSet) :-
	foldl(..., ComputedItemSet0::in, ComputedItemSet1::out) is det :-
		create_as_set_of_new_items(SomeNewItems),
		ComputedItemSet1 = ComputedItemSet0 \/ SomeNewItems
	
It turns out that the union inside the foldl (ie the inner loop) results
in O(n^2) behaviour (The list that we're folding over is of similar size
to the sets). I found that I could change this to O(n log n) by constructing
a list of new sets in the inner loop, and then unioning the list of sets
in a pairwise fashion. eg:
	[A, B, C, D, E, F] ->
	[A \/ B, C \/ D, E \/ F] -> ....

For the test case of the C grammar, this halved the running time. If people
think it a good idea, I could add the predicate to the standard library.
It would look like:
	:- pred union_list(list(set(T)), set(T)).
	:- mode union_list(in, out) is det.

	
-- 
 Thomas Conway )O+     Every sword has two edges.
     Mercurian            <conway at cs.mu.oz.au>
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------