• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Collection iteration strategy

 
Ranch Hand
Posts: 1170
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Mr. C Lamont Gilbert
Ranch Hand
Posts: 1170
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Ranch Hand
Posts: 1780
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Mr. C Lamont Gilbert
Ranch Hand
Posts: 1170
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 52
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 1780
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic