  Multiversioning is widely used in databases, transactional memory, and
concurrent data structures. It can be used to support read-only transactions
that appear atomic in the presence of concurrent update operations. Any system
that maintains multiple versions of each object needs a way of efficiently
reclaiming them. We experimentally compare various existing reclamation
techniques by applying them to a multiversion tree and a multiversion hash
table.
  Using insights from these experiments, we develop two new multiversion
garbage collection (MVGC) techniques. These techniques use two novel concurrent
version list data structures. Our experimental evaluation shows that our
fastest technique is competitive with the fastest existing MVGC techniques,
while using significantly less space on some workloads. Our new techniques
provide strong theoretical bounds, especially on space usage. These bounds
ensure that the schemes have consistent performance, avoiding the very high
worst-case space usage of other techniques.
