Collections.synchronizedlist() remove element while iterating from end

Question

I am using Collections.Synchronizedlist() to make my arraylist thread safe. What I want to ask is the following code thread-safe i.e. remove while iterating over list from the end:-

pendingExecutionList = Collections.synchronizedList(new ArrayList<>(initialCapacity));

I am creating the list in main thread. and adding to this list from different threads. But, iteration and removal is being done only from a single Scheduled thread as shown below:-

for (int i = pendingExecutionList.size() - 1; i >= 0; i--) 
{
   if (someCondition(pendingExecutionList.get(i))) 
   {
      process(pendingExecutionList.remove(i));
   }
}

The above code is executed by only a single thread while multiple threads are adding to this list.

I want to avoid using iterator over synchronized(list) as that is not fail-safe.

The answer can be found at http://stackoverflow.com/questions/9468187/collections-synchronizedlist-and-synchronized — Sajeev, Apr 18 '16 at 08:11
No, it's not thread-safe.[The javadoc](http://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#synchronizedList-java.util.List-) is extremely clear about it: *It is imperative that the user manually synchronize on the returned list when iterating over it*. — JB Nizet, Apr 18 '16 at 08:12
@ingrid, my question is little bit different as my use case is different. — maveroid, Apr 18 '16 at 09:03

score 3 · Answer 1 · answered Apr 18 '16 at 08:16

3

Instead holding the lock, you are actually obtaining the lock once per element. This has a risk of being slower than just holding the lock while you do your check.

I suggest you consider using a PriorityQueue with an appropriate ordering. This will order the queue so the ones you are about to process next will be at the start and the cost of removal is relatively cheap regardless of the number of waiting tasks.

answered Apr 18 '16 at 08:16

Peter Lawrey

525,659
79
751
1,130

I am not taking lock anywhere. Can you explain? – maveroid Apr 18 '16 at 09:02
1

@maveroid If you are using method on a `Collections.synchronizedList` where all the methods are `synchronized` you are using a lock whether you want to admit it or not ;) – Peter Lawrey Apr 18 '16 at 09:04
Okay, got it but the lock is on add() and remove() not on iteration. Right? – maveroid Apr 18 '16 at 09:05
1

@maveroid yes, and `get()` so this is obtaining and releasing the lock at least once on every iteration. – Peter Lawrey Apr 18 '16 at 09:07
1

@maveroid I am not saying this is undesirable, but it depends on how long your condition and process take. i.e. you might want to be able to add tasks while these are running. – Peter Lawrey Apr 18 '16 at 09:41
yup... I want that – maveroid Apr 18 '16 at 09:44

score 1 · Accepted Answer · answered Apr 18 '16 at 09:04

1

If I'm understanding correctly your workflow pipeline, I would suggest trying some variant of a BlockingQueue instead of a synchronizedList().

ArrayBlockingQueue would allow you to have fair scheduling of the executions and should keep the caches of the multiple producers fairly hot (unless your producers start overtaking the cache prefetcher, in which case you'll experience false sharing).

If you are in the mood for experimenting, you can take a look at the MPSC (multiple producers, single consumer) queues available outside of the JDK, like Nitsan Wakart's MpscArrayQueue or the Disruptor.

answered Apr 18 '16 at 09:04

Dimitar Dimitrov

16,032
5
53
55

But size of list is not fixed. It can grow. Which variant of BlockingQueue would you prefer? – maveroid Apr 18 '16 at 09:33
1

If you are not developing for mobile or embedded environment, chances are that you are able to accommodate an appropriate buffer being allocated on your application start up. Like Martin Thompson (the mechanical-sympathy guy/one of the Disruptor guys) says, unbounded queues are often used as a band-aid that may run the system out of memory (see http://mechanical-sympathy.blogspot.bg/2012/05/apply-back-pressure-when-overloaded.html). Still, if you feel that you are better off with an unbounded queue, you can try `LinkedBlockingQueue` or the non-blocking `ConcurrentLinkedQueue`. – Dimitar Dimitrov Apr 18 '16 at 09:39

Collections.synchronizedlist() remove element while iterating from end

2 Answers2

Linked