CodeBlab

We have all been there. Multiple threads, many objects, and than you realize you need per-object locking. Maybe you should add a mutex to each and every object, but there are many objects and collisions are rare. So, you should use a linked list with a 4-tuple node: {mutex, count, &object, &next}. Before you use an object, lock the list, see if the object is in any node: if yes, increment the count, if no, create a node with a count of 1. In either case get a pointer to the mutex and unlock the list. Now lock the node, using the pointer to the mutex and do it to the object. After which you lock the list again and either decrement the count or delete the node. Implementing that won’t be hard, just follow the doodle you just made while inserting imaginary objects A, B, A, and C (on the right). But you feel you can do better: collisions of the same object are rare but collisions of unrelated objects run rampant. You realize locking and searching the list might become a bottleneck. How about chopping the linked list into chunks with a hash array? You doodle some more (on the left). A little more complex, but doable. Given a large enough hash array, the list chunks will be seldom longer than one. Than you realize that you can give each list chunk its own mutex. And than you get that special feeling. You know the one I mean. Utter happiness hits you: Why not just fill the hash array with mutexes only? You can’t help but drawing it out (to the right), just to prolong that nice feeling. What a world, what a life, you are in love. Well, maybe not “in love” but your ventral tegmental floods your caudate with dopamine like there is no tomorrow. If you read this far, you know I am not joking.