Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 40 ยท Applications

Tabling and Performance Tuning

Make Prolog programs fast. Use tabling for memoization and left recursion, write tail-recursive predicates with accumulators, avoid needless choice points, and measure with time/1 and statistics.

Prolog is fast enough for most tasks, but the language makes it easy to write programs that are accidentally terrible: exponential recursion, endless left recursion, quadratic list building. The cure is a short list of habits, and one powerful feature, tabling, that fixes two classic problems with a single directive. This lesson covers both, and ends with the tools for measuring.

Prolog is not available on this site, so the Prolog code is read-only; the runnable examples are Python models that count work, so you can see why each technique helps.

The two problems tabling solves

Repeated work. Naive Fibonacci calls itself twice per step and recomputes the same values exponentially often:

PROLOG
fib(0, 0).
fib(1, 1).
fib(N, F) :-
    N > 1,
    N1 is N - 1, N2 is N - 2,
    fib(N1, F1), fib(N2, F2),
    F is F1 + F2.

fib(30, F) gives F = 832040, but it makes millions of calls, and fib(40, F) takes a very long time.

Left recursion. The most natural definition of transitive closure is also the most dangerous:

PROLOG
path(X, Y) :- path(X, Z), edge(Z, Y).
path(X, Y) :- edge(X, Y).

Prolog calls path(X, Z) with the same arguments before doing anything else, so it recurses without bound and ends with a stack overflow, even on a graph with no cycles.

Both are cured by one directive:

PROLOG
:- table fib/2.
:- table path/2.

A tabled predicate remembers every answer it has produced for each distinct call (its variant). A repeated call is answered from the table instead of being recomputed, and a call that is already in progress (as in the left-recursive path/2) waits for answers instead of looping. The technique is called SLG resolution or tabled evaluation.

PROLOG
?- fib(100, F).
F = 354224848179261915075.

?- findall(X, path(a, X), L), sort(L, S).
S = [a, b, c].

With the facts edge(a, b), edge(b, a), edge(b, c) the second query terminates even though the graph has a cycle between a and b. Tabling also gives correct, complete answers for left-recursive grammars, which is why it appears in parsing and in Datalog-style database queries.

What tabling gives you

Memoization Each call is solved once.
Left recursion Loops become fixpoints.
Cycles Graph search terminates.
Aggregation Keep only the best answer.

Add :- table name/arity. and keep the clauses.

1 / 2

The Python model below counts the work done by naive recursion and by a table.

Python Naive recursion versus a table (Python model)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The naive call count grows by a factor of about 1.6 with each step, while the tabled one grows by only two calls per step. That is the difference between "works for 25" and "works for 10,000".

Tabling a cyclic graph is a fixpoint computation: start with the direct successors, repeatedly add everything reachable from answers found so far, and stop when nothing new appears.

Python Left recursion becomes a fixpoint (Python model)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Habits that keep programs fast

Use tail recursion with an accumulator. A call that is the last goal of a clause, with no choice points left, can reuse its stack frame (last-call optimization). Counting a list's length without and with an accumulator:

PROLOG
len([], 0).
len([_|T], N) :- len(T, N0), N is N0 + 1.      % work after the call: stack grows

len(L, N) :- len(L, 0, N).
len([], N, N).
len([_|T], A, N) :- A1 is A + 1, len(T, A1, N).   % last call: constant stack

The first version needs one stack frame per element; for a million elements it uses a lot of memory. The second needs none. (SWI-Prolog's built-in length/2 is already implemented in C, so use it in real code.)

Avoid leaving choice points. A predicate that succeeds but could still backtrack keeps its whole frame alive. Good clause design (mutually exclusive heads) lets the system see that no alternative remains. SWI-Prolog indexes on the first argument and, with JIT indexing, on other arguments when they are bound at call time. Put the argument you will pass bound first.

Order goals by selectivity. Run the goal that fails soonest or produces the fewest solutions first. age(X, 30), lives_in(X, paris) explores every 30-year-old; lives_in(X, paris), age(X, 30) explores every Parisian. Both are correct, but one may be a thousand times faster.

Do not build lists at the wrong end. append(Acc, [X], Acc1) copies the entire list on every call, making loops quadratic. Build the list backwards with [X|Acc] and reverse/2 once at the end, or use a difference list.

Choose the right data structure. A list lookup is linear. For large key-value stores use library(assoc) (AVL trees, logarithmic), library(rbtrees) or SWI-Prolog dicts. For many facts, rely on first-argument or JIT indexing instead of lists of facts.

Use findall/3, aggregate_all/3, msort/2 and other built-ins instead of hand-written loops. They are written in C and optimized.

Prefer constraints over generate-and-test. If a program enumerates a million candidates and filters them, see CLP(FD): propagation can prune the search before it starts.

Measure first

Never optimize by guessing. SWI-Prolog gives you several tools:

PROLOG
?- time(fib(25, F)).
% (a line with the number of inferences and the CPU time)
F = 75025.

The numbers depend on your machine and version. The unit LIPS (logical inferences per second) is the traditional speed measure; a modern SWI-Prolog does several million.

  • time/1 reports inferences and CPU time for a goal.
  • statistics/2 (for example statistics(inferences, N)) reads counters directly.
  • profile/1 shows where time goes, predicate by predicate.
  • prolog_stack_property/2 and the --stack-limit flag control the stack; a "Stack limit exceeded" error usually means unbounded recursion rather than a small limit.
  • call_with_time_limit/2 aborts runaway goals.

Optimize the predicate that dominates the profile, re-measure, and stop when it is fast enough.

Common mistakes

  • Tabling a predicate with side effects (printing, asserting). The table replays answers without re-running the body.
  • Tabling with huge or ever-growing answer sets and forgetting to free memory with abolish_all_tables/0.
  • Adding cuts "for speed" without understanding the semantics, which usually makes programs wrong rather than fast.
  • Using length/2 or nth1/3 inside loops over the same long list.
  • Comparing timings from a cold run with a warm one; run the goal twice and use the second result.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does :- table fib/2. do?

    Tabling is memoization with support for recursion and cycles, so each distinct call is solved once.
  2. 2. Why does path(X, Y) :- path(X, Z), edge(Z, Y). fail without tabling?

    Left recursion never makes progress in plain Prolog; tabled evaluation turns it into a fixpoint computation.
  3. 3. Which version of length counting uses constant stack space?

    The accumulator version makes the recursive call its last goal, so last-call optimization can reuse the frame.
  4. 4. What should you do before optimizing a slow program?

    Measure first, optimize the dominant cost, then measure again.

Summary

  • :- table Name/Arity. memoizes a predicate, and makes left-recursive and cyclic definitions terminate.
  • Use accumulators for tail recursion; avoid needless choice points and end-of-list appends.
  • Put selective goals first; pick data structures (assoc, dicts, indexed facts) to match the access pattern.
  • Measure with time/1, statistics/2 and profile/1 before and after every change.
  • Tabling is for pure predicates; free tables with abolish_all_tables/0 when data changes.

Next: Project: A Sudoku Solver