  The recent availability of fast, dense, byte-addressable non-volatile memory
has led to increasing interest in the problem of designing and specifying
durable data structures that can recover from system crashes. However,
designing durable concurrent data structures that are efficient and also
satisfy a correctness criterion has proven to be very difficult, leading many
algorithms to be inefficient or incorrect in a concurrent setting. In this
paper, we present a general transformation that takes a lock-free data
structure from a general class called traversal data structure (that we
formally define) and automatically transforms it into an implementation of the
data structure for the NVRAM setting that is provably durably linearizable and
highly efficient. The transformation hinges on the observation that many data
structure operations begin with a traversal phase that does not need to be
persisted, and thus we only begin persisting when the traversal reaches its
destination. We demonstrate the transformation's efficiency through extensive
measurements on a system with Intel's recently released Optane DC persistent
memory, showing that it can outperform competitors on many workloads.
