aspose file tools*
The moose likes Java in General and the fly likes Collection iteration strategy Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Soft Skills this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Collection iteration strategy" Watch "Collection iteration strategy" New topic
Author

Collection iteration strategy

Mr. C Lamont Gilbert
Ranch Hand

Joined: Oct 05, 2001
Posts: 1170

I am having trouble with my collecitons. My program exists in a multithreaded environment so I must protect them. So access to modify the collection is synchronized. But iteration is a form of access, and iteration is not synchronized. Even on Collections.synchronizedXXX the iteration is not synchornized.

My collections are not meant to be modified outside of their parent. so iterator#remove will not be used.

So at this point I see 3 options.

1. Don't return iterators, but return a copy of the Collection. Or return an iterator over a copy of the collection. Where the copy was created while the collection was locked.

2. create a locking scheme that locks the collection while one iterates over it, and then release the lock when one is done iterating. This is cheaper since i won't have to copy the collection.

3. If concurrent modification exception is thrown during iteration, catch it and restart the iteration. But this seems unsafe as the exception unexplainably is best effort!?

I used to return arrays instead of collecitons. In anticipation of a move to 1.5 i started returning collecitons. Plus with arrays you can only be sure of what will come out of it, not what you can put into it. With generics there will be safety both ways. But here these collections are intended to be unmodifiable (or return copy) and nothing can be put into them.

There is only 1 use for the returned collections and that is to see all the elements in it.

Looking for the cheapest way. Of course it has to be 100% safe.

Any tips here? Thanks in advance
[ November 06, 2005: Message edited by: Mr. C Lamont Gilbert ]
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

If you use Collections.synchronizedList() and you lock the List while iterating, then iteration is synchronized, so that's an easy way to do #2.

Returning a iterator over an immutable copy of the list is another valid solution, and I've used that. Copying a list, especially an ArrayList, isn't very expensive.

Swing uses a cheap scheme to do event notification in the case that the event listener collection might be modified reentrantly, as opposed to from another thread: it does the iteration using get() instead of iterator(), and it counts backwards.

#3 is rarely a good option because, as you say, many times your operation won't be an idempotent one.


[Jess in Action][AskingGoodQuestions]
Mr. C Lamont Gilbert
Ranch Hand

Joined: Oct 05, 2001
Posts: 1170

idempotent. There is a word I havent heard on 20 years

I discovered the visitor pattern is a great option here. I love it when I get to find a solid reason to use a pattern. So instead of handing out a collection, i'll accept a visitor that will visit each member of the collection. This way I can lock the visit session and it works out great! Its really a form of #2.
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

Originally posted by Mr. C Lamont Gilbert:
idempotent. There is a word I havent heard on 20 years


I'm pretty sure I larnt it from the HTTP specification. GET is for idempotent requests, POST for things that oughtn't be repeated.
Jeff Albertson
Ranch Hand

Joined: Sep 16, 2005
Posts: 1780
I seem to be making this suggestion often, recently. Since you are moving to 1.5,
you should definitely check out java.util.concurrent.CopyOnWriteArrayList.
I don't know what your context is, but it works great for maintaining listener lists,
or any situtation where you rarely modify the list but often access it, for
example, iterate over it without modification. Its iterator will not throw
a ConcurrentModificationException and it does this without locking the list
during iteration, so it is not a scalibility bottleneck. Even if you are not
using the current version of Java, you can grab the source code and make it
your own.

Here is an article about it from Brian Goetz: Java theory and practice: Concurrent collections classes.


There is no emoticon for what I am feeling!
Mr. C Lamont Gilbert
Ranch Hand

Joined: Oct 05, 2001
Posts: 1170

Copy on write seems interesting. I do have listeners and I handle them differently than my other collections since nobody will ever ask for the list of listeners. I copy on use rather than copy on write. it is true however that its used a LOT more than it is changed.

The copy is performed within synchronized block, and the new list is iterated over outside of the synchronized block. I don't like to fire events from within synch blocks. So if I had copy on write, i would still have copy on fire anyway.

Or maybe not. All I need to do is synch when I create the iterator. The set can be changed once i create the iterator and i need to synch to ensure i get the latest collection. Ill give that a shot.
JuanP barbancho
Ranch Hand

Joined: Oct 25, 2005
Posts: 52
Hi,

I think that you need reading as fast as possible and you write to the collection only a few of times.

I think that you could use a internall Object flags that have different values, by example, READING, WRITING, HAVEWRITED, HAVEREAD etc.

You could make a system that in reading mode enable the concurrent read of the collection, in writing make a queue of the rest, in havewriting ....
you only finish to start writing ...

Is most complex, but you could reading in most than 1 thread.
Jeff Albertson
Ranch Hand

Joined: Sep 16, 2005
Posts: 1780
Originally posted by JuanP barbancho:
...
I think that you could use a internall Object flags that have different values, by example, READING, WRITING, HAVEWRITED, HAVEREAD etc.


Rather than reinventing the wheel, read the source code for CopyOnWriteArrayList.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Collection iteration strategy