Package 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

Package 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:

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.
        public Set<Term> getTerms() { 
            return _terms.unmodifiable();
        }
    }

Fast collections (or maps) can be made thread-safe by marking them FastCollection#shared shared Having a shared collection (or map) means that it can be safely used without synchronization. It does not mean that a change made by a thread is automatically viewed by another thread (that would require synchronizing). For example:

     class Foo {
          private static final Collection<Foo> INSTANCES = new FastTable().shared();
          public Foo() {
              INSTANCES.add(this);
         }
         public static void showInstances() {
             for (Foo foo : INSTANCES) {
                 System.out.println(foo);
             }
         }
     }

Collection/maps of primitive types can be created using the Index class. It avoids the overhead of wrapping primitives types (for reasonably small int values). For example:

    public class SparseVector<F> {
        FastMap<Index, F> _elements = new FastMap<Index, F>();
        ...
   }

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

.

Temporary collection classes can be recycled (e.g. throw-away collections) to avoid the creation cost. For example:

    static void removeDuplicate(List<Person> persons) {
        FastSet<Person> tmp = FastSet.newInstance(); // Possibly recycled instance.
        try {
            tmp.addAll(persons);
            persons.clear();
            persons.addAll(tmp);
        } finally {
            FastSet.recycle(tmp); // Recycles the temporary instance.
        }
   }

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 when marked as shared
No array resize/copy ever performed
FastList Insertion Order Yes setValueComparator(FastComparator) Node Thread-safe when marked as shared
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 the collections/maps are marked FastCollection#setShared shared. 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 or removed (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 Collection<Unit> getInstances() {
                return Collections.unmodifiableCollection(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 Collection<Unit> INSTANCES = new FastTable<unit>().shared();
            public static Collection<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 threads have 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. Nevertheless, if your code use ConcurrentHashMap to "synchronize" between two threads then shared FastMap is not going to work.

    * It is important for both threads to synchronize on the same monitor in order to set up the happens-before relationship properly. It is not the case that everything visible to thread A when it synchronizes on object X becomes visible to thread B after it synchronizes on object Y. The release and acquire have to "match" (i.e., be performed on the same monitor) to have the right semantics. Otherwise, the code has a data race.

  5. Are all Javolution collection thread-safe?

    Collections/Maps are thread-safe only if marked shared. In which case, the implementation may perform synchronization only when structural modification occurs.

  6. What is the overhead in term of performance when FastMap are shared ?

    Marking the map shared avoid synchronizing when possible (e.g. put when entry already exists or remove when entry does not exist), if a new entry is created and added, synchronization is performed internally. In all cases there is no impact on reading (never synchronized).

Copyright © 2005-2012 Javolution. All Rights Reserved.