Ordered Lists and Thread Safety Class

Question

I have a class that has:

• 2 fields containing a time-ordered list (list1, list2).
• 3 read-only methods that iterate over lists to generate summary statistics.
• 1 mutating method that searches for a match for a given “new item” in list1. If no match is found, it adds the "new item" to list1. If a match is found, it removes the match from list1 and adds both match and 'new-item' to list2.

Suppose that multiple methods can be called simultaneously. I need to ensure thread safety at maximum performance.

Approach1 (extremely slow) . Declare field types as ArrayList and use the synchronize keyword for all methods.

Approach2 . Declare the field type as CopyOnWriteArrayList and synchronize the mutating method.

Questions

• Does Approach2 provide thread safety?
• Are there any better alternatives?

Answer 1

Do you need random access offered by ArrayList? Instead, can you use a stream-ordered collection like ConcurrentSkipListSet (non-blocking) or PriorityBlockingQueue (lock)? Both have log (n) inserts.

Mutation methods in both cases are thread safe.

Edit: Just notice, you will still encounter atomic issues. If you want the addition to be done automatically, you will need a tougher lock.

Answer 2

Approach No. 2 does not guarantee flow safety.

Two operations on sets are not atomic: first you delete the item, then add it to another collection. Some threads may, in the meantime, execute a read-only method to find out that the item is not in list 1 and has not yet been added to list 2. It depends on your application if this is valid.

On the other hand, it is also possible that: the read-only method iterates over list 1 first and finds that it contains the element x; at the same time, the update method executes and passes the x element; the read-only method continues and is repeated through list 2, in which it finds element x another element. Again, this depends on your application, whether it is permissible.

Other solutions are possible, but this will require more detailed information about what you are trying to achieve.

One obvious way would be to change the number 1 approach, and instead of using synchronization for each method, use read-write lock. You will block reading in each read-only mode and block writing in mutant mode.

You can also use two separate read-write locks. One for the first collection and one for the other. If your read-only methods are repeated on both lists, they will have to read - get both locks in front before doing anything. On the other hand, the mutation method would first have to write-get the first lock, and if it wants to pass the element, then it should write-get the second lock.

You will need to do some testing to see if it works well for you. However, there are even better ways to handle this, but you need to provide more details.

Answer 3

Method lock time is less than microsecond. If the fraction of a microsecond is important, you can think of something more complex, otherwise something simple is usually better.

Just using streaming security is not enough if you perform several operations, for example. remove from one list and add two operations to another, and any number of threads can fall between these operations.

Note. If you do a lot of updates, it might be slower.