Why are ConcurrentSkipListSet ascending Iterators 'faster' than descending ones?

Question

I’m using the descendingIterator method on ConcurrentSkipListSet. I’ve just checked the documentation and noticed the following comment:

‘Ascending ordered views and their iterators are faster than descending ones.’

See https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentSkipListSet.html#descendingIterator--

Unfortunately it doesn’t provide any more information on this. What kind of performance difference is there? is it significant? and why is there a performance difference?

Answer 1

If you look at the Wikipedia page for Skip Lists you will see that they are effectively a complicated form of linked list with the links going in the direction of an ordering of the list entries. (The diagram illustrates this clearly ...)

When you traverse the skip list in the forward direction, you are simply following the links. Each next() call is an O(1) operation.

When you traverse the skip list in the reverse direction, each next() call has to find the key before the last key returned. This is an O(logN) operation.

(However, traversing a skip list backwards is still substantially faster than traversing a singly linked list backwards. That would be O(N) for each next() call ...)

If you look under the hood, you will see that a ConcurrentSkipListSet is actually a wrapper for a ConcurrentSkipListMap. In that class, the Node objects in the skip list representation of the map form singly linked chains ... in the ascending key direction. It follows (from the previous) that ascending iteration is faster than descending iteration.

The performance difference will be significant, and it will get more significant as the set size increases because of the O(1) versus O(logN) difference.