[concurrency-interest] Subject: Re: ConcurrentHashMapV8

Peter Firmstone peter.firmstone at zeus.net.au
Sat Oct 8 06:26:10 EDT 2011


With Reference to Iterators, why not do something like this:

interface AtomicIterator<T> extends Iterator<T>{

    T getIfHasNext();
    
}


Example use (ignore the unchecked cast please, just to keep it simple):

AtomicIterator<T> iter = (AtomicIterator) keys.iterator<T>();

T t = iter.getIfHasNext();
while ( t != null ) {
  // Do something with t;
  t = iter.getIfHasNext();
}

Then you could back your AtomicIterator with a queue, every time there's
a mutation, add it to the end of the queue, or remove it.

Just a thought.

Cheers,

Peter.


On Sat, 2011-10-08 at 10:09, concurrency-interest-request at cs.oswego.edu
wrote:
> Send Concurrency-interest mailing list submissions to
> 	concurrency-interest at cs.oswego.edu
> 
> To subscribe or unsubscribe via the World Wide Web, visit
> 	http://cs.oswego.edu/mailman/listinfo/concurrency-interest
> or, via email, send a message with subject or body 'help' to
> 	concurrency-interest-request at cs.oswego.edu
> 
> You can reach the person managing the list at
> 	concurrency-interest-owner at cs.oswego.edu
> 
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of Concurrency-interest digest..."
> 
> 
> Today's Topics:
> 
>    1. Re: AtomicXXX.lazySet and	happens-before	reasoning (Boehm, Hans)
>    2. Re: ConcurrentHashMapV8 (Gregg Wonderly)
>    3. Re: ConcurrentHashMapV8 (Bob Lee)
>    4. Re: AtomicXXX.lazySet and happens-before	reasoning
>       (Ruslan Cheremin)
>    5. Re: AtomicXXX.lazySet and happens-before reasoning (Boehm, Hans)
>    6. Re: AtomicXXX.lazySet and happens-before	reasoning
>       (Vitaly Davidovich)
> 
> 
> ----------------------------------------------------------------------
> 
> Message: 1
> Date: Fri, 7 Oct 2011 18:02:19 +0000
> From: "Boehm, Hans" <hans.boehm at hp.com>
> To: Doug Lea <dl at cs.oswego.edu>, Ruslan Cheremin <cheremin at gmail.com>
> Cc: "concurrency-interest at cs.oswego.edu"
> 	<concurrency-interest at cs.oswego.edu>
> Subject: Re: [concurrency-interest] AtomicXXX.lazySet and
> 	happens-before	reasoning
> Message-ID:
> 	<A3E67C2071F49C4CBC4F17E6D77CDDD20422BB at G4W3299.americas.hpqcorp.net>
> Content-Type: text/plain; charset="us-ascii"
> 
> > From: Doug Lea
> > 
> > On 10/07/11 09:24, Ruslan Cheremin wrote:
> > > After some thinking and reading I still do not understand some
> > issues...
> > >
> > > As far, as I can see from description of lazySet, it is just ordinary
> > > store with StoreStore barrier just before it. But if it is so, what
> > is
> > > the difference between it and ordinary volatile write? In JSR-133
> > > implementation cookbook http://gee.cs.oswego.edu/dl/jmm/cookbook.html
> > > you've shown volatile store implementation as store having exactly
> > > StoreStore barrier before it.
> It also needs a LoadStore fence, in both cases.  But even then, it's important to remember that although his may be a sufficient implementation, this is an incorrect description from the user's perspective.  In particular, if v is volatile (and certainly if it's accessed using lazySet), and x and y are ordinary variables, then the assignments to x and y in the following may be visibly reordered:
> 
> x = 1;
> v = 2;
> y = 3;
> 
> Volatiles are not fences.
> 
> > 
> > Plus, for a volatile, a StoreLoad fence between the write and any read.
> > Almost always, the only good choice for where to place it is
> > immediately after the write. In addition to disabling
> > more optimizations, StoreLoad fences translate to
> > instructions that are not cheap on any platform, although they are
> > currently a lot cheaper than they were about 5 years ago on most
> > platforms. But in any case, if you have a situation that is
> > guaranteed not to need one to preserve correctness, it is always
> > faster not to require one.
> > 
> And on something like PowerPC, the implementation rules are actually currently quite unclear.  The currently preferred implementation, at least for the C++ equivalents, actually associates much of the volatile overhead with loads, though it's not completely clear that's the right choice.  Just adding a StoreLoad fence to stores isn't sufficient, for fairly complex reasons related to the fact that this view of fences is too simplistic for PowerPC.  If Java implementations follow the recommendations in http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html, then lazySet saves a relatively small percentage of the overhead, and the change amounts to weakening the fence before the store, not dropping one after it.  But that's because the StoreLoad fence is associated with the load, for which Java doesn't have a weaker form.  And having Java follow a different recipe from the C++ one is probably also a bad idea, since it essentially breaks mixed applications.
> 
> Hans
> 
> 
> 
> ------------------------------
> 
> Message: 2
> Date: Fri, 07 Oct 2011 14:57:58 -0500
> From: Gregg Wonderly <gregg at cytetech.com>
> To: Mark Thornton <mthornton at optrak.com>
> Cc: concurrency-interest at cs.oswego.edu
> Subject: Re: [concurrency-interest] ConcurrentHashMapV8
> Message-ID: <4E8F59C6.4070701 at cytetech.com>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
> 
> On 10/7/2011 9:45 AM, Mark Thornton wrote:
> > On 07/10/11 15:32, David M. Lloyd wrote:
> >> Yeah, but I think that's not outside of what should be reasonably expected
> >> when you iterate a (non-COW) concurrent hash map. As you say, hasNext()/next()
> >> can be made consistent by actually getting a snapshot ref to the next entry in
> >> hasNext(), but it doesn't have to be a copy of the Entry, it can still be the
> >> literal Entry in the map.
> > I have several nonconcurrent map implementations which do not have Entry
> > instances internally --- they are created on the fly as needed to satisfy the
> > entrySet requirements. I usually do this where I can't afford the space required
> > by literal Entry instances.
> 
> It is important for an iterator to snapshot if you can ask it for the next 
> entry.  What would be better, to avoid copying and to manage concurrency easier, 
> without the hasNext()/next() issue, would be to have iteration functionality in 
> an expression so that there was no hasNext()/next() pairing. But rather put the 
> collection in control of performing a call out to the "task" for the next 
> element in the collection.  As in something like
> 
> public interface IterationPoint<T> {
> 	public void iterateFor( T value );
> }
> 
> public interface IterationProvider<T> {
> 	public int iterateOver( IterationPoint<T> point );
> }
> 
> This would then allow complete freedom from hasNext()/next() pairing because 
> only if the collection found another value, would it need to reveal it to the 
> IterationPoint.
> 
> Lambdas would make this easy, but even with inner classes, it's still usable.
> 
> Gregg Wonderly
> 
> 
> 
> ------------------------------
> 
> Message: 3
> Date: Fri, 7 Oct 2011 13:52:02 -0700
> From: Bob Lee <crazybob at crazybob.org>
> To: Doug Lea <dl at cs.oswego.edu>
> Cc: concurrency-interest at cs.oswego.edu
> Subject: Re: [concurrency-interest] ConcurrentHashMapV8
> Message-ID:
> 	<CAGmsiP7_6x2SdiWAUBtstz4iTVJUVxPY6eDPyaXftOdtzry7rQ at mail.gmail.com>
> Content-Type: text/plain; charset="iso-8859-1"
> 
> On Wed, Oct 5, 2011 at 6:11 AM, Doug Lea <dl at cs.oswego.edu> wrote:
> 
> > To me, fixing the mis-feature is more important
> > than retaining pure compatibility for a usage
> > that probably didn't do what people expected anyway.
> > But if you've ever done anything relying on the old j.u.c
> > behavior, could you let us know? Thanks!
> 
> 
> Is it correct to assume that "fixing" CHM.entrySet().toArray() requires more
> work on our part? If so, it's probably not worth the effort
> 
> If we assume the user wants a snapshot of the entry set, here's the code
> using toArray():
> 
>     Set<Map.Entry<K, V>> original = map.entrySet();
>     // This array isn't used outside of this code, so we can ignore the
> warning.
>     @SuppressWarnings("unchecked")
>     Map.Entry<K, V>[] array = original.toArray(
>         (Map.Entry<K, V>[]) new Map.Entry[0]);
>     // We erroneously get an "unchecked generic array creation" warning
> here.
>     @SuppressWarnings("unchecked")
>     Set<Map.Entry<K, V>> copy = new HashSet<Map.Entry<K, V>>(
>         Arrays.asList(array));
> 
> Yuck. It requires two unsafe operations. We actually shouldn't get a warning
> in the second case, and it'll go away either way with Java 7, but I do get a
> warning with my current setup. Copying entries from a concurrent map to an
> exact-length array is tricky and inefficient. The user can call size() and
> use it to create the passed-in array, but the array size could change. It
> can also change while copying the entries in which case toArray() may have
> to create a copy. If the size goes down, the array needs to be truncated. If
> the size goes up, any remaining entries are ignored.
> 
> It's simpler, safer, and more efficient for users to copy the entries
> manually:
> 
>     Set<Map.Entry<K, V>> copy = new HashSet<Map.Entry<K, V>>(map.size());
>     for (Map.Entry<K, V> entry : map.entrySet()) {
>       copy.add(new AbstractMap.SimpleEntry<K, V>(entry));
>     }
> 
> Thanks,
> Bob
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20111007/aad6db23/attachment-0001.html>
> 
> ------------------------------
> 
> Message: 4
> Date: Sat, 8 Oct 2011 01:44:52 +0400
> From: Ruslan Cheremin <cheremin at gmail.com>
> To: "Boehm, Hans" <hans.boehm at hp.com>
> Cc: "concurrency-interest at cs.oswego.edu"
> 	<concurrency-interest at cs.oswego.edu>
> Subject: Re: [concurrency-interest] AtomicXXX.lazySet and
> 	happens-before	reasoning
> Message-ID:
> 	<CAOwENiKEPcfmDP-75B4=L7k7i3TB-8fM4aMww1aR9wqGRywzaQ at mail.gmail.com>
> Content-Type: text/plain; charset=ISO-8859-1
> 
> > It also needs a LoadStore fence, in both cases.
> 
> But why lazySet needs LoadStore fence? It seems what lazySet javadoc
> does not put any ordering constraints on loads...
> 
> >?In particular, if v is volatile (and certainly if it's accessed using lazySet), and x and y are ordinary variables,
> > then the assignments to x and y in the following may be visibly reordered:
> > x = 1;
> > v = 2;
> > y = 3;
> 
> You mean what vstore is not "transparent" upside down, but
> "transparent" downside up, so this
> 
> y=3
> x=1
> v=2
> 
> is allowed reordering?
> 
> 
> 
> ------------------------------
> 
> Message: 5
> Date: Fri, 7 Oct 2011 23:22:33 +0000
> From: "Boehm, Hans" <hans.boehm at hp.com>
> To: Ruslan Cheremin <cheremin at gmail.com>
> Cc: "concurrency-interest at cs.oswego.edu"
> 	<concurrency-interest at cs.oswego.edu>
> Subject: Re: [concurrency-interest] AtomicXXX.lazySet and
> 	happens-before reasoning
> Message-ID:
> 	<A3E67C2071F49C4CBC4F17E6D77CDDD20424AF at G4W3299.americas.hpqcorp.net>
> Content-Type: text/plain; charset="iso-8859-1"
> 
> > From: Ruslan Cheremin [mailto:cheremin at gmail.com]
> > > It also needs a LoadStore fence, in both cases.
> > 
> > But why lazySet needs LoadStore fence? It seems what lazySet javadoc
> > does not put any ordering constraints on loads...
> I do read it as imposing such a constraint, though we all agree that a more precise spec would help.  Certainly C++11's memory_order_release imposes such a constraint.
> 
> If not, it would mean that e.g.
> 
> Thread 1:
> x = ...;
> ...
> r1 = x;
> done_with_x.lazySet(true);
> 
> Thread 2:
> if (done_with_x.get()) {
>    x = ...;
>    ...
>    r2 = x;
> }
> 
> wouldn't work as expected.
> 
> In my opinion, that's an indefensible design point, especially since I don't believe it makes lazySet appreciably cheaper on any modern architectures.
> 
> 
> > 
> > >?In particular, if v is volatile (and certainly if it's accessed using
> > lazySet), and x and y are ordinary variables,
> > > then the assignments to x and y in the following may be visibly
> > reordered:
> > > x = 1;
> > > v = 2;
> > > y = 3;
> > 
> > You mean what vstore is not "transparent" upside down, but
> > "transparent" downside up, so this
> > 
> > y=3
> > x=1
> > v=2
> > 
> > is allowed reordering?
> Correct.
> 
> Hans
> 
> 
> 
> ------------------------------
> 
> Message: 6
> Date: Fri, 7 Oct 2011 20:09:45 -0400
> From: Vitaly Davidovich <vitalyd at gmail.com>
> To: "Boehm, Hans" <hans.boehm at hp.com>
> Cc: "concurrency-interest at cs.oswego.edu"
> 	<concurrency-interest at cs.oswego.edu>
> Subject: Re: [concurrency-interest] AtomicXXX.lazySet and
> 	happens-before	reasoning
> Message-ID:
> 	<CAHjP37FCUURtwfKJNajvUnoTXxuSe7k_GV+1nN-e8wS69RPSFg at mail.gmail.com>
> Content-Type: text/plain; charset="iso-8859-1"
> 
> Does it even make sense to say that lazySet needs a LoadStore fence? The
> get() does but that's because it has same semantics as volatile read.
> On Oct 7, 2011 7:29 PM, "Boehm, Hans" <hans.boehm at hp.com> wrote:
> 
> > > From: Ruslan Cheremin [mailto:cheremin at gmail.com]
> > > > It also needs a LoadStore fence, in both cases.
> > >
> > > But why lazySet needs LoadStore fence? It seems what lazySet javadoc
> > > does not put any ordering constraints on loads...
> > I do read it as imposing such a constraint, though we all agree that a more
> > precise spec would help.  Certainly C++11's memory_order_release imposes
> > such a constraint.
> >
> > If not, it would mean that e.g.
> >
> > Thread 1:
> > x = ...;
> > ...
> > r1 = x;
> > done_with_x.lazySet(true);
> >
> > Thread 2:
> > if (done_with_x.get()) {
> >   x = ...;
> >   ...
> >   r2 = x;
> > }
> >
> > wouldn't work as expected.
> >
> > In my opinion, that's an indefensible design point, especially since I
> > don't believe it makes lazySet appreciably cheaper on any modern
> > architectures.
> >
> >
> > >
> > > > In particular, if v is volatile (and certainly if it's accessed using
> > > lazySet), and x and y are ordinary variables,
> > > > then the assignments to x and y in the following may be visibly
> > > reordered:
> > > > x = 1;
> > > > v = 2;
> > > > y = 3;
> > >
> > > You mean what vstore is not "transparent" upside down, but
> > > "transparent" downside up, so this
> > >
> > > y=3
> > > x=1
> > > v=2
> > >
> > > is allowed reordering?
> > Correct.
> >
> > Hans
> >
> > _______________________________________________
> > Concurrency-interest mailing list
> > Concurrency-interest at cs.oswego.edu
> > http://cs.oswego.edu/mailman/listinfo/concurrency-interest
> >
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20111007/d6bd4ed5/attachment.html>
> 
> ------------------------------
> 
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
> 
> 
> End of Concurrency-interest Digest, Vol 81, Issue 11
> ****************************************************



More information about the Concurrency-interest mailing list