ConcurrentNavigableMap additional methods: 6415641

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

ConcurrentNavigableMap additional methods: 6415641

Jason Mehrens
Since the ConcurrentNavigableMap has methods to poll entries from the map,
it might be worth considering adding the related methods (modified from the
BlockingQueue):
int drainTo(Map<? super K, ? super V> m)
int drainTo(Map<? super K, ? super V> m, int maxEntries)

The main reason I can think of for adding these methods is from the
BlockingQueue documentation which states: "This operation may be more
efficient than repeatedly polling...".  It would also allow some maps to
make this operation of polling all entries atomic.

Regards,

Jason Mehrens


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentNavigableMap additional methods: 6415641

tpeierls
On 4/25/06, Jason Mehrens <[hidden email]> wrote:
Since the ConcurrentNavigableMap has methods to poll entries from the map, it might be worth considering adding the related methods (modified from the BlockingQueue):
int drainTo(Map<? super K, ? super V> m)
int drainTo(Map<? super K, ? super V> m, int maxEntries)

The main reason I can think of for adding these methods is from the BlockingQueue documentation which states: "This operation may be more efficient than repeatedly polling...".

The BlockingQueue spec says that Collection methods need not be implemented efficiently, leaving drainTo as the only available efficient bulk removal operation for blocking queues. But the same is not true of other subinterfaces of Collection; in particular, it is reasonable to expect efficient iteration over the entries of a ConcurrentNavigableMap.


It would also allow some maps to make this operation of polling all entries atomic.

Not ConcurrentHashMap or ConcurrentSkipListMap, for which only weak consistency of iterators is guaranteed. If you want strongly consistent snapshots, you need something like Collections.synchronizedMap.

I can imagine an implementation of ConcurrentNavigableMap that does provide strong consistency for its iterators, but in that case you don't need an additional method in the interface -- i.e., the following would do the right thing:

ConcurrentNavigableMap<X, Y> scm = new StronglyConsistentConcurrentMap<X, Y>();
...
// relies on strongly consistent iteration over scm:
Map<X, Y> snapshot = new HashMap<X, Y>(scm);

--tim

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentNavigableMap additional methods: 6415641

Jason Mehrens
In reply to this post by Jason Mehrens
Tim,

Thanks for the comments.  I wanted to clarify that strong/weak Iteration is
not what I was focusing on (maybe I should have been).

The code bellow is an example of how to drain a NavigableMap to another Map
(clearly not atomic):
  public static <K,V> int drainTo(ConcurrentNavigableMap<K,V> m, Map<? super
K, ? super V> fill) {
    int count = 0;
    Map.Entry<K,V> e = m.pollFirstEntry();
    while(e != null) {
      fill.put(e.getKey(), e.getValue());
      count++;
      e = m.pollFirstEntry();
    }
    return count;
  }

Take the ConcurrentSkipListMap (the ConcurrentHashMap does not apply because
it is not a NavigableMap), there is one volatile reference to the head node.
  The clear operation simply creates and assigns a new head node to clear
the map.  So if there was a drainTo method on the ConcurrentSkipListMap, it
could simply CAS the head reference (an atomic operation) and traverse the
snapshot without the cost of unlinking nodes.  I haven't tested the idea so
I could be totally wrong.
The presence of a drainTo method could be unnecessary, I just wanted to be
sure that the idea is out there for review.

Regards,

Jason Mehrens

>From: "Tim Peierls" <[hidden email]>
>To: "Jason Mehrens" <[hidden email]>
>CC: [hidden email]
>Subject: Re: [concurrency-interest] ConcurrentNavigableMap additional
>methods: 6415641
>Date: Tue, 25 Apr 2006 15:51:21 -0400
>
>On 4/25/06, Jason Mehrens <[hidden email]> wrote:
> >
> > Since the ConcurrentNavigableMap has methods to poll entries from the
>map,
> > it might be worth considering adding the related methods (modified from
>the
> > BlockingQueue):
> > int drainTo(Map<? super K, ? super V> m)
> > int drainTo(Map<? super K, ? super V> m, int maxEntries)
> >
> > The main reason I can think of for adding these methods is from the
> > BlockingQueue documentation which states: "This operation may be more
> > efficient than repeatedly polling...".
>
>
>The BlockingQueue spec says that Collection methods need not be implemented
>efficiently, leaving drainTo as the only available efficient bulk removal
>operation for blocking queues. But the same is not true of other
>subinterfaces of Collection; in particular, it is reasonable to expect
>efficient iteration over the entries of a ConcurrentNavigableMap.
>
>
>It would also allow some maps to make this operation of polling all entries
> > atomic.
>
>
>Not ConcurrentHashMap or ConcurrentSkipListMap, for which only weak
>consistency of iterators is guaranteed. If you want strongly consistent
>snapshots, you need something like Collections.synchronizedMap.
>
>I can imagine an implementation of ConcurrentNavigableMap that does provide
>strong consistency for its iterators, but in that case you don't need an
>additional method in the interface -- i.e., the following would do the
>right
>thing:
>
>ConcurrentNavigableMap<X, Y> scm = new StronglyConsistentConcurrentMap<X,
>Y>();
>...
>// relies on strongly consistent iteration over scm:
>Map<X, Y> snapshot = new HashMap<X, Y>(scm);
>
>--tim


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentNavigableMap additional methods: 6415641

