Java Map AirConcurrentMap versus ConcurrentSkipListMap Speed

AirConcurrentMap is an implementation of the Java ConcurrentNavigableMap interface, so it provides ordered key-based accesses as well as concurrency. The Java standard Map that does this is ConcurrentSkipListMap. AirConcurrentMap is faster and more memory efficient as shown in the graphs below. For info contact

Faster Key-Based Operations

AirConcurrentMap is nearly twice as fast for key-based operations as ConcurrentSkipListMap. For example, get, put, and remove are roughly 90% faster, as are the related higher, lower, cieling, and floor retrievals that are available only on ordered maps like NavigableMaps and their superclass SortedMap. Iterators and other ordered scanning techniques provided by AirConcurrentMap, plus its memory efficiency are superior also – see AirConcurrentMap Space Efficiency and VisitorsAndThreadedVisitors. For an extensive performance analysis see

The Need for Ordering

Ordering of the keys in a Map such as a NavigableMap or SortedMap like AirConcurrentMap, ConcurrentSkipListMap or TreeMap is necessary in certain situations, and using an unordered Map like HashMap or ConcurrentHashMap is simply not possible. For example, ‘fuzzy matching’ for a known prefix of a key requires one of the ordered key-based operations higher, lower, ceiling, or floor. Another example is the storage of an x/y function in ascending x-coordinates. A history of stock prices needs to be displayed in time-order, so the keys might be the timestamps of the transactions. NavigableMaps can be used for sorting of data added to the Map and scanned in order by Iterating or by AirConcurrentMap’s Visitors or ThreadedVisitors. Some algorithms that scan a Map need to see adjacent x coordinate data, such as a differencer or an averager that show relative changes. The uses of ordering are countless.

The Need for ConcurrentMaps

A wikipedia article on the capabilities of Java ConcurrentMaps is at Java ConcurrentMap. ConcurrentMaps are not only thread-safe but also allow multiple-core access and weak consistency. ConcurrentMaps are safer in that no thread can block other threads for unlimited time in Iterators and for other reasons explained in the article. Latency is minimized and throughput is maximized.

The Danger of Omitting Thread Safety

In general, any system containing threads should use ConcurrentMaps to prevent bugs that are extremely difficult to detect and diagnose that result from concurrent write-write or write-read conflicts. These bugs may show up at any future time in the field and possibly never in development or testing and at any frequency dependent on data, execution patterns, system load, configuration, user actions, or any other variable. For example, HashMap and TreeMap are not thread-safe and have ‘undefined’ behavior in the concurrent case.

Performance Charts

Here are charts for 8-thread gets and puts. Note that the performance rolls off with increasing Map size because the complexity of an ordered Map access operation usually has an O(log(n)) characteristic. Single-thread performance is similar but slower. Scaling is good but not linear. A synchronized HashMap or TreeMap (e.g.. using Collections.synchronizedMap()) will be much slower with multiple threads, possibly causing a ‘convoy’ that can dramatically decrease performance. The get performance is representative of all key-based retrievals. AirConcurrentMap’s curve ends farther to the right due to higher memory efficiency above about 1K entries. For more graphs like these see the AirConcurrentMap page. For an extensive description of overall performance including the extremely high internally-threaded scan speed and memory efficiency see

Here is the put performance. The AirConcurrentMap and ConcurrentSkipListMap Java Maps start empty with a cold JVM. The performance of put and remove are similar to get in a warm JVM. Again the AirConcurrentMap curve ends higher due to memory efficiency.