Re: some ideas for multithreading support

[<Joe...@t-...>]

Hi,

Don Cohen wrote:
>I don't think it's ok to miss keys that were present at the
>beginning of the iteration and never removed.
>Nor do I think it's ok to present the same key twice in any case.
>I do agree that the iteration should not crash.

There's what I wrote, and there's another half I didn't write:

A) The idea is to give a minimum set of guarantees when users are programming in the wild, without locks.
Basically: no crash, no endless iteration due to sudden cycles in internal data structures.
Perhaps attempt to detect that and raise an error as Bruno suggested?

B) Other parts would use locks in order to give stronger guarantees.

For instance, clisp would internally use locks when updating or iterating a package's hash table, because
1) without them you can hardly guarantee uniqueness;
2) you want unwarranted (not thread-aware) apps to obtain stable (or shall I say sensible?)
    results when iterating across e.g. the keyword package.

Therefore, it does not make sense to raise the minimum set of guarantees for the A case.

Of course, you can try and make A and B collapse using algorithms for concurrent hash-tables.
I have some doubts that this can work because e.g. the package example shows that often enough
you need locks (or rather, critical sections) above and surrounding the level where you have
atomic/concurrent updates to individual parts. The hash tables may support concurrent updates,
but they are only part of the package object which (likely) has more invariants and postconditions.

I have not analyzed your algorithm in sufficient detail to determine whether it could work as
a concurrent hash table implementation. But that's what it wants to be. My proposal was way
more limited: just use the present, non concurrent code, add a few checkpoints / atomics /
fences to ensure it will terminate. But I don't see how a simple non-concurrent bucket-based
algorithm could prevent keys from disappearing from an enumeration in the presence of
parallel deletion of other keys. That's precisely why CL forbids such modifications.

One could RPLACA the deleted element with #<UNBOUND> to preserve the integrity of the
bucket list. But that would be a burden imposed on all tables, not exactly nice.

Regards,
	Jörg