Package javolution37.javolution.util

Provides high-performance collection classes and miscellaneous utilities; although this package provides very few collection classes, they are substitutes for most of java.util.* classes (for example, java.util.IdentityHashMap would be a FastMap with an identity key comparator).

See: Description

Interface Summary

Interface	Description
FastCollection.Record	This interface represents the collection records which can directly be iterated over.

Class Summary

Class	Description
FastCollection<E>	This class represents collections which can quickly be iterated over (forward or backward) in a thread-safe manner without creating new objects and without using iterators .
FastComparator<T>	This class represents a comparator to be used for equality as well as for ordering; instances of this class provide a hashcode function consistent with equal (if two objects are equal, they have the same hashcode), equality with null values is supported.
FastList<E>	This class represents a linked list with real-time behavior; smooth capacity increase and no memory allocation as long as the list size does not exceed its initial capacity.
FastList.Node<E>	This class represents a FastList node; it allows for direct iteration over the list values.
FastMap<K,V>	This class represents a hash map with real-time behavior; smooth capacity increase and no rehashing ever performed.
FastMap.Entry<K,V>	This class represents a FastMap entry.
FastSet<E>	This class represents a set collection backed by a FastMap; smooth capacity increase and no rehashing ever performed.
FastTable<E>	This class represents a random access collection with real-time behavior; smooth capacity increase (no array resize/copy ever) and no memory allocation as long as the collection size does not exceed its initial capacity.
FastTable.Index	This class represents a FastTable index; it allows for direct iteration over the collection.
LocalMap<K,V>	This class represents a map which can be temporarily modified without impacting other threads (locally scoped changes).
ReentrantLock	This class represents a reentrant lock with the same semantics as built-in Java synchronized locks: Once a thread has a lock, it can re-obtain it any number of times without blocking.
StandardLog	This class represents a specialized logging context forwarding events to a standard logger (java.util.logging.Logger).

Package javolution37.javolution.util Description

Provides high-performance collection classes and miscellaneous utilities; although this package provides very few collection classes, they are substitutes for most of java.util.* classes (for example, java.util.IdentityHashMap would be a FastMap with an identity key comparator).

Overview:

Javolution collections are compliant with standard collections (generic when built with the ant target 1.5) and they can safely be used with RTSJ virtual machines (e.g. if the capacity of a collection increases, the extension part is allocated from the same memory area as the collection itself).

They support direct iterations with the following advantages:

• Faster than iterators, see benchmark.
• No object creation not even the iterator object itself. For example, visiting a tree structure using iterators creates as many iterators as they are nodes in the tree:

      public static void visit(Collection<Collection> node) {
          for (Collection<Collection> i : node) { // Creates iterator.
              visit(i);
          }
      }

  Not so with direct iterations:

      public static void visit(FastCollection<FastCollection> node) {
          for (FastCollection.Record r = node.head(), end = node.tail(); (r = r.getNext()) != end;) {
              visit(node.valueOf(r));
          }
      }

• Used to implement most of FastCollection base class methods (including iterator()).
• Support forward/backward iterations from the start (head) or from the end (tail)
• Thread-Safe as long as the record sequence iterated over is not modified by another thread. Objects can safely be append/prepend by other threads during iteration but not inserted/removed. (Note: Shared FastMap are always thread-safe even when entries are removed).
• Fully integrated with the JDK1.5+ generic framework (strong typing) and still compatible with other platforms (J2ME, 1.4, GCJ).

Here are few examples of direct iterations:

    FastList<String> list;
    for (FastList.Node<String> n = list.head(), end = list.tail(); (n = n.getNext()) != end;) {
        String value = n.getValue(); // No typecast necessary.    
    }
    ...
    FastMap<String, Thread> map;
    for (FastMap.Entry<String, Thread> e = map.head(), end = map.tail(); (e = e.getNext()) != end;) {
        String key = e.getKey(); // No typecast necessary.
        Thread value = e.getValue(); // No typecast necessary.
    }

Users may provide a read-only view of any FastCollection (or FastMap) instance using the FastCollection.unmodifiable() (or FastMap.unmodifiable()) method. For example:

    public class Polynomial {
       
        private final FastSet<Term> _terms = new FastSet<Term>();

        // Read-only view (also thread-safe as terms are not "deleted").
        public Set<Term> getTerms() { 
            return _terms.unmodifiable();
        }
    }

