Tables can both be private to a thread or shared
between all threads. Private tables are used only by the calling threads
and are discarded as the thread terminates. Shared tables are used by
all threads and can only be discarded explicitly. Tables are declared as
shared using, e.g.,
:- table (p/1, q/2) as shared.
A thread may find a table for a particular variant of a shared tabled
predicate in any of the following states:
- Complete
- If the table is complete we can simply use its answers.
- Fresh/non-existent
- If the table is still fresh, claim ownership for it and start filling
the table. When completed, the ownership relation is terminated.
- Incomplete
- If the table is incomplete and owned by the calling thread, simply
continue. If it is owned by another thread we wait for the
table
unless there is a cycle of threads waiting for each others table.
The latter situation would cause a deadlock and therefore we raise a
deadlock exception. This exception causes the current SCC
to be abandoned and gives other threads the opportunity to claim
ownership of the tables that were owned by this thread. The thread that
raised the exception and abandoned the SCC simply restarts the leader
goal of the SCC. As other threads now have claimed more variants of the
SCC it will, in most cases, wait for these threads instead of creating a
new deadlock.
A thread that waits for a table may be faced with three results. If
the table is complete it can use the answers. It is also possible that
the thread that was filling the table raised an exception (either a
deadlock or any other exception), in which case we find a
fresh table for which we will try to claim ownership. Finally,
some thread may have abolished the table. This situation is the same as
when the owning thread raised an exception.
This section briefly explains the interaction between deleting shared
tables and running threads. The core rule is that abolishing a
shared table has no effect on the semantics of the tabled predicates.
An attempt to abolish an incomplete table results in the table to be
marked for destruction on completion. The thread that is completing the
table continues to do so and continues execution with the computed table
answers. Any other thread blocks, waiting for the table to complete.
Once completed, the table is destroyed and the waiting threads see a
fresh table192Future
versions may avoid waiting by converting the abolished shared table to a
private table..
The current implementation never reclaims shared tables. Instead,
they remain part of the global variant table and only the answers of the
shared table are reclaimed. Future versions may garbage collect such
tables. See also abolish_shared_tables/0.
Currently, shared tabling has many restrictions. The implementation
does not verify that the limitations are met and violating these
restrictions may cause incorrect results or crashes. Future versions are
expected to resolve these issues.
- Shared tabling currently only handles the basic scenario and cannot
yet deal with well formed semantics or incremental tabling.
- As described in section
7.9.1, abolishing shared tables may cause unnecessary waiting for
threads to complete the table.
- Only the answers of shared tables can be reclaimed, not the answer
table itself.
SWI-Prolog's continuation based tabling offers the
opportunity to perform completion using multiple threads.
