Note that the scales are different for the 2 graphs. Looks like TCC performs about the same for HashMap and Balanced Tree; coarse locks have worse performance in Balanced Tree because there might be more collisions, while HashMap distributes the elements evenly so it's better.

As @haiyuem mentioned above, the scales are different for the 2 graphs where for balanced tree, the performance with fine locks has much higher execution time at the beginning. I think one thing that contributed to this might be when the root of the tree is locked, no other lock can proceed on the tree from the root whereas the lists within a hashmap is more distributed and there is no single point of bottleneck.

I wonder what will happen to the graph if there are different lock sets for read and write in the two cases of locks - will that improve the performance of locks? Or, is that equivalent to transaction?

@orz I'm also curious about this. I assume that there would be more locking overhead, but this seems like it would increase parallelism, so it may be possible for performance to improve on certain workloads. Since transactions follow a similar locking approach, I'm curious if there's any difference as well.