AirConcurrentMap Iterators and forEach are faster than those for any Java library Map – even HashMap as shown here graphically. AirConcurrentMap also has two ways to provide fast Java Map scanning that are better than Iterators, forEach() or streams for any of the standard Java Maps, including HashMap, ConcurrentHashMap, TreeMap, and ConcurrentSkipListMap as shown. The scanning performance of Java Maps is normally limited either by the Java Map Iterators, or forEach() which are sequential, or else by the Java Map 8 streams feature, which has a parallel option. All of these standard Java Map scanning techniques are slower than the scanning techniques shown below. Memory efficiency is better than any of these Java Maps as well – see AirConcurrentMap Space Efficiency. For an extensive performance analysis see AirConcurrentMap_Performance_Testing.pdf . For overview see AirConcurrentMap. For more info contact support@boilerbay.com
If the AirConcurrentMap client code implements a subclass of MapVisitor by overriding visit(Object key,Object value), then that subclass can be used directly in a scan using the airConcurrentMap.visit(MapVisitor map) method in order to handle all of the key/value pairs in the Java Map in ascending order. The ascending ordering is possible because AirConcurrentMap not only implements ConcurrentMap, but also NavigableMap, which is a subinterface of SortedMap (these are all multiply-inherited by ConcurrentNavigableMap). If the client code further implements two simple methods – split() and merge() – in order to subclass ThreadedMapVisitor, then the airConcurrentMap.visit() method can similarly be invoked, but AirConcurrentMap will use a parallel scanning technique for extreme speed. The parallelization is internal and transparent.
Both of the techniques are available in Java Map versions 6 or 7 for AirConcurrentMap, making it compatible with systems that are not yet able to support the Java 8 streams, such as older Android phones, or “Internet of Things” distributed devices.
The performance of these techniques is higher than that for scanning any standard Java Map such as HashMap, TreeMap, ConcurrentHashMap, and ConcurrentSkipListMap using either Iterators or streams. Here is
The MapVisitor technique
Here is a MapVisitor. It can simply be invoked with airConcurrentMap.visit(MapVisitor) to print all of the key/value pairs in the Java Map:
static class PrintVisitor extends MapVisitor<Object, Object> {
public void visit(Object key, Object value) {
System.out.println("key=" + key + " value=" + value);
}
}
static class Summer extends MapVisitor<Object, Number> {
// We could use double or float as well.
long sum;
public long getSum(VisitableMap<?, Number> map) {
sum = 0;
map.visit(this);
return sum;
}
@Override
public void visit(Object key, Number value) {
sum += value.longValue();
}
}
Then this visitor can be used with AirConcurrentMap or other existing or future VisitableMaps very simply and in even less lines than a for loop:
System.out.println("sum=" + new Summer().getSum(map));
The ThreadedMapVisitor technique
The ThreadedMapVisitor technique only requires two additional methods and can be used anywhere a simple MapVisitor can be used (keys are not ordered):
static class ThreadedSummer extends ThreadedMapVisitor<Object, Number> {
// We could use double or float as well.
long sum;
public long getSum(VisitableMap<?, Number> map) {
sum = 0;
map.visit(this);
return sum;
}
@Override
public void visit(Object key, Number value) {
sum += value.longValue();
}
// One of the two threading-specific methods
@Override
public ThreadedMapVisitor<Object, Number> split() {
return new ThreadedSummer();
}
// The other threading-specific method
@Override
public void merge(ThreadedMapVisitor<Object, Number> visitor) {
this.sum += ((ThreadedSummer)visitor).sum;
}
}
Performance
The results of these techniques are shown below with a simple value summer. First, we show the results not even using MapVisitors at all, but just the usual Iterators. This is over the regular Map.values().iterator(): (The test source code is included in the distribution.)
As can be seen, the AirConcurrentMap Iterators are already several times faster than the standard Java Map Iterators, in particular the Iterators for ConcurrentSkipListMap (CSLM) and ConcurrentHashMap (CHM), which are representative of other non-concurrent Maps. Now we show the further performance improvement of the MapVisitor technique over all of the Java Map scanning techniques including Iterators and Java Map version 8 streaming, both sequential and parallel. We have an x-axis that is the logarithm of the Java Map size in order to show the entire spectrum of possible use cases.
AirConcurrentMap Iterators, in red, are good over the entire size scale, and are clearly optimal for the area to the right, above about 1K Entries, showing again tremendous performance. Furthermore, the topmost curve – the green one – is the AirConcurrentMap MapVisitor technique, which is about twice as fast again, and over almost all size scales. Notice that the streaming techniques are very peaky: the sequential stream peaks at 64 entries, and the parallel peaks at 32K entries, with an almost zero area near 32 entries. The MapVisitor wins from 32 to 16 million entries. The source code for these tests is included in the distribution.
Now finally, the ThreadedMapVisitor is compared with the Java 8 streams technique, this time with a linear x-axis. The algorithm is a summing of the values. The red line is AirConcurrentMap using ThreadedMapVisitor, CHM_STR_PAR is ConcurrentHashMap parallel stream, and CSLM_STR_PAR is ConcurrentSkipListMap parallel streaming. The latter two are the fastest way available in Java 8 to scan a Java Map. It is clear that AirConcurrentMap’s ThreadedMapVisitor scan is far faster. The test source code is included in the distribution. A quad-core Intel hyperthreaded system was used.
Implementation Simplicity
The ThreadedMapVisitor technique can be compared to the Java 8 streams feature in terms of amount of client code. The difference is primarily in the location of the implementation. With streams, the lambda feature can be used to reduce the apparent complexity in terms of lines of code, but the resulting readability is often not as high as expected from the terseness of the code. The MapVisitor technique makes the client code obvious at the point of use, and pushes the lines of code into the MapVisitor implementation.
For example, our first cut at a parallel summer with streams on a Map<Long, Number> is:
long sum = map.values().stream().parallel().reduce(0L, (x, y) -> x + y);
However, this produces a compile error because the values are not longs but Numbers so we try:
long sum = map.values().stream().parallel().reduce( 0L, (x, y) -> x.longValue() + y.longValue());
long sum = map.values().stream().parallel().reduce(
0L, (x, y) -> x.longValue() + y.longValue()).longValue();
System.out.println("sum by reducing=" + sum);
System.out.println("sum=" + new Summer().getSum(map));
With the predefined visitor the implementation of the scanning is separated from the client usage, so the implementation can be altered independently for speed or for any other reason. The total lines of code depends on the reuse frequency. Also, some environments, such as pre-Java-8 JVMs have no lambdas or streams. The MapVisitor can be made flexible so the getSum(..) can be made to handle regular Maps as well as Sets, Lists, arrays and so on. A possible extra overload of getSum(List) could be:
public long getSum(List<Number> list) {
return getSum(new VisitableListWrapper(list));
}
System.out.println("sum=" + new Summer().getSum(
new VisitableListWrapper<Number>(list));