Path: utzoo!attcan!uunet!husc6!mailrus!cornell!uw-beaver!teknowledge-vaxc!sri-unix!quintus!ok
From: ok@quintus.uucp (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: "A Note on the Speed of Prolog"
Keywords: prolog execution speed
Message-ID: <174@quintus.UUCP>
Date: 19 Jul 88 01:05:25 GMT
References: <6251@megaron.arizona.edu> <563@ecrcvax.UUCP>
Sender: news@quintus.UUCP
Reply-To: ok@quintus.UUCP (Richard A. O'Keefe)
Organization: Quintus Computer Systems, Inc.
Lines: 44

In article <563@ecrcvax.UUCP> bruno@ecrcvax.UUCP (Bruno Poterie) writes:
>In article <6251@megaron.arizona.edu> debray@arizona.edu (Saumya Debray) writes:
>>The current (August 88) issue of ACM SIGPLAN Notices has an article
>>"A Note on the Speed of Prolog", by J. Paakki, that's
>>interesting.  The author reports on an experiment comparing the
>>speeds of compilers, written in Pascal and Prolog, for the
>>...
>>available), this seems to suggest that using a "state-of-the-art"
>>Prolog system, one could actually have a Prolog version of the
>>compiler that was faster than the Pascal version.

>I do not believe that we can apply the speed-up factor for a compiler
>application. Remember that this "10 to 50 times" is the speed-up of the
>pure "Prolog Engine" part of the system, while the builts-in are in both
>case written in the implementation language, therefore remaining identical
>in speed.

How the built-ins are implemented depends on the implementation.  Some of
them might be wired into the emulator, some might be coded in C, some might
be coded in Prolog.  Some of them might even be compiled to native code.

However, the speed of the built-ins doesn't matter a lot in this case.
Read the paper!  Three variants were measured:  a Prolog version (which
was written first), a Pascal version (based on the Prolog version), and
a version written using the GAG translator-writing system (also based on
the Prolog version).  Only _part_ of the compiler was so coded:  lexing
and parsing was done with conventional methods, and the measured stuff
did semantic analysis.  That is, the stuff which was measured was pure
tree-walking, which is what Prolog compilers are best at, and input/output
was explicitly excluded from the figures in question.  (Figures were also
presented including I/O.)

Given that I/O was excluded, that semantic analysis is straightforward
tree-walking, and that C Prolog has no indexing, and no TRO, I think a
speed-up by 10 is entirely credible.  (The paper reports _measured_
speed-ups of 4 or 5 with a Karlsruhe compiler, so there's a lower bound.)

Since none of the actual code was exhibited, we are left wondering whether
speed-ups could be obtained with a decent compiler by using purer Prolog.

On the other hand, we have no reason to believe that the Pascal compiler
was particularly good either.  I used to recode Pascal into Prolog on the
DEC-10 at Edinburgh to make my programs faster, but then the Pascal
compiler was not the best.