Re: some ideas for multithreading support

[<don...@is...>]

 > That's OK, and I believe exactly this feature has been on the clisp
 > wish-list for as long as threads exist.
 > 
 > My idea A was that, until the time when somebody will fulfill this
 > wish, we can live with minor updates to the current hash table code
 > just good enough to terminate iteration and to not crash.

Ok, but that requires a lot of understanding of the current
implementation.  I was not even aware that the current implementation
could crash in this case.

 > >Then an iteration would only have to keep track of the current key,
 > >right?  It could lock the table in order to find the next key and
 > >then unlock the table.
 > Might work. Even if that key has been deleted meanwhile, the CDR of
 > the list can still point to the former remaining elements
 > (some of those may well have been deleted since ...).

You're imagining holding on to the tail of the list.  I don't think
that would work, but it might depend on other details of how things
are inserted and removed from the list.
What I had in mind was much simpler - just remember which key you got
last.  In order to get the next one, compute its bucket, search that
bucket in order until you find something ordered after the previous 
key.

 > Alternatively, the hash-table may weakly link to all iterators, so
 > their current index can be checked.

Meaning that if you have a lot of iterations in progress any update
can take a long time (while holding a lock) to adjust their states.

 > Maybe that's more in line with what Bruno wants:

 > Check during update that nobody is iterating at another position -
 > even when single-threaded.  That implies that iterating through
 > *PACKAGE*, calling READ/INTERN is likely to fail, ouch!

You mean if you just signal an error when there's another thread
holding a lock you want.
In addition to the huge cost of locking (I think of CAR as one 
instruction so I don't want to spend even one more instruction 
locking the cons cell and another one unlocking it), this seems
to place an unreasonable burden on the user, unless he wants to
get these errors all the time.  I suppose you could run everything
inside a handler that waits for the lock to become available and
thereby end up with something close to what we expect, other than
in performance.

 > >My specification says there should be some ordering of the keys that
 > >were in the table at the start of iteration along with those added
 > >during the iteration.
 > Why not: Push new at start, remove anywhere?
 > That too implies that once you are mid-list, you won't see new elements.

The time the key was last added to the table makes a reasonable order.
We can actually maintain a list of keys in this order - each entry in
the table contains not only a key and value but also the next entry in
this ordering.  So we could always visit keys in the order they were 
last added (most recently added are visited first).
The fact that this order changes during an iteration seems ok.
We can define the order the iteration visits keys as:
for those keys that were in the table at the start of the iteration
and either never deleted or visited before they were first deleted, 
the inverse of the order in which they were added before the iteration
started, and for those keys that were either in the table initially
and then deleted before being visited in that order or those keys
that were added without being in the table initially, the ordering
by the time they were last added or deleted as of the end of the
iteration (so they never get visited).

This seems like it would even avoid any GC related problems.