Java ArrayList's set thread-safety

Question

I have a usecase where multiple threads can be reading and modifying an ArrayList where the default values for these booleans are True.

The only modification the threads can make is setting an element of that ArrayList from True to False.

All of the threads will be also reading the ArrayList concurrently, but it is okay to read staled values.

Note: The size of the ArrayList will not change throughout the lifetime of the ArrayList.

Question:

Is it necessary to synchronize the ArrayList across these threads? The only synchronization I'm doing is marking the ArrayList as volatile such that any update to it will be flushed back to the main memory from a thread's local memory. Is this enough?

Here is a sample code on how this ArrayList gets used by threads

myList is the ArrayList in question and its values are initialized to True

if (!myList.get(index)) {
   return;
} else {
  // do some operations to determine if we should
  // update the value of myList to False.
  if (needToUpdateList) {
      myList.set(index, False);
   }
}

Update

I previously said these threads do not care about staled values which is true. However, I have another thread that only reads these values and perform one final action. This thread does care about staleness. Does the synchronization requirement change?

Is there a cheaper way to "publish" the updated values besides requiring synchronization on every update? I'm trying to minimize locking as much as possible.

Answer 1

As it says in the Javadoc of ArrayList:

Note that this implementation is not synchronized. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally.

You're not modifying the list structurally, so you don't need to synchronize for that reason.

The other reason you'd want to synchronize is to avoid reading stale values; but you say that don't care about that.

As such there is no reason to synchronize.

Edit for the update #3

If you do care about reading stale values, you do need to synchronize.

An alternative to synchronization which would avoid locking the entire list would be to make it a List<AtomicBoolean>: this would not require synchronization of the list, because you aren't changing the values stored in the list; but reads of an AtomicBoolean value guarantees visibility.

Answer 2

It depends on what you want to do when an element is true. Consider your code, with a separate thread messing with the value you're looking at:

if (!myList.get(index)) {    // <--- at this point, the value is True, so go to else branch
   return;
} else {
  // <--- at this point, other thread sets value to False.

  // do some operations to determine if we should
  // update the value of myList to False.

  // **** Do these operations assume the value is still True?
  // **** If so, then your application is not thread-safe.

  if (needToUpdateList) {
      myList.set(index, False);
   }
}

Answer 3

Update

I previously said these threads do not care about staled values which is true. However, I have another thread that only reads these values and perform one final action. This thread does care about staleness. Does the synchronization requirement change?

You just invalidated a lot of perfectly good answers.

Yes, synchronization matters now. In fact probably atomicity matters too. Use a synchronized List or maybe even a Concurrent list or map of some sort.

Anytime you read-modify-write the list, you probably also have to hold the synchronized lock to preserve atomicity:

synchronized( myList ) {
    if (!myList.get(index)) {
       return;
    } else {
      // do some operations to determine if we should
      // update the value of myList to False.
      if (needToUpdateList) {
          myList.set(index, False);
       }
    }
}

Edit: to reduce the time the lock is held, a lot depends on how long "do some operations" take, but a CocurrentHashMap reduces lock contention at the cost of some additional overhead. It might be worth profiling your code to determine the actual overhead and which method is faster/better.

ConcurrentHashMap<Integer,Boolean> myList = new ConcurrentHashMap<>();
//...

if( myList.get( index ) != null ) return;
   // "do some opertaions" here
if( needToUpdate )
   myList.put( index, false );

But I'm still not convinced that this isn't premature optimization. Write correct code first, fully synchronizing the list is probably fine. Then profile working code. If you do find a bottleneck, then you can worry about whether reducing lock contention is a good idea. But probably the code bottleneck won't be in the lock contention and will in fact be somewhere totally different.

Answer 4

I did some more googling and found that each thread might be storing the values in the registry or the local cache. The specs only offer some guarantee on when data would be written to shared/global memory.

https://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.5

basically volatile, synchronized, thread.start(), thread.join()...

So yeah using the AtmoicBoolean will probably be the easiest, but you can also synchronize or make a class with a volatile boolean in it.

check this link out: http://tutorials.jenkov.com/java-concurrency/volatile.html#variable-visibility-problems