MARTIN-LUTHER-UNIVERSITÄT HALLE-WITTENBERG
Institut für Informatik
Prof. Dr. Stefan Brass

Implementation Alternatives for Bottom-Up Evaluation

(Download Page for Example Programs, Under Construction, Last Change: July 14, 2010)

Paper

A first report about this research appeared as:

Stefan Brass: Implementation Alternatives for Bottom-Up Evaluation.
Technical Communications of the 26th International Conference on Logic Programming (ICLP'10)
Manuel Hermenegildo and Torsten Schaub (Eds.)
Leibniz International Proceedings in Informatics (LIPIcs), Vol. 7, pages 44-53,
ISBN 978-3-939897-17-0, ISSN 1868-8969,
Schloss Dagstuhl, 2010.
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2582/, DOI: 10.4230/LIPIcs.ICLP.2010.44.

There is also a Technical Report version of this paper with an appendix that explains the performance tests: PDF, Postscript.

Here are the slides for my short talk at ICLP 2010: PDF (preliminary version).

Test 1: Basic Comparison, Push Implementation Variants

Logic Program

p3(X, Z) :- p2(X, Y), q(Y, Z).
p2(X, Z) :- p1(X, Y), q(Y, Z).
p1(X, Z) :- p0(X, Y), q(Y, Z).
p0(X, Y) :- r(X, Y).

Test Data (EDB Predicates)

q = {(i, i+1) | 1 <= i <= 5000 }
r = {(i, i) | 1 <= i <= 5000 }

Program Code

Runtimes

Method	Windows PC	Linux Server	Solaris Server
Method 1: Materialization	515ms	380ms	430ms
Method 2: Pull	937ms	320ms	930ms
Method 3: Push (no opt.)	562ms	250ms	950ms
Method 3: Push (with opt.)	546ms	250ms	950ms
Method 3: Push (static)	578ms	220ms	1100ms
Method 3: Push (local)	515ms	250ms	490ms
Method 3: Push (main)	515ms	240ms	330ms

Test Machines

The times listed under "Windows PC" were measured on a PC with Intel Core2 Duo CPU E8200 @ 2.66GHz with 4 GB main memory, running Windows XP Professional, the programs were compiled with Microsoft Visual C++ 2008 Express Edition with the standard settings for the "Release" configuration (includes optimization).
The times listed under "Linux Server" were measured on a system with four Opteron 852 CPUs (2.6 GHz) and 16 GB memory running Ubuntu 8.04 64bit. The used compiler is gcc 4.2.4 with -O2 code optimization.
The times listed under "Solaris Server" were measured on a SunFire V490 (4 dual core UltraSparc IV processors, 16 GB memory) running SunOS 5.10. The gcc version was 3.4.6, -O2 code optimization was used.
Each program was run three times, the median value is reported in the table. If the runtimes were very different, more tests were done, and again the median value reported.

Test 2: Loop Order, Passing Bindings

Logic Program

p3(X, Z) :- q(X, Y), p2(Y, Z).
p2(X, Z) :- q(X, Y), p1(Y, Z).
p1(X, Z) :- q(X, Y), p0(Y, Z).
p0(X, Y) :- r(X, Y).

Test Data (EDB Predicates)

q = {(i, i+1) | 1 <= i <= 5000 }
r = {(i, i) | 1 <= i <= 5000 }

Program Code

Runtimes

Method	Windows PC	Linux Server	Solaris Server
Method 1: Materialization	781ms	830ms	1950ms
Method 2: Pull (size 200 instead 5000)	24843ms	3400ms	19660ms
Method 3: Push (no opt., local vars)	531ms	290ms	340ms
Method 4: Push+Bindings	609ms	260ms	330ms

Test 3: Using Keys

Logic Program (same as in Test 2)

p3(X, Z) :- q(X, Y), p2(Y, Z).
p2(X, Z) :- q(X, Y), p1(Y, Z).
p1(X, Z) :- q(X, Y), p0(Y, Z).
p0(X, Y) :- r(X, Y).

Test Data (EDB Predicates)

q = {(i, i+1) | 1 <= i <= 5000 }
r = {(i, i) | 1 <= i <= 5000 }

This time, we use the knowledge that the first argument of q and r is a key (and the push method uses this for the second argument of q).
This also implies that the first argument of p0, p1, p2, p3 is a key.

Program Code

Runtimes

Method	Windows PC	Linux Server	Solaris Server
Method 1: Materialization	390ms	360ms	740ms
Method 3: Push (no opt., local vars, other key)	250ms	110ms	230ms
Method 4: Push+Bindings	281ms	110ms	180ms
Method 4: Push+Bindings: Function	265ms	110ms	190ms

Test 4: Using Ordering, Merge Join

Logic Program (same as in Test 2)

p3(X, Z) :- q(X, Y), p2(Y, Z).
p2(X, Z) :- q(X, Y), p1(Y, Z).
p1(X, Z) :- q(X, Y), p0(Y, Z).
p0(X, Y) :- r(X, Y).

Test Data (EDB Predicates): Note the increase to one million!

q = {(i, i+1) | 1 <= i <= 1000000 }
r = {(i, i) | 1 <= i <= 1000000 }

This time, we use the knowledge that q and r facts are generated with strictly ascending values in both arguments.
From this, one can conclude that p0, p1, p2, p3 facts are also computed in sort order.

Program Code

Runtimes

Method	Windows PC	Linux Server	Solaris Server
Method 1: Materialization	765ms	710ms	1710ms
Method 2: Pull	93ms	10ms	90ms
Method 3: Push	78ms	20ms	80ms

Test 5: Disjunctions, Larger Tuples

Logic Program

p1(A) :- q(A).
p2(A,1) :- p1(A).
p2(A,2) :- p1(A).
p3(A,B,1) :- p2(A,B).
p3(A,B,2) :- p2(A,B).
p4(A,B,C,1) :- p3(A,B,C).
p4(A,B,C,2) :- p3(A,B,C).
p5(A,B,C,D,1) :- p4(A,B,C,D).
p5(A,B,C,D,2) :- p4(A,B,C,D).
p6(A,B,C,D,E,1) :- p5(A,B,C,D,E).
p6(A,B,C,D,E,2) :- p5(A,B,C,D,E).
p7(A,B,C,D,E,F,1) :- p6(A,B,C,D,E,F).
p7(A,B,C,D,E,F,2) :- p6(A,B,C,D,E,F).

Test Data (EDB Predicates):

q = {i | 1 <= i <= 50000 }

Program Code

Runtimes

Method	Windows PC	Linux Server	Solaris Server
Method 1: Materialization	1562ms	1220ms	41500ms
Method 2: Pull	390ms	20ms	100ms
Method 3: Push	453ms	300ms	400ms
Method 3: Push (with optimization)	171ms	100ms	150ms

Test 6: Strings, Large Records

Logic Program (same as in Test 1)

p3(X, Z) :- p2(X, Y), q(Y, Z).
p2(X, Z) :- p1(X, Y), q(Y, Z).
p1(X, Z) :- p0(X, Y), q(Y, Z).
p0(X, Y) :- r(X, Y).

Test Data (EDB Predicates): Strings of Length 20 in Array of Length 1000

q = {(ABCDEFGHIJKLMNO-<i>, ABCDEFGHIJKLMNO-<i+1>) | 1 <= i <= 5000 }
r = {(ABCDEFGHIJKLMNO-<i>, ABCDEFGHIJKLMNO-<i>) | 1 <= i <= 5000 }

Program Code

Runtimes

Method	Windows PC	Linux Server	Solaris Server
Method 1: Materialization	6453ms	4280ms	12620ms
Method 2: Pull	6906ms	3600ms	12210ms
Method 3: Push	5985ms	3590ms	12450ms

Remarks

The predicates q and r are stored as linked list. Although the strings are of length 20, the arrays are of length 1000, so that the records of the linked list are slightly over 2000 bytes large. In this way, the CPU cache is not so helpful.
The listed times do not include the generation of the linked lists for q and r.
All three methods work with pointers to the strings in the q- and r-facts, i.e. the strings are not copied, also not in the materialization method. But of course the strings are compared byte by byte when the equality needs to be tested.

Test 7: Example from Paper

Logic Program

p(X, Z, 2) :- q(X, Y), r(Y, 5, Z).
q(X, Y) :- s(X, Y), Y >= 0.

Test Data (EDB Predicates):

r = {(i,j,k) | 1 <= i <= 10000, 1 <= j <= 100, 1 <= k <= 100}
r can be accessed with binding pattern bff (index on first argument).
s = {(i,i) | 1 <= i <= 10000 }.

Program Code

Runtimes

Method	Windows PC	Linux Server	Solaris Server
Method 1: Materialization	921ms	490ms	1550ms
Method 2: Pull	843ms	140ms	1340ms
Method 3: Push	812ms	170ms	1360ms

Test 8: Recursion (seminaive, no eliminiation of duplicates necessary)

Logic Program

p(X, Y) :- q(X, Y).
p(X, Z) :- q(X, Y), p(Y, Z).

Test Data (EDB Predicates):

q = {(i, i+1) | 1 <= i <= 1000 }

Program Code

Runtimes

Method	Windows PC	Linux Server	Solaris Server
Method 1: Materialization	5468ms	1150ms	5310ms
Method 2: Pull with Bindings	10859ms	2780ms	39180ms
Method 3: Push	4359ms	840ms	7080ms

Note:

To be continued: More Tests follow soon (especially more recursive ones) ...

Stefan Brass (brass@acm.org), 27. February 2010

Original URL: http://www.informatik.uni-halle.de/~brass/botup/ [XHTML 1.0 Checked] [Links checked]