ConcurrentSkipListMap sort on values() not keys() ?

[nnn6-twfe]

Hi,

We have a large J2EE enterprise application, and we make heavy use of the concurrency library. We use ConcurrentHashMap in many places.

One desire we have had was to have a ConcurrentHashMap but also have the values sorted in a default order so that we don't need to sort the results unless a custom sort is required.

We have looked at ConcurrentSkipListMap[K,V], and that seems to do exactly what we want, *except* it sorts based on the keys not the values.

Here is an simplified example of what we would like to do:
 
private class Group {
  int id;
  String name;
}

private final ConcurrentSkipListMap[Integer,Group] mGroups = new ConcurrentSkipListMap[Integer,Group]();

We have approximately 1000 to 10000 of these group objects and we have many threads accessing them concurrently almost 99.999% of time read only, so read/iteration access without locking is very important.
The code has two main code paths, either get a group by integer unique id, or iterating over the entire set.   When iterating over the entire set, we want them to be in a certain order, e.g. the String name of the group.

Group group = new Group(0,"global");
map.put(id,group)

So, the Key is the integer id, and the value is the Group object.

The ConcurrentSkipListMap specification says it sorts by key rather than value.
We could write a custom comparator, but to sort on a field in the Group object, we would have to use the map to look it up, which may cause a problem? I don't know if it's safe to call methods of the map from inside the comparator.

   class GroupComparator implements Comparator
    {

        public int compare(
            Object o1, Object o2
        ) {
            Integer id1 = (Integer) o1;
            Integer id2 = (Integer) o2;
            // referring back to the map while it is sorting the keys
            // may cause problem?
            Group group1 = (Group) map.get(id1);
            Group group2 = (Group) map.get(id2);
            return group1.getName().compareTo(group2.getName());
        }
    }

If anyone can suggest an alternative data structure or solution, or can confirm it is safe for the Comparator to call get() method on the map, I would appreciate it.

Thanks,

-Alex



_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Joe Bowbeer]

ConcurrentSkipListMap is a SortedMap, so the comparator is used for all key comparisons:

"... a sorted map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal."

A comparator that compares values instead of keys will not permit multiple keys to be mapped to the same (or equal) values.

Joe

On Sun, Oct 11, 2009 at 10:40 PM, Alex wrote:

Hi,

We have a large J2EE enterprise application, and we make heavy use of the concurrency library. We use ConcurrentHashMap in many places.

One desire we have had was to have a ConcurrentHashMap but also have the values sorted in a default order so that we don't need to sort the results unless a custom sort is required.

We have looked at ConcurrentSkipListMap[K,V], and that seems to do exactly what we want, *except* it sorts based on the keys not the values.

Here is an simplified example of what we would like to do:

private class Group {
 int id;
 String name;
}

private final ConcurrentSkipListMap[Integer,Group] mGroups = new ConcurrentSkipListMap[Integer,Group]();

We have approximately 1000 to 10000 of these group objects and we have many threads accessing them concurrently almost 99.999% of time read only, so read/iteration access without locking is very important.
The code has two main code paths, either get a group by integer unique id, or iterating over the entire set.   When iterating over the entire set, we want them to be in a certain order, e.g. the String name of the group.

Group group = new Group(0,"global");
map.put(id,group)

So, the Key is the integer id, and the value is the Group object.

The ConcurrentSkipListMap specification says it sorts by key rather than value.
We could write a custom comparator, but to sort on a field in the Group object, we would have to use the map to look it up, which may cause a problem? I don't know if it's safe to call methods of the map from inside the comparator.

  class GroupComparator implements Comparator
   {

       public int compare(
           Object o1, Object o2
       ) {
           Integer id1 = (Integer) o1;
           Integer id2 = (Integer) o2;
           // referring back to the map while it is sorting the keys
           // may cause problem?
           Group group1 = (Group) map.get(id1);
           Group group2 = (Group) map.get(id2);
           return group1.getName().compareTo(group2.getName());
       }
   }

