Hoard: a scalable memory allocator for multithreaded applications

By Emery D. Berger, Kathryn S. McKinley, R. Blumofe, P. Wilson. 2000

577 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications, Hardware and Architecture, ML Systems & Hardware

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Hardware and Architecture

In ML Systems & Hardware

Citations in the corpus

PyTorch: An Imperative Style, High-Performance Deep Learning Library (2019, methodology): “PyTorch can rely on optimized libraries [39, 40, 41] to handle this task on CPU.”
NOVA: A Log-structured File System for Hybrid Volatile/Non-volatile Main Memories (2016, methodology): “This allocation scheme is similar to scalable memory allocators like Hoard [5].”
The RAMCloud Storage System (2015, unknown): ““Hoard” [Berger et al. 2000], “jemalloc” [Evans 2006], and “tcmalloc’ [SourceForge 2013] are noncopying allocators designed”
NV-Heaps: making persistent objects fast and safe with next-generation, non-volatile memories (2011, background): “Hoard: a scalable memory allocator for multithreaded applications.”
Mnemosyne: lightweight persistent memory (2011, methodology): “Hoard sindexes, which speed allocation, arein volatile memory and mustbe regenerated when a program starts.”
A Scalable Concurrent malloc(3) Implementation for FreeBSD (2006, methodology): “FreeBSD's previous malloc(3) implementation by Kamp (1998), commonly referred to as phkmalloc, has long been considered one of the best available, and has fared well in published comparisons (Feng and Berger, 2005; Berger et al., 2000; Bohra and Gabber, 2001).”
Conservative interpolation between volume meshes by local Galerkin projection (2011, methodology): “015 of the Intel compiler suite and used the Hoard memory allocator [3].”
Flat combining and the synchronization-parallelism tradeoff (2010, methodology): “We ran benchmarks in C++ using the same compiler on both machines, and using the scalable Hoard memory allocator [1] to ensure that malloc calls are not a sequential bottleneck.”
A lightweight infrastructure for graph analytics (2013, background): “While there has been considerable effort towards creating scalable memory allocators [1, 22, 28], we have found that existing solutions do not scale to large-scale multi-threaded workloads that are very allocation intensive nor do they directly address non-uniform memory access (NUMA) concerns, whic”