ok@quintus (07/22/88)
Micha Meier says that they have a compiler which is "10 times" faster than the Quintus compiler, and suggests that this may be due to it being coded in C. According my measurements, when you say compile(somefile) in Quintus Prolog, over half the time goes in I/O. This has little to do with Prolog as such, and more to do with Quintus Prolog's user-definable streams. [Our data- base interface actually exploits this to compile an encrypted file directly.] As for the rest, remember that C is essentially the same as BCPL, which is 20 years old. It would be a strange thing if we didn't know how to use it by now! The DEC-10 Prolog family is about 10 years old and we still have a lot of learning to do. I have been able to speed several components of the Quintus Prolog system up (figures proprietary, but I'm pleased with them) by rewriting them in **cleaner** Prolog. [No, I do not know when the new system will be ready for release.] A fast compiler is well worth having, but I think it is better for Prolog users in the long run if vendors try to make faster compilers *in Prolog*.
micha@ecrcvax.UUCP (Micha Meier) (08/03/88)
In article <184@quintus.UUCP> ok@quintus () writes: >A fast compiler is well worth having, but I think it is better for Prolog >users in the long run if vendors try to make faster compilers *in Prolog*. I absolutely agree, but the question I am raising is "is that possible?" and "how can it be done?". I definitely don't have a 20 years' experience with programming in C (I knew Prolog before C), and I haven't tried to write the compiler in Prolog; however, I've seen quite a few Prolog compilers in Prolog, and all of them are really *slow* compared to the C version. I suggest that people analyze their Prolog compilers and share the experiences, because as long as the compilers in Prolog cannot compete the ones in C, Prolog cannot be claimed to be 'the compiler implementation language'. I know that lot of people will say that a compiler in Prolog is more readable, better maintainable etc., but so is my Sepia compiler in C. Bruno has already noted that his compiler spends the majority of time in managing the database (record*), and of course in C is this much easier. My compilers spends 56 units in the lexical analysis, 90 units in parsing, 47 units in the second pass and 25 units in the code generation (and other units elsewhere). This looks like the first pass is the most expensive one (I'm not a compiler expert :-)). How is it in a compiler written in Prolog? Are other compilers in C similar? (units measured compiling CHAT-80). --Micha
ok@quintus.uucp (Richard A. O'Keefe) (08/05/88)
In article <607@ecrcvax.UUCP> micha@ecrcvax.UUCP (Micha Meier) writes: >In article <184@quintus.UUCP> ok@quintus () writes: >>A fast compiler is well worth having, but I think it is better for Prolog >>users in the long run if vendors try to make faster compilers *in Prolog*. > I absolutely agree, but the question I am raising is > "is that possible?" and "how can it be done?" ... > I've seen quite a few Prolog compilers in Prolog, and all of them > are really *slow* compared to the C version. ... > My compiler spends 56 units in the lexical analysis, 90 units > in parsing, 47 units in the second pass and 25 units in the > code generation (and other units elsewhere). Meier's figures summarise as: reading terms: 2/3 of total compiling: 1/3 of total The ratio isn't quite that extreme in Quintus Prolog, more like 3/5 to 2/5. Suppose Quintus were to rewrite our compiler in OukErgon (the language that does no work at all, so is infinitely fast). There's a 40% speedup. If _that's_ all we'd get from OukErgon, what price C? My answer to Meier's questions are -- yes, it is possible. -- here is how it can be done: (a) If going through a WAM-like stage, improve the interpreter (if not generating native code) or the macros (if generating native code). Even Quintus Prolog could be speeded up; the trick is to do it in a portable way. If you speed the emulator up, the compiler goes faster *and* the generated code goes faster. If you rewrite the compiler in C, that does *nothing* for the user's code. (b) Make the compiler as clean and pure as you can. This is likely, if done well, to result in *large* improvements. I haven't seen "quite a few" Prolog compilers in Prolog, only about 6. Some of them were quite shockingly ugly Prolog code, hacks all over the place. Oddly enough, those were the slower ones. (c) Do better indexing (blush). This will speed up the user's code, and a well-written Prolog compiler will have quite a few tables, especially in code-generation, so the compiler is likely to go faster, even doing more work. (d) Write an "optimising" compiler, that is free to take longer than would be tolerable for incremental development, and that does a good job of spotting determinacy, common subexpressions, special cases, &c, and then compile the usual compiler with it. (Step (b) is an important prerequisite for this.) The only way we'll find out whether it is possible to write faster compilers in Prolog is to TRY. People who sell Prolog systems must not take the performance of present compilers as licence to run whimpering to C, but as a stimulus to improve their Prolog systems. (In the interests of existing customers, better a fast compiler in C than a slow compiler in Prolog, but that must not be regarded as anything but a temporary expedient to be tolerated for the shortest possible time.)
debray@arizona.edu (Saumya Debray) (08/05/88)
In article <607@ecrcvax.UUCP>, micha@ecrcvax.UUCP (Micha Meier) writes: > In article <184@quintus.UUCP> ok@quintus () writes: > >A fast compiler is well worth having, but I think it is better for Prolog > >users in the long run if vendors try to make faster compilers *in Prolog*. > I've seen quite a few Prolog compilers in Prolog, and all of them > are really *slow* compared to the C version. I suggest that > people analyze their Prolog compilers and share the experiences, In SB-Prolog, much of the compilation time is accounted for by the front end: the parser, which is written in Prolog, builds a term from a list of tokens; this term is then transformed to an annotated syntax tree. This -- especially the transformation to the annotated syntax tree -- seems to account for a large fraction of the total compilation time. (The less-than-optimal symbol table management strategy doesn't help.) The lack of destructive assignment also undoubtedly affects compilation speed: e.g., during peephole optimization, the instruction stream is copied repeatedly instead of being modified in place. However, my feeling is that the effect of this isn't as bad as one might expect, and can be reduced substantially with proper choice of data structures (sorry, no numbers). -- Saumya Debray CS Department, University of Arizona, Tucson internet: debray@arizona.edu uucp: arizona!debray
ok@quintus.uucp (Richard A. O'Keefe) (08/14/88)
In article <614@ecrcvax.UUCP> micha@ecrcvax.UUCP (Micha Meier) writes: > I don't see your point - everybody can speed up his/her Prolog > system, independently on what compiler is being used. You are > saying "if I'm speeding up my compiler, user's code is speeded > up as well (as a side effect)". Well I don't need to speed > up my compiler, I can concentrate on speeding up the user's code. No, that is the direct opposite of what I am saying. What I am saying is that IF you improve the quality of the code that you generate, or the efficiency with which that code is executed, then *BOTH* the user's code *AND* the compiler speed up. Neither is a side effect: both are the very same primary effect. The point is that with a compiler written in Prolog the vendor has an _incentive_ to do things which will benefit the customer as well. >> ... This will speed up the user's code, >> and a well-written Prolog compiler will have quite a few tables, > > actually, a Prolog compiler does not need much more than 6 tables :-) No Prolog program needs more than one table: you can pack the entire program into a table of unit clauses and run an interpreter over it. Do you have some specific reason for quoting the number 6? > I cannot avoid noting that there are > quite a few Prolog compilers around, and their writers > probably have not followed your suggestions ( I can understand > it, what a challenging problem to write a Prolog compiler, > no matter how). I have no doubt that it is possible to write > a clean and relatively fast Prolog compiler, but is what > you suggest enough to achieve that? The only way is to try, > but is there anybody out there trying to write a *clean* > Prolog compiler? It's easier to do that in C, I'm afraid. Remember Sturgeon's law? "90% of _everything_ is crud". Why should Prolog compilers be an exception? There is something rather interesting here. I come from the "Edinburgh" culture. I believe that David Warren originally started to write the DEC-10 Prolog compiler in BCPL (maybe it was BLISS-10), and then switched over to Prolog because it was easier. I had a nodding acquaintance with the ML-in-ML compiler. What I am about to say is an expression of my feelings, not a reasoned argument. I feel safe and confident about writing compilers in "declarative" languages: if I had to write another Prolog compiler and didn't have Prolog to do it in I'd do it in ML, and if I couldn't get my hands on that I'd fall back on Lisp. I find the thought of writing a Prolog compiler in C almost frightening, it strikes me as so tedious, so unsafe, so clumsy. (C++, now, I might almost consider _that_.) I believe that the freedom to change data structures around is important for producing an efficient compiler, and it is very easy to do that in Prolog and quite hard in C (not so hard in C++). The idea that it could be considered easy to write a Prolog compiler in C is very strange to me. Evidently, I need to be instructed. I understand that ECRC is no more in the business of giving things away free to strangers than Quintus is, but is there anything written up about how to write Prolog compilers in C? How do you execute bits of the source code at compile time? [Tokenisers for Prolog in C, I understand. Parsers for Prolog in C, I understand. Peephole optimisers and assemblers for WAM instructions in C, I understand. It's the bit in the middle I need to have explained. ]