If anyone can suggest an alternative data structure or solution, or can confirm it is safe for the Comparator to call get() method on the map, I would appreciate it.

Thanks,

-Alex

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[nnn6-twfe]

Joe,

Thanks for the reply.

For our use case, each key (group unique integer id), there is one-to-one relationship between the ID and a Group object.  Each Group object is mapped to only one ID. However, what we are sorting on, the Group name, is not guaranteed to be unique. We can have multiple groups with the same name.

After thinking about this more, even if what I suggested could be made to work, the problem is we are iterating over the map.values() not the map.keys(), so it doesn't help that the keys are sorted based on custom comparator.  We would have to iterate over map.keys() and then lookup each value, which wouldn't be efficient.

Currently we just use ConcurrentHashMap so that concurrent lookups of the Group object by unique integer id is fast. Iteration over the group objects through map.values() is also fast.  But the inefficient part is that at a higher layer we end up having to sort the Group objects by name every where they are
displayed in list.  If somehow we could have a data structure that allowed for fast map lookups but also kept the values in sorted order (via Comparator or natural order), that would be the ultimate solution.    We don't care if updates or sorting is relatively slow, since 99.999% of the time there are only reader threads.

This is a generic problem we have throughout our application. We have many different objects like Group object which have the same use case.

In the UI, we have paginated views, so we only show the first 50 rows by default, but in order to figure out which are the first 50 rows, you have to sort all the objects by the sort key, e.g. name.


-Alex

On Sun, 11 Oct 2009 23:04 -0700, "Joe Bowbeer"
<joe.bowbeer@...> wrote:

  ConcurrentSkipListMap is a SortedMap, so the comparator is
  used for all key comparisons:
  "... a sorted map performs all key comparisons using its
  compareTo (or compare) method, so two keys that are deemed
  equal by this method are, from the standpoint of the sorted
  map, equal."
  A comparator that compares values instead of keys will not
  permit multiple keys to be mapped to the same (or equal)
  values.
  Joe

On Sun, Oct 11, 2009 at 10:40 PM, Alex wrote:

  Hi,
  We have a large J2EE enterprise application, and we make heavy
  use of the concurrency library. We use ConcurrentHashMap in
  many places.
  One desire we have had was to have a ConcurrentHashMap but
  also have the values sorted in a default order so that we
  don't need to sort the results unless a custom sort is
  required.
  We have looked at ConcurrentSkipListMap[K,V], and that seems
  to do exactly what we want, *except* it sorts based on the
  keys not the values.
  Here is an simplified example of what we would like to do:
  private class Group {
   int id;
   String name;
  }
  private final ConcurrentSkipListMap[Integer,Group] mGroups =
  new ConcurrentSkipListMap[Integer,Group]();
  We have approximately 1000 to 10000 of these group objects and
  we have many threads accessing them concurrently almost
  99.999% of time read only, so read/iteration access without
  locking is very important.
  The code has two main code paths, either get a group by
  integer unique id, or iterating over the entire set.   When
  iterating over the entire set, we want them to be in a certain
  order, e.g. the String name of the group.
  Group group = new Group(0,"global");
  map.put(id,group)
  So, the Key is the integer id, and the value is the Group
  object.
  The ConcurrentSkipListMap specification says it sorts by key
  rather than value.
  We could write a custom comparator, but to sort on a field in
  the Group object, we would have to use the map to look it up,
  which may cause a problem? I don't know if it's safe to call
  methods of the map from inside the comparator.
    class GroupComparator implements Comparator
     {
         public int compare(
             Object o1, Object o2
         ) {
             Integer id1 = (Integer) o1;
             Integer id2 = (Integer) o2;
             // referring back to the map while it is sorting
  the keys
             // may cause problem?
             Group group1 = (Group) map.get(id1);
             Group group2 = (Group) map.get(id2);
             return
  group1.getName().compareTo(group2.getName());
         }
     }
  If anyone can suggest an alternative data structure or
  solution, or can confirm it is safe for the Comparator to call
  get() method on the map, I would appreciate it.
  Thanks,
  -Alex
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Dimitris Andreou]

