Sharing array of bins between threads

Question

I have an application that is multithreaded and working OK. However it's hitting lock contention issues (checked by snapshotting the java stack and seeing whats waiting).

Each thread consumes objects off a list and either rejects each or places it into a Bin.

The Bins are initially null as each can be expensive (and there is potentially a lot of them).

The code that is causing the contention looks roughly like this:

public void addToBin(Bin[] bins, Item item) {
   Bin bin;
   int bin_index = item.bin_index
   synchronized(bins) {
      bin = bins[bin_index];
      if(bin==null) {
        bin = new Bin();
        bins[bin_index] = bin;
      }
   }
   synchronized(bin) {
     bin.add(item);
   }
}

It is the synchronization on the bins array that is the bottleneck.

It was suggested to me by a colleague to use double checked locking to solve this, but we're unsure exactly what would be involved to make it safe. The suggested solution looks like this:

public void addToBin(Bin[] bins, Item item) {
   int bin_index = item.bin_index
   Bin bin = bins[bin_index];

   if(bin==null) {
     synchronized(bins) {
        bin = bins[bin_index];
        if(bin==null) {
          bin = new Bin();
          bins[bin_index] = bin;
        }
     }
   }

   synchronized(bin) {
     bin.add(item);
   }
}

Is this safe and/or is there a better/safer/more idiomatic way to do this?

Answer 1

As already stated in the answer of Malt, Java already provides many lock-free data structures and concepts that can be used to solve this problem. I'd like to add a more detailed example using AtomicReferenceArray:

Assuming, bins is an AtomicReferenceArray, the following code performs a lock free update in case of a null entry:

Bin bin = bins.get(index);
while (bin == null) {
    bin = new Bin();
    if (!bins.compareAndSet(index, null, bin)) {
        // some other thread already set the bin in the meantime
        bin = bins.get(index);
    }
}
// use bin as usual

Since Java 8, there is a more elegant solution for that:

Bin bin = bins.updateAndGet(index, oldBin -> oldBin == null ? new Bin() : oldBin);
// use bin as usual

Node: The Java 8 version is - while still non-blocking - perceptibly slower than the Java 7 version above due to the fact that updateAndGet will always update the array even if the value does not change. This might or might not be negligible depending on the overal costs for the entire bin-update-operation.

---

Another very elegant strategy might be to just pre-fill the entire bins array with newly created Bin instances, before handing over the array to the worker threads. As the threads then don't have to modify the array, this will reduce the needs for synchronization to the Bin objects themselves. Fill the array can be easily done multi-threaded by using Arrays.parallelSetAll (since Java 8):

Arrays.parallelSetAll(bins, i -> new Bin());

Update 2: If this is an option depends on the expected output of your algorithm: Will in the end the bins array be filled totally, densely or just sparsely? (In the first case, pre-filling is advicable. In the second case, it depends - as so often. In the latter case it's probably a bad idea).

---

Update 1: Don't use double-checked-locking! It is not safe! The problem here is visibility, not atomicitiy. In your case, the reading thread might get a partly constructed (hence corrupt) Bin instance. For details see http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html.

Answer 2

Java has a variety of excellent lock-free concurrent data structures, so there's really no need to use arrays with synchronizations for this type of thing.

ConcurrentSkipListMap is a concurrent, sorted, key-value map. ConcurrentHashMap is a concurrent unsorted key-value.

You can simply use one of these instead of the array. Just set the map key be the Integer index you already use and you're good to go.

There's also Google's ConcurrentLinkedHashMap and Google's Guava Cache, which are excellent for keeping ordered data, and for removing old entries.