Hoard Memory Allocator

Hoard is a fast, scalable, and memory-efficient memory allocator designed for multithreaded programs running on multiprocessors and multicore CPUs. It serves as a drop-in replacement for malloc.

Hoard addresses three primary issues found in many standard allocators:

1. Contention: It eliminates the bottleneck where multiple threads serialize while attempting to allocate or deallocate memory.
2. False Sharing: It is designed to prevent threads on different CPUs from sharing the same cache line, which can significantly degrade performance.
3. Blowup: It provides provably bounded memory consumption, preventing the common issue where memory usage multiplies by the number of CPUs in a multithreaded environment.

To build Hoard from source on Linux, Mac OS X, or Windows WSL2, follow these steps.

Linux Prerequisites You may need to install libstdc++-dev (e.g., libstdc++-12-dev):

sudo apt install libstdc++-dev

Build Steps

git clone https://github.com/emeryberger/Hoard
mkdir build && cd build
cmake ..
make

Using Hoard after building

You can use Hoard by linking it with your executable or by using environment variables to intercept allocations:

Linux:

export LD_PRELOAD=/path/to/libhoard.so

Mac OS X:

export DYLD_INSERT_LIBRARIES=/path/to/libhoard.dylib

You can link Hoard directly into your application using the MSVC compiler.

Requirement: Programs must be compiled with /MD (dynamic C runtime).

cl /Ox /MD yourapp.cpp /link hoard.lib

To install the current version of Hoard on Mac OS X, use Homebrew. This installs the library and provides a hoard command to run any program through the Hoard allocator.

brew tap emeryberger/hoard
brew install --HEAD emeryberger/hoard/libhoard

To run a specific program using Hoard:

hoard myprogram-goes-here

Hoard uses Microsoft Detours for function interposition on Windows, which is automatically handled by CMake. This build supports x86, x64, ARM, and ARM64 architectures.

git clone https://github.com/emeryberger/Hoard
cd Hoard
mkdir build && cd build
cmake ..
cmake --build . --config Release

This produces build\Release\hoard.dll and the tools withdll.exe and setdll.exe.

For unmodified executables, use withdll.exe to inject Hoard into a program at runtime. This is similar to LD_PRELOAD on Linux.

Requirement: Programs must be compiled with /MD (dynamic C runtime). Programs compiled with /MT (static C runtime) cannot be intercepted by Hoard.

build\Release\withdll.exe /d:build\Release\hoard.dll yourapp.exe [args...]

You can use setdll.exe to modify an executable's import table to include Hoard permanently.

Add Hoard to an executable (creates a backup named executablename.exe~):

build\Release\setdll.exe /d:build\Release\hoard.dll yourapp.exe

Remove Hoard from an executable:

build\Release\setdll.exe /r:hoard.dll yourapp.exe

# Add Hoard
build\Release\setdll.exe /d:build\Release\hoard.dll yourapp.exe

# Remove Hoard
build\Release\setdll.exe /r:hoard.dll yourapp.exe

The HoardManager is a multiprocessor memory allocator that manages memory through a hierarchy of Superblocks.

Key Concepts:

• Superblocks: The fundamental unit of memory management. Each superblock contains objects of a specific size class.
• Bins: Superblocks are organized into bins based on their size class.
• Emptiness Thresholds: HoardManager tracks the usage statistics (allocated vs. in-use) for each bin. When a superblock becomes 'empty enough' (determined by a thresholdFunctionClass), it is moved up to the ParentHeap to prevent memory blowup and fragmentation.
• Hierarchy: A HoardManager can have a ParentHeap (to which it returns superblocks) and a SourceHeap (from which it acquires new memory if the parent is empty).

Hoard provides a lock-free delayed free mechanism to handle cross-thread frees efficiently. This allows a thread to 'free' an object without immediately acquiring a lock, instead pushing it to a bounded queue.

Workflow

1. Producer (Cross-thread free): Use tryPushDelayedFree(void* ptr) to attempt to add a pointer to the delayed free queue. This is a lock-free, bounded operation. If it returns false, the queue is full and the caller should fall back to a slower, locking path.
2. Consumer (Owner thread): The thread that owns the superblock should call drainDelayedFrees() (typically during a malloc call) to move objects from the delayed free queue into the local freelist. This returns the number of objects successfully freed.
3. Status Check: Use hasDelayedFrees() to check if there are pending frees in the queue.

The shbench benchmark involves each thread allocating and randomly freeing a number of random-sized objects.

Note: The source for this benchmark is hosted externally and differs from the version used in the original Hoard paper.

Download source: http://www.microquill.com/smartheap/shbench/bench.zip

The cache-scratch benchmark (referred to as "passive-false" in the Hoard paper) tests an allocator's resilience against passive false sharing.

Parameters: <threads> <inner-loop> <object-size> <iterations>

Example usage:

# Run with 1 thread, 100 inner loops, 8-byte objects, for 1,000,000 iterations
cache-scratch 1 100 8 1000000

# Run using the number of processors (P) in your system
cache-scratch P 100 8 1000000

The linux-scalability benchmark (and its Hoard-enabled counterpart linux-scalability-hoard) is used to evaluate malloc performance in a multithreaded Linux environment.

To run the benchmark, use the following command structure:

./[executable] [size] [iterations] [P]

Where:

• size: The allocation size (e.g., 512).
• iterations: The number of iterations (e.g., 10000000).
• P: The number of processors to test. To test single-threaded performance, set P = 1. To test scalability, set P to the number of processors available on your system.