AirConcurrentMap parallel scans are faster than streams

AirConcurrentMap is a Java ConcurrentNavigableMap that is free and closed-source for non-commercial uses and open-source for commercial uses.

High Performance

AirConcurrentMap has a high-performance threaded parallel scanning feature that provides about 4 times more speed than Java 8 serial or parallel streams over a wide spectrum of Map sizes. This diagram shows its parallel internally-threaded scan performance advantage, with parallel streams being significantly slower, for a simple sum. Here the red line is for the faster AirConcurrentMap ThreadedMapVisitors feature, while ConcurrentHashMap and ConcurrentSkipListMap parallel streams are green and blue. HashMap and other Maps have similar results. Serial streams are considerably slower.

The Full Use Case Spectrum

Here is the same information with a logarithmic x-axis to show the entire spectrum of use cases, from empty to 32 million entries. Going rightwards, each increment of 1 represents a Map 10 times larger. The AirConcurrentMap red line is far above the others over the entire range. The green line is a ‘MapVisitor’ feature that is similar but simpler, and serial, and it still beats the streams for either serial or parallel. The streams are for ConcurrentSkipListMap, and other Maps are similar. The algorithm is a summing of longs. For large Maps, AirConcurrentMap is roughly 4 to 10 times faster.

 

Java 8 Streams are Peaky

The Java streams implementation is very ‘peaky’ requiring the client to properly choose serial versus parallel execution in order to optimize performance. Both serial and parallel streams are effective over only a small subrange of the full spectrum of use cases as shown above, and both have significant ranges over which the performance is extremely low. Serial streams peak at about 64 entries, while parallel peaks at about 32K entries, and there are significant stalled ranges. AirConcurrentMap is faster than streams over the full range.

Client Code

The AirConcurrentMap client code simply implements a subclass of ThreadedMapVisitor and submits it to AirConcurrentMap for the fast internally-threaded parallel scan. Only two threading-related methods are overridden: split() and merge(), and they perform obvious trivial operations on the ThreadedMapVisitor, with the result being similar to map/reduce, but more flexible. A simpler class, MapVisitor, is the superclass of the ThreadedMapVisitor, and its abstract visit(K key, V value) method is implemented to accept the key/value pairs. To do a parallel sum, the client code can do something simple like:

        System.out.println("sum=" + new Summer().getSum(map));

Here is the code for a reusable parallel summing ThreadedVisitor:

    static class ThreadedSummer extends ThreadedMapVisitor<Object, Number> {
        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;
        }
    }

The getSum(VisitableMap) method is the external entry point, and the other three methods are used by the scan. This code is more flexible than map/reduce, using lambdas, for example, and is simpler and clearer at the point of client use, since the client simply instantiates the Summer  and invokes getSum() on a VisitableMap. Furthermore, the actual algorithm for the splitting and merging is under the control of the MapVisitor implementation for optimum speed. AirConcurrentMap is a VisitableMap, and other such VisitableMaps are in development. Also, there are wrappers for Lists, arrays, and Sets to allow the MapVisitors or ThreadedMapVisitor to be reused on them as well.

More Use Cases Including Iterators

This rather daunting chart shows almost all possible use cases, including keySet Iterators for AirConcurrentMap, ConcurrentHashMap and ConcurrentSkipListMap. Furthermore, The AirConcurrentMap MapVisitors, as well as ConcurrentSkipListMap serial and parallel streams are included. Note that the brown line, MapVisitors, is at the top over almost the entire range and has no stalled regions. This chart does not even show the ThreadedMapVisitors, which would be far above the top of the chart as shown in the chart above, and only the simpler serial MapVisitor implementation, with just the visit(K key, V value) method is shown. Even without AirConcurrentMap’s parallel scan, streams are shown to be inferior, being slow and peaky, with stalled regions. The x axis is logarithmic, meaning that each increment to the right doubles the Map size, and a wide spectrum of use cases is included. The brown line at top shows AirConcurrentMap’s simple serial MapVisitors, and the red line is its keySet Iterators: notice that towards the right – the area of very large Maps – AirConcurrentMap is far faster even for Iterators. Thus AirConcurrentMap is the dominant in-memory ‘big data’ key/value store.

 

See AirConcurrentMap for an overview its further advantages, including AirConcurrentMap Space Efficiency. This information is expanded slightly in Fast Java Map Iterators, MapVisitors and ThreadedMapVisitors. For other speed information see Java Map AirConcurrentMap versus ConcurrentSkipListMap Speed. For extensive testing, see AirConcurrentMap_Performance_Testing For licenses see Java Key/Value Data Storage Products.