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
?
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.