tpeierls
Do you have any use cases for an atomic "drainTo" operation on ConcurrentNavigableMap? And why do you restrict it to CNM?

If you aren't too worried about consistency, you could create a wrapper class that delegates to an underlying CNM via an AtomicReference, and implements drainTo by cas'ing a new empty delegate and filling the result map from the original delegate.
--tim

On 4/26/06, Jason Mehrens <[hidden email]> wrote:
Tim,

Thanks for the comments.  I wanted to clarify that strong/weak Iteration is
not what I was focusing on (maybe I should have been).

The code bellow is an example of how to drain a NavigableMap to another Map
(clearly not atomic):
  public static <K,V> int drainTo(ConcurrentNavigableMap<K,V> m, Map<? super
K, ? super V> fill) {
    int count = 0;
    Map.Entry<K,V> e = m.pollFirstEntry();
    while(e != null) {
      fill.put(e.getKey(), e.getValue());
      count++;
      e = m.pollFirstEntry();
    }
    return count;
  }

Take the ConcurrentSkipListMap (the ConcurrentHashMap does not apply because
it is not a NavigableMap), there is one volatile reference to the head node.
  The clear operation simply creates and assigns a new head node to clear
the map.  So if there was a drainTo method on the ConcurrentSkipListMap, it
could simply CAS the head reference (an atomic operation) and traverse the
snapshot without the cost of unlinking nodes.  I haven't tested the idea so
I could be totally wrong.
The presence of a drainTo method could be unnecessary, I just wanted to be
sure that the idea is out there for review.

Regards,

Jason Mehrens

>From: "Tim Peierls" <[hidden email]>
>To: "Jason Mehrens" < [hidden email]>
>CC: [hidden email]
>Subject: Re: [concurrency-interest] ConcurrentNavigableMap additional
>methods: 6415641
>Date: Tue, 25 Apr 2006 15:51:21 -0400
>
>On 4/25/06, Jason Mehrens <[hidden email]> wrote:
> >
> > Since the ConcurrentNavigableMap has methods to poll entries from the
>map,
> > it might be worth considering adding the related methods (modified from
>the
> > BlockingQueue):
> > int drainTo(Map<? super K, ? super V> m)
> > int drainTo(Map<? super K, ? super V> m, int maxEntries)
> >
> > The main reason I can think of for adding these methods is from the
> > BlockingQueue documentation which states: "This operation may be more
> > efficient than repeatedly polling...".
>
>
>The BlockingQueue spec says that Collection methods need not be implemented
>efficiently, leaving drainTo as the only available efficient bulk removal
>operation for blocking queues. But the same is not true of other
>subinterfaces of Collection; in particular, it is reasonable to expect
>efficient iteration over the entries of a ConcurrentNavigableMap.
>
>
>It would also allow some maps to make this operation of polling all entries
> > atomic.
>
>
>Not ConcurrentHashMap or ConcurrentSkipListMap, for which only weak
>consistency of iterators is guaranteed. If you want strongly consistent
>snapshots, you need something like Collections.synchronizedMap.
>
>I can imagine an implementation of ConcurrentNavigableMap that does provide
>strong consistency for its iterators, but in that case you don't need an
>additional method in the interface -- i.e., the following would do the
>right
>thing:
>
>ConcurrentNavigableMap<X, Y> scm = new StronglyConsistentConcurrentMap<X,
>Y>();
>...
>// relies on strongly consistent iteration over scm:
>Map<X, Y> snapshot = new HashMap<X, Y>(scm);
>
>--tim




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentNavigableMap additional methods: 6415641

Jason Mehrens
In reply to this post by Jason Mehrens
The only use case I can think of would be clearing a global cache and using
the resulting Map to log the entries ejected from the cache at that point in
time.  Given the nature of the ConcurrentMaps, there is probably no real
difference between repeated polling and drainTo.  However, I would think the
same would hold true of BlockingQueues.  As you stated before, "..drainTo as
the only available efficient bulk removal operation for blocking queues."  
But, I would think clear() is the other efficient bulk removal operation
(even though it is specified by Collection).  You just can't get any
additional information from clear().  Which is why it "might" be useful to
have a drainTo specified in the interface.
Third party classes like a "copy on write binary tree" or a "NavigableMap to
ConcurrentNavigableMap wrapper" could have fast clear and drainTo methods
but slower polling methods.  Overall those types are poor performers but you
get the idea.

