/* BENCH.PL : The classic Prolog benchmark

        Supplied by Quintus Computer Systems, Inc.
        April 30th 1984
*/

/* ======================================================================
   This benchmark gives the raw speed of a Prolog system.

   The measure of logical inferences per second (Lips) used here is taken to
   be procedure calls per second over an example with not very complex
   procedure calls. The example used is that of "naive reversing" a list,
   which is an expensive, and therefore stupid, way of reversing a list.  It
   does, however, produce a lot of procedure calls. (In theoretical terms,
   this algorithm is O(n^2) on the length of the list).

   The use of a single simple benchmark like this cannot, of course, be
   taken to signify a great deal. However, experience has shown that this
   benchmark does provide a very good measure of basic Prolog speed and
   produces figures which match more complex benchmarks. The reason for
   this is that the basic operations performed here: procedure calls with a
   certain amount of data structure access and construction; are absolutely
   fundamental to Prolog execution. If these are done right, then more
   complex benchmarks tend to scale accordingly. This particular benchmark
   has thus been used as a good rule of thumb by Prolog implementors for
   over a decade and forms a part of the unwritten Prolog folklore. So -
   use this benchmark, with this in mind, as a quick, but extremely useful,
   test of Prolog performance.

   In a complete evaluation of a Prolog system you should also be taking
   account speeds of asserting and compiling, tail recursion, memory
   utilisation, compactness of programs, storage management and garbage
   collection, debugging and editing facilities, program checking and help
   facilities, system provided predicates, interfaces to external
   capabilities, documentation and support, amongst other factors.

   ====================================================================== */


/* ----------------------------------------------------------------------
        get_cpu_time(T) -- T is the current cpu time.

        ** This bit will probably require changes to work on your Prolog
           system, since different systems provide this facility in
           different ways. See your Prolog manual for details.
        ** Also check the code for calculate_lips/4 below.
   ---------------------------------------------------------------------- */


get_cpu_time(T) :- statistics(runtime,[T,_]). /* Quintus Prolog version */

/*  get_cpu_time(T) :- T is cputime.     C-Prolog version       */


/* ----------------------------------------------------------------------
        nrev(L1,L2)      -- L2 is the list L1 reversed.
        append(L1,L2,L3) -- L1 appended to L2 is L3.
        data(L)          -- L is a thirty element list.

        This is the program executed by the benchmark.
        It is called "naive reverse" because it is a very expensive way
        of reversing a list. Its advantage, for our purposes, is that
        it generates a lot of procedure calls. To reverse a thirty element
        list requires 496 Prolog procedure calls.
   ---------------------------------------------------------------------- */

nrev([],[]).
nrev([X|Rest],Ans) :- nrev(Rest,L), append(L,[X],Ans).

append([],L,L).
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).


data([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,
                           21,22,23,24,25,26,27,28,29,30]).


/* ----------------------------------------------------------------------
        lots -- Run benchmark with a variety of iteration counts.

        Call this to run the benchmark with increasing numbers
        of iterations. The figures produced should be about the same -
        except that there may be inaccuracies at low iteration numbers
        if the time these examples take to execute on your machine are
        too small to be very precise (because of the accuracy the
        operating system itself is capable of providing).
        If the time taken for these examples is too long or short then
        you should adjust the eg_count(_) facts.
   ---------------------------------------------------------------------- */

lots :-
        eg_count(Count),
        bench(Count),
        fail.
lots.

eg_count(10).
eg_count(20).
eg_count(50).
eg_count(100).
eg_count(200).
eg_count(500).
eg_count(1000).
eg_count(2000).
eg_count(5000).
eg_count(10000).


/* ----------------------------------------------------------------------
        bench(Count) -- Run the benchmark for Count iterations.

        bench provides a test harness for running the naive reverse
        benchmark. It is important to factor out the overhead of setting
        the test up and using repeat(_) to iterate the right number of
        times. This is done by running some dummy code as well to see how
        much time the extra operations take.
   ---------------------------------------------------------------------- */

bench(Count) :-
        get_cpu_time(T0),
        dodummy(Count),
        get_cpu_time(T1),
        dobench(Count),
        get_cpu_time(T2),
        report(Count,T0,T1,T2).


/* ----------------------------------------------------------------------
        dobench(Count) -- nrev a 30 element list Count times.
        dodummy(Count) -- Perform the overhead operations Count times.
        repeat(Count)  -- Predicate which succeeds Count times

        This is the supporting code, which is reasonably clear.
   ---------------------------------------------------------------------- */

dobench(Count) :-
        data(List),
        repeat(Count),
        nrev(List,_),
        fail.
dobench(_).


dodummy(Count) :-
        data(List),
        repeat(Count),
        dummy(List,_),
        fail.
dodummy(_).

dummy(_,_).

repeat(_N).
repeat(N) :- N >1, N1 is N-1, repeat(N1).


/* ----------------------------------------------------------------------
        report(Count,T0,T1,T2) -- Report the results of the benchmark.
        calculate_lips(Count,Time,Lips,Units) --
                Doing Count interations in Time implies Lips lips assuming
                that time is given in Units.

        This calculates the logical inferences per second (lips) figure.
        Remember that it takes 496 procedure calls to naive reverse a
        thirty element list once. Lips, under this benchmark, thus means
        "Prolog procedure calls per second, where the procedure calls
        are not too complex (i.e. those for nrev and append)".

        ** This version of the code assumes that the times (T0.. etc)
           are integers giving the time in milliseconds. This is true for
           Quintus Prolog.  Your Prolog system may use some other
           representation.  If so, you will need to adjust the Lips
           calculation.  There is a C-Prolog version below for the case
           where times are floating point numbers giving the time in
           seconds.
   ---------------------------------------------------------------------- */

report(Count,T0,T1,T2) :-
        Time1 is T1-T0,
        Time2 is T2-T1,
        Time  is Time2-Time1,           /* Time spent on nreving lists */
        calculate_lips(Count,Time,Lips,Units),
        nl,
        write(Lips), write(' lips for '), write(Count),
        write(' iterations taking '), write(Time),
        write(' '), write(Units), write(' ('),
        write(Time2-Time1), write(')'),
        nl.



calculate_lips(_Count,Time,Lips,'msecs') :-     /* Time can be 0 for small */
        Time is 0, !, Lips is 0.                /* values of Count!        */
calculate_lips(Count,Time,Lips,'msecs') :-
        Lips  is (496*float(Count)*1000)/Time.

/* --- C-Prolog version

calculate_lips(Count,Time,Lips,'secs') :- Lips  is (496*Count)/Time.

   --- */