  The future of main memory appears to lie in the direction of new non-volatile
memory technologies that provide strong capacity-to-performance ratios, but
have write operations that are much more expensive than reads in terms of
energy, bandwidth, and latency. This asymmetry can have a significant effect on
algorithm design, and in many cases it is possible to reduce writes at the cost
of reads. In this paper, we study which algorithmic techniques are useful in
designing practical write-efficient algorithms. We focus on several fundamental
algorithmic building blocks including unordered set/map implemented using hash
tables, ordered set/map implemented using various binary search trees,
comparison sort, and graph traversal algorithms including breadth-first search
and Dijkstra's algorithm. We introduce new algorithms and implementations that
can reduce writes, and analyze the performance experimentally using a software
simulator. Finally we summarize interesting lessons and directions in designing
write-efficient algorithms.
