8

I don't know if the question is stupid or not, locking and the Monitor is kind a black box to me.

But I'm dealing with a situation where I can either use the same lock object to lock everything all the time or use a indefinite number of object to lock at a more fine grain level.

I know that the second way will reduce the lock contention, but I may end up using 10K objects as locks and I don't know if it has an impact or not.

Bottom line: does too many locks hurt locking or it has no impact?

Edit

I wrote a lib that maintain a graph of objects, the number could be very high. For now it's not thread safe, mainly for the reason Eric stated in his comment.

I initially thought that if the user wanted to do some multi-threading then he/she would have to take care of the locking.

But now I'm wondering that if I would have to make it thread-safe, what would be the best way to do it (note that making it thread-safe wouldn't be a short and easy ride for me so testing both solutions is something I can't do easily)?

As the purpose is to make each object of the graph thread-safe, then I could use the instance of the object for the lock when I want to access/modify its properties. I know it's the best way to reduce contention, but I don't know if it would scale as much as having only one lock for the whole graph.

I know there's a lot to consider, how many threads and especially (I think) the chance of an object being accessed/changed by multiple threads at a time (which I estimate to be pretty low). But I can't find accurate information about locks and their overhead in such case.

Nock
  • 6,561
  • 1
  • 28
  • 27
  • 2
    The best way to answer your question is to compare the performances between the two solutions. – Cédric Bignon Aug 21 '14 at 21:19
  • There is no way to say in the general case. It'll be highly context specific. It'll depend on how much lock contention you reduce by synchronization at a finer granularity versus how much effort you spend determining which object you should be locking on. That will vary widely depending on how you go about determining what to lock on and the actual contention given your specific data, machine, code, etc. – Servy Aug 21 '14 at 21:38
  • Why would you need 10,000 locks in one application? The reason you need a lock is to update a shared object. Do you have that many global/shared objects? Can they be grouped? – Black Frog Aug 21 '14 at 21:58
  • 4
    If you're asking this question that's evidence that today is a good day to take a step back and ask "what architectural decisions led me to a place where I'm considering making ten thousand lock objects?" **That** is the fundamental problem here; that you are even considering this speaks to some failure of design earlier on, probably starting on the day when someone said "two threads would be twice as awesome as one". Multithreading is most of the time a bad idea, and sharing objects across threads is worse. – Eric Lippert Aug 21 '14 at 22:37
  • @EricLippert this is a lib that maintain an object graph that can reach a very high count. For now the whole thing is not thread safe and is limited to one thread only (mainly because of the two remarks you said). Now I'm wondering how would I proceed to make it thread-safe (if I want it to be)? One lock for the whole graph or using each object of the graph for its own lock to enable changes by many threads? My question is more about understanding the fundamentals of the lock resource and how it scale in theory beside memory. – Nock Aug 21 '14 at 23:58
  • @Nock: So-called "thread safety" is nothing more than simply the statement that certain invariants are maintained when objects are accessed via multiple points of control that are interleaved arbitrarily. The lock strategy you pursue must therefore be informed by the set of invariants you wish to maintain. For example, suppose the graph is nondirected; do you require that the invariant `x.HasNeighbor(y) == y.HasNeighbor(x)` be maintained? If so, that will require a very different locking strategy than a graph which does not require this invariant to be maintained. – Eric Lippert Aug 22 '14 at 17:41
  • Without stating *precisely* which invariants you require to be maintained, it is impossible to say what locking strategy is *correct*, much less which is *adequately performant*. This is why threading is hard; to get it right requires an extremely precise and deep understanding of all the possible interleavings of control and how they interact with *every* invariant. This is why I strongly recommend *against* making complex data structures shared across threads. Frankly, most people cannot get *Booleans* shared correctly across threads, and you want to do arbitrary graphs. – Eric Lippert Aug 22 '14 at 17:43
  • Yes I'm that good! :) Kidding aside, I understand your point, I think an object can be locked only on its own when you change its state, changing the relation between objects is indeed a different matter but I don't think I would end up with dead-locks because I already prevent bad relations that would end up in an infinite loop. The graph always has a direction, if I respect this direction, I think I should be fine. – Nock Aug 22 '14 at 18:03
  • OK, so the graph is directed. That doesn't change my point. Do you want to maintain the invariant that "if B is reachable from A and C is reachable from B then C is reachable from A"? That invariant can be violated in some implementations of multi-threaded graphs and not violated in others; do you consider this invariant part of "thread safety" or not? My point is that in order to be thread safe you first have to *very carefully define what invariants you seek to maintain*. – Eric Lippert Aug 25 '14 at 16:49
  • No I don't need to maintain such thing, every relation between two objects has a direction and you set the relation always from a given part, the opposite object being updated automatically (if the relation on its side is already fetched). I understand your point though and fully agree, I spent more time to write the different Use Cases and invariants than coding right now. I know that porting my lib to MT is a big challenge, I laid the foundation for MT since the beginning but I know it's going to take some time to stabilize the whole thing. – Nock Aug 25 '14 at 20:18
  • If I can get MT working well, I will be able to have the WCF wrapper for remote access of the graph working in Mutli concurrency, right now it's Single only, it doesn't scale as much as my coworkers would like to (but it's easy for them to say so, I am the point that pay the price :)) – Nock Aug 25 '14 at 20:20

3 Answers3

5

To get a more clearer view of what's going on I looked at the source code of the Monitor class and its C++ counterpart in clr/src/vm/syncblk.cpp in the Shared Source Common Language Infrastructure released by Microsoft.

To answer my own question: no, having a lot of locks doesn't hurt in any harmful way I could think of.

What I learned:

1) A lock that's is already taken by the same thread is processed "almost free".

