Browse Prior Art Database

A High Performance Implementation of Prolog

IP.com Disclosure Number: IPCOM000127953D
Original Publication Date: 1986-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 15 page(s) / 44K

Publishing Venue

Software Patent Institute

Related People

Michael O. Newton: AUTHOR [+3]

Abstract

We discuss an efficient implementation of the Warren Abstract Machine (WAM) (121 in detail. Spe-cial attention is given to data formats, memory layout, WAM optimizations and code generation techniques. A final section describes some hardware considerations for even higher performance exe-cution. Currently the compiler produces code that runs at approximately 900,000 logical inferences per second (LIPS) on a single processor of an IBM 3090 using the naive reverse benchmark. Using several of the yet unimplemented optimizations, we expect this figure to top one million LIPS. [Equation ommitted] Branches if second highest order bit is set (structure). R1 may x be any odd numbered register. R1 is destroyed by this operation. If the item is a pointer, we must determine if it is a free variable or part of a pointer chain. There are several possible ways of representing this choice: * As above, by using the second highest order bit. * By having a free variable point to itself.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 15

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A High Performance Implementation of Prolog

Michael O. Newton

v Technical Report TR:5234:86 April 10. 1987

Caltech Computer Science Department Pasadena, California 91125

Abstract

We discuss an efficient implementation of the Warren Abstract Machine (WAM) (121 in detail. Spe-cial attention is given to data formats, memory layout, WAM optimizations and code generation techniques. A final section describes some hardware considerations for even higher performance exe-cution. Currently the compiler produces code that runs at approximately 900,000 logical inferences per second (LIPS) on a single processor of an IBM 3090 using the naive reverse benchmark. Using several of the yet unimplemented optimizations, we expect this figure to top one million LIPS.

(Equation Omitted)

Branches if second highest order bit is set (structure). R1 may x be any odd numbered register. R1 is destroyed by this operation.

If the item is a pointer, we must determine if it is a free variable or part of a pointer chain. There are several possible ways of representing this choice:

* As above, by using the second highest order bit.

* By having a free variable point to itself.

* By having a free variable be stored as a zero.

Which of these should be chosen is highly architecture dependent. I will discuss the differences in detail.

The first choice, using the second highest order bit is a simple but effective way of implementing unbound variable tagging. Usually however, one of the other two methods would be quicker, as bit tests are usually not as efficient as comparisons or sign tests.

The second possibility has the advantage that it is very robust - it is very unlikely that a random location in memory points to itself without being set up this way. This is very useful when debugging a compiler. However, it involves several inefficiencies. One of these is during garbage collection. Each free variable that is moved must have its address translated. In addition, to test for a free variable, one must do a memory reference, so a performance penalty is likely.

California Institute of Technology Page 1 Dec 31, 1986

Page 2 of 15

A High Performance Implementation of Prolog

The final possibility, storing a free variable as a zero, is risky when first debugging a compiler - there are many other ways that a zero can be located in memory. But, the advantages are numerous. Instead of the need for doing memory references to determine whether a variable is free or not, only a simple test must be done. When storing multiple free variables (as in allocate
(N) ), one needs only do a block copy of zeroes.

2.1.2 Lists as structures

Another minor modification to the WAM in our implementation was the removal of the distinct tags for structures and list. This is most noticeable in the switch-on-term instruction, which now only takes two arguments - the place to go for atoms, and the place to go for structures. We did this...