2009/10/12  <nnn6-twfe@...>:
> After thinking about this more, even if what I suggested could be made to work, the problem is we are iterating over the map.values() not the map.keys(), so it doesn't help that the keys are sorted based on custom comparator.  We would have to iterate over map.keys() and then lookup each value, which wouldn't be efficient.

Iterators of map.values() and map.keySet() are in the same order (the
order of keys), quite naturally.

Dimitris

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Gregg Wonderly-2]

nnn6-twfe@... wrote:

> Joe,
>
> Thanks for the reply.
>
> For our use case, each key (group unique integer id), there is one-to-one relationship between the ID and a Group object.  Each Group object is mapped to only one ID. However, what we are sorting on, the Group name, is not guaranteed to be unique. We can have multiple groups with the same name.
>
> After thinking about this more, even if what I suggested could be made to work, the problem is we are iterating over the map.values() not the map.keys(), so it doesn't help that the keys are sorted based on custom comparator.  We would have to iterate over map.keys() and then lookup each value, which wouldn't be efficient.
>
> Currently we just use ConcurrentHashMap so that concurrent lookups of the Group object by unique integer id is fast. Iteration over the group objects through map.values() is also fast.  But the inefficient part is that at a higher layer we end up having to sort the Group objects by name every where they are
> displayed in list.  If somehow we could have a data structure that allowed for fast map lookups but also kept the values in sorted order (via Comparator or natural order), that would be the ultimate solution.    We don't care if updates or sorting is relatively slow, since 99.999% of the time there are only reader threads.
>
> This is a generic problem we have throughout our application. We have many different objects like Group object which have the same use case.
>
> In the UI, we have paginated views, so we only show the first 50 rows by default, but in order to figure out which are the first 50 rows, you have to sort all the objects by the sort key, e.g. name.
>
>
> -Alex
>
> On Sun, 11 Oct 2009 23:04 -0700, "Joe Bowbeer"
> <joe.bowbeer@...> wrote:
>
>   ConcurrentSkipListMap is a SortedMap, so the comparator is
>   used for all key comparisons:
>   "... a sorted map performs all key comparisons using its
>   compareTo (or compare) method, so two keys that are deemed
>   equal by this method are, from the standpoint of the sorted
>   map, equal."
>   A comparator that compares values instead of keys will not
>   permit multiple keys to be mapped to the same (or equal)
>   values.
>   Joe
>
> On Sun, Oct 11, 2009 at 10:40 PM, Alex wrote:
>
>   Hi,
>   We have a large J2EE enterprise application, and we make heavy
>   use of the concurrency library. We use ConcurrentHashMap in
>   many places.
>   One desire we have had was to have a ConcurrentHashMap but
>   also have the values sorted in a default order so that we
>   don't need to sort the results unless a custom sort is
>   required.
>   We have looked at ConcurrentSkipListMap[K,V], and that seems
>   to do exactly what we want, *except* it sorts based on the
>   keys not the values.
>   Here is an simplified example of what we would like to do:
>   private class Group {
>    int id;
>    String name;
>   }
>   private final ConcurrentSkipListMap[Integer,Group] mGroups =
>   new ConcurrentSkipListMap[Integer,Group]();
>   We have approximately 1000 to 10000 of these group objects and
>   we have many threads accessing them concurrently almost
>   99.999% of time read only, so read/iteration access without
>   locking is very important.
>   The code has two main code paths, either get a group by
>   integer unique id, or iterating over the entire set.   When
>   iterating over the entire set, we want them to be in a certain
>   order, e.g. the String name of the group.
>   Group group = new Group(0,"global");
>   map.put(id,group)
>   So, the Key is the integer id, and the value is the Group
>   object.
>   The ConcurrentSkipListMap specification says it sorts by key
>   rather than value.
>   We could write a custom comparator, but to sort on a field in
>   the Group object, we would have to use the map to look it up,
>   which may cause a problem? I don't know if it's safe to call
>   methods of the map from inside the comparator.
>     class GroupComparator implements Comparator
>      {
>          public int compare(
>              Object o1, Object o2
>          ) {
>              Integer id1 = (Integer) o1;
>              Integer id2 = (Integer) o2;
>              // referring back to the map while it is sorting
>   the keys
>              // may cause problem?
>              Group group1 = (Group) map.get(id1);
>              Group group2 = (Group) map.get(id2);
>              return
>   group1.getName().compareTo(group2.getName());
>          }
>      }
>   If anyone can suggest an alternative data structure or
>   solution, or can confirm it is safe for the Comparator to call
>   get() method on the map, I would appreciate it.
>   Thanks,

