  Epoch based memory reclamation (EBR) is one of the most popular techniques
for reclaiming memory in lock-free and optimistic locking data structures, due
to its ease of use and good performance in practice. However, EBR is known to
be sensitive to thread delays, which can result in performance degradation.
Moreover, the exact mechanism for this performance degradation is not well
understood. This paper illustrates this performance degradation in a popular
data structure benchmark, and does a deep dive to uncover its root cause-a
subtle interaction between EBR and state of the art memory allocators. In
essence, modern allocators attempt to reduce the overhead of freeing by
maintaining bounded thread caches of objects for local reuse, actually freeing
them (a very high latency operation) only when thread caches become too large.
EBR immediately bypasses these mechanisms whenever a particularly large batch
of objects is freed, substantially increasing overheads and latencies. Beyond
EBR, many memory reclamation algorithms, and data structures, that reclaim
objects in large batches suffer similar deleterious interactions with popular
allocators. We propose a simple algorithmic fix for such algorithms to amortize
the freeing of large object batches over time, and apply this technique to ten
existing memory reclamation algorithms, observing performance improvements for
nine out of ten, and over 50% improvement for six out of ten in experiments on
a high performance lock-free ABtree. We also present an extremely simple token
passing variant of EBR and show that, with our fix, it performs 1.5-2.6x faster
than the fastest known memory reclamation algorithm, and 1.2-1.5x faster than
not reclaiming at all, on a 192 thread four socket Intel system.
