[concurrency-interest] CAS patterns (Re: Reference Collections)

David M. Lloyd david.lloyd at redhat.com
Wed Jan 4 12:23:58 EST 2012


Good to know.  I ask because I commonly use this sort of pattern with 
int/long field updaters:

int old, new;
do {
     old = fieldVal;
     if (old == threshold) { return; }
     new = old + diff;
} while (! updater.compareAndSet(this, old, new));
...act on new value...

which strikes me as being read/compare/read+write as well as subject to 
spurious failure under contention.  Sometimes, however, it is possible 
to do this instead:

int old = updater.getAndAdd(this, diff);
if (old + diff > threshold) {
    updater.getAndAdd(this, -diff);
    return;
}
...act on new value...

which is semantically the same (assuming you have a big enough "cushion" 
that the updated field can't wrap or whatever), but it's hard to say 
whether it's "better".

On 01/04/2012 10:59 AM, Nathan Reynolds wrote:
> Yes. A CAS operation has to load the cache line, invalidate the cache
> line on all other processors, do the comparison and possibly write to
> the cache line. A volatile read only has to load the cache line and
> perform the comparison in another instruction. The volatile read +
> comparison saves time by avoiding the invalidation.
>
> The queue will be empty most of the time. Only right after GC will the
> queue have entries. Those entries will be removed and the queue will
> become empty again. The common case is for the queue to be empty. So, if
> the queue is not empty, then the volatile read + comparison + CAS
> (tryLock) will take longer. However, this longer path will save time for
> the common case.
>
> When the queue is non-empty, the threads will execute tryLock() on each
> access. This means while 1 thread is busy cleaning the queue, the other
> threads will tryLock() several times. A better approach would be to do
> the following. This code does the volatile read and comparison. If the
> queue is not empty, then with 1 CAS instruction the queue is made empty
> and the thread gets the entire contents of the queue. The thread can
> then process the queue and the rest of the threads will see an empty queue.
>
> public Reference<? extends T> pollAll()
> {
> Reference<? extends T> head;
>
> do
> {
> head = this.head;
>
> if (head == null)
> return(null);
> }
> while (!s_atomicHead.compareAndSet(this, head, null));
>
> return(head);
> }
>
> Nathan Reynolds
> <http://psr.us.oracle.com/wiki/index.php/User:Nathan_Reynolds> |
> Consulting Member of Technical Staff | 602.333.9091
> Oracle PSR Engineering <http://psr.us.oracle.com/> | Server Technology
>
> On 1/4/2012 9:11 AM, David M. Lloyd wrote:
>> Are you saying that a failed CAS has greater impact than a volatile
>> read + external comparison?
>>
>> On 01/04/2012 09:56 AM, Nathan Reynolds wrote:
>>>> Do you think that all calling threads attempting to obtain the
>>>> tryLock(), (once only) will cause any performance issues?
>>>
>>> tryLock() will ideally execute a CAS instruction to acquire the lock.
>>> Under no contention, this means that each access will execute a CAS.
>>> This is going to be a performance problem. It will cost at least 10s of
>>> cycles. If you're lucky, it won't be significant. Under contention, the
>>> CAS instruction will stall the processor pipeline and become a
>>> bottleneck. If the tryLock() is called heavily, the system won't be able
>>> to scale past 3-socket Nehalem system.
>>>
>>> The JDK's ReferenceQueue.poll() simply reads a volatile variable. If the
>>> queue is empty, then the impact will simply be reading the variable's
>>> value from cache or RAM. If the value is in L1 cache, then this will
>>> only cost 3 cycles. If the queue is not empty, then the code acquires a
>>> lock and does the poll operation. You probably want to do likewise
>>> except instead of acquiring the lock, do a tryLock(). Thus, threads
>>> won't block on the clean up.
>>>
>>> Nathan Reynolds
>>> <http://psr.us.oracle.com/wiki/index.php/User:Nathan_Reynolds> |
>>> Consulting Member of Technical Staff | 602.333.9091
>>> Oracle PSR Engineering <http://psr.us.oracle.com/> | Server Technology
>>>
>>> On 1/4/2012 5:02 AM, Peter Firmstone wrote:
>>>> Hi,
>>>>
>>>> Over at river.apache.org, we've got a reference collections library,
>>>> utilised for concurrent caches, it's straightforward clean and simple
>>>> code. Easy to use, although Generics are a little verbose. RC is a
>>>> class with a simple public api, containing static methods used to wrap
>>>> any of the java collections interfaces, allowing you to use any
>>>> reference type, to refer to objects contained in your collections.
>>>>
>>>> All implementation is package private, sync / locking strategies are
>>>> left to the underlying collection, removal / cleaning is performed by
>>>> any thread that obtains a lock on a private ReferenceQueue (each
>>>> collection has it's own), which is guarded by a
>>>> ReentrantLock.tryLock(),
>>>> threads that don't obtain the lock, continue without performing any
>>>> cleanup. Do you think that all calling threads attempting to obtain the
>>>> tryLock(), (once only) will cause any performance issues? Garbage
>>>> collection occurs concurrently with other operations.
>>>>
>>>> Reference types available are Weak Identity, Weak, Soft Identity, Soft
>>>> and Strong. It's relatively simple to add additional reference types
>>>> such as a timed reference, however this isn't implemented at present.
>>>>
>>>> Here's a useage example, straight from our SecurityManager code:
>>>>
>>>> <SNIP>
>>>> private final ConcurrentMap<AccessControlContext,
>>>> NavigableSet<Permission>> checked;
>>>> private final Comparator<Referrer<Permission>> permCompare;
>>>> </SNIP>
>>>>
>>>> <SNIP-FROM-CONSTRUCTOR>
>>>> ConcurrentMap<Referrer<AccessControlContext>,Referrer<NavigableSet<Permission>>>
>>>> refmap
>>>> = new
>>>> ConcurrentHashMap<Referrer<AccessControlContext>,Referrer<NavigableSet<Permission>>>(100);
>>>>
>>>>
>>>> checked = RC.concurrentMap(refmap, Ref.SOFT, Ref.STRONG);
>>>> permCompare = RC.comparator(new PermissionComparator());
>>>>
>>>> </SNIP-FROM-CONSTRUCTOR>
>>>>
>>>> <SNIP-METHOD>
>>>> @Override
>>>> public void checkPermission(Permission perm, Object context) throws
>>>> SecurityException {
>>>> if (!(context instanceof AccessControlContext)) throw new
>>>> SecurityException();
>>>> if (perm == null ) throw new NullPointerException("Permission
>>>> Collection null");
>>>> /* The next line speeds up permission checks related to this
>>>> SecurityManager. */
>>>> if ( SMPrivilegedContext.equals(context) ||
>>>> SMConstructorContext.equals(context)) return; // prevents endless loop
>>>> in debug.
>>>> AccessControlContext executionContext = (AccessControlContext)
>>>> context;
>>>> // Checks if Permission has already been checked for this
>>>> context.
>>>> NavigableSet<Permission> checkedPerms =
>>>> checked.get(executionContext);
>>>> if (checkedPerms == null){
>>>> /* A ConcurrentSkipListSet is used to avoid blocking during
>>>> * removal operations that occur while the garbage collector
>>>> * recovers softly reachable memory. Since this happens
>>>> while
>>>> * the jvm's under stress, it's important that permission
>>>> checks
>>>> * continue to perform well.
>>>> *
>>>> * Although I considered a multi read, single write Set, I
>>>> wanted
>>>> * to avoid blocking under stress, caused as a result
>>>> * of garbage collection.
>>>> *
>>>> * The Reference Collection that encapsulates the
>>>> ConcurrentSkipListSet
>>>> * uses a ReentrantLock.tryLock() guard the ReferenceQueue
>>>> used
>>>> * to remove objects from the Set. This allows other
>>>> threads to
>>>> * proceed during object removal. Only one thread is given
>>>> access
>>>> * to the ReferenceQueue, the unlucky caller thread performs
>>>> garbage
>>>> * removal from the Set before accessing the Set for its
>>>> original
>>>> * purpose.
>>>> */
>>>> NavigableSet<Referrer<Permission>> internal =
>>>> new
>>>> ConcurrentSkipListSet<Referrer<Permission>>(permCompare);
>>>> checkedPerms = RC.navigableSet(internal, Ref.SOFT);
>>>> NavigableSet<Permission> existed =
>>>> checked.putIfAbsent(executionContext, checkedPerms);
>>>> if (existed != null) checkedPerms = existed;
>>>> }
>>>> if (checkedPerms.contains(perm)) return; // don't need to check
>>>> again.
>>>>
>>>> </SNIP-METHOD>
>>>>
>>>> Serialization is implemented so implementations can be replaced and
>>>> upgraded, serial form is a separate concern; see the Serialization
>>>> Builder pattern for details:http://wiki.apache.org/river/Serialization
>>>>
>>>> This a copy of some implementation code:
>>>>
>>>> /*
>>>> * Licensed to the Apache Software Foundation (ASF) under one
>>>> * or more contributor license agreements. See the NOTICE file
>>>> * distributed with this work for additional information
>>>> * regarding copyright ownership. The ASF licenses this file
>>>> * to you under the Apache License, Version 2.0 (the
>>>> * "License"); you may not use this file except in compliance
>>>> * with the License. You may obtain a copy of the License at
>>>> *
>>>> *http://www.apache.org/licenses/LICENSE-2.0
>>>> *
>>>> * Unless required by applicable law or agreed to in writing, software
>>>> * distributed under the License is distributed on an "AS IS" BASIS,
>>>> * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
>>>> implied.
>>>> * See the License for the specific language governing permissions and
>>>> * limitations under the License.
>>>> */
>>>>
>>>> package org.apache.river.impl.util;
>>>>
>>>>
>>>> import java.lang.ref.Reference;
>>>> import java.util.Random;
>>>> import java.util.concurrent.ConcurrentMap;
>>>> import java.util.logging.Level;
>>>> import java.util.logging.Logger;
>>>>
>>>> /**
>>>> * A referenced hash map, that encapsulates and utilises any
>>>> ConcurrentMap
>>>> * implementation passed in at construction.
>>>> *
>>>> * Based on any ConcurrentMap implementation, it doesn't accept null
>>>> keys or values.
>>>> *
>>>> * It is recommended although not mandatory to use identity based
>>>> References for keys,
>>>> * unexpected results occur when relying on equal keys, if one key is no
>>>> longer
>>>> * strongly reachable and has been garbage collected and removed from
>>>> the
>>>> * Map.
>>>> *
>>>> *
>>>> *
>>>> * If either a key or value, is no longer strongly reachable, their
>>>> mapping
>>>> * will be queued for removal and garbage collection, in compliance with
>>>> * the Reference implementation selected.
>>>> *
>>>> * @param<K>
>>>> * @param<V>
>>>> * @see Ref
>>>> * @author Peter Firmstone.
>>>> *
>>>> * @since 2.3
>>>> */
>>>> class ReferenceConcurrentMap<K, V> extends ReferenceMap<K, V>
>>>> implements
>>>> ConcurrentMap<K, V> {
>>>>
>>>> // ConcurrentMap must be protected from null values? It changes
>>>> it's behaviour, is that a problem?
>>>> private final ConcurrentMap<Referrer<K>, Referrer<V>> map;
>>>>
>>>> ReferenceConcurrentMap(ConcurrentMap<Referrer<K>,Referrer<V>> map,
>>>> Ref key, Ref val){
>>>> super (map, key, val);
>>>> this.map = map;
>>>> }
>>>>
>>>> ReferenceConcurrentMap(ConcurrentMap<Referrer<K>, Referrer<V>> map,
>>>> ReferenceQueuingFactory<K, Referrer<K>> krqf,
>>>> ReferenceQueuingFactory<V, Referrer<V>> vrqf, Ref key, Ref val){
>>>> super(map, krqf, vrqf, key, val);
>>>> this.map = map;
>>>> }
>>>>
>>>> public V putIfAbsent(K key, V value) {
>>>> processQueue(); //may be a slight delay before atomic
>>>> putIfAbsent
>>>> Referrer<K> k = wrapKey(key, true, false);
>>>> Referrer<V> v = wrapVal(value, true, false);
>>>> Referrer<V> val = map.putIfAbsent(k, v);
>>>> while ( val != null ) {
>>>> V existed = val.get();
>>>> // We hold a strong reference to value, so
>>>> if ( existed == null ){
>>>> // stale reference must be replaced, it has been garbage
>>>> collect but hasn't
>>>> // been removed, we must treat it like the entry doesn't
>>>> exist.
>>>> if ( map.replace(k, val, v)){
>>>> // replace successful
>>>> return null; // Because officially there was no
>>>> record.
>>>> } else {
>>>> // Another thread may have replaced it.
>>>> val = map.putIfAbsent(k, v);
>>>> }
>>>> } else {
>>>> return existed;
>>>> }
>>>> }
>>>> return null;
>>>> }
>>>>
>>>> @SuppressWarnings("unchecked")
>>>> public boolean remove(Object key, Object value) {
>>>> processQueue();
>>>> return map.remove(wrapKey((K) key, false, true), wrapVal((V)
>>>> value, false, true));
>>>> }
>>>>
>>>> public boolean replace(K key, V oldValue, V newValue) {
>>>> processQueue();
>>>> return map.replace(wrapKey(key, false, true), wrapVal(oldValue,
>>>> false, true), wrapVal(newValue, true, false));
>>>> }
>>>>
>>>> public V replace(K key, V value) {
>>>> processQueue();
>>>> Referrer<V> val = map.replace(wrapKey(key, false, true),
>>>> wrapVal(value, true, false));
>>>> if ( val != null ) return val.get();
>>>> return null;
>>>> }
>>>> }
>>>>
>>>> /*
>>>> * Licensed to the Apache Software Foundation (ASF) under one
>>>> * or more contributor license agreements. See the NOTICE file
>>>> * distributed with this work for additional information
>>>> * regarding copyright ownership. The ASF licenses this file
>>>> * to you under the Apache License, Version 2.0 (the
>>>> * "License"); you may not use this file except in compliance
>>>> * with the License. You may obtain a copy of the License at
>>>> *
>>>> *http://www.apache.org/licenses/LICENSE-2.0
>>>> *
>>>> * Unless required by applicable law or agreed to in writing, software
>>>> * distributed under the License is distributed on an "AS IS" BASIS,
>>>> * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
>>>> implied.
>>>> * See the License for the specific language governing permissions and
>>>> * limitations under the License.
>>>> */
>>>>
>>>> package org.apache.river.impl.util;
>>>>
>>>> import java.io.InvalidObjectException;
>>>> import java.io.ObjectInputStream;
>>>> import java.io.ObjectStreamException;
>>>> import java.io.Serializable;
>>>> import java.io.WriteAbortedException;
>>>> import java.lang.ref.Reference;
>>>> import java.lang.ref.ReferenceQueue;
>>>> import java.util.AbstractCollection;
>>>> import java.util.ArrayList;
>>>> import java.util.Collection;
>>>> import java.util.Iterator;
>>>> import java.util.List;
>>>> import java.util.Set;
>>>> import java.util.logging.Level;
>>>> import java.util.logging.Logger;
>>>>
>>>> /**
>>>> * A Collection of Reference Objects, the developer may chose any
>>>> Collection
>>>> * implementation to store the References, which is passed in a runtime.
>>>> *
>>>> * The underlying Collection implementation governs the specific
>>>> behaviour of this
>>>> * Collection.
>>>> *
>>>> * Synchronisation must be implemented by the underlying Collection and
>>>> cannot
>>>> * be performed externally to this class. The underlying Collection
>>>> must
>>>> * also be mutable. Objects will be removed automatically from the
>>>> underlying
>>>> * Collection when they are eligible for garbage collection.
>>>> *
>>>> * Weak, Weak Identity, Soft, Soft Identity or Strong references may be
>>>> used.
>>>> * This Collection may be used as an Object pool cache or any other
>>>> purpose
>>>> * that requires unique memory handling.
>>>> *
>>>> * For concurrent threads, it is recommended to encapsulate the
>>>> underlying
>>>> * collection in a multi read, single write collection for scalability.
>>>> *
>>>> * @see Ref
>>>> * @see ConcurrentCollections#multiReadCollection(java.util.Collection)
>>>> * @author Peter Firmstone.
>>>> */
>>>> class ReferenceCollection<T> extends AbstractCollection<T>
>>>> implements Collection<T>, Serializable {
>>>> private static final long serialVersionUID = 1L;
>>>> private final Collection<Referrer<T>> col;
>>>> private final ReferenceQueuingFactory<T, Referrer<T>> rqf;
>>>> private final Ref type;
>>>>
>>>> ReferenceCollection(Collection<Referrer<T>> col, Ref type){
>>>> this(col, new ReferenceProcessor<T>(col, type, type ==
>>>> Ref.STRONG ? null : new ReferenceQueue<T>()), type);
>>>> }
>>>>
>>>> ReferenceCollection(Collection<Referrer<T>> col,
>>>> ReferenceQueuingFactory<T, Referrer<T>> rqf, Ref type){
>>>> this.col = col;
>>>> this.rqf = rqf;
>>>> this.type = type;
>>>> }
>>>>
>>>> void processQueue(){
>>>> rqf.processQueue();
>>>> }
>>>>
>>>> ReferenceQueuingFactory<T, Referrer<T>> getRQF(){
>>>> return rqf;
>>>> }
>>>>
>>>> Ref getRef(){
>>>> return type;
>>>> }
>>>>
>>>> Referrer<T> wrapObj(T t, boolean enqueue, boolean temporary){
>>>> return rqf.referenced(t, enqueue, temporary);
>>>> }
>>>>
>>>> public int size() {
>>>> processQueue();
>>>> return col.size();
>>>> }
>>>>
>>>> public boolean isEmpty() {
>>>> processQueue();
>>>> return col.isEmpty();
>>>> }
>>>>
>>>> public boolean contains(Object o) {
>>>> processQueue();
>>>> return col.contains(wrapObj((T) o, false, true));
>>>> }
>>>>
>>>> /**
>>>> * This Iterator may return null values if garbage collection
>>>> * runs during iteration.
>>>> *
>>>> * Always check for null values.
>>>> *
>>>> * @return T - possibly null.
>>>> */
>>>> public Iterator<T> iterator() {
>>>> processQueue();
>>>> return new ReferenceIterator<T>(col.iterator());
>>>> }
>>>>
>>>> public boolean add(T e) {
>>>> processQueue();
>>>> return col.add(wrapObj(e, true, false));
>>>> }
>>>>
>>>> public boolean remove(Object o) {
>>>> processQueue();
>>>> return col.remove(wrapObj((T) o, false, true));
>>>> }
>>>>
>>>>
>>>> @SuppressWarnings("unchecked")
>>>> public boolean containsAll(Collection<?> c) {
>>>> processQueue();
>>>> return col.containsAll(new CollectionWrapper<T>((Collection<T>)
>>>> c, getRQF(), false, true));
>>>> }
>>>>
>>>>
>>>> @SuppressWarnings("unchecked")
>>>> public boolean addAll(Collection<? extends T> c) {
>>>> processQueue();
>>>> return col.addAll(new CollectionWrapper<T>((Collection<T>) c,
>>>> getRQF(), true, false));
>>>> }
>>>>
>>>> public void clear() {
>>>> col.clear();
>>>> }
>>>>
>>>> /*
>>>> * The next three methods are suitable implementations for
>>>> subclasses also.
>>>> */
>>>> public String toString(){
>>>> return col.toString();
>>>> }
>>>>
>>>> @Override
>>>> public int hashCode() {
>>>> if ( col instanceof List || col instanceof Set ){
>>>> return col.hashCode();
>>>> }
>>>> return System.identityHashCode(this);
>>>> }
>>>>
>>>> /**
>>>> * Because equals and hashCode are not defined for collections, we
>>>> * cannot guarantee consistent behaviour by implementing equals and
>>>> * hashCode. A collection could be a list, set, queue or deque.
>>>> * So a List != Queue and a Set != list. therefore equals for
>>>> collections is
>>>> * not defined.
>>>> *
>>>> * However since two collections may both also be Lists, while
>>>> abstracted
>>>> * from the client two lists may still be equal.
>>>> * @see Collection#equals(java.lang.Object)
>>>> */
>>>>
>>>> @Override
>>>> public boolean equals(Object o){
>>>> if ( o == this ) return true;
>>>> if ( col instanceof List || col instanceof Set ){
>>>> return col.equals(o);
>>>> }
>>>> return false;
>>>> }
>>>>
>>>> final Object writeReplace() throws ObjectStreamException {
>>>> try {
>>>> // returns a Builder instead of this class.
>>>> return SerializationOfReferenceCollection.create(getClass(),
>>>> col, type );
>>>> } catch (InstantiationException ex) {
>>>> throw new WriteAbortedException("Unable to create
>>>> serialization proxy", ex);
>>>> } catch (IllegalAccessException ex) {
>>>> throw new WriteAbortedException("Unable to create
>>>> serialization proxy", ex);
>>>> }
>>>> }
>>>>
>>>> private void readObject(ObjectInputStream stream)
>>>> throws InvalidObjectException{
>>>> throw new InvalidObjectException("Builder required");
>>>> }
>>>>
>>>> }
>>>>
>>>>
>>>> _______________________________________________
>>>> Concurrency-interest mailing list
>>>> Concurrency-interest at cs.oswego.edu
>>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>
>>>
>>> _______________________________________________
>>> Concurrency-interest mailing list
>>> Concurrency-interest at cs.oswego.edu
>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>>


-- 
- DML


More information about the Concurrency-interest mailing list