Prolog Speed

Appeared in Volume 8/3, August 1995

nelsonb@mathcs.carleton.edu
16th May 1995

I have heard that Prolog is fast. Is this true? If it is, why?

Don_Ferguson@notes.pw.com
Don Ferguson
20th May 1995

Fergus Henderson writes:
Speed is an economic issue. The choice of language greatly affects the economics of producing efficient code. If efficiency is very important to your project, Prolog is not likely to be a good choice.

There is a common perception that Prolog is a slow, interpretted toy, unsuitable for use in commercial business applications. For those of us who make a living programming in Prolog, it is galling to have the language dismissed out-of-hand by people who don't know what they're talking about (no, I don't mean Fergus). Common desktop hardware now has enough memory and power to run Prolog applications effectively. From the standpoint of Prolog's acceptability to the world at large, this is incredibly significant. I would be happy to see Prolog considered a viable component in commercial applications. But that will not happen under the current cloud of misperceptions.

Henderson continues:
Name two good Prolog compilers that generate very fast code.

For my purposes, Sicstus and Quintus. Perhaps "very fast" is an overstatement, but they are fast enough to deliver commercial applications on PC desktops, competing head-to-head with similar applications written in C. I am thinking of Quintus CustomerQ, the modifiable client-server customer support system, which competes directly with products from Vantive, Scopus, Clarify, Remedy, and others. By coming to market quickly with advanced functionality, Quintus gained an early advantage in this market. In that sense, I agree that speed is an economic issue. What Quintus lost in performance by using Prolog was offset by speed of development.

If an application exhibits adequate performance, superior functionality, and reliability, should anyone care what it's written in?

andrew@cee.hw.ac.uk
Andrew Dinn
23rd May 1995

nelsonb@mathcs.carleton.edu wrote:
I have heard that Prolog is fast. Is this true? If it is, why?

James A Hammerton replied:
I don't know where you heard that from. Prolog is not going to be as fast as say C or C++, because...

The answer here is almost as irrelevant as the question. A language can hardly be described as slow or fast per se. Firstly, it depends what you try to do with it. So programs are fast or slow, not languages. Secondly, even if one resorts to picking a particular task and coding it in say Prolog and C++ that might tell you something about the job in hand and might indicate some likely corollaries when it comes to coding other (similar) tasks but it might also just tell you something about the compiler or operating system you are using or even your ability as a coder in these two languages. So much depends.

It is true that the interpretation of Prolog affects performance but whether this is for the better or worse is not clear. Compilation to native code is an alternative but this often leads to code bloat and massive swapping problems. Mind you, code bloat in C++ systems also affects performance. Smalltalk-80 uses on the fly compilation to native code to very great effect, almost halving execution time on most programs. This is not a simple issue.

Undoubtedly, for many tasks a Prolog program, even when coded by an expert, cannot do the same job as fast as a C++ program coded by an expert. But for some tasks the converse is the case. Take away the qualification that the programmer is an expert and the answer is far less clear cut. And to add insult to injury, if you are not an expert then you probably ought to either become one, find one to do the job for you, or stop worrying about raw speed and start worrying about other more important properties which your programs need to have such as readability, maintainability, reusability, testability etc. Speed is the cherry. Learn to bake the cake first.

vanroy@dfki.uni-sb.de
Peter Van Roy
23rd May 1995

Don Ferguson is right: commercial Prologs have converged to a technology that is adequate for its applications.

It has been proven that there is no inherent reason why Prolog can't be made to run as fast as C; I think that by now this should be obvious to anyone who is well-informed about Prolog implementation technology. Constructive proofs include the systems Parma and Aquarius; the latter is available for free and can run large programs.

Commercial tools have not yet used the latest Prolog implementation technology to get every last ounce of performance. Perhaps this is because they don't feel the need? Perhaps an execution-time factor that is less than an order of magnitude (which is the difference between C and SICStus or Quintus) doesn't make any difference, given today's high-performance machines.

fjh@munta.cs.mu.oz.au
Fergus Henderson
3rd June 1995

Peter Van Roy writes:
It has been proven that there is no inherent reason why Prolog can't be made to run as fast as C; ...

I think there are reasons why Prolog can't be made to run as fast as C with current implementation technology. In particular, the lack of arrays and pointers with destructive update in Prolog means that tasks that use matrix multiplication, graph manipulation, hash tables, and so forth are significantly faster in C.

Peter Van Roy continues:
Commercial tools have not yet used the latest Prolog implementation technology to get every last ounce of performance. Perhaps this is because they don't feel the need?

That's because anyone who really cares about performance will write their applications in some other language. Prolog vendors don't care about performance because their customers don't care about it. Customers for whom efficiency is important don't choose Prolog. It's a vicious circle.

conway@mundil.cs.mu.oz.au
Thomas Charles Conway
1st June 1995

Since we all probably agree that predicate logic is am elegant and powerful notation for writing programs, it would be nice to use a logic programming language to write software for my digital signal processing applications, my operating system, and so on. I think it is possible to settle on accepting Prolog as being a good tool for a particular group of problems, and to miss the oppertunity to bring the power of LP to other problem domains.

andrew@cee.hw.ac.uk
Andrew Dinn
4th June 1995

There are many elegant and powerful notations and some inelegant and powerful ones too. Some of them work well for describing some kind of problems, others well for other kinds of problems. Is your inference based on dogma or hard reasoning? experience or faith?

Logic is a useful notation and the right notation is usually half of any solution to a problem. But the notation usually needs to be germane to the problem otherwise the expression of the solution is clumsy, cluttered and ultimately unclear.

A better approach is to pick a suitable notation for modelling the problem in hand and its solution and then implement that model, either directly in a language which supports the chosen formalism or indirectly by translating from the chosen formalism to an implementation language using a translation which is known to preserve the relevant semantics of the original. The latter approach neither mandates nor rules out the use of any particular language, because what is at stake is not the robustness of the language per se but the validity of your translation.

Yannis Cosmadopoulos
yac@sirius.com
4th June 1995

Issues of speed and completeness are not of paramount importance. The Prolog community has been concentrating on these issues all along, and in so doing has been digging a hole for itself. Choice of a language for solving a problem depends on many factors. Speed, cost, availability of programmers, portability, footprint, speed of development, integration with other tools and many others.

More seriously, for commercial acceptance, the programming support and integration tools tend to be of utmost importance. For whatever reasons, in this domain the hands down winners are C, C++ and on Windows, Visual Basic. As a programmer, I would much prefer to write a parser in Prolog, but if I use yacc I can more easily embed this in a larger system which allows me to use all the 3rd party add-ons available. The language is more like the glue which holds the application together.

Conclusion: If Prolog (and logic programming) is to survive outside a small, predominantly research oriented gheto, we need to concentrate on embedability and integration. Otherwise, we risk having a wonderful language which nobody uses.

Don_Ferguson@notes.pw.com
Don Ferguson
5th June 1995

Fergus Henderson writes:
Prolog vendors don't care about performance because their customers don't care about it. Customers for whom efficiency is important don't choose Prolog. It's a vicious circle. Prolog vendors care very much about performance and efficient memory utilization. However, by now they realize that speed is not the reason why people don't choose Prolog. Decisions are made by humans, who are ruled by fear and prejudice as much as by logic. C programmers feeling threatened by competitive technologies tend to reject them. Managers who would be fired for making risky and unpopular choices choose the safest path. Herd mentality rules, and as Yannis Cosmadopoulos points out, there are real benefits derived from the economies of scale.

For Prolog to be adopted more widely, common perceptions would have to change. An optimistic scenario follows:

1) Prolog is positioned as an ideal embeddable component to add "rules" to object oriented systems. As an add-on technology with limited ambitions, it can be accepted by the C++ community.

