|
J avolution v5.3 (J2SE 1.5+) | ||||||||
PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES |
java.util.
See:
Description
Interface Summary
FastCollection.Record
This interface represents the collection records which can directly be
iterated over.
Class Summary
FastBitSet
This class represents either a table of bits or a set of non-negative
numbers.
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 thread-safe without external
synchronization when shared
.
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).
Index
This class represents a unique index which can be used instead of
java.lang.Integer
for primitive data types collections.
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 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 objects are not inserted/removed during iterations. Objects can safely be
append/prepend by the current thread or other threads.
(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();
}
}
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.
tmp.addAll(persons);
persons.clear();
persons.addAll(tmp);
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 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:
- 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).
- 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();
}
}
- 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!
- 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.
* 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.
- Are all Javolution collection thread-safe?
Collections/Maps are thread-safe with regard to access (no need to
synchronize reading even if the collection is modified concurrently).
But the modifications themselves require either the collection/map to be
marked shared or synchronization to be used.
- What is the overhead in term of performance when
FastMap.setShared
is set to true
?
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).
Overview
Package
Class
Tree
Deprecated
Index
Help
J
avolution v5.3 (J2SE 1.5+)
PREV PACKAGE
NEXT PACKAGE
FRAMES
NO FRAMES
Copyright © 2005 - 2009 Javolution.