Java – sharing databases between threads

I have an application that is multithreaded and works properly However, it encountered lock contention (looking at the Java stack through a snapshot and looking at what was waiting)

Each thread removes the object from the list and rejects each thread or puts it in bin

The boxes are initially empty because each can be expensive (and there may be many of them)

The code causing contention is roughly as follows:

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 synchronization on the bottleneck array, which is the bottleneck

A colleague suggested to me to use double locking to solve this problem, but we are not sure what it will involve to make it secure The proposed solution is as follows:

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 or / or is there a better / safer / more conventional way to do this?

Solution

As stated in malt's answer, Java has provided many lockless data structures and concepts that can be used to solve this problem I want to add a more detailed example using atomicreferencearray:

Assuming that bins is an atomicreferencearray, the following code performs an idle update to prevent entries:

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 has been a more elegant solution:

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

Node: because, in fact, updateandget will always update the array even if the value does not change, the Java 8 version is still in a non blocking state This may or may not be negligible, depending on the overall cost of the entire bin update operation

Another elegant strategy might be to pre fill the entire bin array of the newly created bin instance, and then hand over the array to the worker thread Since threads do not have to modify the array, this reduces the need to synchronize with the bin object itself By using arrays Parallelsetall (starting with Java 8) can easily complete array filling multithreading:

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

Update 2: if this is an option, it depends on the expected output of your algorithm: eventually fill the array completely, densely or just sparse? (in the first case, pre filling is desirable, in the second case, it depends on this situation, and in the latter case, this may be a bad idea)

Update 1: do not use double check locking! It's not safe! The problem here is visibility, not atomicity In your case, the read thread may partially construct (and therefore corrupt) the bin instance See details http://www.cs.umd.edu/ ~pugh/java/memoryModel/DoubleCheckedLocking. html.