Hoard: A Scalable Memory Allocator for Multithreaded Applications
📜 Abstract
Parallel, multithreaded C and C++ programs such as web servers, database managers, news servers, and scientific applications are becoming increasingly prevalent. For these applications, the memory allocator is often a bottleneck that severely limits program performance and scalability on multiprocessor systems. Previous allocators suffer from problems that include poor performance and scalability, and heap organizations that introduce false sharing. Worse, many allocators exhibit a dramatic increase in memory consumption when confronted with a producer-consumer pattern of object allocation and freeing. This increase in memory consumption can range from a factor of P (the number of processors) to unbounded memory consumption. This paper introduces Hoard, a fast, highly scalable allocator that largely avoids false sharing and is memory efficient. Hoard is the first allocator to simultaneously solve the above problems. Hoard combines one global heap and per-processor heaps with a novel discipline that provably bounds memory consumption and has very low synchronization costs in the common case. Our results on eleven programs demonstrate that Hoard yields low average fragmentation and improves overall program performance over the standard Solaris allocator by up to a factor of 60 on 14 processors, and up to a factor of 18 over the next best allocator we tested.
✨ Summary
Summary
The paper introduces Hoard, a multithreaded memory allocator organized around per-processor heaps, a shared global heap, and fixed-size superblocks. Its central policy transfers sufficiently empty superblocks from private heaps to the global heap, allowing freed memory to be reused across processors while bounding memory blowup. Returning freed blocks to their owning superblocks and restricting concurrent allocation from a superblock also reduces allocator-induced active and passive false sharing.
The analysis establishes a constant-factor bound on memory blowup, expressed as O(U + P), where U is the application’s live memory and P is the number of processors. The experiments, conducted on a 14-processor Sun Enterprise 5000, report near-linear scaling on several allocation-intensive workloads, no observed allocator-induced false-sharing objects in the tested multithreaded benchmarks, and generally low fragmentation. The principal weakness identified by the authors is reduced efficiency for workloads using many size classes and highly random object lifetimes, particularly shbench.
The work had continuing influence in both research and practice. Hoard received the 2019 ASPLOS Influential Paper Award, recognizing its lasting contribution to scalable memory allocation research. (sigops.org) Subsequent allocator research, including scalloc and snmalloc, treats Hoard as a representative design based on private heaps, size classes, superblocks or spans, and mechanisms for handling remotely freed memory. (cs.uni-salzburg.at) The Hoard project remains publicly maintained and is used as a comparison point in contemporary allocator benchmarks; its maintainers also state that the original design influenced improvements to the Mac OS X memory allocator. (github.com) The modern implementation has evolved substantially from the version evaluated in this paper. (github.com)