2

To use intrinsic locking in Java you do

Object o = new Object()
...
sychronized (o) {
 ...
}

So one monitor already requires one Object i.e. 8 bytes or 16 bytes for 64bit (or 12 bytes for compressed ops and 64bit).

Now assume you want to use lots of these monitors e.g. for an array which one can synchronize over certain areas and that has better concurrency (entry based) than Collections.synchronizedList. Then what is the most efficient way to implement this? Could I somehow use 2 nested locks for 4 entries or 3 for 8 etc? Or could I make use of "one lock per thread" e.g. in a ConcurrentHashMap<array_index, lock>?

Community
  • 1
  • 1
Karussell
  • 17,085
  • 16
  • 97
  • 197
  • If you have an array of references, and the array object itself doesn't need synchronization, but only the individual reference values in the cells of the array, then what are you synchronizing/locking? [Reference values are atomic](http://stackoverflow.com/a/2576542/5221149), so you don't need synchronization for that, so are you doing it to establish happens-before barriers, or what? – Andreas Sep 07 '16 at 21:59
  • This isn't my use case. I have multiple int or byte values in an array which I have to handle as 'one object'. E.g. assume you have a huge list of coordinates (latitude and longitude) then you would waste lots of memory if you would use references. Value types will probably solve this but are not yet available in the JVM. Will clarify this in the post. – Karussell Sep 07 '16 at 22:03
  • 2
    @Karussell have you checked out `StripedLock` ? – Victor Sorokin Sep 07 '16 at 22:07
  • Thanks a bunch! Have not yet heard about it but already sounds good :) ... do you have any links of an explanation? So far can only find source code (jboss etc) ... edit: is this what you meant? http://codingjunkie.net/striped-concurrency/ – Karussell Sep 07 '16 at 22:55
  • By reading the mentioned article this will not help in my case as I already use a similar technique (using the same monitor lock for multiple 'rows') – Karussell Sep 07 '16 at 23:01

2 Answers2

1

Depending on access patterns, you might increase concurrency with fewer locks by segmenting your data structure and using a single intrinsic lock to guard multiple elements. This technique is used in some of the concurrent collections provided in the java.util.concurrent package.

"Could I somehow use 2 nested locks for 4 entries or 3 for 8 etc?" It sounds like you are planning to treat each lock like a bit in the entry index: if the bit is set, acquire the lock; if it's clear, skip it. This won't work. Think about index 0. No locks would be acquired and you'd have no concurrency control.

You could make it "work" by doubling the number of locks (have a "set" and "clear" lock for each bit), but it's still a bad idea because you'd be wasting locks and getting really poor concurrency. The outermost lock would guard half the entries. Any nested locks acquired subsequently would be useless, because other threads are already excluded from that segment.

That takes you back to segmenting your data, with one lock per segment, just like java.util.concurrency does.

erickson
  • 265,237
  • 58
  • 395
  • 493
  • Thanks a lot for trying (or already better understanding) the lock idea with 'bits'. Will have to think about this again :). And yes, using fewer locks via segments I already do but I cannot make this into the extreme, will have to figure out how large my list can get and if segment size is small enough. – Karussell Sep 07 '16 at 23:06
  • Where does `java.util.concurrency` use this segment approach? And could I use one lock per thread with a `ConcurrentMap` ... somehow :) ? – Karussell Sep 08 '16 at 09:47
  • @Karussell `ConcurrentHashMap` used it in Java 7, but it looks like a different approach is used in Java 8, and `Segment` is only retained to support serialization compatibility with old versions. One lock per thread... I don't follow. If each thread only tries to acquire its own lock, it will always succeed and be like there is no lock. I can't guess what you mean. – erickson Sep 09 '16 at 18:14
  • Thanks for the response and sorry for not being too descriptive here. What I meant is if I check a lock (from a `C..H..Map`) for a thread before it 'enters' a specific array index and after 'leaving' one will unlock it and then remove it from the map (to save memory). Which means reading threads will see the same lock and block or enter if `null`. I hoped CHMap could help but fear this is somehow not really possible or very complex to make it still fast (optimistic locking?). But still think there is some data structure with locks proportional to the number of threads not array indices. – Karussell Sep 11 '16 at 21:05
  • 1
    I see. I haven't thought this through or seen a working example of what you describe, but I think it might be possible. I will think about it a bit more. – erickson Sep 11 '16 at 21:17
  • I've thought a bit about this but didn't come to a final conclusion :) http://stackoverflow.com/q/39675003/194609 – Karussell Sep 24 '16 at 09:54
0

To get a monitor, you need an object, so to get the functionality you're after, i.e. locking a set of primitive values, you need an object for the set.

Rather than creating an array of values and treating blocks of values as a set, with a separate Object for the monitor, just create objects for the set of values.

It's the OO way.

Andreas
  • 154,647
  • 11
  • 152
  • 247
  • As explained in the comments, this is not what I'm after. I'm after a memory efficient array or list and for that list I need a memory efficient way for locking :) – Karussell Sep 07 '16 at 22:55