This discussion is archived
8 Replies Latest reply: Dec 16, 2010 4:59 AM by 800330 RSS

Sorting and CopyOnWriteArrayList

800330 Explorer
Currently Being Moderated
Hi,

Last week I found myself working around the following problem: I have a list of data that is being searched already while new data is still added. Knowing to take care of the dreaded ConcurrentModificationException, I chose the [url http://download.oracle.com/javase/6/docs/api/java/util/concurrent/CopyOnWriteArrayList.html]CopyOnWriteArrayList implementation and I discovered that that class does not play well with Collections.sort():
import java.util.Collections;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class OTNConcurrentArrayListSorting {

     public static void main(String[] args) {
          List<String> l = new CopyOnWriteArrayList<String>();
          l.add("oracle");
          l.add("java");
          Collections.sort(l);
          
     }
}
leads to:
Exception in thread "main" java.lang.UnsupportedOperationException
     at java.util.concurrent.CopyOnWriteArrayList$COWIterator.set(CopyOnWriteArrayList.java:1013)
     at java.util.Collections.sort(Collections.java:121)
     at OTNConcurrentArrayListSorting.main(OTNConcurrentArrayListSorting.java:12)
This came as a surprise to me, but it is documented and after a bit of thinking quite understandable. After all what good is sorting if new elements are added to the list unseen and not taken into account in the sort.

The way I worked around it, is using a binary search to find out where to add the new element and thus keeping the list sorted at all times. Only in preparation of this post, it occurred to me that I'd need the additions to be synchronized for that idea to work, so I ended up with this fragment:
synchronized (revolutions) {
     int i = Collections.binarySearch(revolutions, info);
     if (i < 0) {
          revolutions.add(-(i+1), info);
     } 
}
I am not unhappy with the solution and it serves the purpose, but still I wonder whether there's a better alternative. Any ideas?
  • 1. Re: Sorting and CopyOnWriteArrayList
    802316 Pro
    Currently Being Moderated
    The problem is that CopyOnWriteArrayList is designed to be thread safe.

    The sort operation, by its nature is not thread safe with this class. Without using reflection, the closest you can get is to toArray() the collection, sort that, clear the original and add all the elements with addAll. With reflection you can call the setArray to avoid the clear/addAll.

    However, any elements added/removes while you are performing the sort will be lost.
  • 2. Re: Sorting and CopyOnWriteArrayList
    800330 Explorer
    Currently Being Moderated
    Thanks for the reply. As said I require the thread-safety.

    I had to resort to external sychronization on the add operation, and wondered whether anyone knew of a "better" way than where I ended up to have my multi-threaded sorted list, see above. From the way you've worded your response, I get that you're not advertising it as "better", right?
  • 3. Re: Sorting and CopyOnWriteArrayList
    802316 Pro
    Currently Being Moderated
    A binary search is slower than a hash lookup. If all you need is a fast lookup I suggest you try
    Set<String> set = Collections.newSetFromMap(new ConcurrentHashMap<String, Boolean>());
    This will give you a faster add, remove and contains and doesn't require synchronization as it is already thread safe. You don't have to maintain a sorted collection.

    If you still need a SortedSet, I suggest trying ConcurrentSkipListSet. This is thread safe and always sorted. However it is slower than my suggestion, but much faster than using a sorted CopyOnWriteArrayList.
  • 4. Re: Sorting and CopyOnWriteArrayList
    800330 Explorer
    Currently Being Moderated
    Great suggestion! The list I am maintaining is a sort of index for elements like this, where the number is positive and the interval is a start and end date (the intervals are non overlapping and their sorting goes hand-in-hand with the number):
         /**
          * Packs the revolution number and the date range covered by it,
          * while {@link #compareTo(RevolutionInfo)} orders according to the number. 
          *
          */
         private static class RevolutionInfo implements Comparable<RevolutionInfo>{
              int number;
              Interval span;
              
              @Override
              public String toString() {
                   return "Revolution "+number+" "+ span.toString();               
              }
              
              @Override
              public int compareTo(RevolutionInfo o) {
                   return number - o.number;
              }
         }
    I need to support both a search by number to retrieve the Interval of dates (an exact match, will work very well with the HashMap) and a search by date to get the revolution number. The two are now unified in one piece of search code and two different Comparator implementations.

    I am already maintaining an underlying datastructure in a HashMap, which I could use to improve the by number lookup-performance. By the way, the main (and measured) performance penalty I am trying to avoid is the following. I have a datastructure SkyMap, one per revolution (we'll reach 1000 in a couple of weeks) which I read from a 2 Mb XML-file (which is 400 maps, benchmarked at ~8 maps per second). In one use case, all the maps are alredy pre-loaded and can be served out of memory. In a much rarer use case, the maps are being loaded and a request (get number for a given date) needs to be handled: it's here that I want to remove the overhead of waiting for the entire file to be processed, but go about the business as soon as the SkyMap covering that date is available.
  • 5. Re: Sorting and CopyOnWriteArrayList
    802316 Pro
    Currently Being Moderated
    Can you have the following to do the look up?
    I need to support both a search by number to retrieve the Interval of dates (an exact match, will work very well with the HashMap)
    Use ConcurrentHashMap<Integer, Interval>

    and
    and a search by date to get the revolution number.
    Use ConcurrentHashMap<Interval, Integer>

    I don't see why you need a comparator here.

    Edited by: Peter Lawrey on Dec 14, 2010 9:34 AM
  • 6. Re: Sorting and CopyOnWriteArrayList
    800330 Explorer
    Currently Being Moderated
    and a search by date to get the revolution number.
    Use ConcurrentHashMap<Interval, Integer>

    I don't see why you need a comparator here.
    I think I cannot because I go in with a single date and want to find a "hit" when that date is covered by the interval. Typically the interval spans 3 days, the single date is just a point in time.
  • 7. Re: Sorting and CopyOnWriteArrayList
    800268 Expert
    Currently Being Moderated
    Since you say intervals don't overlap, how about a ConcurrentSkipListMap<Date, MapData> using the start date of the interval as key. Then floorEntry(date) to get a possible matching entry and then check if the interval actually contains the date.

    For number to MapData you'll need a separate map of course but for (only) thousands of entries that shouldn't be too much memory over head.
  • 8. Re: Sorting and CopyOnWriteArrayList
    800330 Explorer
    Currently Being Moderated
    Hi Walter,

    I skipped the SkipList classes but now that you mentioned the ConcurrentSkipListMap, I took an actual look to its documentation. That's a piece of work, that class! Both you and P_L: thanks for taking me around this neighborhood of API's

    Mx