Re: [Xsb-development] abolishing tables in the MT engine

[Terrance S. <ts...@cs...>]

 > Anyway, give me until the end of the week to come up with a
 > radically revised proposal.  There are a lot of strong reasons for
making
 > thread-shared tables the default

Consider first static code.  Basically whenever the MT engine calls a
table it checks to see whether it is not yet called, complete, or
incomplete.  If the table is not yet called, the thread calls it, and
if the table is complete the thread suspends and waits for the table
to complete, then backtracks through the completed trie.  In the case
of mutually dependant cycles across threads deadlock detection is
done, and one of the threads grabs the tables.  Thus the approach uses
optimistic concurrency control, and is unlikely to be needed
frequently due to properties of local evaluation that I wont go into
here.  With thread-specific tables another step is needed, which is to
create a thread-specific call with table.  Doing this creates a bit
more overhead, as well as changes to table meta predicates, abolishing
tables --- oh, wait... thinking about how to implement thread-specific
tables is what got me thinking about abolishing tables in the first
place.

My point is that for static code sharing tables is an elegant
extension of single-threaded tables (good work Rui!)  Of course the
devil is in dynamic code.

From my point of view the main semantic problem is that the actions of
one thread may have unexpected effects on the computations of another
thread.  We'd (I'd?) like to enforce read consistency (derivation
consistency?).  For a designated goal G, I'd like to ensure that if G
is called at time T in thread H, it finds a sound and complete set of
answers implied by the program at time T.  This differs from the
"logical" view of assert and retract in that changes to dynamic code
are not visible in H until G is completed, and protects H from
unexpected changes by other threads.  Note that unless dynamic code is
thread-specific also (or is changed), thread-specific tables will have
the problem of inconsistency just as thread-shared tables.

So we have two coherent approaches: thread-specific dynamic code and
tables, or enforcing read consistency among ALL tables and dynamic
code.  Lets look at the latter.  For dynamic code we'd finally
implement logical assert as we have discussed lo these many years.
There would be a difference in that each thread would have in its
private context a CLOCK value.  Whenever an assert or retract was
made, a global GLOBAL_CLOCK would be incremented.  Each time a
designated top-level call was made by thread H, the value of
GLOBAL_CLOCK would be copied into the private clock H.  The private
clock would then be checked against the time intervals in dynamic code
exactly as with logical assert but would not be updated until the call
was over (as opposed to the GLOBAL CLOCK).

Retraction would mark the DEATH field of a clause as in logical
assert.  To reclaim space we'd keep information along the lines of
what David suggested.  Rather than scanning the CP stacks we'd keep
information to indicate that a thread had entered a dynamic predicate,
and this information would be removed when the thread left the
predicate, exited, cut over the choice point, etc.  It would be a
little more complicated in that we'd have the threads and their time
of call, rather than the number of current calls.

Changes to tables would be similar, but simpler.  Tables would be
marked with a BIRTH and DEATH date.  The BIRTH date would be the time
of the thread that created the table, while the death date would be
set to non-infinity when the table was abolished.  Threads would check
their times against the birth and death date of a table only upon
table entry.  We'd keep the same information on entry to a table as on
a dynamic predicate to enable space reclamation of abolished tables,
and update this info when the calling thread leaves the table, exits,
cuts over the completed trie choice points, etc.  Various strategies
can be used to determine when to GC abolished tables, but in principle
the GC check could be made whenever the check was made for retracted
clauses.

Of course the same read consistency that is used for shared tables can
be used for local tables and is necessary to avoid the murky semantics
for global assert.  By an large, enforcing read consistency for all
tables and coming up with good space reclamation should not be much
harder than logical assert (with space reclamation).

Terry