🚀 go-pugleaf

Some people argue that Prolog is too slow, others claim  that  it  is
fast enough, yet others that it is even faster than languages like C,
for particular problems. I would like to contribute to  this  discus-
sion  from another point of view. I can say, and so can everybody who
has seriously tried to implement an efficient Prolog  compiler,  that
Prolog  could  be  made much faster than it is now, because there are
numerous redundant operations being performed all the time. Trying to
optimize them all away requires generating a lot of code to catch all
various possibilities and generate optimal code  for  each  of  them.
With  the  use of abstract interpretation it might be possible to ob-
tain enough information to generate both good and short code, but the
current  abstract interpretation techniques are not yet mature enough
to be available in commercial systems.

Consequently, people are trying to locate what are the bottlenecks of
Prolog execution and modify the compiler and the engine to get rid of
them. This, however, may only make the whole story more  complicated,
because  often  the criteria that decide what are the bottlenecks are
rather questionable. There have been many papers published which  say
something like "on the set of benchmarks B the feature F showed to be
very important and therefore we present a WAM modification that  han-
dles  the  feature F very efficiently".  In almost all cases the men-
tioned benchmark suite includes only very short programs,  which  can
in  no  way  be representative for current real-life Prolog programs.
*Current* is important here because in some  years  from  now,  these
programs  may become more representative because the way of executing
them may change, the current bottlenecks disappear, and the feature F
really  becomes significant. But until then, small benchmark programs
cannot be trusted! I have an interesting example with several  suites
of benchmark programs which were used to test the ECRC Sepia system.

The first one consists of the benchmark programs set up by  the  Com-
puter  Architecture  group at ECRC several years ago, and it tries to
test single Prolog actions, like creating a choice point, an environ-
ment,  dereferencing,  unification, etc.  The Pereira benchmarks used
for the same purpose are not well suited because they  often  measure
something different than they say.

The second benchmark set was also set up by  the  Computer  Architec-
ture, it includes small, but well known benchmark programs like naive
reverse, map colouring, sieve, quicksort, queens etc.

The third benchmark suite consists of large programs.
I have selected them using the following criteria:
        - The program must run long enough to be safely measurable
        - The program must contain a sufficient number of different
          procedure calls. 100 is sufficient.
        - The program has to make at least 100000 procedure calls
          and these calls must not be concentrated into one or
          two procedures only.
(SEPIA contains a profiler that shows the number of ports passed
for each procedure.)
These programs were taken from the L.A. benchmarking workshop,
some were written at ECRC and yet others come from various sources.

With these three benchmarks suites (I have also others, but they  are
rather  biased) one gets a reasonable feeling for the speed of a Pro-
log system. Now what is interesting is that I have run  these  bench-
marks  with  Quintus  2.0  and SEPIA 3.0.5 (academic release) and the
results are quite different:

                                time Quintus/SEPIA
        Single features                 0.79
        Small programs                  0.77
        Large programs                  1.33

The difference for the small benchmarks is mainly  due  to  the  fact
that  SEPIA  uses  32  bits for the tag and 32 for the value, and its
ability to handle coroutining and asynchronous interrupts.   For  the
large programs, however, one can see that actually other features may
outweigh.  I don't want to claim  here  that  SEPIA  is  faster  than
Quintus, there are enough programs even in the suite where it is 40 %
slower, but I want to claim that small benchmarks are not enough.

My point is that Prolog needs an official benchmark suite. We have at
least  to  start discussing which programs should or should not be in
the suite, and what are the criteria to select them. Currently, every
vendor  uses  some  benchmark suite, of course that one which is good
for his Prolog system, and other benchmarks are usually refused.   We
have  to  move  away  from this. I think that by now everyone can see
that Prolog systems are going to be much faster  and  that  a  vendor
will  not  be able to say "yes, on this benchmark the other Prolog is
faster, but only because it optimizes feature F which  in  real  pro-
grams  would not matter".  Sooner or later, all features will have to
be optimized.  I know it will be hard, but until we get  rid  of  the
"naive reverse curse", Prolog will not be taken seriously.

Last year in Cleveland I have talked to people from  several  commer-
cial  companies and it turned out that everyone basically agrees that
a benchmark suite is necessary, but everybody also wants to  partici-
pate  in  the  selection.  We more or less agreed that benchmark pro-
grams should be used 'as is'.  If a system has a way to generate e.g.
mode declarations automatically, it can use it, but declarations can-
not be added by hand.  Everybody can of course add some  declarations
and  say  "our  system runs the benchmark suite in X seconds but with
added mode declarations in Y seconds!".

There are always problems when running some programs  with  two  dif-
ferent Prolog systems, because the same functionality can be obtained
in different ways, and so e.g. using assert/1 to make a  counter  can
be  fast in one system, but hopelessly slow in another, which has its
own efficient primitive to handle counters.  These problems  have  to
be  handled  on  a case by case basis, the idea is that some programs
would have simple predicates that can be  defined  for  a  particular
Prolog system, e.g.  inc_counter(c) would be defined in one system as

inc_counter(C) :-
        erase(C, Value),
        NewVal is Value + 1,
        recorda(C, NewValue).

in another one as

inc_counter(C) :-
        ctr_inc(C).

or

inc_counter(C) :-
        incval(C).
This approach should make each vendor reasonably happy, and could be-
come  obsolete after the ISO standard appears (but probably will not,
because Prolog systems will continue to offer extra features to  han-
dle  frequent  operations).  The benchmark programs should be written
in a syntax which is not too distant from the current ISO  draft,  so
that they can be made ISO compatible when needed.

I would like to collect more programs from which the benchmark  suite
could  be selected.  Using our profiler, I can collect the statistics
for every program, both at the level of box ports and at the level of
WAM  instructions,  and I can send this statistics to everyone who is
interested.  I can also make my benchmark suites available to  people
who want to participate in the selection of benchmark programs.

Since I have already enough small programs (everybody has :-)),  what
I  need is more large programs, but also maybe programs tuned to test
other single features.  Please, if you have some  real-life  programs
which  are sufficiently large and which can be made public, send them
to me together with a sample data and reference output. If your  pro-
gram is good, you can in turn get SEPIA with discount, so it pays off
for you.  Moreover, if your program is in the benchmark suite, then a
lot  of  implementors all around the world will be trying to speed up
*your* program, wouldn't that be great?  The best media is a Sun car-
tridge, but mailing a compressed file would do as well. Everybody who
contributes with a program will be acknowledged in the suite.

--Micha Meier

Disclaimer as usual.

USA     micha%ecrc.de@pyramid.com
	pyramid!ecrc!micha

EUROPE  micha@ecrc.de
	unido!ecrc!micha

MAIL	Micha Meier
	ECRC
	Arabellastr. 17
	8000 Munich 81
	West Germany
--
USA     micha%ecrc.de@pyramid.com, pyramid!ecrc!micha

EUROPE  micha@ecrc.de, unido!ecrc!micha