AtomicBoolean (or any other of the atomic family) does not guarantee synchronization with a different variable. so no. the code does not guarantee that when data is modified, you will get isDirty()==true. The only guarantee you have is that all threads always see the same value of isDirty(). in fact, neither of the options listed make that guarantee.

the only way to make the guarantee is to have exclusive lock on the whole code block inside the set method: the if statement together with the assignment. this can be achieved with synchronized keyword (either on the method or in a code block) or use one of the locking mechanisms in java.util.concurrency

Several notes about your solution with AtomicBoolean.

What kind of thread-safety do you look for? I don't see why do you care that much about read-write ordering of dirty flag. Get/set operations for this flag might be perfectly ordered in time and still result in races.

Race condition

In both your examples I see a race condition between setValue and isDirty:

1. Thread 1 calls setValue, updates dirty flag and preempts to Thread 2 before setting data[index] = value.
2. Thread 2 calls isDirty, it returns true, but the array data is not updated yet, because Thread 1 was preempted.
3. If Thread 2 proceeds with actions on dirty array, e.g. copy it to another location, the copy would be non-coherent with the array in memory after Thread 1 resumes execution with data[index] = value.

Changing the order of operations solves this race, but introduces another one.

    public void setValue(int index, byte value) {
        data[index] = value;
        dirty = true;
    }

Consider the following sequence:

1. Thread 1 sets value at index 0. Flag dirty became true.
2. Thread 1 started setting value at index 1. data[1] = value got executed, and Thread 1 is preempted just before dirty = true.
3. Thread 2 check the flag and syncs the array to disk.
4. Thread 1 resumes execution, and sets the dirty flag.

The race is that the array is coherent with an external copy, but marked as dirty. This race might lead to excessive copy operations.

AtomicBoolean operation

Your use of AtomicBoolean is non-atomic. A thread could be preempted just between conditional and then statement. The atomic equivalent of the if construct used by you is dirty.compareAndSet(false, true);.

Actually, you don't need it this way. dirty.set(true) is sufficient since you uncoditionally set the dirty flag upon update any value.

But the sad story is that even AtomicBoolean.set doesn't save from the race condition. Thread could be preempted just between setting the dirty flag and updating the data. The race condition described above doesn't depent on atomicity of flag update.

Synchronized

Since the very beginning Java provides a pattern exactly for this case: synchronized.

public class SyncronizedDirtyArray {
    private byte[] data;

    public SyncronizedDirtyArray (byte[] data) {
        this.data = data;
    }

    private boolean dirty = false;

    public synchronized void setValue(int index, byte value) {
        dirty = true;
        data[index] = value;
    }

    public synchronized boolean isDirty() {
        return dirty;
    }
}

synchronized ensures that no thread can interfere between dirty = true; and data[index] = value;.

It might be slower compared to unsynchronized solution, but saves you from the race conditions. Try this solution with your benchmarks.

UPDATE: Benchmark

I made my own benchmark, very simple, but revealing.

I impemented several variants of DirtyArray with different sync primitives.

• DirtyArrayNoSync: the plain implementation without any sync
• DirtyArraySync: using synchronized
• DirtyArrayLock: using ReentrantLock
• DirtyArrayVolatile: using volatile boolean
• DirtyArrayAtomic: the implementation from the topic starter
• DirtyArrayAtomicSet: using AtomicBoolean.set and AtomicBoolean.get

The benchmar was to call setValue for every element in the array with 100 mln elements. The output is duration in milliseconds.

Configuration: OpenJDK 11.0.6, Core i7, Windows 10 Home

org.example.sync.DirtyArrayNoSync: 112
org.example.sync.DirtyArraySync: 2222
org.example.sync.DirtyArrayLock: 16752
org.example.sync.DirtyArrayVolatile: 7555
org.example.sync.DirtyArrayAtomic: 7591
org.example.sync.DirtyArrayAtomicSet: 3066

Yes, syncronization makes it 20 times slower, but it is the second fastest solution. All others, even with AtomicBoolean, are slower.

UPDATE 2.

Benchmark for jdk-14.0.1 showed practically same results:

org.example.sync.DirtyArrayNoSync: 102
org.example.sync.DirtyArraySync: 2323
org.example.sync.DirtyArrayLock: 16801
org.example.sync.DirtyArrayVolatile: 7942
org.example.sync.DirtyArrayAtomic: 7984
org.example.sync.DirtyArrayAtomicSet: 3320

I think that Sharon's answer has nailed it. All attempts to solve this using volatile or Atomic* classes will lead to race conditions where either isDirty() returns true before the array updates can be seen OR array updates can be see when isDirty() returns false.

