[concurrency-interest] Reference Collections

Nathan Reynolds nathan.reynolds at oracle.com
Thu Jan 5 11:19:34 EST 2012


 >  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 
<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 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20120105/4b676c71/attachment-0001.html>


More information about the Concurrency-interest mailing list