Re: Locks and threads

[Clinton Ebadi]

Linas Vepstas <address@hidden> writes:

> An alternative idea is to try to apply some principles from
> functional programming, e.g. "copy on write" (COW): when
> the obarray needs to be updated, make a copy of it. Any
> readers in other threads continue to safely use the
> original version. When the new obarray is fully constructed,
> new readers will use it.  The old obarray is garbage-collected
> in due time.  I dunno if this could be applied for this case;
> at least we have garbage collection, which removes one
> major stumbling block for using COW.

If the obarray were implemented as a persistent tree instead of hash
table you wouldn't even need to copy it--the only operation that would
need to be atomic would be committing the change--swap the pointer to
the root, but only if the current root is the same as when you started
modifying the obarray; otherwise merge your changes into what is
presently the root if it changed in the meantime (alternatively, lock
around the entire insertion/replace block).

Lookup time would be increased from amortized O(1) to O(logN) and
generate a bit of garbage on every insert (depth(tree) nodes), but
minimizes potentially expensive locking (e.g. if multiple concurrent
readers are allowed while writing to the hash table you have to handle
locking everyone out when the table needs rehashing--with the persistent
tree approach readers *never* block). I suppose the best way to find out
would be to implement it, and I may do so as an experiment (it would
require modifying some C, however, which I am not so inclined to use for
a mere thought experiment).

-- 
Lindsay (Carlton): should i eat more post its