Abstract
The long-lived renaming problem appears in shared-memory systems where a set of threads need to register and deregister frequently from the computation, while concurrent operations scan the set of currently registered threads. Instances of this problem show up in concurrent implementations of transactional memory, flat combining, thread barriers, and memory reclamation schemes for lock-free data structures. In this paper, we analyze a randomized solution for long-lived renaming. The algorithmic technique we consider, called the LevelArray, has previously been used for hashing and one-shot (single-use) renaming. Our main contribution is to prove that, in long-lived executions, where processes may register and deregister polynomially many times, the technique guarantees constant steps on average and $O(\log \log n)$ steps with high probability for registering, unit cost for deregistering, and $O(n)$ steps for collect queries, where $n$ is an upper bound on the number of processes that may be active at any point in time. We also show that the algorithm has the surprising property that it is self-healing: under reasonable assumptions on the schedule, operations running while the data structure is in a degraded state implicitly help the data structure re-balance itself. This subtle mechanism obviates the need for expensive periodic rebuilding procedures. Our benchmarks validate this approach, showing that, for typical use parameters, the average number of steps a process takes to register is less than two and the worst-case number of steps is bounded by six, even in executions with billions of operations. We contrast this with other randomized implementations, whose worst-case behavior we show to be unreliable, and with deterministic implementations, whose cost is linear in $n$.
Introduction
In high-performance concurrent programming, threads often need to "check in" and "check out" of a computation. This is known as long-lived renaming (or dynamic collect). For example, a garbage collector needs to know which threads are currently active to avoid deleting memory they are still using.
The challenge is building a data structure that allows thousands of threads to register and deregister millions of times per second without contention or performance degradation over time. Deterministic solutions often scale poorly (linear time), while simple randomized solutions (like basic hashing) can suffer from "primary clustering" or rare but catastrophic worst-case delays that worsen as the system runs longer. The LevelArray provides a highly efficient solution, achieving constant average time and $O(\log \log n)$ worst-case time for registration, while naturally re-balancing itself during normal operation.
Methods
The authors propose the LevelArray, a randomized data structure that organizes memory into a series of "levels" or batches.
- Structure: An array of size $2n$ (where $n$ is the max number of active threads) is split into $O(\log n)$ levels. The first level is large ($3n/2$), and subsequent levels get exponentially smaller.
- Registration (Get): A thread tries to find an empty slot by performing a constant number of random probes at each level, starting from the largest. If it fails at Level 0, it moves to Level 1, and so on. Because the upper levels are sparsely populated, most threads find a spot almost immediately.
- Deregistration (Free): A thread simply resets its slot to zero.
- Collect: To see who is active, a thread scans the entire $2n$ array.
While the "level" concept had been used before for one-shot tasks, this paper provides the first rigorous proof that it works for long-lived executions where threads join and leave indefinitely.
Results and Key Insights
The algorithm was evaluated using synthetic benchmarks on a Fujitsu PRIMERGY RX600 S6 with 80 hardware threads. Key findings include:
- Efficiency and Predictability: In a benchmark with 80 concurrent threads and a billion operations, the average number of probes to register was less than two, and the worst-case was only six. In contrast, simple randomized methods showed much higher variance and less reliable worst-case bounds.
- The Self-Healing Property: Unlike most data structures that require explicit rebalancing, the LevelArray naturally pushes the distribution of occupied slots back toward a "balanced" state through normal registration and deregistration.
- Double Exponential Success: The probability of a thread failing to find a spot in a level decreases "doubly exponentially." This explains the $O(\log \log n)$ worst-case time—even with millions of threads, very few levels are needed.
- Stability: Unlike linear probing, which slows down over time due to clustering, LevelArray’s performance remains rock-steady even after billions of operations.
Discussion and Future Work
While robust, the theoretical proofs assume an "oblivious adversary." Additionally, the "Collect" operation takes $O(n)$ time, which remains a bottleneck for applications requiring extremely frequent queries of active threads. Future directions include applying these level-based randomized techniques to other coordination problems, such as elimination trees or rendezvous structures, to leverage similar self-healing properties.
Summary updated