Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxn!ihnp4!qantel!lll-lcc!lll-crg!seismo!mcvax!unido!ecrcvax!jclaude From: jclaude@ecrcvax.UUCP (Jean Claude Syre) Newsgroups: net.lang.prolog Subject: Benchmarking Prolog Systems (Version1, part2) Message-ID: <227@ecrcvax.UUCP> Date: Mon, 28-Apr-86 16:21:17 EDT Article-I.D.: ecrcvax.227 Posted: Mon Apr 28 16:21:17 1986 Date-Received: Fri, 2-May-86 09:50:55 EDT Organization: ECRC, D-8000 Muenchen 81, W. Germany Lines: 576 A Proposal for *********************************************** *** BENCHMARK PROGRAMS FOR PROLOG SYSTEMS *** *********************************************** Part 2 (of 3) 1.3. Program to test the handling of environments (envir). The creation of environments is an important feature in prolog machines. The following program attempts to evaluate that. A usual condition to have environments is that the clause is made of several goals. Thus there will be calls in the clause creating environments, and some work to set the parameters of each call. Three arguments per goal were chosen because this number comes close to the average number of arguments of a predicate and to the average number of permanent variables in an environment. The arguments were arranged in different orders for every goal, because we did not want to measure the merits of register transfer optimisations. -----------------cut here - beginning of program listing-------------------- /* creates 79 environments and 158 calls */ /* suggested value for N: 1000 (interp), 1000 (comp) */ /* results for Cprolog: N=1000 */ /* Tloop=38.6 Tcomp=0.97 Tnet=37.6 Klips=4.23 */ envir(N):-T1 is cputime, cre_env(N), T2 is cputime, compens_loop(N), T3 is cputime, print_times(T1,T2,T3,N,159). cre_env(0). cre_env(N):-M is N-1, env0(X,Y,Z), cre_env(M). compens_loop(0). compens_loop(N):-M is N-1,compens_loop(M). env0(X,Y,Z):-env1(Z,X,Y),env2(Y,Z,X). /* creates 79 environments */ env1(X,Y,Z):-env3(Z,Y,X),env4(Y,Z,X). env2(X,Y,Z):-env3(Z,Y,X),env4(Y,Z,X). /* and 158 calls */ env3(X,Y,Z):-env5(Z,Y,X),env6(Y,Z,X). env4(X,Y,Z):-env5(Z,Y,X),env6(Y,Z,X). env5(X,Y,Z):-env7(Z,Y,X),env8(Y,Z,X). env6(X,Y,Z):-env7(Z,Y,X),env8(Y,Z,X). env7(X,Y,Z):-env9(Z,Y,X),env10(Y,Z,X). env8(X,Y,Z):-env9(Z,Y,X),env10(Y,Z,X). env9(X,Y,Z):-env11(Z,Y,X),env12(Y,Z,X). env10(X,Y,Z):-env12(Z,Y,X),env12(Y,Z,X). env11(X,Y,Z):-env12(Z,Y,X),env12(Y,Z,X). env12(X,Y,Z). print_times(T1,T2,T3,X,I) :- /* prints the results */ TT1 is T2 - T1, TT2 is T3 - T2, TT is TT1 - TT2, write('T overall loop: '),write(TT1), nl, write('T compens loop: '),write(TT2), nl, write('T net: '),write(TT),nl, write('KLips: '), Li is I * X, Lips is Li / TT, KLips is Lips / 1000, write(KLips),nl,nl. ----------------------------cut here - end of program listing---------------- 1.4. Program to test indexing mechanisms. We give only one test for indexing, i.e. the selection of a clause due to the type of an argument. This program does not test the merits of indexing on an argument other than the first one. It does not test for multiple indexing either. It does not show the inefficiency which occurs if 2 choice points per clause are created. This may happen e.g. in Warren's indexing scheme. Each of these tests would require an extra benchmark program. The program given below tests the main point in indexing. Right now we think it is not worth adding all this complexity to the benchmarks, in order to measure all the details in indexing. Therefore we give only this single test. -----------------------cut here - beginning of program listing--------------- /* This program is called with "index(N)" */ /* It tests the efficiency of simple indexing on the first argument */ /* suggested value for N: 500 (interp), 2000(comp) */ /* results for Cprolog: N=500 */ /* Tloop=8.98 Tcomp=0.52 Tnet=8.47 Klips=1.24 */ index(N) :- T1 is cputime, index_loop(N), T2 is cputime, compens_loop(N), T3 is cputime, print_times(T1,T2,T3,N,21). /* loop with calls to the actual benchmark program for indexing */ index_loop(0). index_loop(X) :- p(a), p([a]), p(s(a)), /* queries to the actual */ p(b), p([b]), p(s(b)), /* benchmark program */ p(c), p([c]), p(s(c)), p(d), p([d]), p(s(d)), p(e), p([e]), p(s(e)), p(f), p([f]), p(s(g)), p(g), p([g]), p(s(g)), Y is X - 1, index_loop(Y). /* compensation loop */ compens_loop(0). compens_loop(X) :- Y is X - 1, compens_loop(Y). /* test program which can be optimised by indexing */ p(a). p([a]). p(s(a)). p(b). p([b]). p(s(b)). p(c). p([c]). p(s(c)). p(d). p([d]). p(s(d)). p(e). p([e]). p(s(e)). p(f). p([f]). p(s(f)). p(g). p([g]). p(s(g)). print_times(T1,T2,T3,X,I) :- /* prints the results */ TT1 is T2 - T1, TT2 is T3 - T2, TT is TT1 - TT2, write('T first loop: '),write(TT1), nl, write('T compens loop: '),write(TT2), nl, write('T net: '),write(TT),nl, write('KLips: '), Li is I * X, Lips is Li / TT, KLips is Lips / 1000, write(KLips),nl,nl. -------------------cut here - end of program listing------------------------- 1.5. Programs to test unification. We have 6 programs to evaluate the process of unification in the Prolog system. As usual, we will use the "compens_loop" predicate as a compensation for the extra work done for looping a little, and the "print_times" predicate to print results. --------------------cut here - beginning of program listing----------------- /* The predicates are called with: */ /* benchmark_name(X). */ /* where benchmark_name is the name of the predicate */ /* and X is the number of (external) loop iterations */ /* The benchmarks on this file are: construct_list */ /* match_list */ /* construct_structure */ /* match_structure */ /* match_nested_structure */ /* general_unification */ /* Test of list construction via unification */ /* suggested value for N: 100 (interp), 500(comp) */ /* results for Cprolog: N=100 */ /* Tloop=1.77 Tcomp=0.1 Tnet=1.67 Klips=6.0 */ construct_list(X) /* uses unification to */ :- T1 is cputime, /* construct a list of 100 elts */ do_construct_list(X), T2 is cputime, compens_loop(X), T3 is cputime, print_times(T1,T2,T3,X,100). /* Test of list matching unification */ /* suggested value for N: 100 (interp), 1000(comp) */ /* results for Cprolog: N=100 */ /* Tloop=2.47 Tcomp=0.1 Tnet=2.39 Klips=4.2 */ match_list(X) :- list100(Z), /* construction of the matching list is done */ T1 is cputime, /* outside of the loop, in order not to count */ do_match_list(X,Z), /* the construction of the list */ T2 is cputime, compens_loop(X), T3 is cputime, print_times(T1,T2,T3,X,100). /* Test of structure construction via unification */ /* this program is equivalent to construct_list, except that it uses */ /* the standard structure representation instead of the simplified */ /* list notation */ /* suggested value for N: 100 (interp), 500(comp) */ /* results for Cprolog: N=100 */ /* Tloop=1.75 Tcomp=0.08 Tnet=1.67 Klips=6 */ construct_structure(X) :- T1 is cputime, do_construct_structure(X), T2 is cputime, compens_loop(X), T3 is cputime, print_times(T1,T2,T3,X,100). /* Test of structure matching via unification */ /* this predicate matches a list of 100 elements in structure notation */ /* suggested value for N: 100 (interp), 100(comp) */ /* results for Cprolog: N=100 */ /* Tloop=2.42 Tcomp=0.08 Tnet=2.34 Klips=4.3 */ match_structure(X) :- structure100(Z), T1 is cputime, do_match_structure(X,Z), T2 is cputime, compens_loop(X), T3 is cputime, print_times(T1,T2,T3,X,100). /* Test to match a nested structure */ /* this predicate tests the (compiled) unification of a complex structure */ /* suggested value for N: 200 (interp), 200(comp) */ /* results for Cprolog: N=200 */ /* Tloop=1.34 Tcomp=0.17 Tnet=1.18 Klips=0.17 */ match_nested_structure(X) :- nested_structure1(Z), /* the structure to match is constructed */ /* outside the loop, in order to measure */ /* only the matching time */ T1 is cputime, do_match_nested_structure(X,Z), T2 is cputime, compens_loop(X), T3 is cputime, print_times(T1,T2,T3,X,1). /* Test of general unification of 2 complex structures */ /* this predicate tests general unification, i.e. unification which */ /* cannot be compiled */ /* suggested value for N: 200 (interp), 500(comp) */ /* results for Cprolog: N=200 */ /* Tloop=1.38 Tcomp=0.18 Tnet=1.20 Klips=0.17 */ general_unification(X) :- nested_structure1(A), nested_structure2(B), T1 is cputime, do_general_unification(X,A,B), T2 is cputime, compens_loop(X), T3 is cputime, print_times(T1,T2,T3,X,1). /* predicate to print the results of the benchmarking */ print_times(T1,T2,T3,X,I) :- TT1 is T2 - T1, TT2 is T3 - T2, TT is TT1 - TT2, write('T overall loop: '),write(TT1), nl, write('T compens loop: '),write(TT2), nl, write('T benchmark: '),write(TT),nl, write('KLips: '), Li is I * X, Lips is Li / TT, KLips is Lips / 1000, write(KLips),nl,nl. /* compensation loop, used to measure the time spent in the loop */ compens_loop(0). compens_loop(X) :- Y is X - 1, compens_loop(Y). /* list constructing loop */ do_construct_list(0). do_construct_list(X) :- cl1(Z), Y is X - 1, do_construct_list(Y). /* list matching loop */ do_match_list(0,Z). do_match_list(X,Z) :- cl1(Z), Y is X - 1, do_match_list(Y,Z). /* structure constructing loop */ do_construct_structure(0). do_construct_structure(X) :- cs1(Z), Y is X - 1, do_construct_structure(Y). /* structure matching loop */ do_match_structure(0,Z). do_match_structure(X,Z) :- cs1(Z), Y is X - 1, do_match_structure(Y,Z). /* loop to match a nested structure */ do_match_nested_structure(0,Z). do_match_nested_structure(X,Z) :- nested_structure2(Z), Y is X - 1, do_match_nested_structure(Y,Z). /* loop for general unification */ do_general_unification(0,A,B). do_general_unification(X,A,B) :- unify(A,B), Y is X - 1, do_general_unification(Y,A,B). /* general unification */ unify(X,X). /* complex structure as example for unification tests */ /* the same structure is given twice, in order to make sure that */ /* even implementations using structure sharing execute the unification */ /* and do not just pass pointers */ nested_structure1( [a( [a1([1,2,3],a),a2([4,5,6],b),a3([7,8,9],c)], [a4([0,1,2],d),a5([3,4,5],e),a6([6,7,8],f)], [a7([9,0,1],g),a8([2,3,4],h),a9([5,6,7],i)]), b( [b1([1,2,3],a),b2([4,5,6],b),b3([7,8,9],c)], [b4([0,1,2],d),b5([3,4,5],e),b6([6,7,8],f)], [b7([9,0,1],g),b8([2,3,4],h),b9([5,6,7],i)]), c( [c1([1,2,3],a),c2([4,5,6],b),c3([7,8,9],c)], [c4([0,1,2],d),c5([3,4,5],e),c6([6,7,8],f)], [c7([9,0,1],g),c8([2,3,4],h),c9([5,6,7],i)])]). nested_structure2( [a( [a1([1,2,3],a),a2([4,5,6],b),a3([7,8,9],c)], [a4([0,1,2],d),a5([3,4,5],e),a6([6,7,8],f)], [a7([9,0,1],g),a8([2,3,4],h),a9([5,6,7],i)]), b( [b1([1,2,3],a),b2([4,5,6],b),b3([7,8,9],c)], [b4([0,1,2],d),b5([3,4,5],e),b6([6,7,8],f)], [b7([9,0,1],g),b8([2,3,4],h),b9([5,6,7],i)]), c( [c1([1,2,3],a),c2([4,5,6],b),c3([7,8,9],c)], [c4([0,1,2],d),c5([3,4,5],e),c6([6,7,8],f)], [c7([9,0,1],g),c8([2,3,4],h),c9([5,6,7],i)])]). /* list of 100 elements used for match_list */ list100([a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a, a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a, a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a]). /* structure of 100 elements used for match_structure */ structure100(st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a, st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a, st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a, st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a, st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a, st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a, st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a, st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a, st(a,st(a,st(a,st(a,nil) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))). /* predicates to test unification of lists */ cl1([a|X]) :- cl2(X). cl2([a|X]) :- cl3(X). cl3([a|X]) :- cl4(X). cl4([a|X]) :- cl5(X). cl5([a|X]) :- cl6(X). cl6([a|X]) :- cl7(X). cl7([a|X]) :- cl8(X). cl8([a|X]) :- cl9(X). cl9([a|X]) :- cl10(X). cl10([a|X]) :- cl11(X). cl11([a|X]) :- cl12(X). cl12([a|X]) :- cl13(X). cl13([a|X]) :- cl14(X). cl14([a|X]) :- cl15(X). cl15([a|X]) :- cl16(X). cl16([a|X]) :- cl17(X). cl17([a|X]) :- cl18(X). cl18([a|X]) :- cl19(X). cl19([a|X]) :- cl20(X). cl20([a|X]) :- cl21(X). cl21([a|X]) :- cl22(X). cl22([a|X]) :- cl23(X). cl23([a|X]) :- cl24(X). cl24([a|X]) :- cl25(X). cl25([a|X]) :- cl26(X). cl26([a|X]) :- cl27(X). cl27([a|X]) :- cl28(X). cl28([a|X]) :- cl29(X). cl29([a|X]) :- cl30(X). cl30([a|X]) :- cl31(X). cl31([a|X]) :- cl32(X). cl32([a|X]) :- cl33(X). cl33([a|X]) :- cl34(X). cl34([a|X]) :- cl35(X). cl35([a|X]) :- cl36(X). cl36([a|X]) :- cl37(X). cl37([a|X]) :- cl38(X). cl38([a|X]) :- cl39(X). cl39([a|X]) :- cl40(X). cl40([a|X]) :- cl41(X). cl41([a|X]) :- cl42(X). cl42([a|X]) :- cl43(X). cl43([a|X]) :- cl44(X). cl44([a|X]) :- cl45(X). cl45([a|X]) :- cl46(X). cl46([a|X]) :- cl47(X). cl47([a|X]) :- cl48(X). cl48([a|X]) :- cl49(X). cl49([a|X]) :- cl50(X). cl50([a|X]) :- cl51(X). cl51([a|X]) :- cl52(X). cl52([a|X]) :- cl53(X). cl53([a|X]) :- cl54(X). cl54([a|X]) :- cl55(X). cl55([a|X]) :- cl56(X). cl56([a|X]) :- cl57(X). cl57([a|X]) :- cl58(X). cl58([a|X]) :- cl59(X). cl59([a|X]) :- cl60(X). cl60([a|X]) :- cl61(X). cl61([a|X]) :- cl62(X). cl62([a|X]) :- cl63(X). cl63([a|X]) :- cl64(X). cl64([a|X]) :- cl65(X). cl65([a|X]) :- cl66(X). cl66([a|X]) :- cl67(X). cl67([a|X]) :- cl68(X). cl68([a|X]) :- cl69(X). cl69([a|X]) :- cl70(X). cl70([a|X]) :- cl71(X). cl71([a|X]) :- cl72(X). cl72([a|X]) :- cl73(X). cl73([a|X]) :- cl74(X). cl74([a|X]) :- cl75(X). cl75([a|X]) :- cl76(X). cl76([a|X]) :- cl77(X). cl77([a|X]) :- cl78(X). cl78([a|X]) :- cl79(X). cl79([a|X]) :- cl80(X). cl80([a|X]) :- cl81(X). cl81([a|X]) :- cl82(X). cl82([a|X]) :- cl83(X). cl83([a|X]) :- cl84(X). cl84([a|X]) :- cl85(X). cl85([a|X]) :- cl86(X). cl86([a|X]) :- cl87(X). cl87([a|X]) :- cl88(X). cl88([a|X]) :- cl89(X). cl89([a|X]) :- cl90(X). cl90([a|X]) :- cl91(X). cl91([a|X]) :- cl92(X). cl92([a|X]) :- cl93(X). cl93([a|X]) :- cl94(X). cl94([a|X]) :- cl95(X). cl95([a|X]) :- cl96(X). cl96([a|X]) :- cl97(X). cl97([a|X]) :- cl98(X). cl98([a|X]) :- cl99(X). cl99([a|X]) :- cl100(X). cl100([a]). /* predicates to test unification of structures */ cs1(st(a,X)) :- cs2(X). cs2(st(a,X)) :- cs3(X). cs3(st(a,X)) :- cs4(X). cs4(st(a,X)) :- cs5(X). cs5(st(a,X)) :- cs6(X). cs6(st(a,X)) :- cs7(X). cs7(st(a,X)) :- cs8(X). cs8(st(a,X)) :- cs9(X). cs9(st(a,X)) :- cs10(X). cs10(st(a,X)) :- cs11(X). cs11(st(a,X)) :- cs12(X). cs12(st(a,X)) :- cs13(X). cs13(st(a,X)) :- cs14(X). cs14(st(a,X)) :- cs15(X). cs15(st(a,X)) :- cs16(X). cs16(st(a,X)) :- cs17(X). cs17(st(a,X)) :- cs18(X). cs18(st(a,X)) :- cs19(X). cs19(st(a,X)) :- cs20(X). cs20(st(a,X)) :- cs21(X). cs21(st(a,X)) :- cs22(X). cs22(st(a,X)) :- cs23(X). cs23(st(a,X)) :- cs24(X). cs24(st(a,X)) :- cs25(X). cs25(st(a,X)) :- cs26(X). cs26(st(a,X)) :- cs27(X). cs27(st(a,X)) :- cs28(X). cs28(st(a,X)) :- cs29(X). cs29(st(a,X)) :- cs30(X). cs30(st(a,X)) :- cs31(X). cs31(st(a,X)) :- cs32(X). cs32(st(a,X)) :- cs33(X). cs33(st(a,X)) :- cs34(X). cs34(st(a,X)) :- cs35(X). cs35(st(a,X)) :- cs36(X). cs36(st(a,X)) :- cs37(X). cs37(st(a,X)) :- cs38(X). cs38(st(a,X)) :- cs39(X). cs39(st(a,X)) :- cs40(X). cs40(st(a,X)) :- cs41(X). cs41(st(a,X)) :- cs42(X). cs42(st(a,X)) :- cs43(X). cs43(st(a,X)) :- cs44(X). cs44(st(a,X)) :- cs45(X). cs45(st(a,X)) :- cs46(X). cs46(st(a,X)) :- cs47(X). cs47(st(a,X)) :- cs48(X). cs48(st(a,X)) :- cs49(X). cs49(st(a,X)) :- cs50(X). cs50(st(a,X)) :- cs51(X). cs51(st(a,X)) :- cs52(X). cs52(st(a,X)) :- cs53(X). cs53(st(a,X)) :- cs54(X). cs54(st(a,X)) :- cs55(X). cs55(st(a,X)) :- cs56(X). cs56(st(a,X)) :- cs57(X). cs57(st(a,X)) :- cs58(X). cs58(st(a,X)) :- cs59(X). cs59(st(a,X)) :- cs60(X). cs60(st(a,X)) :- cs61(X). cs61(st(a,X)) :- cs62(X). cs62(st(a,X)) :- cs63(X). cs63(st(a,X)) :- cs64(X). cs64(st(a,X)) :- cs65(X). cs65(st(a,X)) :- cs66(X). cs66(st(a,X)) :- cs67(X). cs67(st(a,X)) :- cs68(X). cs68(st(a,X)) :- cs69(X). cs69(st(a,X)) :- cs70(X). cs70(st(a,X)) :- cs71(X). cs71(st(a,X)) :- cs72(X). cs72(st(a,X)) :- cs73(X). cs73(st(a,X)) :- cs74(X). cs74(st(a,X)) :- cs75(X). cs75(st(a,X)) :- cs76(X). cs76(st(a,X)) :- cs77(X). cs77(st(a,X)) :- cs78(X). cs78(st(a,X)) :- cs79(X). cs79(st(a,X)) :- cs80(X). cs80(st(a,X)) :- cs81(X). cs81(st(a,X)) :- cs82(X). cs82(st(a,X)) :- cs83(X). cs83(st(a,X)) :- cs84(X). cs84(st(a,X)) :- cs85(X). cs85(st(a,X)) :- cs86(X). cs86(st(a,X)) :- cs87(X). cs87(st(a,X)) :- cs88(X). cs88(st(a,X)) :- cs89(X). cs89(st(a,X)) :- cs90(X). cs90(st(a,X)) :- cs91(X). cs91(st(a,X)) :- cs92(X). cs92(st(a,X)) :- cs93(X). cs93(st(a,X)) :- cs94(X). cs94(st(a,X)) :- cs95(X). cs95(st(a,X)) :- cs96(X). cs96(st(a,X)) :- cs97(X). cs97(st(a,X)) :- cs98(X). cs98(st(a,X)) :- cs99(X). cs99(st(a,X)) :- cs100(X). cs100(st(a,nil)).