Re: AtomicReference.updateAndGet() mandatory updating?

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating?

Mike Duigou
I am glad that my original question led to such a fruitful discussion.
With the conclusion that the Java 8 semantics will be preserved as much
as possible and the Java 9 descriptions (and implementations?) will be
amended to conform is there interest in pursuing the "optimized"
write-eliminating versions? For algorithms (most?) that don't rely on
the CAS write happening for unchanged values elimination of the write
seems like a sizeable win for functions that rarely change the value.

public static <T> boolean compareAndSetOpt(AtomicReference<T> ref, T
expect, T update) {
   return expect != update
     ? ref.compareAndSet(expect, update)
     : expect == ref.get();
}

public static <V> V updateAndGetOpt(AtomicReference<V> ref,
UnaryOperator<V> updateFunction) {
      V prev = ref.get(), next = null;
      for (boolean haveNext = false;;) {
          if (!haveNext)
              next = updateFunction.apply(prev);
          if (compareAndSetOpt(ref, prev, next))
              return next;
          haveNext = (prev == (prev = ref.get()));
      }
}

Typical usage for me is a linked list:

class Foo {
   final AtomicReference<Foo> nextFoo = new AtomicReference<>();

   /**
    * Returns the successor Foo to this Foo creating it if necessary
    *
    * @return the next Foo
   */
   public Foo nextFoo() {
     return nextFoo.updateAndGet(e -> null != e ? e : new Foo());
   }
}

For this usage the value of nextFoo is only ever changed once, from null
to some Foo the first time nextFoo() is called. Because this particular
usage is extreme with the value only changing once I am actually using a
slightly different version of nextFoo() currently:

public Foo nextFoo() {
   Foo next = nextFoo.get();
   return null != next ? next : nextFoo.updateAndGet(e -> null != e ? e :
new Foo());
}

which optimizes for read at the cost of an extra volatile read for
update. I have other usages that are more balanced between the update
function returning the original value or a different value and use the
original version of nextFoo().
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: AtomicReference.updateAndGet() mandatory updating?

Justin Sampson
Hi Mike,

That particular use case really sounds like you want something like Guava's Suppliers.memoize(), which has the added benefit of guaranteeing to only invoke the lambda once (thereby avoiding the occasional garbage Foo being created).

Still, it does seem to me that we need some language somewhere in the JDK docs describing the kind of optimized CAS that you're talking about, since there are already two compareAndSet methods in j.u.c.atomic that behave that way.

Cheers,
Justin


On 6/5/17, 12:40 PM, "Concurrency-interest on behalf of Mike Duigou" <[hidden email] on behalf of [hidden email]> wrote:

    I am glad that my original question led to such a fruitful discussion.
    With the conclusion that the Java 8 semantics will be preserved as much
    as possible and the Java 9 descriptions (and implementations?) will be
    amended to conform is there interest in pursuing the "optimized"
    write-eliminating versions? For algorithms (most?) that don't rely on
    the CAS write happening for unchanged values elimination of the write
    seems like a sizeable win for functions that rarely change the value.
   
    public static <T> boolean compareAndSetOpt(AtomicReference<T> ref, T
    expect, T update) {
       return expect != update
         ? ref.compareAndSet(expect, update)
         : expect == ref.get();
    }
   
    public static <V> V updateAndGetOpt(AtomicReference<V> ref,
    UnaryOperator<V> updateFunction) {
          V prev = ref.get(), next = null;
          for (boolean haveNext = false;;) {
              if (!haveNext)
                  next = updateFunction.apply(prev);
              if (compareAndSetOpt(ref, prev, next))
                  return next;
              haveNext = (prev == (prev = ref.get()));
          }
    }
   
    Typical usage for me is a linked list:
   
    class Foo {
       final AtomicReference<Foo> nextFoo = new AtomicReference<>();
   
       /**
        * Returns the successor Foo to this Foo creating it if necessary
        *
        * @return the next Foo
       */
       public Foo nextFoo() {
         return nextFoo.updateAndGet(e -> null != e ? e : new Foo());
       }
    }
   
    For this usage the value of nextFoo is only ever changed once, from null
    to some Foo the first time nextFoo() is called. Because this particular
    usage is extreme with the value only changing once I am actually using a
    slightly different version of nextFoo() currently:
   
    public Foo nextFoo() {
       Foo next = nextFoo.get();
       return null != next ? next : nextFoo.updateAndGet(e -> null != e ? e :
    new Foo());
    }
   
    which optimizes for read at the cost of an extra volatile read for
    update. I have other usages that are more balanced between the update
    function returning the original value or a different value and use the
    original version of nextFoo().
 

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

Re: AtomicReference.updateAndGet() mandatory updating?

Martin Buchholz-3
In reply to this post by Mike Duigou
I'm still hoping for a failed CAS to NOT be equivalent to a volatile write, but instead a volatile read, as in C++.

For low-level lock-free linked list manipulating code (LinkedTransferQueue), I would not use updateAndGet but instead write my own CAS loops.

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