The solution is to use locking. (In this case, primitive locking should be fastest. Pak's benchmarking seems to confirm this.)

But what I really wanted to say that you may well be worrying too much about the concurrency overheads of locking versus atomic types / volatile. In real applications, locking is a concern if the lock is contended, either because their are lots of threads trying to use it, or because the lock is held for a long time.

In this example, the second does not apply, a lock is likely to be held for 10 or less machine instructions. But the flipside is that your benchmark does not look remotely realistic.

• If you were going to use the DirtyArray class like that, you would be better off with a setValue method that sets multiple values in one call.
• If not ... you are most likely triggering far more cache flushing, etc than you would see in real life.

Another alternative is that you could relax your requirements. For example, does your application actually require isDirty() to correct at all times? If not, your initial solution may be good enough.

Finally, one thing that bugs be about your problem is how your application could make use of the strong consistency properties of the isDirty flag:

• Suppose that you want to know if the array is dirty so that you can do something with the updated values in their current state. That implies that you need to stop the updates, but there is nothing in your class that will do that.

• Suppose that you want to know if the array is dirty to determine if it (still) needs to be updated. Consider this attempt at doing this:

  if (!da.isDirty()) {
      da.setValue(...);
  }
  

  There is a race condition in the above. Some other thread could jump in between the test and the setValue and make is own setValue call. So you would end up with two changes to the array.

Maybe the real version of this class has a more complicated API and/or other use-cases. But if that is so, I am not convinced that lessons learned from this question will translate into the more complicated problem.

You could try to use AtomicReferenceArray (see docs here). This array provides you guarantees with respect concurrent access.

I found an example of usage here which I copy-paste here for you to try:

import java.util.concurrent.atomic.AtomicReferenceArray;

public class TestThread {
   private static String[] source = new String[10];
   private static AtomicReferenceArray<String> atomicReferenceArray 
      = new AtomicReferenceArray<String>(source);

   public static void main(final String[] arguments) throws InterruptedException {

      for (int i = 0; i<atomicReferenceArray.length(); i++) {
         atomicReferenceArray.set(i, "item-2");
      }

      Thread t1 = new Thread(new Increment());
      Thread t2 = new Thread(new Compare());
      t1.start();
      t2.start();

      t1.join();
      t2.join();        
   }  

   static class Increment implements Runnable {
      
      public void run() {
         
         for(int i = 0; i<atomicReferenceArray.length(); i++) {
            String add = atomicReferenceArray.getAndSet(i,"item-"+ (i+1));
            System.out.println("Thread " + Thread.currentThread().getId() 
               + ", index " +i + ", value: "+ add);
         }
      }
   }

   static class Compare implements Runnable {
      
      public void run() {
         
         for(int i = 0; i<atomicReferenceArray.length(); i++) {
            System.out.println("Thread " + Thread.currentThread().getId() 
               + ", index " +i + ", value: "+ atomicReferenceArray.get(i));
            boolean swapped = atomicReferenceArray.compareAndSet(i, "item-2", "updated-item-2");
            System.out.println("Item swapped: " + swapped);
            
            if(swapped) {
               System.out.println("Thread " + Thread.currentThread().getId() 
                  + ", index " +i + ", updated-item-2");
            }
         }
      }
   }
}

Output:

Thread 9, index 0, value: item-2
Thread 10, index 0, value: item-1
Item swapped: false
Thread 10, index 1, value: item-2
Item swapped: true
Thread 9, index 1, value: updated-item-2
Thread 10, index 1, updated-item-2
Thread 10, index 2, value: item-3
Item swapped: false
Thread 10, index 3, value: item-2
Item swapped: true
Thread 10, index 3, updated-item-2
Thread 10, index 4, value: item-2
Item swapped: true
Thread 10, index 4, updated-item-2
Thread 10, index 5, value: item-2
Item swapped: true
Thread 10, index 5, updated-item-2
Thread 10, index 6, value: item-2
Thread 9, index 2, value: item-2
Item swapped: true
Thread 9, index 3, value: updated-item-2
Thread 10, index 6, updated-item-2
Thread 10, index 7, value: item-2
Thread 9, index 4, value: updated-item-2
Item swapped: true
Thread 9, index 5, value: updated-item-2
Thread 10, index 7, updated-item-2
Thread 9, index 6, value: updated-item-2
Thread 10, index 8, value: item-2
Thread 9, index 7, value: updated-item-2
Item swapped: true
Thread 9, index 8, value: updated-item-2
Thread 10, index 8, updated-item-2
Thread 9, index 9, value: item-2
Thread 10, index 9, value: item-10
Item swapped: false

I'd consider other options.

First, you should't use finalizers, cleaners or reference queues to implement such application requirements. For instance, although unlikely, someone can use a no-gc JVM instance. On a more practical matter, there's no guarantee that finalizers, cleaners and reference queues will run when the application is exiting.

You should use other mechanisms, such as parallel streams and/or completable futures, to handle this. You can actually use both approaches.

Then, you're locking or atomically updating on every pixel operation, which will without a doubt add a significant overhead. You should definitely make it more coarse and handle a bunch of pixels at a time. Although at first it seems like many of the embarrassingly-parallelizable algorithms could be run in parallel on each pixel, the truth is that doing so may add even more overhead.

You could have something in your library that allows configuring about how few pixels are worth the overhead of parallelizing work. Perhaps even have a benchmarking method that would try a binary search of time taken to process pixels sequentially and in parallel, until it finds an amount where the total parallel time is lower than sequential, and perhaps the overhead is low enough to justify, given a degree of parallelism.

In this particular case, if you target the same array, you may be victim of false sharing, where you might see worse performance due to frequent cache line invalidation. So, your benchmark may hopefully find a value very close to the cache line size.

You can't get a better than linear speedup. An n-core machine can't run better than 1/n the original sequential time, due at least to synchronization and cache invalidation, and generally to everything else that the machine is doing. Perhaps an overhead of about 1% to 5% might be good enough, for instance, a 2-core machine running the parallel approach in 52% of the sequential time.

Anyway, I believe you should definitely rethink this approach in these 2 points: not relying on GC to store your data, and having coarser operations properly synchronized. I'm assuming your operations are totally independent from each other, because otherwise this isn't about embarrassingly-parallel algorithms.

It seems to me as if the dirty flag is only changed from false to true. If it is set to true, it will never be reset.

If you, as you suggest in your question, believe to manage the visibility of changes to other threads with other means than synchronization and volatility, would it not suffice if you synchronize around the state change of the dirty flag with something like this:

public void setValue(int index, byte value) {
    if (dirty) {
        data[index] = value;
    }
    else {
        synchronized(this) {
            dirty = true;
            data[index] = value;
        }
    }
}

This way, the synchronized overhead will only apply for the first method call and following method calls will be much faster. Just to make sure that I have pointed it out: With this code, modifications of the data array are not immediately visible to other threads.

If you want to make sure that changes to the data array are visible to other threads, you might consider further access methods, which are not only updating a single byte, but e.g. filling ranges with a given value or copying ranges from a source array like:

void fill(byte value, int offset, int length);
void setValue(byte[] source, int offset, int length);

With such methods, you might be able to properly synchronize and propagate changes without too much extra impact on the runtime.

You should also consider if this level of synchronization is good enough for other purposes as well. Your benchmark is perhaps not representative for real usage, but if you are updating the content of a DirtyArray by setting one byte at a time and you usually update several bytes at once, do you want other threads to access the object and see a partially updated byte array?

So as you might know from the definition of the volatile variable it values is always visible to all threads.

Why volatile usually used wrong: what people usually mess up with a volatile, that they can't update it atomically without race conditions.

Let's take a counter as an example:

class Counter {
  volatile int counter = 0;

  void incrementCounter() {
    counter = counter + 1; 
  } 
}

This wouldn't work, because there are 2 different operations that are happening with a counter: read and write. And if there is something happen to the value between reading and write counter will lose that value:

1. read counter inside the function | value is 100
2. counter is changed in other thread/place | value is 105
3. increment the counter value and write it back | value is 101

Volatile in your code

You DON'T have read and write operations over the flag in one place, so your code in setValue is already atomic.

Also, there are no issues with concurrency between writing and reading from volatile variables in your code. According to the JMM, writing and reading from volatile variables are sententially consistent, so you don't need to do any actions to synchronize it.

Fixing performance

As you noticed volatile might be slower than nonvolatile.

Because volatile is synchronized between threads, JVM has to do some extra work. But the good part that it's done during the write operation. So if you add the read check before modification it should make it faster.

I'll keep it short and concise.

You can go for either (1) synchronized methods to modify and/or read your boolean field, or (2) just use AtomicBoolean, which is inherently thread-safe.

You could use an approach similar to what AtomicMarkableReference does.

public class DirtyArray {
    private final Cell[] cells;

    public DirtyArray(byte[] data) {
        cells = new Cell[data.length];
        Arrays.setAll(cells, i -> new Cell(data[i], false));
    }

    public void setValue(int index, byte value) {
        Cell cell = cells[index];
        if (cell.value != value || !cell.dirty) {
            cells[index] = new Cell(value, true);
        }
    }

    public boolean isDirty() {
        for (Cell cell : cells) {
            if (cell.dirty) {
                return true;
            }
        }
        return false;
    }

    private static class Cell {
        final byte value;
        final boolean dirty;

        Cell(byte value, boolean dirty) {
            this.value = value;
            this.dirty = dirty;
        }
    }
}