Analytic benchmarks

Testing Calls

This is the one you always dreamed to test! Like all benchmarks, it uses a loop calling the actual benchmark program. The benchmark program consists of a sequence of 200 predicates having no arguments, no choice points, NOTHING. 200 is chosen to have sufficient accuracy in measuring the execution time.

The results show the effect of pure calls, and the Klips performance can be called the peak performance of the prolog system. Note that the peak performance has very little significance to classify the overall performance of a Prolog system.

Testing non-deterministic behavior

This program contains a series of 3 different benchmark predicates.

The predicate choice_point/1 tests calls invoking the creation of a choice point, i.e. a branch point where the execution will possibly come back to in case of backtracking. It does NOT backtrack. Two versions are proposed, one with and the other without arguments.

We then present two predicates to evaluate the mechanism of backtracking during execution. Both predicates create one choice_point and then backtrack 20 times on every loop iteration step. baktrak1/1 exhibits a kind of backtracking called deep, while baktrak2/1 deals with shallow backtracking. Both are worth being tried, whatever your particular Prolog System is.

Testing environment handling

The creation and deletion of environments are 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. Note that these transfers exist, so the results cannot be compared with those given by the program which creates choice points (generally slower).

Another version, envir0ar/1, with 0 argument in each call, can also be usefully tried

Testing 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.

Testing unification

We have 6 programs to evaluate the process of unification in the Prolog system:

• Test of list construction via unification.

• Test of list matching unification.

• 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.

• Test of structure matching via unification. This predicate matches a list of 100 elements in structure notation.

• Test to match a nested structure. This predicate tests the (compiled) unification of a complex structure.

• Test of general unification of 2 complex structures. This predicate tests general unification. We call it general unification, because it cannot be analysed at compile time. Therefore this kind of unification cannot be compiled and, even in a compiled system, it must be handled at run time, exactly as by an interpreter. This is done by a general procedure for unification. The name of the benchmark therefore does not reflect that the unification is general, i.e. including all Prolog types (e.g. it does not contain variables), but it reflects the use of the procedure for general unification as opposed to specific, compiled unification.

Manuel Carro: note that in this case the term "Logical Inference" is a bit contrived, since by design some of these (head) unifications are very more compled, naturally being slower and giving slow KLIPS results.

Testing dereferencing

Program to benchmark the dereferencing speed. It constructs a list containing 500 variables which are then bound together. Since different systems use different strategies for binding variables on the global stack, the whole is made for two lists and the long variable chain is created only in one of them.

Manuel Carro: different results in this benchmark are not likely to affect larger, general programs. It is a well-known fact that n programs tend not to generate long dereferencing chains. Empirical measurements show that dereference chains of length greater than three are extremely rare. So a suboptimal / optimal behavior in this test is not likely to affect greatly the overall speed of a system.

Testing the cut

It seems almost impossible to isolate the cut operator in a simple test program. However, the cut-testing program in this benchmark set contains a lot of cut at exec time. It may be regarded as a partial test of cut, and may be worthwhile for some software implementations of Prolog. cuttest/1 calls the cutit11 predicate, which performs 100 calls to a predicate cutt1 where a cut operator appears in the second clause. Having indexing makes the evaluation of the cut more accurate, so please indicate in our result whether or not your Prolog system uses indexing, to clarify the comparison with others.

Assorted small programs

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, Micha Meier and Pascal Van Hentenryck.

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.

Also, some more programs have been added since the last release and some corrections have been made. Most of the writes were removed in order to reduce i/o activity.

The programs added were symbolic differentiation (from Warren's paper) and a quick sort algorithm using difference lists. The last addition is a bit of a rogue: its a naive reverse, where one can enter the list length. The list gets constructed and then gets reversed.

We are grateful to Saumya Debray from Stony Brook and others for comments, suggestions, feedback and useful inputs.

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 584 lines.

Name      |      Call by      |  # of Inferences  | KLips
          |                   |  (one iteration)  | (C-Prolog)
----------+-------------------+-------------------+-----------
fib       | fibonacci(1).     |        4932       |   2.0
----------+-------------------+-------------------+-----------
map       | map(200).         |          68       |   1.3
----------+-------------------+-------------------+-----------
mham      | mham(1).          |      493824       |   1.7
----------+-------------------+-------------------+-----------
mutest    | mutest(1).        |        1366       |   2.3
----------+-------------------+-------------------+-----------
quicksort | qs(10).           |         601       |   1.9
----------+-------------------+-------------------+-----------
queens    | qu(10).           |         684       |   1.7
----------+-------------------+-------------------+-----------
query     | query(1).         |        2294       |   0.9
----------+-------------------+-------------------+-----------
sym_diff  | differen(150).    |          71       |   1.5
----------+-------------------+-------------------+-----------
diff_lists| diff(50).         |         608       |   2.1
----------+-------------------+-------------------+-----------
nrev  10  | nrev.             |          66       |   2.0
----------+-------------------+-------------------+-----------
nrev  30  | nrev.             |         496       |   2.5
----------+-------------------+-------------------+-----------
nrev  50  | nrev.             |        1326       |   2.5
----------+-------------------+-------------------+-----------
nrev 100  | nrev.             |        5151       |   2.5
----------+-------------------+-------------------+-----------
nrev 150  | nrev.             |       11476       |   2.5
----------+-------------------+-------------------+-----------
nrev 200  | nrev.             |       20301       |   2.5
----------+-------------------+-------------------+-----------

Usage and interface

Documentation on exports

benchmark_usage('--estimation').
benchmark_usage('--no-machine').
benchmark_usage('--no-human').
benchmark_usage('--send-info').
benchmark_usage('--base-file-name').

Known bugs and planned improvements

• The actual logical inferences each benchmark does has to be checked.