I usually do something like that, and if you use Generics and put "Comparable"
on classes involved you can reduce some of the visible code.

Map<Integer,String>map = new ConcurrentHashMap<Integer,String>();
List<Integer>sorted = new ArrayList<Integer>( map.keySet() );

Collections.sort( sorted, new Comparator<Integer>() {
        public int compare( Integer i1, Integer i2 ) {
                return map.get(i1).compareTo( map.get(i2) );
        }
});

This works quite well as long as you have appropriate locking in use.

Gregg Wonderly
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Luke Blanshard-2]

On Mon, Oct 12, 2009 at 12:40 AM, <nnn6-twfe@...> wrote:

...

If anyone can suggest an alternative data structure or solution, or can confirm it is safe for the Comparator to call get() method on the map, I would appreciate it.

 You can tell that it's not safe for the comparator to rely solely on the map to locate the correct group, just consider how a new group is added to the map.  The comparator needs to be invoked to determine the placement of the group within the map, and since it isn't there yet the comparator will blow up.

Likewise, consider how a lookup happens.  To find out where in the map to look for the group, the map must invoke the comparator.  And the comparator tries to get the group from the map to be able to tell it.  Stack overflow.

You could consider a hybrid structure, using both a hash map and a skip list.  Use the hash map for lookup by id, and the skip list for iteration in the correct order.  The skip list's comparator uses the hash map to pull out the objects being compared.  So the "put" implementation for this hybrid map first puts into the hash map, then into the skip list.  Because the comparator relies only on the hash map, this will be safe.  (Though there is a race condition between put and remove, unless you have some extra synchronization.  Probably not a factor in practice, but you'd have to prove that to yourself.)

Luke

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Gilgamesh Nootebos-2]

Hi Alex,

It's also possible to create a custom map that uses the skiplistmap as
a backing structure and and wrap every key in an internal key that
defines a comparator on the value.

I've created a little example of this concept to show what I mean.
It's by no means complete or very robust but its only a demo after
all. I haven't given much thought on the performance properties of
reading values from the map, perhaps you can use a readonly view of
the internal map to bypass the abstractmap implementation.

Hope this brings you closer to a solution for your question.

Regards,

Gilgamesh Nootebos



On Mon, Oct 12, 2009 at 16:22, Luke Blanshard <blanshlu@...> wrote:

