From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,9d303864ae4c70ad X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2004-04-16 09:30:43 PST Path: archiver1.google.com!news1.google.com!news.glorb.com!newsfeed3.easynews.com!easynews.com!easynews!border1.nntp.sjc.giganews.com!nntp.giganews.com!local1.nntp.sjc.giganews.com!nntp.comcast.com!news.comcast.com.POSTED!not-for-mail NNTP-Posting-Date: Fri, 16 Apr 2004 11:30:42 -0500 Date: Fri, 16 Apr 2004 12:30:41 -0400 From: "Robert I. Eachus" User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: Reprise: 'in out' parameters for functions References: <5ad0dd8a.0404090512.15af2908@posting.google.com> <5ad0dd8a.0404091828.6e79bb4e@posting.google.com> <8Oadneu6eY9pweDdRVn-hA@comcast.com> <5ad0dd8a.0404151752.4f598e1a@posting.google.com> <5ad0dd8a.0404160338.5a1c9116@posting.google.com> In-Reply-To: <5ad0dd8a.0404160338.5a1c9116@posting.google.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Message-ID: NNTP-Posting-Host: 24.147.90.114 X-Trace: sv3-qImY+NFDZXs9WIQca6+8W/LjMr6WzG2XzOG8w8m6mK3BA5RhsgqQYJlc2j1uXwQtYmESVG6OPs8VsdI!72sZClMPM+daH+VEAeZJlRZwsUzhRAlZNsg53r8e7rqETLtjh+9R/sph4JU+8Q== X-Complaints-To: abuse@comcast.net X-DMCA-Complaints-To: dmca@comcast.net X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.1 Xref: archiver1.google.com comp.lang.ada:7212 Date: 2004-04-16T12:30:41-04:00 List-Id: 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