2) A lock that's taken for the first time is basically the cost of an InterlockedCompareExchange.

3) Multiple threads waiting for a lock is fairly cheap to track (a link list is maintained, O(1) complexity).

4) A thread waiting for a lock to release is by far the most costly use case, the implem first spinwaits to try to get out, but if it's not enough a thread switch will occurs, putting the thread to sleep until a mutex signals it's time to wake up because of the lock release.

I got my answer by digging for the 2): if you're always locking with the same object or 10K different one, it's basically the same (extra initialization is performed the first time you lock a given object, but it's not too bad). The InterlockedCompareExchange doesn't care about being called on the same or different memory location (AFAIK).

Contention is by far the most critical concern. Having many locks would reduce (drastically in my case) the chance of contention, so it can only be a good thing.

1) is also an important learned lesson: if I lock/unlock for each property change/access I can improve performances by locking the object first, then changing many properties and release the lock. This way there will be only one InterlockedCompareExchange and the lock/unlock inside the implementation of the property change/access will only increment an internal counter.

To dig deeper I would have to find more information about the implementation of the InterlockedCompareExchange, I think it relies on the CPU specific assembly instruction...

Nock
  • 6,561
  • 1
  • 28
  • 27
4

Typically, performance concerns around locking are related to contention. Acquiring an uncontested lock is on the order of 10s of nanoseconds. Contention is the real performance killer. As you point out, having more locks (higher lock granularity) can improve performance by decreasing contention.

The drawback to having multiple locks is typically lock management must be more complex. If multiple locks are required to perform an operation there is the increased possibility of resource starvation issues like deadlock or livelock. Proper lock management, such as enforcing lock acquisition order, can alleviate these issues.

Absent more details, I would probably go with one lock, since implementation is simpler and monitor performance of my application closely. Specifically there are .NET performance counters related to lock contention which can help diagnose/detect lock contention related perf issues.

Mike Zboray
  • 39,828
  • 3
  • 90
  • 122
0

As with all performance related answers I'd like to refer to this excepional blog post by Eric Lippert, it depends. Have a look at his six questions, what are the answers in your case? Try what happens during your conditions.

Number of cores, contention, caching etc, all matters, so see what happens for you in your case, it's really impossible to know beforehand.

For those not clicking on the link; run them horses!

I'm not talking about performance as in speed here, but rather as in what happens when the application has been running for a while. According to Lock (Monitor) internal implementation in .NET the Monitor implementation is quite smart in .NET, so the having internal locks for each object might seem a viable approach, since you said objects in the tens of thousands and not millions.

Bottom line: does too many locks hurt locking or it has no impact?

Not on it's own, but it might be a reason to have a look at the architecture of your program, having a gazillion objects locked at the same time will cause overhead though.

Community
  • 1
  • 1
flindeberg
  • 4,887
  • 1
  • 24
  • 37
  • 1
    Sorry it's irrelevant for me, my question is not about "which way is faster", I don't even spoke about "fast", I'm just wondering if the count of object I would use as lock could end up being "a bad thing" or not. – Nock Aug 22 '14 at 00:02
  • @Nock The difference between "which is faster" and "has x a negative influence on performance compared to y?"isn't exceedingly clear. – Voo Aug 22 '14 at 08:01
  • @Nock I didn't say fast either, I was talking about performance, since this is so architecture dependent you must test it. I'll edit my answer and see if it makes more sense. – flindeberg Aug 22 '14 at 08:51
  • 1
    It's not because I have gazillion objects that they get locked at the same time, there's no correlation between the object count and the number of thread. I won't have more than one object locked per thread. Which means I may have 10K objects used by 50 threads, so maximum 50 locks at a given time using max 50 different locks among 10K locks possible. – Nock Aug 22 '14 at 11:24
  • Too much opinion surrounding a single link without useful data extracted. Please stick to answering the question, or at least do so as a primary response. – user2864740 Dec 24 '17 at 02:50