[mercury-users] SICStus vs Mercury

[Fergus Henderson]

On 20-Sep-2000, Mattias Waldau <mattias.waldau at abc.se> wrote:
> I selected to test Mercury by implementing a simple genetic program,
> currently it sorts an array. The program can be found at the links below.
> I selected this problem, since the program was deterministic and very moded.
> It is a perfect candidate for Mercury.
...
> Mercury is about 3 times faster than SICStus on this problem. I expected
> more since the program is completely deterministic. Maybe one of the
> developers of Mercury or HAL should include this program into their test
> suite and try to understand why the difference isn't bigger.
> 
> http://www.abc.se/~m10217/download/genetic_test.pl
> http://www.abc.se/~m10217/download/genetic_test.m

Well, to start with, make sure you compile the Mercury version with
all optimizations enabled, e.g. using the following Mmakefile

	$ cat Mmakefile
	MCFLAGS = -O6 --intermodule-optimization
	CFLAGS = -DML_OMIT_ARRAY_BOUNDS_CHECKS

> P.P.s. Comments on how to make the Mercury-programs better is appreciated.

The first step is to run the profiler:

	$ mmake GRADEFLAGS=--profiling
	$ ./genetic_test
	$ mprof | less
	$ mprof -c | less

This quickly shows that this program is "map-limited", i.e. it is spending
most of its time in map__insert, specifically the calls from mate_copy/7.

The following patch, which changes the program to use an array rather
than a map for representing the set of ints, improved the speed of the
program by a factor of about 3.5.

There was a similar performance problem in the standard library
predicate random__permutation -- it was using a map when an array
would have been faster.  I have fixed that in the latest development
version of the Mercury compiler.  That change improved the speed
a bit more, up to about 5.5 times the speed of the original.

Cheers,
	Fergus.

--- genetic_test.m.orig	Mon Sep 25 18:22:35 2000
+++ genetic_test.m	Mon Sep 25 18:49:24 2000
@@ -527,18 +528,18 @@
 %%% between Start and Stop in Master is copied to Copy. Copied is a tree
 %%% of all the positions copied, which will be used to fast lookup.
 :- pred mate_copy(int::in, int::in, array(int)::in,
-		  array(int)::array_uo, map(int,int)::out
+		  array(int)::array_uo, intset::intset_uo
 		 ) is det.
 mate_copy(Start, Stop, Master, NewCopy, NewCopied) :-
 	%% create an initial empty Copy
 	array__init(array__size(Master), -1, Copy),
-	map__init(Copied),
+	intset_init(array_max_elem(Master) + 1, Copied),
 	mate_copy(Start, Stop, Master, Copy, NewCopy, Copied, NewCopied).
 
 :- pred mate_copy(int::in, int::in, array(int)::in,
 		  array(int)::array_di, array(int)::array_uo,
-		  map(int,int)::in, map(int,int)::out
-		 ) is det.
+		  intset::intset_di, intset::intset_uo
+		  ) is det.
 mate_copy(Current, Stop, Master, Copy, NewCopy, Copied, NewCopied) :-
 	(
 	  Current > Stop
@@ -548,13 +549,38 @@
 	;
 	  Element = array__lookup(Master, Current),
 	  array__set(Copy, Current, Element, Copy2),
-	  map__det_insert(Copied, Element, 1, Copied2),
+	  intset_add(Copied, Element, Copied2),
 	  mate_copy(Current+1, Stop, Master, Copy2, NewCopy, Copied2, NewCopied)
 	).
 
+:- func array_max_elem(array(int)) = int.
+array_max_elem(Array) = array_max_elem_2(Array, MinInt, 0, array__size(Array)) :-
+	int__min_int(MinInt).
+
+:- func array_max_elem_2(array(int), int, int, int) = int.
+array_max_elem_2(Array, Max0, Count, Size) = Max :-
+	( Count = Size ->
+		Max = Max0
+	;
+		Elem = array__lookup(Array, Count),
+		int__max(Max0, Elem, Max1),
+		Max = array_max_elem_2(Array, Max1, Count + 1, Size)
+	).
 
-
-
+:- type intset == array(bool).
+:- mode intset_di == array_di.
+:- mode intset_uo == array_uo.
+
+:- pred intset_init(int::in, intset::array_uo) is det.
+intset_init(Size, IntSet) :- array__init(Size, no, IntSet).
+
+:- pred intset_add(intset::array_di, int::in, intset::array_uo).
+intset_add(IntSet0, Elem, IntSet) :-
+	array__set(IntSet0, Elem, yes, IntSet).
+
+:- pred intset_contains(intset::in, int::in) is semidet.
+intset_contains(IntSet, Elem) :-
+	array__lookup(IntSet, Elem, yes).
 
 %%% mate_otherhalf(Start, Stop, Master, Copy, Copied, NewCopy, Duplicates, Empty) is true if all elements
 %%% in Master between Start and Stop os copied into Copy, the result is NewCopy.
@@ -565,7 +591,7 @@
 %%%
 %%% I had to change arg 3 from array_di to in, since I only know in!
 :- pred mate_otherhalf(int::in, int::in, array(int)::in,
-		       array(int)::array_di, map(int,int)::in,
+		       array(int)::array_di, intset::in,
 		       array(int)::array_uo, list(int)::out, list(int)::out
 		      ) is det.
 mate_otherhalf(Start, Stop, Master, Copy, Copied,
@@ -579,7 +605,7 @@
 	;
 	  Element = array__lookup(Master, Start),
 	  (
-	    map__search(Copied, Element, _) %could use map__member
+	    intset_contains(Copied, Element)
 	  ->
 	    %% this value already exists 
 	    mate_otherhalf(Start+1, Stop, Master, Copy, Copied,

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------