Gang,
I have long (>10years) been annoyed over the mutability of the JDK
collection classes, especially since one has to take great care when
being in multi-threaded applications, especially the dreaded
ConcurrentModificationException, but also the general thread-safety is
fairly often missed giving nasty problems.
By using immutable collections, one can avoid a lot of that, and I
finally sat down and started working on this idea... (see listings
below).
The idea is that any "modification" returns a new instance with the
modification present. I am also growing fond of the Visitor pattern,
as we have used extensively in Qi4j (also avoids the CMException).
I was also concerned that if the collections are really large, the
performance impact would be too large, so a Builder concept was
introduced. So, some measurements for the HashMap implementation can
be found below...
The testcase is generating Random.nextLong() as Strings (both key and
value) into the HashMaps.
I will decline from making any conclusions to the numbers for now,
other than "Interesting".
So, what does this community think about Immutable and Thread-safe
Collection classes??
Numbers in brackets are "number of entries"
1-by-1 Populate ; For each value, map = map.put( k, v ), so a lot of
array copies happen in background.
(3) = 3000 ns/entry
(10) = 5800 ns/entry
(30) = 14266 ns/entry
(100) = 44920 ns/entry
(300) = 102840 ns/entry
(1000) = 94686 ns/entry
(3000) = 179593 ns/entry
(10000) = 573841 ns/entry
Builder Populate; The Builder is mutable and will create an immutable
HashMap at the end of it.
(3) = 1000 ns/entry
(10) = 500 ns/entry
(30) = 466 ns/entry
(100) = 270 ns/entry
(300) = 353 ns/entry
(1000) = 264 ns/entry
(3000) = 210 ns/entry
(10000) = 175 ns/entry
Visitor ; Visitor pattern, you map.visit( visitor ), and the HashMap
calls the visitor once per entry.
(3) = 333 ns/entry
(10) = 200 ns/entry
(30) = 133 ns/entry
(100) = 130 ns/entry
(300) = 120 ns/entry
(1000) = 117 ns/entry
(3000) = 143 ns/entry
(10000) = 29 ns/entry
JDK HashMap Populate, standard map.put( k, v ).
(3) = 1000 ns/entry
(10) = 600 ns/entry
(30) = 966 ns/entry
(100) = 910 ns/entry
(300) = 820 ns/entry
(1000) = 947 ns/entry
(3000) = 835 ns/entry
(10000) = 1436 ns/entry
JDK Iterate, for( Map.Entry<String,String> entry : map.entrySet() )
(3) = 1333 ns/entry
(10) = 600 ns/entry
(30) = 400 ns/entry
(100) = 400 ns/entry
(300) = 423 ns/entry
(1000) = 920 ns/entry
(3000) = 389 ns/entry
(10000) = 927 ns/entry
Initial cut on the interfaces;
-o-o-o-o-o-o-o-o-o-o-o-o-
public interface Collection<E>
{
int size();
boolean contains( E o );
boolean containsAll( Collection<E> c );
Collection<E> add( E e );
Collection<E> remove( E o );
Collection<E> addAll( Collection<E> c );
Collection<E> removeAll( Collection<E> c );
void visit( Collection.Visitor<E> visitor );
interface Visitor<E>
{
boolean visit( E value );
}
}
public interface List<E> extends Collection<E>
{
int size();
boolean contains( E o );
boolean containsAll( Collection<E> collection );
E get( int index );
int indexOf( E o );
int lastIndexOf( E o );
List<E> add( E e );
List<E> add( int index, E element );
List<E> remove( E o );
List<E> remove( int index );
List<E> replace( int index, E element );
List<E> subList( int fromIndex, int toIndex );
List<E> addAll( Collection<E> c );
List<E> addAll( int index, Collection<E> c );
List<E> removeAll( Collection<E> c );
}
public interface Set<E> extends Collection<E>
{
int size();
boolean contains( E o );
boolean containsAll( Collection<E> collection );
Set<E> add( E e );
Set<E> remove( E o );
Set<E> addAll( Collection<E> c );
Set<E> removeAll( Collection<E> c );
}
public interface Map<K, V>
{
int size();
boolean containsKey( K key );
boolean containsValue( V value );
V get( K key );
Map<K, V> put( K key, V value );
Map<K, V> remove( K key );
Map<K, V> putAll( Map<K,V> m );
Set<K> keySet();
Collection<V> values();
Set<Entry<K, V>> entrySet();
void visit( Map.Visitor<K,V> vistor );
interface Entry<K, V>
{
K getKey();
V getValue();
}
interface Visitor<K,V>
{
void visit( Map.Entry<K,V> entry );
}
}
--
Niclas Hedhman, Software Developer
http://www.qi4j.org - New Energy for Java
I live here; http://tinyurl.com/2qq9er
I work here; http://tinyurl.com/2ymelc
I relax here; http://tinyurl.com/2cgsug
_______________________________________________
general mailing list
general@lists.ops4j.org
http://lists.ops4j.org/mailman/listinfo/general