Although all collections capacity increases smoothly (no resizing/copy or rehashing ever performed), it is nevertheless possible to specify an initial capacity; in which case, all necessary storage is allocated at creation. For RTSJ VMs, all collections/maps can reside in ImmortalMemory (e.g. static) and be used by all threads (including NoHeapRealtimeThread) without resulting into memory leaks or illegal access errors. For example:

    public class XmlFormat {
        // RTSJ Unsafe! Memory leaks (when entries removed) or IllegalAssignmentError (when new entries while in ScopedArea).   
        static HashMap<Class, XmlFormat> ClassToFormat = HashMap<Class, XmlFormat>();
        
       // RTSJ Safe! Removed entries are internally recycled, new entries are in ImmortalMemory.
       static FastMap<Class, XmlFormat> ClassToFormat = FastMap<Class, XmlFormat>();
   }

For more details, please read Javolution-Collection.pdf

.

Here is a summary of the collection classes with their defining characteristics:

Javolution Collections Classes

	Ordering	Duplication Allowed	Custom Comparators	Record Type	Miscellaneous
FastTable	Insertion Order	Yes	setValueComparator(FastComparator)	Index	Thread-safe random access collection No array resize/copy ever performed
FastList	Insertion Order	Yes	setValueComparator(FastComparator)	Node	Recycle their own nodes (no adverse effect on GC)
FastSet	Insertion Order	No	setValueComparator(FastComparator)	Record	Based on FastMap (same characteristics)
FastTree	Comparator	No	setValueComparator(FastComparator)	TreeNode	(not implemented)
FastMap	Insertion Order	Key: No Value: Yes	setKeyComparator(FastComparator) setValueComparator(FastComparator)	Entry	Thread-safe when marked as shared No rehash/resize ever performed Recycle their own entries (no adverse effect on GC)

FAQ:

1. ArrayList may throw ConcurrentModificationException, but Javolution FastTable does not, why?

   FastTable (or any Javolution collection/map) do support concurrent modifications as long as these are not insertions at an arbitrary position or deletions (Note: Shared FastMap does support concurrent deletions). In other words you can safely iterate (using iterators or not) through a FastList, FastMap (entries, keys values), FastTable, etc. while new elements/entries are being added (by you or another thread). You can also export a read-only view over your collection and still add more elements to it.

   Disallowing concurrent modifications (standard java util) has proven to be a performance killer for many (forcing users to work with copies of their whole collections). Furthermore the additional checks required directly impact performance (e.g. ArrayList iterations about 3x slower than FastTable iterations).

2. Do you have a test case showing any scenario of concurrent modification where ArrayList "fails" and FastTable doesn't?

   Let's say that you have a collection of "Units", and you want to provide users with a read-only view of these units. The following code will fail miserably:

       public class Unit {
           static ArrayList<Unit> INSTANCES = new ArrayList<unit>();
           public static List<Unit> getInstances() {
               return Collections.unmodifiableList(INSTANCES);
            }
       }

   Why? Because, it the user iterates on the read-only list of units while a new unit is added to the collection (by another thread) a ConcurrentModificationException is automatically raised. In other words, it is almost impossible to provide a "read-only" view of non-fixed size collections with the current java.util classes (e.g. you will have to replace the whole collection each time a new unit is added).

   Now with FastTable the following is completely safe even when new units are added:

       public class Unit {
           static FastTable<Unit> INSTANCES = new FastTable<unit>();
           public static List<Unit> getInstances() {
               return INSTANCES.unmodifiable();
           }
       }

3. Do checks for concurrent modifications make your code safer?

   Not really. The current checks for concurrent modifications do not "guarantee" that concurrent modifications will not occur! You can imagine two threads one updating a collection and the other one iterating the collection. As long as the update is not performed while the other thread is iterating, everything is fine (no ConcurrentModificationException)! But, if for a reason or another the timing changes (e.g. in the user environment) and iterations are performed at the wrong time then your application crashes... Not a good thing and very high probability for this to happen!

4. Are shared maps valid substitutes for ConcurrentHashMap?

   Unlike ConcurrentHashMap access to a shared FastMap never blocks. Retrieval reflects the map state not older than the last time the accessing thread has been synchronized (for multi-processors systems synchronizing ensures that the CPU internal cache is not stale).

   In practice, it means that most well-written concurrent programs should be able to use shared FastMap in place of ConcurrentHashMap as threads are already synchronized to ensure proper behavior.