> On Mon, Oct 12, 2009 at 12:40 AM, <nnn6-twfe@...> wrote:
>>
>> ...
>>
>> If anyone can suggest an alternative data structure or solution, or can
>> confirm it is safe for the Comparator to call get() method on the map, I
>> would appreciate it.
>
>  You can tell that it's not safe for the comparator to rely solely on the
> map to locate the correct group, just consider how a new group is added to
> the map.  The comparator needs to be invoked to determine the placement of
> the group within the map, and since it isn't there yet the comparator will
> blow up.
>
> Likewise, consider how a lookup happens.  To find out where in the map to
> look for the group, the map must invoke the comparator.  And the comparator
> tries to get the group from the map to be able to tell it.  Stack overflow.
>
> You could consider a hybrid structure, using both a hash map and a skip
> list.  Use the hash map for lookup by id, and the skip list for iteration in
> the correct order.  The skip list's comparator uses the hash map to pull out
> the objects being compared.  So the "put" implementation for this hybrid map
> first puts into the hash map, then into the skip list.  Because the
> comparator relies only on the hash map, this will be safe.  (Though there is
> a race condition between put and remove, unless you have some extra
> synchronization.  Probably not a factor in practice, but you'd have to prove
> that to yourself.)
>
> Luke
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest@...
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>

[ValueSortedConcurrentMap.java]

---

package gilgamesh.sortedvalues;

import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Set;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ConcurrentSkipListMap;

/**
 * Hello world!
 *
 */
public class ValueSortedConcurrentMap<K, V extends Comparable<V>> extends AbstractMap<K, V> implements ConcurrentMap<K, V> {

    private final ConcurrentMap<Key<K, V>, V> map = new ConcurrentSkipListMap<Key<K, V>, V>();

    public static void main(String[] args) {

        final ConcurrentMap<Integer, Group> map = new ValueSortedConcurrentMap<Integer, Group>();

        map.putIfAbsent(0, new Group("zero"));
        map.putIfAbsent(1, new Group("one"));
        map.putIfAbsent(2, new Group("two"));
        map.putIfAbsent(3, new Group("three"));
        map.putIfAbsent(4, new Group("four"));
        map.putIfAbsent(5, new Group("five"));

        for (Group g : map.values()) {
            System.out.println(g.name);
        }
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        return new AbstractSet<Entry<K, V>>() {

            @Override
            public Iterator<Entry<K, V>> iterator() {
                return new Iterator<Entry<K, V>>() {

                    private final Iterator<Entry<Key<K, V>, V>> iterator = map.entrySet().iterator();

                    @Override
                    public boolean hasNext() {
                        return iterator.hasNext();
                    }

                    @Override
                    public Entry<K, V> next() {
                        return new Entry<K, V>() {

                            private final Entry<Key<K, V>, V> entry = iterator.next();

                            @Override
                            public K getKey() {
                                return entry.getKey().code;
                            }

                            @Override
                            public V getValue() {
                                return entry.getValue();
                            }

                            @Override
                            public V setValue(V value) {
                                throw new UnsupportedOperationException("Not supported yet.");
                            }
                        };
                    }

                    @Override
                    public void remove() {
                        throw new UnsupportedOperationException("Not supported yet.");
                    }
                };
            }

            @Override
            public int size() {
                return map.size();
            }
        };
    }

    @Override
    public V putIfAbsent(K key, V value) {
        return map.putIfAbsent(new Key<K, V>(key, value), value);
    }

    @Override
    public boolean remove(Object key, Object value) {
        if (!(key instanceof Key)) {
            throw new IllegalArgumentException();
        }
        final Key k = (Key) key;
        return map.remove(k.code, value);
    }

    @Override
    public boolean replace(K key, V oldValue, V newValue) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    @Override
    public V replace(K key, V value) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    static class Key<T, V extends Comparable<V>> implements Comparable<Key<T, V>> {

        private final T code;
        private final V group;

        public Key(T code, V group) {
            assert code != null;
            this.code = code;
            this.group = group;
        }

        public Key(T code) {
            this(code, null);
        }

        @Override
        public int compareTo(Key<T, V> o) {
            if (group == null || o.group == null) {
                throw new IllegalStateException("Sentinel should not be used");
            }
            return group.compareTo(o.group);
        }
    }

    static class Group implements Comparable<Group> {

        private final String name;

        public Group(String name) {
            assert name != null;
            this.name = name;
        }

        @Override
        public int compareTo(Group o) {
            return name.compareTo(o.name);
        }
    }
}

---

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest