Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!linus!philabs!cmcl2!harvard!caip!seismo!mcvax!unido!ecrcvax!jclaude From: jclaude@ecrcvax.UUCP (Jean Claude Syre) Newsgroups: net.lang.prolog Subject: Benchmarking Prolog Systems (Version1, part3) Message-ID: <229@ecrcvax.UUCP> Date: Tue, 29-Apr-86 09:29:10 EDT Article-I.D.: ecrcvax.229 Posted: Tue Apr 29 09:29:10 1986 Date-Received: Sat, 3-May-86 01:47:06 EDT Organization: ECRC, D-8000 Muenchen 81, W. Germany Lines: 503 A Proposal for *********************************************** *** BENCHMARK PROGRAMS FOR PROLOG SYSTEMS *** *********************************************** Part 3 (of 3) 2. Small Prolog programs. 2.1 Introduction. Here we deal with prolog programs that do something, while being still small but representative of some well-known prolog computations. This set should be augmented by other programs, some of them might come from your ideas. Some of the following programs were taken from the Berkeley paper by Peter Van Roy "A Prolog Compiler for the PLM". Other programs were kindly donated by the following ECRC members: Helmut Simonis, Mehmet Dincbas and Pascal Vanhentenryck. The programs have been statically analysed and they represent fairly standard programs as far as the statistical averages are concerned. That is the arity of most clauses is 2 or 3 and there are usually 2 or 3 clauses per predicate. The programs range from fairly trivial programs like fibonacci series to problems such as Hamiltonian graph traversal. We have included two versions of main - one for the muprolog and one for the cprolog (default) dialect. In case neither work for your prolog system, you should modify these to write an appropriate message and use a stopwatch for the timing. These benchmarks were run on a VAX 785 with 8 Meg of memory, under 4.2 BSD Unix. The interpreter was C-Prolog version 1.5. This entire file (without mail/net headers) contains 502 lines. 2.2. Program names and main figures. Name | Call by | # of Inferences | KLips (C-Prolog) ----------+-------------------+-------------------+----------- mainm | for use as a template only --- | --- ----------+-------------------+-------------------+----------- fib | fibonacci(1). | 4932 | 1.97 ----------+-------------------+-------------------+----------- map | map(200). | 68 | 1.29 ----------+-------------------+-------------------+----------- mham | mham(1). | 493824 | 1.69 ----------+-------------------+-------------------+----------- mutest | mutest(1). | 1366 | 2.34 ----------+-------------------+-------------------+----------- quicksort | qs(10). | 605 | 1.90 ----------+-------------------+-------------------+----------- queens | qu(10). | 684 | 1.70 ----------+-------------------+-------------------+----------- query | query(1). | 2294 | 0.90 ----------+-------------------+-------------------+----------- 2.3. Program source listings. % This is the main loop for Mu-Prolog systems. % It loops 200 times (for use with naive and map) main :-utime X, loop(200), utime Y, compens_loop(200), utime N, Real is Y - N, write('Realtime is :'), write(Real), nl. compens_loop(0). compens_loop(X) :- Y is X - 1, compens_loop(Y). loop(0). loop(X) :- top, Y is X - 1, loop(Y). % Here is the normal main loop for Mu-Prolog... main :-utime X, top, utime Y, write(Y), write(' millseconds'), nl. % Note: has to be not(top) for the 4-queens and query ! -------------------------CUT HERE------------------------------ % Common functions... print_times(T1,T2,T3,L) :- TT1 is T2 - T1, TT2 is T3 - T2, TT is TT1 - TT2, write('Net Time is : '), write(TT), nl, Lips is L / TT, Klips is Lips / 1000, write('KLips are: '), write(Klips), nl. compens_loop(0). compens_loop(X) :- Y is X - 1, compens_loop(Y). el(X,[X|L]). el(X,[Y|L]):-el(X,L). %--------------------------------------------------- % Fibonacci Series the slow way % fibonacci(1) will do... fibonacci(N) :- X is cputime, fib_loop(N), Now is cputime, compens_loop(N), M is cputime, Li is 4932 * N, print_times(X,Now,M,Li). fib_loop(0). fib_loop(X) :- top_fib(15,Z), Y is X - 1, fib_loop(Y). top_fib(0,1). top_fib(1,1). top_fib(X,Y):- X1 is X-1, X2 is X-2, top_fib(X1,Y1), top_fib(X2,Y2), Y is Y1+Y2. %------------------------------------ % Map colouring problem % map(200) is advised. map(N) :- X is cputime, map_loop(N), Now is cputime, compens_loop(N), M is cputime, Li is 68 * N, print_times(X,Now,M,Li). map_loop(0). map_loop(X) :- map_top, Y is X - 1, map_loop(Y). map_top:- el(X1,[b]), el(X2,[r]), el(X7,[g]), el(X13,[w]), el(X3,[b,r,g,w]), not(X2=X3), not(X3=X13), el(X4,[b,r,g,w]), not(X2=X4), not(X7=X4), not(X3=X4), el(X5,[b,r,g,w]), not(X13=X5), not(X3=X5), not(X4=X5), el(X6,[b,r,g,w]), not(X13=X6), not(X5=X6), el(X8,[b,r,g,w]), not(X7=X8), not(X13=X8), el(X9,[b,r,g,w]), not(X13=X9), not(X4=X9), not(X8=X9), el(X10,[b,r,g,w]), not(X4=X10), not(X5=X10), not(X6=X10), not(X9=X10), el(X11,[b,r,g,w]), not(X11=X13), not(X11=X10), not(X11=X6), el(X12,[b,r,g,w]), not(X12=X13), not(X12=X11), not(X12=X9), display([X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12,X13]),nl. map_top. %------------------------------------ % Hamiltonian Graphs... % long (nearly half a million LI's !) mham(N) :- X is cputime, mham_loop(N), Now is cputime, compens_loop(N), M is cputime, Li is 493824 * N, print_times(X,Now,M,Li). mham_loop(0). mham_loop(X) :- mham_top, Y is X - 1, mham_loop(Y). mham_top:- cycle_ham([a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t],X), write(X),nl, fail. mham_top. cycle_ham([X|Y],[X,T|L]):- chain_ham([X|Y],[],[T|L]), edge(T,X). chain_ham([X],L,[X|L]). chain_ham([X|Y],K,L):- delete(Z,Y,T), edge(X,Z), chain_ham([Z|T],[X|K],L). delete(X,[X|Y],Y). delete(X,[U|Y],[U|Z]):- delete(X,Y,Z). edge(X,Y):- connect(X,L), el(Y,L). connect(0,[1,2,3,4,5,6,7,8,9]). connect(1,[0,2,3,4,5,6,7,8,9]). connect(2,[0,1,3,4,5,6,7,8,9]). connect(3,[0,1,2,4,5,6,7,8,9]). connect(4,[0,1,2,3,5,6,7,8,9]). connect(5,[0,1,2,3,4,6,7,8,9]). connect(6,[0,1,2,3,4,5,7,8,9]). connect(7,[0,1,2,3,4,5,6,8,9]). connect(8,[0,1,2,3,4,5,6,7,9]). connect(9,[0,1,2,3,4,5,6,7,8]). connect(a,[b,j,k]). connect(b,[a,c,p]). connect(c,[b,d,l]). connect(d,[c,e,q]). connect(e,[d,f,m]). connect(f,[e,g,r]). connect(g,[f,h,n]). connect(h,[i,g,s]). connect(i,[j,h,o]). connect(j,[a,i,t]). connect(k,[o,l,a]). connect(l,[k,m,c]). connect(m,[l,n,e]). connect(n,[m,o,g]). connect(o,[n,k,i]). connect(p,[b,q,t]). connect(q,[p,r,d]). connect(r,[q,s,f]). connect(s,[r,t,h]). connect(t,[p,s,j]). %------------------------------------ % Hofstader's mu math (mutest) proving muiiu % from Godel Escher Bach mutest(N) :- X is cputime, mu_loop(N), Now is cputime, compens_loop(N), M is cputime, Li is 1366 * N, print_times(X,Now,M,Li). mu_loop(0). mu_loop(X) :- mu_top, Y is X - 1, mu_loop(Y). mu_top:- theorem(5,[m,u,i,i,u]). rules(S, R) :- rule3(S,R). rules(S, R) :- rule4(S,R). rules(S, R) :- rule1(S,R). rules(S, R) :- rule2(S,R). rule1(S,R) :- append(X, [i], S), append(X, [i,u], R). rule2([m | T], [m | R]) :- append(T, T, R). rule3([], -) :- fail. rule3(R, T) :- append([i,i,i], S, R), append([u], S, T). rule3([H | T], [H | R]) :- rule3(T, R). rule4([], -) :- fail. rule4(R, T) :- append([u, u], T, R). rule4([H | T], [H | R]) :- rule4(T, R). theorem(Depth, [m, i]). theorem(Depth, []) :- fail. theorem(Depth, R) :- Depth > 0, D is Depth - 1, theorem(D, S), rules(S, R). append([], X, X). append([A | B], X, [A | B1]) :- !, append(B, X, B1). %------------------------------------ % Quicksort of 50 element list % qs(N) :- X is cputime, qs_loop(N), Now is cputime, compens_loop(N), M is cputime, Li is 605 * N, print_times(X,Now,M,Li). qs_loop(0). qs_loop(X) :- qs_top, Y is X - 1,qs_loop(Y). qs_top:- list50(L), qsort(L,X,[]), write(X),nl. qsort([X|L],R,R0) :- partition(L,X,L1,L2), qsort(L2,R1,R0), qsort(L1,R,[X|R1]). qsort([],R,R). partition([X|L],Y,[X|L1],L2) :- X =< Y,!, partition(L,Y,L1,L2). partition([X|L],Y,L1,[X|L2]) :- partition(L,Y,L1,L2). partition([],_,[],[]). list50([27,74,17,33,94,18,46,83,65,2, 32,53,28,85,99,47,28,82,6,11, 55,29,39,81,90,37,10,0,66,51, 7,21,85,27,31,63,75,4,95,99, 11,28,61,74,18,92,40,53,59,8]). %------------------------------------ % Queens on a chess board problem... % Only two solution on a 4x4 board... % about 5 - 10 is advised for N. qu(N) :- X is cputime, qu_nloop(N), Now is cputime, compens_loop(N), M is cputime, Li is 684 * N, print_times(X,Now,M,Li). qu_nloop(0). qu_nloop(X) :- not(qu_top), Y is X - 1, qu_nloop(Y). qu_top :- run(4,X), fail. size(4). snint(1). snint(2). snint(3). snint(4). run(Size, Soln) :- get_solutions(Size, Soln), inform(Soln). get_solutions(Board_size, Soln) :- solve(Board_size, [], Soln). % newsquare generates legal positions for next queen newsquare([], square(1, X)) :- snint(X). newsquare([square(I, J) | Rest], square(X, Y)) :- X is I + 1, snint(Y), not(threatened(I, J, X, Y)), safe(X, Y, Rest). % safe checks whether square(X, Y) is threatened by any % existing queens safe(X, Y, []). safe(X, Y, [square(I, J) | L]) :- not(threatened(I, J, X, Y)), safe(X, Y, L). % threatened checks whether squares (I, J) and (X, Y) % threaten each other threatened(I, J, X, Y) :- (I = X), !. threatened(I, J, X, Y) :- (J = Y), !. threatened(I, J, X, Y) :- (U is I - J), (V is X - Y), (U = V), !. threatened(I, J, X, Y) :- (U is I + J), (V is X + Y), (U = V), !. % solve accumulates the positions of occupied squares solve(Bs, [square(Bs, Y) | L], [square(Bs, Y) | L]) :- size(Bs). solve(Board_size, Initial, Final) :- newsquare(Initial, Next), solve(Board_size, [Next | Initial], Final). inform([]) :- nl. inform([M | L]) :- write(M), nl, inform(L). %------------------------------------ % Query does simple database queries. % query(N) :- X is cputime, que_nloop(N), Now is cputime, compens_loop(N), M is cputime, Li is 2294 * N, print_times(X,Now,M,Li). que_nloop(0). que_nloop(X) :- not(que_top), Y is X - 1, que_nloop(Y). que_top:- que(X), write(X),nl, fail. que([C1,D1,C2,D2]) :- density(C1,D1), density(C2,D2), D1>D2, 20*D1<21*D2. density(C,D) :- pop(C,P), area(C,A), D is (P*100)/A. pop(china,8250). pop(india,5863). pop(ussr,2521). pop(usa,2119). pop(indonesia,1276). pop(japan,1097). pop(brazil,1042). pop(bangladesh,750). pop(pakistan,682). pop(w_germany,620). pop(nigeria,613). pop(mexico,581). pop(uk,559). pop(italy,554). pop(france,525). pop(philippines,415). pop(thailand,410). pop(turkey,383). pop(egypt,364). pop(spain,352). pop(poland,337). pop(s_korea,335). pop(iran,320). pop(ethiopia,272). pop(argentina,251). area(china,3380). area(india,1139). area(ussr,8708). area(usa,3609). area(indonesia,570). area(japan,148). area(brazil,3288). area(bangladesh,55). area(pakistan,311). area(w_germany,96). area(nigeria,373). area(mexico,764). area(uk,86). area(italy,116). area(france,213). area(philippines,90). area(thailand,200). area(turkey,296). area(egypt,386). area(spain,190). area(poland,121). area(s_korea,37). area(iran,628). area(ethiopia,350). area(argentina,1080). %--------------------------------------------------*/ 3. Real Prolog programs. This section is empty for now. We would like to have your advice and/or your programs, with comments on how significant they are to be considered candidates for benchmarking, and figures on how long they take, which kinds of queries are advisable, etc... . Thank you for your collaboration.