2) Somebody builds something significant in Prolog, or some other logic programming language.

3) The popular press, bored with object oriented programming and looking for something different to hype, decides on logic programming, which was mostly overlooked in the 1980's AI-hypefest (at least in the US).

4) Managers, venture capitalists, programmers, etc. become comfortable enough with the idea of using Prolog, that it is no longer considered wierd and risky. Over time, it may even become "main stream".

It's pretty unlikely, but not impossible. The computing eco-system continues to change, as application functionality continues spiraling upwards, and memory prices continue spiraling down. Languages that were perfectly suited to the old environment may be at a disadvantage in the new one.

conway@mundil.cs.mu.oz.au
Thomas Charles Conway
7th June 1995

Andrew Dinn writes:
There are many elegant and powerful notations and some inelegant and powerful ones too. Some of them work well for describing some kind of problems, others well for other kinds of problems. Is your inference based on dogma or hard reasoning? experience or faith? One of my long term goals is to write an OS in a purely declarative parallel logic language. I think that there are a number of good reasons that the LP paradigm is a good one for this type of application. The notion of streams is very powerful for modeling many things that operating systems do (e.g. pipes, ttys and sockets, IPC), and the synchronization mechanism of suspending until a variable is bound makes it relatively easy to build a system that does not have race conditions and other synchronization flaws. There are two main obstacles that current parallel LP systems do not satisfy: first, they are weak from a software engineering point of view -things like strong module systems, types, modes, and determinism make a huge difference to the effectiveness of a system for developing large systems; second, for something like an OS, efficiency is critical in numerous places such as interrupt handlers. Current parallel and coroutining systems do not provide the response needed.

roland@sics.se
Roland Karlsson
7th June 1995

The advantage of Prolog over C is not speed, it is ease of programming certain difficult tasks in a nice way.

But, given the right resources you can always "partial evaluate" the Prolog program to C. There you can do lots of optimization that are not available at the Prolog level. Then you can do the same down to assembly level, where further optimizations are possible. Now, is this really interesting? It might be, if speed is very essential.

Summary: I find this speed contest between Prolog and C uninteresting Both are languages that can be efficiently compiled. They are good at different things. Personally, I use both.

paulward@torolab.vnet.ibm.com
Paul Ward
5th June 1995

The vast majority of computing power today is used by databases. If you want a grand challenge, make your LP language do databases well (and please don't tell me that Prolog does; it isn't even close!).