[concurrency-interest] Reference Collections

Peter Firmstone peter.firmstone at zeus.net.au
Thu Jan 5 18:34:45 EST 2012


Thanks Nathan, can I use it under an Apache 2 license?

Peter.

On Fri, 2012-01-06 at 02:19, Nathan Reynolds wrote:
> >  The symptom seen by calling threads is occasional null return
> values in iterators. 
> 
> You can eliminate this problem by caching the next value in
> hasNext().  Here's an iterator which removes nulls from the source
> iterator.
> 
> public class NoNullIterator<T> implements Iterator<T>
> {
>    private final Iterator<T> m_source;
>    private       T           m_next;
> 
>    public NoNullIterator(Iterator<T> source)
>    {
>       if (source == null)
>          throw new NullPointerException();
> 
>       m_source = source;
>    }
> 
>    public boolean hasNext()
>    {
>       T next;
> 
>       if (m_next != null)
>          return(true);
> 
>       while (m_source.hasNext())
>       {
>          m_next = m_source.next();
>          
>          if (m_next != null)
>             return(true);
>       }
> 
>       return(false);
>    }
> 
>    public T next()
>    {
>       T result;
> 
>       if (m_next == null)
>          if (!hasNext())
>             throw new IllegalStateException();
> 
>       result = m_next;
>       m_next = null;
> 
>       return(result);
>    }
> 
>    public void remove()
>    {
>       m_source.remove();
>    }
> }
> 
> Nathan Reynolds | Consulting Member of Technical Staff | 602.333.9091
> Oracle PSR Engineering | Server Technology
> 
> On 1/4/2012 6:42 PM, Peter Firmstone wrote: 
> > Thanks David,
> > 
> > ...Hmm you're speaking from experience, had the privilege of meeting
> > briefly while you were at Sun in Brisbane.
> > 
> > Users will be given a choice of one dedicated cleanup thread (per
> > Collection) which waits on the ReferenceQueue OR CAS with
> > ReentrantLock.tryLock() to share cleanup between callers.
> > 
> > CAS for single or few threads and less memory consumption, the dedicated
> > cleanup thread for scalability.
> > 
> > Note: Maps will have up to two ReferenceQueue's and two dedicated
> > threads, if based on the existing design. EG: Weak Keys and Soft Values
> > or Weak Keys and Values, when there's a circular reference from the
> > value to the key.  Weak keys with strongly reference values will only
> > have one ReferenceQueue and one cleanup Thread.
> > 
> > Reference Collection's can be widely applied to any java collection
> > type, my current concern is scalability for large collections (including
> > concurrent maps) which I have no way of testing.
> > 
> > In the implementation, the only mutable state is in ReferenceQueue, the
> > underlying collection and Reference, everything else is final or uses
> > method variables.  Dummy References, used for reads, are created and
> > discarded and die young, so never enter main memory.  Hopefully the
> > majority of state should be in cache during execution.  My main concern
> > is the current design employed a ReentrantLock.tryLock() call to hand
> > maintenance to one of the calling threads, I was worried that this would
> > limit scalability.  The feedback so far is yes (info much appreciated).
> > 
> > If ReferenceQueue.remove() is only called by one thread, the calling
> > threads no longer need to perform cleanup, it's done by the maintenance
> > thread, which is blocked on remove, so doesn't consume cpu unless
> > required, although relative to the number of collections in use, will
> > consume more memory.
> > 
> > Nathan suggested more than one thread might be needed to perform
> > cleanup, due to experiences with jrocket's finalizer.  This situation
> > could occur briefly if a large number objects suddenly became reachable,
> > such as a large collection using soft references, when the jvm is low on
> > memory.  We were discussing work stealing, but I guess more concurrency
> > on a bottlenecking underlying collection won't help.
> > 
> > The symptom seen by calling threads is occasional null return values in
> > iterators.  This isn't a problem if the caller expects a null.  I'd
> > imagine the cleanup thread will catch up. ReferenceComparator
> > encapsulates existing Comparator's and guards against null.  This could
> > be a problem for existing code if the collection is used as a drop in
> > replacement.
> > 
> > My experience so far has been that null returns are easy to deal with in
> > new code.
> > 
> > What are your thoughts?
> > 
> > Regards,
> > 
> > Peter.
> > 
> > On Thu, 2012-01-05 at 09:18, David Holmes wrote:
> > > Peter Firmstone writes:
> > > > On Thu, 2012-01-05 at 07:52, Nathan Reynolds wrote:
> > > > > Would the fork-join framework with work steal be an ideal fit?
> > > > For ultimate scalability it would, although I'm unable to test for
> > > > scalability, only reason about it and ask questions of developers who do
> > > > have acces to big iron ;)  It might also make sense to use multiple
> > > > ReferenceQueue's for a collection under some circumstances.
> > > I don't see how FJ would be applicable here. What tasks are you forking and
> > > joining?
> > > 
> > > Using a Thread pool for the cleanup seems like the most scalable approach,
> > > but I think if you are beyond the point where a single cleanup thread
> > > suffices then your design is already in trouble.
> > > 
> > > David
> > > -----
> > > 
> > > > I've implemented Reference Collections to fulfill a need that our
> > > > project has, I'm sure very few are aware of its existence, but since it
> > > > has such a compact public API that's very easy to extend to new
> > > > collection interfaces, it could potentially make a very good collections
> > > > based library for using references in your favoured collection
> > > > implementation.  It's also possible to make new types of refernces, eg:
> > > > timer based.  There's no serialized form lock in either, so evolution
> > > > isn't hampered by serialization and serialization can be easily
> > > > supported in a backward compatible evolutionary manner.
> > > > 
> > > > If there's enough interest, we could split Reference Collections out as
> > > > a separate library or subproject.
> > > > 
> > > > The code can be seen here:
> > > > 
> > > > http://svn.apache.org/viewvc/river/jtsk/skunk/peterConcurrentPolic
> > > > y/src/org/apache/river/impl/util/
> > > > 
> > > > The unit tests here:
> > > > 
> > > > http://svn.apache.org/viewvc/river/jtsk/skunk/peterConcurrentPolic
> > > > y/test/src/org/apache/river/impl/util/
> > > > 
> > > > Or:
> > > > 
> > > > svn checkout (replacing viewvc with repos/asf):
> > > > 
> > > > https://svn.apache.org/repos/asf/river/jtsk/skunk/peterConcurrentP
> > > > olicy/src/org/apache/river/impl/util
> > > > 
> > > > This is the public API:
> > > > 
> > > > /*
> > > >  * 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.lang.Comparable;
> > > > import java.util.Collection;
> > > > import java.util.Collections;
> > > > import java.util.Comparator;
> > > > import java.util.Deque;
> > > > import java.util.List;
> > > > import java.util.Map;
> > > > import java.util.Map.Entry;
> > > > import java.util.ListIterator;
> > > > import java.util.NavigableMap;
> > > > import java.util.NavigableSet;
> > > > import java.util.Queue;
> > > > import java.util.Set;
> > > > import java.util.SortedMap;
> > > > import java.util.SortedSet;
> > > > import java.util.concurrent.BlockingDeque;
> > > > import java.util.concurrent.BlockingQueue;
> > > > import java.util.concurrent.ConcurrentMap;
> > > > import java.util.concurrent.ConcurrentNavigableMap;
> > > > 
> > > > /**
> > > >  * <p>
> > > >  * This class contains a number of static methods for using and
> > > > abstracting
> > > >  * References in Collections.  Interfaces from the Java Collections
> > > > Framework
> > > >  * are supported.
> > > >  * </p><p>
> > > >  * Referents in these collections may implement {@link Comparable} or
> > > >  * a {@link Comparator} may be used for sorting.  When Comparator's are
> > > > utilised,
> > > >  * they must first be encapsulated {@link
> > > > RC#comparator(java.util.Comparator) },
> > > >  * before passing to a constructor for your preferred underlying
> > > > Collection
> > > >  * implementation.
> > > >  * </p><p>
> > > >  * {@link Comparable} is not supported for IDENTITY == referenced
> > > > Collections,
> > > >  * in this case a Comparator must be used.
> > > >  * </p><p>
> > > >  * All other references support {@link Comparable}, if the referent
> > > > Object
> > > >  * doesn't implement {@link Comparable}, then {@link
> > > > Reference#hashCode()} is used
> > > >  * for sorting.  If two referent Objects have identical hashCodes,
> > > >  * but are unequal and do not implement {@link Comparable}, their
> > > > references
> > > >  * will also have identical hashCodes, so only one of the referents can
> > > >  * be added to a {@link SortedSet} or {@link SortedMap}.  This can be
> > > > fixed by using a
> > > >  * {@link Comparator}.
> > > >  * </p><p>
> > > >  * For all intents and purposes these utilities behave the same as your
> > > > preferred
> > > >  * underlying {@link Collection} implementation, with the exception of
> > > >  * {@link Reference} reachability.  An Object or Key,Value entry is
> > > > removed
> > > >  * from a {@link Collection} or {@link Map}, upon becoming eligible for
> > > >  * garbage collection.
> > > >  * </p><p>
> > > >  * Synchronisation must be implemented by your preferred {@link
> > > > Collection}
> > > >  * and cannot be performed externally to the returned {@link
> > > > Collection}.
> > > >  * Your chosen underlying {@link Collection} must also be mutable.
> > > >  * Objects will be removed automatically from underlying Collections
> > > > when
> > > >  * they are eligible for garbage collection, this breaks external
> > > > synchronisation.
> > > >  * {@link
> > > > CollectionsConcurrent#multiReadCollection(java.util.Collection)} may
> > > >  * be useful for synchronising your chosen underlying {@link
> > > > Collection},
> > > >  * especially if Objects are not being garbage collected often and
> > > > writes
> > > >  * are minimal.
> > > >  * </p><p>
> > > >  * An Unmodifiable wrapper {@link
> > > > Collections#unmodifiableCollection(java.util.Collection)}
> > > >  * may be used externally to prevent additions to the underlying
> > > > Collections,
> > > >  * referents will still be removed as they become unreachable however.
> > > >  * </p><p>
> > > >  * Note that any Sub List, Sub Set or Sub Map obtained by any of the
> > > > Java
> > > >  * Collections Framework interfaces, must be views of the underlying
> > > >  * Collection, if the Collection uses defensive copies instead of views,
> > > >  * References could potentially remain in one copy after garbage
> > > > collection,
> > > >  * causing null returns.  If using standard Java Collections Framework
> > > >  * implementations, these problems don't occur as all Sub Lists,
> > > >  * Sub Sets or Sub Maps are views only.
> > > >  * </p><p>
> > > >  * {@link Map#entrySet() } view instances returned preserve your chosen
> > > > reference
> > > >  * behaviour, they even support {@link Set#add(java.lang.Object)} or
> > > >  * {@link Set#addAll(java.util.Collection)} methods, although you'll be
> > > > hard
> > > >  * pressed to find a standard java implementation that does.  If you
> > > > have a
> > > >  * Map with a Set of Entry's implementing add, the implementation will
> > > > need a
> > > >  * Comparator, that compares Entry's only by their keys, to avoid
> > > > duplicating
> > > >  * keys, primarily because an Entry hashCode includes the both key and
> > > > value in its
> > > >  * calculation. {@link Entry#hashCode() }
> > > >  * </p><p>
> > > >  * All other {@link Map#entrySet() } methods are fully implemented and
> > > > supported.
> > > >  * </p><p>
> > > >  * {@link Entry} view instances returned by these methods preserve
> > > > reference
> > > >  * behaviour, all methods are fully implemented and supported.
> > > >  * </p><p>
> > > >  * {@link Set} and it's sub interfaces {@link SortedSet} and
> > > >  * {@link NavigableSet}, return views that preserve reference behaviour,
> > > >  * all methods are fully implemented and supported.
> > > >  * </p><p>
> > > >  * {@link Map} and it's sub interfaces {@link SortedMap}, {@link
> > > > NavigableMap},
> > > >  * {@link ConcurrentMap} and {@link ConcurrentNavigableMap} return
> > > >  * views that preserve reference behaviour, all methods are fully
> > > > implemented
> > > >  * and supported.
> > > >  * </p><p>
> > > >  * {@link List} returns views that preserve reference behaviour, all
> > > > methods are
> > > >  * fully implemented and supported.
> > > >  * </p><p>
> > > >  * {@link Queue} and it's sub interfaces {@link Deque}, {@link
> > > > BlockingQueue} and
> > > >  * {@link BlockingDeque} return views that preserve reference behaviour,
> > > >  * all methods are fully implemented and supported.
> > > >  * </p><p>
> > > >  * {@link Iterator} and {@link ListIterator} views preserve reference
> > > > behaviour, all methods
> > > >  * are fully implemented and supported.
> > > >  * </p><p>
> > > >  * Serialisation is supported, provided it is also supported by
> > > > underlying
> > > >  * collections.  Collections are not defensively copied during
> > > > de-serialisation,
> > > >  * due in part to an inability of determining whether a Comparator is
> > > >  * used and in part, that if it is, it prevents Class.newInstance()
> > > > construction.
> > > >  * </p><p>
> > > >  * Note that when a collection is first de-serialised, it's contents are
> > > >  * strongly referenced, then changed to the correct reference type.
> > > > This
> > > >  * will still occur, even if the Collection is immutable.
> > > >  * </p><p>
> > > >  * RC stands for Reference Collection and is abbreviated due to the
> > > > length of
> > > >  * generic parameter arguments typically required.
> > > >  * </p>
> > > >  * @see Ref
> > > >  * @see Referrer
> > > >  * @see Reference
> > > >  * @author Peter Firmstone.
> > > >  */
> > > > public class RC {
> > > >     private RC(){} // Non instantiable
> > > > 
> > > >     /**
> > > >      * When using a Comparator in SortedSet's and SortedMap's, the
> > > > Comparator
> > > >      * must be encapsulated using this method, to order the Set or Map
> > > >      * by referents and not References.
> > > >      *
> > > >      * @param <T>
> > > >      * @param comparator
> > > >      * @return
> > > >      */
> > > >     public static <T> Comparator<Referrer<T>> comparator(Comparator<?
> > > > super T> comparator){
> > > >         return new ReferenceComparator<T>(comparator);
> > > >     }
> > > > 
> > > >     /**
> > > >      * Wrap a Collection for holding references so it appears as a
> > > > Collection
> > > >      * containing referents.
> > > >      *
> > > >      * @param <T>
> > > >      * @param internal
> > > >      * @param type
> > > >      * @return
> > > >      */
> > > >     public static <T> Collection<T> collection(Collection<Referrer<T>>
> > > > internal, Ref type){
> > > >         return new ReferenceCollection<T>(internal, type, false);
> > > >     }
> > > > 
> > > > //    /**
> > > > //     * The general idea here is, create a factory that produces a the
> > > > underlying
> > > > //     * reference collection, then it can be used again later to
> > > > defensively
> > > > //     * produce a new copy of the original collection after
> > > > de-serialisation.
> > > > //     *
> > > > //     * @param <T>
> > > > //     * @param factory
> > > > //     * @param type
> > > > //     * @return
> > > > //     */
> > > > //    public static <T> Collection<T>
> > > > collection(CollectionFactory<Collection<Referrer<T>>> factory, Ref
> > > > type){
> > > > //        return new ReferenceCollection<T>(factory.create(), type);
> > > > //    }
> > > > 
> > > >     /**
> > > >      * Wrap a List for holding references so it appears as a List
> > > >      * containing referents.
> > > >      *
> > > >      * @param <T>
> > > >      * @param internal
> > > >      * @param type
> > > >      * @return
> > > >      */
> > > >     public static <T> List<T> list(List<Referrer<T>> internal, Ref
> > > > type){
> > > >         return new ReferenceList<T>(internal, type);
> > > >     }
> > > > 
> > > >     /**
> > > >      * Wrap a Set for holding references so it appears as a Set
> > > >      * containing referents.
> > > >      *
> > > >      * @param <T>
> > > >      * @param internal
> > > >      * @param type
> > > >      * @return
> > > >      */
> > > >     public static <T> Set<T> set(Set<Referrer<T>> internal, Ref type){
> > > >         return new ReferenceSet<T>(internal, type);
> > > >     }
> > > >     /**
> > > >      * Wrap a SortedSet for holding references so it appears as a
> > > > SortedSet
> > > >      * containing referents.
> > > >      *
> > > >      * @para        m <T>
> > > >      * @param internal
> > > >      * @param type
> > > >      * @return
> > > >      */
> > > >     public static <T> SortedSet<T> sortedSet(
> > > >             SortedSet<Referrer<T>> internal, Ref type){
> > > >         return new ReferenceSortedSet<T>(internal, type);
> > > >     }
> > > >     /**
> > > >      * Wrap a NavigableSet for holding references so it appears as a
> > > > NavigableSet
> > > >      * containing referents.
> > > >      *
> > > >      * @param <T>
> > > >      * @param internal
> > > >      * @param type
> > > >      * @return
> > > >      */
> > > >     public static <T> NavigableSet<T> navigableSet(
> > > >             NavigableSet<Referrer<T>> internal, Ref type){
> > > >         return new ReferenceNavigableSet<T>(internal, type);
> > > >     }
> > > >     /**
> > > >      * Wrap a Queue for holding references so it appears as a Queue
> > > >      * containing referents.
> > > >      *
> > > >      * @param <T>
> > > >      * @param internal
> > > >      * @param type
> > > >      * @return
> > > >      */
> > > >     public static <T> Queue<T> queue(Queue<Referrer<T>> internal, Ref
> > > > type){
> > > >         return new ReferencedQueue<T>(internal, type);
> > > >     }
> > > >     /**
> > > >      * Wrap a Deque for holding references so it appears as a Deque
> > > >      * containing referents.
> > > >      *
> > > >      * @param <T>
> > > >      * @param internal
> > > >      * @param type
> > > >      * @return
> > > >      */
> > > >     public static <T> Deque<T> deque(Deque<Referrer<T>> internal, Ref
> > > > type){
> > > >         return new ReferenceDeque<T>(internal, type);
> > > >     }
> > > >     /**
> > > >      * Wrap a BlockingQueue for holding references so it appears as a
> > > > BlockingQueue
> > > >      * containing referents.
> > > >      *
> > > >      * @param <T>
> > > >      * @param internal
> > > >      * @param type
> > > >      * @return
> > > >      */
> > > >     public static <T> BlockingQueue<T> blockingQueue(
> > > >             BlockingQueue<Referrer<T>> internal, Ref type){
> > > >         return new ReferenceBlockingQueue<T>(internal, type);
> > > >     }
> > > >     /**
> > > >      * Wrap a BlockingDeque for holding references so it appears as a
> > > > BlockingDeque
> > > >      * containing referents.
> > > >      *
> > > >      * @param <T>
> > > >      * @param internal
> > > >      * @param type
> > > >      * @return
> > > >      */
> > > >     public static <T> BlockingDeque<T> blockingDeque(
> > > >             BlockingDeque<Referrer<T>> internal, Ref type){
> > > >         return new ReferenceBlockingDeque<T>(internal, type);
> > > >     }
> > > >     /**
> > > >      * Wrap a Map for holding references so it appears as a Map
> > > >      * containing referents.
> > > >      *
> > > >      * @param <K>
> > > >      * @param <V>
> > > >      * @param internal
> > > >      * @param key
> > > >      * @param value
> > > >      * @return
> > > >      */
> > > >     public static <K, V> Map<K, V> map(
> > > >             Map<Referrer<K>, Referrer<V>> internal, Ref key, Ref value){
> > > >         return new ReferenceMap<K, V>(internal, key, value);
> > > >     }
> > > >     /**
> > > >      * Wrap a SortedMap for holding references so it appears as a
> > > > SortedMap
> > > >      * containing referents.
> > > >      *
> > > >      * @param <K>
> > > >      * @param <V>
> > > >      * @param internal
> > > >      * @param key
> > > >      * @param value
> > > >      * @return
> > > >      */
> > > >     public static <K, V> SortedMap<K, V> sortedMap(
> > > >             SortedMap<Referrer<K>, Referrer<V>> internal, Ref key, Ref
> > > > value){
> > > >         return new ReferenceSortedMap<K, V>(internal, key, value);
> > > >     }
> > > >     /**
> > > >      * Wrap a NavigableMap for holding Referrers so it appears as a
> > > > NavigableMap
> > > >      * containing referents.
> > > >      *
> > > >      * @param <K>
> > > >      * @param <V>
> > > >      * @param internal
> > > >      * @param key
> > > >      * @param value
> > > >      * @return
> > > >      */
> > > >     public static <K, V> NavigableMap<K, V> navigableMap(
> > > >             NavigableMap<Referrer<K>, Referrer<V>> internal, Ref key,
> > > > Ref value){
> > > >         return new ReferenceNavigableMap<K, V>(internal, key, value);
> > > >     }
> > > >     /**
> > > >      * Wrap a ConcurrentMap for holding references so it appears as a
> > > > ConcurrentMap
> > > >      * containing referents.
> > > >      *
> > > >      * @param <K> - key type.
> > > >      * @param <V> - value type.
> > > >      * @param internal - for holding references.
> > > >      * @param key - key reference type.
> > > >      * @param value - value reference type.
> > > >      * @return
> > > >      */
> > > >     public static <K, V> ConcurrentMap<K, V> concurrentMap(
> > > >             ConcurrentMap<Referrer<K>, Referrer<V>> internal, Ref key,
> > > > Ref value){
> > > >         return new ReferenceConcurrentMap<K, V>(internal, key, value);
> > > >     }
> > > > 
> > > >     /**
> > > >      * Wrap a ConcurrentNavigableMap for holding references so it
> > > > appears as a
> > > >      * ConcurrentNavigableMap containing referents.
> > > >      *
> > > >      * @param <K>
> > > >      * @param <V>
> > > >      * @param internal
> > > >      * @param key
> > > >      * @param value
> > > >      * @return
> > > >      */
> > > >     public static <K, V> ConcurrentNavigableMap<K, V>
> > > > concurrentNavigableMap(
> > > >             ConcurrentNavigableMap<Referrer<K>, Referrer<V>> internal,
> > > > Ref key, Ref value){
> > > >         return new ReferenceConcurrentNavigableMap<K, V>(internal, key,
> > > > value);
> > > >     }
> > > > }
> > > > 
> > > > 
> > > > _______________________________________________
> > > > 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



More information about the Concurrency-interest mailing list