Linas Vepstas <linasveps...@gmail.com> 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
