Why is there a ConcurrentSkipListMap, but no unsynchronized version?

524 views Asked by At

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?

2

There are 2 answers

6
robert_difalco On

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.

0
AnV On

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