Previous | Next --- Slide 14 of 66
Back to Lecture Thumbnails
yey1

I was wondering why the execution on balanced tree with coarse locks is faster than fined locks one when we have few processors.

bob_sacamano

Probably because the hash-map requires one lock in the critical path (the lock for the selected bucket) and the balanced tree implementation uses "hand-over-hand" locking that would encounter O(log n) locks along the critical path. Since lock acquisition isn't very cheap even under low contention I would believe acquiring a single lock would offer better performance than acquiring O(log n) locks. I guess the benefits of fine-grained locking would appear once we have more threads, as they can collectively make progress along different paths concurrently?