Two reasons why fine locks in Balanced Tree need more execution time than coarse locks: 1. Need to acquire more locks (1 vs number of height) 2. acquiring lock at certain sequence (i.e. acquire lock of child before release the lock of the node itself)
thunder
Another reason is that since hand-over-hand locking is used, for each lock sequence, the root node will always be locked first and then the two child nodes and so on which will lead to less parallelism when the number of processor is more than 1.
jocelynh
On the other hand, locking an entire hash table at each access will lead to more contention on the lock than a fine-grained lock (one per bucket) which means that it will consistently perform worse, since only one lock is grabbed per access in either case.
shreeduh
A tree is an organized data structure to allow fast serial traversal, and in a lock free environment gives O(log(n)) traversal. So locking the entire data structure, and allowing for O(log(n)) run time is more effective than going for a fine grained locking in each case, adding to traversal overhead.
Two reasons why fine locks in Balanced Tree need more execution time than coarse locks: 1. Need to acquire more locks (1 vs number of height) 2. acquiring lock at certain sequence (i.e. acquire lock of child before release the lock of the node itself)
Another reason is that since hand-over-hand locking is used, for each lock sequence, the root node will always be locked first and then the two child nodes and so on which will lead to less parallelism when the number of processor is more than 1.
On the other hand, locking an entire hash table at each access will lead to more contention on the lock than a fine-grained lock (one per bucket) which means that it will consistently perform worse, since only one lock is grabbed per access in either case.
A tree is an organized data structure to allow fast serial traversal, and in a lock free environment gives O(log(n)) traversal. So locking the entire data structure, and allowing for O(log(n)) run time is more effective than going for a fine grained locking in each case, adding to traversal overhead.