Linearizability of SkipMap/SkipSet

[ghost]

SkipMap and SkipSet currently don't provide linearizability guarantees for their operations. Let's investigate if it is worthwhile inserting fences at the beginning/end of their methods to make everything linearizable.

The tradeoff is, of course, between performance and correctness (in the sense that bugs are less likely under stronger guarantees). In Rust we typically prefer to have strong guarantees by default with a possibility to opt-in into something faster with weaker guarantees (see HashMap vs FnvHashmap, sort vs sort_unstable, compare_exchange vs compare_exchange_weak, etc.).

See #6 for a previous discussion on the topic.

[ghost]

Java's concurrent collections have pretty weak guarantees. The "Memory Consistency Properties" section here says:

Actions in a thread prior to placing an object into any concurrent collection happen-before actions subsequent to the access or removal of that element from the collection in another thread.

From that I would infer that ConcurrentSkipListMap's guarantees would be equivalent to what we call AcqRel orderings. If those guarantees have worked well for Java for more than a decade, they are probably good to copy.

cc @Amanieu

[jeehoonkang]

Sad that GitHub issue transfer doesn't fix issue number :-|