I would restrict it to the CNM because it is similar to the BlockingDeque.  
The NavigableMap and Deque specify methods to poll from each end but no
drainTo method.  The thread-safe BlockingDeque adds the drainTo (from
BlockingQueue) but the thread-safe ConcurrentNavigableMap doesn't.  While
Collections and Maps are different, the lack of a drainTo for a CNM seems
unbalanced to me.  But a small clear API is important too.

cheers,

Jason Mehrens

>From: "Tim Peierls" <[hidden email]>
>To: "Jason Mehrens" <[hidden email]>
>CC: [hidden email]
>Subject: Re: [concurrency-interest] ConcurrentNavigableMap additional
>methods: 6415641
>Date: Wed, 26 Apr 2006 16:12:09 -0400
>
>Do you have any use cases for an atomic "drainTo" operation on
>ConcurrentNavigableMap? And why do you restrict it to CNM?
>
>If you aren't too worried about consistency, you could create a wrapper
>class that delegates to an underlying CNM via an AtomicReference, and
>implements drainTo by cas'ing a new empty delegate and filling the result
>map from the original delegate.
>--tim


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentNavigableMap additional methods: 6415641

Doug Lea
Jason Mehrens wrote:
> The only use case I can think of would be clearing a global cache and using
> the resulting Map to log the entries ejected from the cache at that point in
> time.  ...  Which is why it "might" be useful to have a drainTo specified in
> the interface.

Well, I'm afraid I'm with Tim that it's probably not worth adding to API.
If there were such a thing as a BlockingNavigableMap
(i.e., that extended ConcurrentNavigableMap to support
methods like takeFirst), then drainTo should
surely be in such an API. But no one has asked us for such
a thing yet.

(BTW, everyone should congratulate Jason for winning the Sun Mustang
Regression contest by pointing out failure to maintain interrupt
conventions in our SynchronousQueue update!)

-Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentNavigableMap additional methods: 6415641

Joshua Bloch-2
Congrats Jason!  Did you get the machine?  Way cool.

That said, I'm with Doug and Tim on this API issue.

        Regards,

        Josh

On 4/30/06, Doug Lea <[hidden email]> wrote:

> Jason Mehrens wrote:
> > The only use case I can think of would be clearing a global cache and using
> > the resulting Map to log the entries ejected from the cache at that point in
> > time.  ...  Which is why it "might" be useful to have a drainTo specified in
> > the interface.
>
> Well, I'm afraid I'm with Tim that it's probably not worth adding to API.
> If there were such a thing as a BlockingNavigableMap
> (i.e., that extended ConcurrentNavigableMap to support
> methods like takeFirst), then drainTo should
> surely be in such an API. But no one has asked us for such
> a thing yet.
>
> (BTW, everyone should congratulate Jason for winning the Sun Mustang
> Regression contest by pointing out failure to maintain interrupt
> conventions in our SynchronousQueue update!)
>
> -Doug
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentNavigableMap additional methods: 6415641

Jason Mehrens
In reply to this post by Jason Mehrens
Thanks Josh and Doug for the congrats and the API review.

I haven't received the machine yet.  It would be funny if it arrives the
week of Java ONE.

Process.waitFor has the same issue (in 5.0 and 6.0) but the bug report
(503840) I filled for it wasn't accepted. I find that funny since the
SynchronousQueue bug was a winner.

Regards,

Jason


>From: "Joshua Bloch" <[hidden email]>
>To: "Doug Lea" <[hidden email]>
>CC: "Jason Mehrens" <[hidden email]>,
>[hidden email]
>Subject: Re: [concurrency-interest] ConcurrentNavigableMap additional
>methods: 6415641
>Date: Sun, 30 Apr 2006 23:35:03 -0700
>
>Congrats Jason!  Did you get the machine?  Way cool.
>
>That said, I'm with Doug and Tim on this API issue.
>
>        Regards,
>
>        Josh
>
>On 4/30/06, Doug Lea <[hidden email]> wrote:
>>Jason Mehrens wrote:
>> > The only use case I can think of would be clearing a global cache and
>>using
>> > the resulting Map to log the entries ejected from the cache at that
>>point in
>> > time.  ...  Which is why it "might" be useful to have a drainTo
>>specified in
>> > the interface.
>>
>>Well, I'm afraid I'm with Tim that it's probably not worth adding to API.
>>If there were such a thing as a BlockingNavigableMap
>>(i.e., that extended ConcurrentNavigableMap to support
>>methods like takeFirst), then drainTo should
>>surely be in such an API. But no one has asked us for such
>>a thing yet.
>>
>>(BTW, everyone should congratulate Jason for winning the Sun Mustang
>>Regression contest by pointing out failure to maintain interrupt
>>conventions in our SynchronousQueue update!)
>>
>>-Doug
>>_______________________________________________
>>Concurrency-interest mailing list
>>[hidden email]
>>http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>>


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest