unification and polymorphism

Bart Demoen bartd at cs.monash.edu.au
Thu Jul 30 17:20:32 AEST 1998


Doing some benchmarking of my own code, I noticed something
unexpected, which in the end boiled down to the following:

the program constructs 2 lists of integers L1 and L2
then I time the unification of these 2 lists
I measured three ways of unifying them:

1) using Mercury's =/2, i.e. the goal was L1 = L2

2) by using my own unify_list_of_ints/2 predicate defined as:

:- pred unify_list_of_ints(list(int)::in,list(int)::in) is semidet.

unify_list_of_ints([],[]).
unify_list_of_ints([X|R],[Y|L]) :-
        X = Y,
        unify_list_of_ints(R,L).

3) by using the polymorphic version of the above, i.e. the declaration
becomes

:- pred unify_list(list(T)::in,list(T)::in) is semidet.

and otherwise same code as above (up to name change)


So the tested goals looked like

	(1) L1 = L2
or
	(2) unify_list_of_ints(L1,L2)
or
	(3) unify_list(L1,L2)

and the construction of the lists was outside of the call to
benchmark_det and so not counted in the timings


A bit to my surprise, (1) and (3) perform almost the same and
almost an order of magnitude SLOWER than (2)

I can understand the difference between (2) and (3): it is the cost of
polymorphism, right ? A bit higher than I expected I must say.

But is there a need for the large difference between (3) and (1) ?

I always assumed that Mercury was generating specialised versions of
unification, so I had expected (1) and (3) to be the same.

BTW, at the call of L1=L2, the Mercury compiler had the info that both
lists had int elements.

Sorry if this is an oldie or if I missed an option with which to
call the Mercury compiler.

Cheers

Bart




More information about the users mailing list