ANN: Jekejeke Prolog 1.1.6 (library modules work distribution)

[j4n bur53]

Dear All,

We have just uploaded the new release of Jekejeke Prolog.
We improved the multi-threading scalability of the
Prolog interpreter.

- Module "clean" (in package "misc"):
This new module provides supervised execution. The predicates
sys_clean_thread/1 and sys_clean_threads/2 run slave threads
which will be cancelled for a termination event in the
continuation or a signal by another thread.

- Module "distributed" (in package "runtime"):
This new module provides meta-predicates to distribute work over
multiple threads. The simplest meta-predicate horde/[1,2]
collects the results of the spawned threads. The meta-predicates
balance/[2,3] and setup_balance/[3,4] allow work distribution
of a generate and test.

- Better Scalability:
We could eleminate locking here and then completely (static
predicates, predicate meta-information). In other cases we
replaced simple mutex locks by read-write pair locks (dynamic
predicates, multi-file predicates and source files). Not
only multi-threaded code profits from these optimizations,
but also single-threaded code.

*Frying Pan Disclaimer:*
Unattended execution or the use of unsuitable hardware to
run multi-threaded code is not recommended. The device might
overheat and automatically switch off, with the result of data
loss. Or the device might keep running, with the result of
hardware damage. No warranty or liability implied.

*New GitHub Resources:*
Some source code excerpts and some code samples have been
uploaded to GitHub. You can now visit the repositories
https://github.com/jburse/jekejeke-devel and
https://github.com/jburse/jekejeke-samples .

Happy coding!

*Android Appstores:*
https://play.google.com/store/apps/details?id=jekpro.platform.headless

*Download:*
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/05_down.jsp

[j4n bur53]

j4n bur53 schrieb:

> - Better Scalability:
> We could eleminate locking here and then completely (static
> predicates, predicate meta-information). In other cases we
> replaced simple mutex locks by read-write pair locks (dynamic
> predicates, multi-file predicates and source files). Not
> only multi-threaded code profits from these optimizations,
> but also single-threaded code.

Technical Note: In contrast to SWI-Prolog, we didn't
invest in concurrent data stuctures (which are good
for many read and many writes requests).

We only invested in read-write locks (which are good
for many reads and few write requests).

Strangely, although SWI-Prolog has some concurrent
data structures awailable, it still uses simple mutexes
here and then, for example erase/1 predicate.

In our case the erase/1 predicate now also uses a
read-write lock. But only if the predicate is dynamic
or (unfortunately)(*) multi-file.

No locks are used by erase/1 in case of a thread-local
predicate, this was already the case before this new
release. This new release only deals with the non-thread-
local predicates.

Bye

(*)
Since multi-file predicates can be loaded by multiple
threads, otherwise they wouldn't be multi-file predicates,
we were forced to apply some locking to them as if they were
dynamic predicates.

We were not able to handle multifile predicates, even the
static ones, as if they were static predicates. i.e. omit
the locking completely. (**)

This is very unfortunate, for example our CLP(FD) makes
heavy use of multi-file predicates, this approach is used
in the hypothetical reasoner, so that we don't see very
good scalability there yet.

(**)
Omitting the locking completely is a little bit tricky.
We us an inline cache, which is nearly a concurrent data
structure. Its a concurrent data structure which has some
redundant idempotent operations.

This also happens when a looking-up the clauses of a
predicate occurs, and some index is generated for the first
time, it can happend that accidentially two or more threads
will generate the same index concurrently.

Correctness is not affected by this, only performance
degrades a little bit. But other more complex solutions,
such as reevaluating locks, could avoid this
double work.

But I guess the more complicated solution is not needed,
since the occurence of double work is possibly very rare.
I have not yet hold of figures measuring this double
work effect and supporting my claim.

[j4n bur53]

j4n bur53 schrieb:

> Correctness is not affected by this, only performance
> degrades a little bit. But other more complex solutions,
> such as reevaluating locks, could avoid this
> double work.

Also reevaluating the locks, results in blocking
the one thread or many of the other threads, so
instead of blocking just letting the one thread or
many of the other threads do some double work
is also fine

(which will be completed in the same time as the
blocking would need, so it doesn't harm the execution
time wise if you don't have too many threads running,
but well you guess it, it might heat up the CPU
a little bit more).

BTW: The predicates use very slim non escalable
read-write locks, which are therefore not slotted,
and I guess pretty fast (depending on the Java JVM
biased fast paths of their object locks):
https://github.com/jburse/jekejeke-devel/blob/master/utils/headless/matula/util/misc/NonescalableRead.java

The source code handles use the heavier escalable
variant of the read-write locks, which are on the
other hand slotted, but we did not yet make them
reentrant, since we do not yet have a use case:
http://github.com/jburse/jekejeke-devel/blob/master/utils/headless/matula/util/misc/LockRead.java

(In one place we need the unproblematic escalation
from write to read of the lock for source code handles)

Source code handlers are not very often locked. Only
when you consult a file, or lookup a predicate, so having
heavy weight RW locks is acceptable.

On the other hand dynamic and multifile predicates are
very often locked, each time the predicate is accessed,
executed or modified, even in recursive execution, for
each recursive call, so having lightweight RW locks
here is important.

[j4n bur53]

j4n bur53 schrieb:

> The source code handles use the heavier escalable
> variant of the read-write locks, which are on the
> other hand slotted, but we did not yet make them
> reentrant, since we do not yet have a use case:
> http://github.com/jburse/jekejeke-devel/blob/master/utils/headless/matula/util/misc/LockRead.java
>
>
> (In one place we need the unproblematic escalation
> from write to read of the lock for source code handles)
>
> Source code handlers are not very often locked. Only
> when you consult a file, or lookup a predicate, so having
> heavy weight RW locks is acceptable.

In Java JVM, even the innocent looking:
Thread thread = Thread.currentThread();
Can be slightly costly...