Re: Reprise: 'in out' parameters for functions

["Robert I. Eachus" <rieachus@comcast.net>]

Wojtek Narczynski wrote:

> I found no examples of data structures with lock granularity lower
> than the whole data structure.

That is what I would expect you would find.  Why would you expect 
anything different?  For a list you might be able to prepend and append 
at the same time, but the more complex organization just doesn't seem 
worth it.

For trees you can have one lock per object, and insertions, for example, 
would only hold the locks on those nodes needed for the insertion.  From 
experience it is _possible_ but the performance of one lock per data 
structure instance performs much better.  (Look at it this way.  If you 
have one lock per node, then every query needs to start by locking the 
root node, so your transactions are going to be serialized anyway.  As 
long as the whole tree _structure_ is in memory, doing the tree walk 
inside that one lock is more efficient than having to acquire and 
release a dozen locks, even though the first lock will serialize everything.

If you have a situation where you need to lock a node for the duration 
of a transaction, the best choice--again from experience--is to have one 
lock for the tree structure, and one lock for the _contents_ of each 
node.  That way you can have many transactions walking the tree at the 
same time (many readers) but the time consuming part of the transaction, 
which may require waiting for human interaction has a write lock on the 
content, not on the tree.  Deleting or inserting a new node does require 
a write lock on the tree as a whole, but for AVL trees or B-trees the 
difference between that and locking 'just' the part of the tree which is 
potentially changing just isn't worth the extra overhead.

To sum up, in theory there is no difference between theory and practice, 
but in practice there is.

Oh one last observation, it may seem that to do an update of a tree node 
only requires a lock on the node contents, but this is not true in all 
cases.  If the update of the contents changes the key, you have to 
delete the entry from the tree and reinsert it.  This means you want to 
choose a key which is not often changed.  (Just one reason why so many 
things are keyed by SSAN.)


-- 

                                           Robert I. Eachus

"The terrorist enemy holds no territory, defends no population, is 
unconstrained by rules of warfare, and respects no law of morality. Such 
an enemy cannot be deterred, contained, appeased or negotiated with. It 
can only be destroyed--and that, ladies and gentlemen, is the business 
at hand."  -- Dick Cheney