3

Most of the classes in Java's Collections Framework are unsynchronized by default, but can be made into something synchronized if you need them to be thread-safe. The synchronization has a performance penalty, so if you're writing something that doesn't need to be thread-safe, you're better off with the unsynchronized version.

But ConcurrentSkipListMap doesn't follow this scheme. There is no unsynchronized version. Why is there not a faster unsynchronized SkipListMap for applications that don't require thread safety, in line with the rest of the Collections Framework?

All I can think is that the simplest implementation of a Skip List is already thread-safe, so there would be no performance penalty for having a synchronized version. This would make some kind of sense, but a look at the source code doesn't quite bear that out. Although there are no synchronized blocks in the code, the Javadoc does start with

This class implements a concurrent variant of SkipLists...

which suggests that it's going out of its way to modify the algorithm to make it thread-safe. Later on, we read

The basic idea in these lists is to mark the "next" pointers of deleted nodes when deleting to avoid conflicts with concurrent insertions...

which also sounds as though there is some kind of overhead involved.

Is it just that this overhead is so small that it's not worth having a non-thread-safe SkipListMap?

chiastic-security
  • 20,430
  • 4
  • 39
  • 67
  • 2
    look [this question](http://stackoverflow.com/questions/256511/skip-list-vs-binary-tree) for a discussion of skip list against binary tree, so the TreeMap is the not synchronized counterpart of ConcurrentSkipListMap. It would not make much sense to add to two non threadsafe implemetations of the NavigableMap interface. – s106mo Nov 13 '14 at 20:12
  • @s106mo That's an interesting discussion, but `TreeMap` implements a red-black tree, which has similar properties, but is not an implementation of a SkipList. – chiastic-security Nov 13 '14 at 20:21
  • 2
    @chiastic-security what are you actually looking to do where you would need a skip-list but not a red-black tree? Just curious. – robert_difalco Nov 13 '14 at 20:26
  • 3
    Sorry, for being unclear: I'm aware that the TreeMap is a red-black tree implementation. My point was that adding an additional nonthreadsafe SkipListMap implemenation would make not much sense. The runtime complexity figures for skip list based maps are not better than those for TreeMap, but the Java API would be bloated. – s106mo Nov 13 '14 at 20:41
  • Sorry for spamming, but one more thing: when Java 1.2 was released in 1998 the invention of the skip list by William Pugh was only 9 years ago. Often, the adoption of new algorithms in professional/commercial products took a while. So this could also have affected the fact, that the default non threadsafe SortedMap implementation in Java is TreeMap (red–black trees were already invented in 1972). – s106mo Nov 13 '14 at 21:06

2 Answers2

2

Although Java doesn't have a SkipListMap, it has a non-synchronized counterpart for ConcurrentSkipListMap - TreeMap

Both TreeMap and ConcurrentSkipListMap implementes SortedMap, NavigableMap and are sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

But TreeMap uses Red-Black tree internally and ConcurrentSkipListMap uses concurrent variant of SkipLists as mentioned in java docs.

So, if you want a unsynchronized version of ConcurrentSkipListMap, you can use TreeMap

AnV
  • 2,794
  • 3
  • 32
  • 43
-2

ConcurrentSkipListMap is a lockless implementation based on CAS operations. Theoretically you should not have to pay any performance penalty if you are using it only in a single thread. There is no synchronization. When there is contention instead of blocking the implementation essentially loops to resolve contention. If un-contended there is no looping.

robert_difalco
  • 4,821
  • 4
  • 36
  • 58
  • just because there is no "synchronization" does _not_ mean that it is perf penalty free for single thread use. presumably it uses the memory strength of "volatile" in java, which has perf penalties. – jtahlborn Nov 13 '14 at 20:14
  • Yes, if you think the use of a volatile will impact the perceptible performance of your app then you are right. But it memory barriers are not in the same category as using synchronization or ReentrantLock. – robert_difalco Nov 13 '14 at 20:19
  • volatile use is in the same category as single-thread, uncontended synchronization. – jtahlborn Nov 13 '14 at 20:25
  • @jtahlborn uncontended they are not in the same category. Mutex acquisition even when uncontended is more expensive. – robert_difalco Nov 13 '14 at 20:31
  • 1
    [java biased locking](http://www.azulsystems.com/blog/cliff/2010-01-09-biased-locking) – jtahlborn Nov 13 '14 at 20:43
  • Even if JIT magic makes volatile itself kind of free - using it will afaik prevent certain instruction reordering optimization that could be done if there was no happens-before barrier at which those need to stop. – zapl Nov 13 '14 at 23:39