There is much overhead on locking/unlocking for fine-grain locks when #processors is small, thus bringing the performance down (compared to coarse locks).

But why is fine-grained lock not producing the same amount of overhead in Hash-Table? I think the amount of locking/unlocking within a Hash-Table would be the same as the amount in Balanced Tree.

Are these hypothetical graphs or is there actual data supporting this? I'm curious what implementation and specs were used to generate the comparisons.

Especially given the conversation at the end of class and the point David brought up on why we don't see more widespread usage.

Why is fine-grain locking a bad option since it's common to have computer with 4 or more cores these days?

@haiyuem re: fine grained lock in hash table vs balanced tree. my guess is that with hash tables, each insertion operation only involves a single locking operation (since we access just one bucket) whereas with a balanced tree, each insertion operations involves potentially many locking operations (one per node that is traversed). Furthermore, each insertion needs to "enter" the tree through the root node, so all tree insertions partially depend on each other, whereas with a hash table, the majority of insertions are completely independent.

@jessiexu I think that if you can achieve similar performance by using coarse-grain locking, then it would be the better option as it has higher chance of correctness over fine-grain locking.

Restating my understanding of this slide, fine locking can sometimes be less productive than coarse locking because of the overhead associated with constantly locking and unlocking locks with a few processors. Coarse locks lock/unlock significantly less and thus incur a significantly smaller overhead.

@ufxela Makes sense. Thank you!