debray@arizona.edu (Saumya Debray) (07/15/88)
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 language Edison. What's interesting is that even though the Prolog implementation used is C-Prolog, the Prolog version of the compiler is typically only about 5 times slower than the Pascal version. Now there are faster Prolog systems readily available that are anywhere from 10 to 50 times faster than C-Prolog. Assuming that the comparison is a fair one (i.e. noone's writing execrable Pascal code or using the slowest Pascal system 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. -- Saumya Debray CS Department, University of Arizona, Tucson internet: debray@arizona.edu uucp: arizona!debray
bruno@ecrcvax.UUCP (Bruno Poterie) (07/18/88)
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. >-- >Saumya Debray CS Department, University of Arizona, Tucson > 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. In fact C-Prolog may be even better because the builts-in are integrated into the emulator loop instaed of beeing linked functions with call overhad. From our own experiences here, writting a (Prolog to WAM-like) compiler in C-Prolog and then compiling it did not increased very much speed, because most of the time was spent in i/o and database access for tables. Although me must take in account the fact that our compiler was a prototype system, we got increases from 1.6 to less than 2.5, depending heavily on the size of the source and therefore on the quantity of i/o and database size and accesses numbers. --Bruno Poterie
ok@quintus.uucp (Richard A. O'Keefe) (07/19/88)
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.
micha@ecrcvax.UUCP (Micha Meier) (07/19/88)
In article <6251@megaron.arizona.edu> debray@arizona.edu (Saumya Debray) writes: >Assuming that the comparison is a fair one (i.e. noone's >writing execrable Pascal code or using the slowest Pascal system >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. Well, I must say that our experiences are different, at least concerning compilers for Prolog. I'm sure everybody agrees that Quintus Prolog is a very fast Prolog, but our compiler, written in C, is about 10 times faster than Quintus compiler written in Prolog (and it does more optimizations). An interesting thing is that most of the time is spent in the first pass, i.e. reading in the clauses; maybe this makes Prolog different from other languages. --Micha
debray@arizona.edu (Saumya Debray) (07/20/88)
In article <564@ecrcvax.UUCP>, micha@ecrcvax.UUCP (Micha Meier) writes: > I'm sure everybody agrees that Quintus Prolog is a very fast Prolog, > but our compiler, written in C, is about 10 times faster than Quintus > compiler written in Prolog ... I'm not surprised at that: you'd expect some performance loss in going from a low-level to a high-level language. A compiler written in Prolog would have a fair amount of structure copying, runtime type checking, tagging/untagging of operands, etc., that you wouldn't find in the corresponding C code. What I found interesting about the SIGPLAN Notices article I referred to originally was that despite the overhead of runtime type checking etc., the Prolog code came as close as it did to the performance of code written in a strongly typed imperative language. -- Saumya Debray CS Department, University of Arizona, Tucson internet: debray@arizona.edu uucp: arizona!debray