source: doc/papers/llheap/Paper.tex@ d2e6f84

% Type: Paper
% 
% Abstract
%
% A new C-based concurrent memory-allocator is presented, called llheap (ll => low latency). It supports C/C++ applications with multiple kernel threads, or it can be embedded into user-threading runtime-systems. llheap extends the C allocation API with new functions providing orthogonal access to allocation features; hence, programmers do have to code missing combinations. llheap also extends the C allocation semantics by remembering multiple aspects of the initial allocation. These properties can be queried, allowing programmers to write safer programs by preserving these properties in future allocations. As well, realloc/reallocarray preserve initial zero-fill and alignment properties when adjusting storage size, again increasing future allocation safety. The allocator provides a contention-free statistics gathering mode, and a debugging mode for dynamically checking allocation pre/post conditions and invariants. These modes are invaluable for understanding and debugging a program's dynamic allocation behaviour, with low enough cost to be used in production code. An example is presented for condensing the allocation API using advanced type-systems, providing a single type-safe allocation routine using named arguments. Finally, performance results across a number of benchmarks show llheap is competitive with other modern memory allocators.
% 
% Upload: llheap.pdf
% 
% Computing Classification Systems
% 
% Add
% 500 Software and its engineering > Software libraries and repositories
% Add
% 300 Computing methodologies > Concurrent programming languages
%
% Authors, submitter has to have an orcid
%
% Details & Comments
%
% cover letter
%
% Funding
%  yes
%  Government of Canada >
%  Natural Sciences and Engineering Research Council of Canada
% 
% Electronic Supplementary Materials No
% Are you submitting a conference paper extension: No
% X  ACM uses CrossCheck, an automated service that checks for plagiarism. Any submission to ACM is subject to such a check. Confirm that you are familiar with the ACM Plagiarism Polic
% To confirm that you have reviewed all title, author, and affiliation information in the submission form and the manuscript for accuracy, and approve its exact use in the final, published article, please check the box to the right. X

\documentclass[manuscript,screen,review]{acmart}

% Latex packages used in the document.

\usepackage{comment}
\usepackage{epic,eepic}
\usepackage{upquote}                                                                    % switch curled `'" to straight
\usepackage{relsize}
\usepackage{xspace}
\usepackage{xcolor}
\usepackage{calc}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{enumitem}
\usepackage{tabularx}                                                                   % allows \lstMakeShortInline@
\usepackage[scaled=0.88]{helvet}                                                % descent Helvetica font and scale to times size
\usepackage[T1]{fontenc}
\usepackage{listings}                                                                   % format program code
\usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt,font={rm,md,up}]{subfig}
\renewcommand{\thesubfigure}{(\alph{subfigure})}

\hypersetup{breaklinks=true}
\usepackage{breakurl}

% \usepackage[pagewise]{lineno}
% \renewcommand{\linenumberfont}{\scriptsize\sffamily}

\usepackage{varioref}                                   % extended references
% adjust varioref package with default "section" and "page" titles, and optional title with faraway page numbers
% \VRef{label} => Section 2.7, \VPageref{label} => page 17
% \VRef[Figure]{label} => Figure 3.4, \VPageref{label} => page 17
% \renewcommand{\reftextfaceafter}{\unskip}
% \renewcommand{\reftextfacebefore}{\unskip}
% \renewcommand{\reftextafter}{\unskip}
% \renewcommand{\reftextbefore}{\unskip}
% \renewcommand{\reftextfaraway}[1]{\unskip, p.~\pageref{#1}}
% \renewcommand{\reftextpagerange}[2]{\unskip, pp.~\pageref{#1}--\pageref{#2}}
% \newcommand{\VRef}[2][Section]{\ifx#1\@empty\else{#1}\nobreakspace\fi\vref{#2}}
% \newcommand{\VRefrange}[3][Sections]{\ifx#1\@empty\else{#1}\nobreakspace\fi\vrefrange{#2}{#3}}
% \newcommand{\VPageref}[2][page]{\ifx#1\@empty\else{#1}\nobreakspace\fi\pageref{#2}}
% \newcommand{\VPagerefrange}[3][pages]{\ifx#1\@empty\else{#1}\nobreakspace\fi\pageref{#2}{#3}}

\makeatletter
\newcommand{\abbrevFont}{\textit}                       % set empty for no italics
\newcommand{\CheckCommaColon}{\@ifnextchar{,}{}{\@ifnextchar{:}{}{,\xspace}}}
\newcommand{\CheckPeriod}{\@ifnextchar{.}{}{.\xspace}}
\newcommand{\EG}{\abbrevFont{e}.\abbrevFont{g}.}
\newcommand{\eg}{\EG\CheckCommaColon}
\newcommand{\IE}{\abbrevFont{i}.\abbrevFont{e}.}
\newcommand{\ie}{\IE\CheckCommaColon}
\newcommand{\ETC}{\abbrevFont{etc}}
\newcommand{\etc}{\ETC\CheckPeriod}
\newcommand{\VS}{\abbrevFont{vs}}
\newcommand{\vs}{\VS\CheckPeriod}

\newcommand{\newtermFont}{\emph}
\newcommand{\newterm}[1]{\newtermFont{#1}}

\newcommand{\CFAIcon}{\textsf{C}\raisebox{\depth}{\rotatebox{180}{\textsf{A}}}\xspace} % Cforall symbolic name
\newcommand{\CFA}{\protect\CFAIcon}             % safe for section/caption
\newcommand{\CFL}{\textrm{Cforall}\xspace}      % Cforall symbolic name
\newcommand{\CCIcon}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}} % C++ icon
\newcommand{\CC}[1][]{\protect\CCIcon{#1}\xspace}               % C++ symbolic name
\newcommand{\uC}{$\mu$\CC}
\newcommand{\Csharp}{C\raisebox{-0.7ex}{\relsize{2}$^\sharp$}\xspace} % C# symbolic name

\newcommand{\LstBasicStyle}[1]{{\lst@basicstyle{#1}}}
\newcommand{\LstKeywordStyle}[1]{{\lst@basicstyle{\lst@keywordstyle{#1}}}}
\newcommand{\LstCommentStyle}[1]{{\lst@basicstyle{\lst@commentstyle{#1}}}}
\newcommand{\LstStringStyle}[1]{{\lst@basicstyle{\lst@stringstyle{#1}}}}

\newlength{\parindentlnth}
\setlength{\parindentlnth}{\parindent}
\newlength{\gcolumnposn}                                % temporary hack because lstlisting does not handle tabs correctly
\newlength{\columnposn}
\setlength{\gcolumnposn}{3.25in}
\setlength{\columnposn}{\gcolumnposn}
\renewcommand{\C}[2][\@empty]{\ifx#1\@empty\else\global\setlength{\columnposn}{#1}\global\columnposn=\columnposn\fi\hfill\makebox[\textwidth-\columnposn][l]{\lst@basicstyle{\LstCommentStyle{#2}}}}
\newcommand{\CRT}{\global\columnposn=\gcolumnposn}
\makeatother

\lstset{
columns=fullflexible,
basicstyle=\linespread{0.9}\sf,                 % reduce line spacing and use sanserif font
stringstyle=\fontsize{9}{9}\selectfont\tt,      % use typewriter font
tabsize=5,                                                              % N space tabbing
xleftmargin=\parindentlnth,                             % indent code to paragraph indentation
escapechar=\$,                                                  % LaTeX escape in CFA code
mathescape=false,                                               % disable LaTeX math escape in CFA code $...$
keepspaces=true,                                                %
showstringspaces=false,                                 % do not show spaces with cup
showlines=true,                                                 % show blank lines at end of code
aboveskip=4pt,                                                  % spacing above/below code block
belowskip=2pt,
numberstyle=\footnotesize\sf,                   % numbering style
moredelim=**[is][\color{red}]{@}{@},
% replace/adjust listing characters that look bad in sanserif
literate=
%  {-}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.75ex}{0.1ex}}}}1
  {-}{\raisebox{0pt}{\ttfamily-}}1
  {^}{\raisebox{0.6ex}{\(\scriptstyle\land\,\)}}1
  {~}{\raisebox{0.3ex}{\(\scriptstyle\sim\,\)}}1
%  {'}{\ttfamily'\hspace*{-0.4ex}}1
  {`}{\raisebox{-2pt}{\large\textasciigrave\hspace{-1pt}}}1
  {<-}{$\leftarrow$}2
  {=>}{$\Rightarrow$}2
%  {->}{\raisebox{-1pt}{\texttt{-}}\kern-0.1ex\textgreater}2,
}% lstset

% CFA programming language, based on ANSI C (with some gcc additions)
\lstdefinelanguage{CFA}[ANSI]{C}{
        morekeywords={
                _Alignas, _Alignof, __alignof, __alignof__, and, asm, __asm, __asm__, _Atomic, __attribute, __attribute__,
                __auto_type, basetypeof, _Bool, catch, catchResume, choose, coerce, _Complex, __complex, __complex__, __const, __const__,
                coroutine, _Decimal32, _Decimal64, _Decimal128, disable, enable, exception, __extension__, fallthrough, finally, fixup,
                __float80, float80, __float128, float128, _Float16, _Float32, _Float32x, _Float64, _Float64x, _Float128, _Float128x,
                forall, fortran, generator, _Generic, _Imaginary, __imag, __imag__, inline, __inline, __inline__, int128, __int128, __int128_t,
                __label__, monitor, mutex, _Noreturn, __builtin_offsetof, one_t, or, recover, report, restrict, __restrict, __restrict__,
                __signed, __signed__, _Static_assert, suspend, thread, __thread, _Thread_local, throw, throwResume, timeout, trait, try,
                typeof, __typeof, __typeof__, typeid, __uint128_t, __builtin_va_arg, __builtin_va_list, virtual, __volatile, __volatile__,
                vtable, waitfor, waituntil, when, with, zero_t,
    },
        moredirectives={defined,include_next},
}

% uC++ programming language, based on ANSI C++
\lstdefinelanguage{uC++}[GNU]{C++}{
        morekeywords={
                _Accept, _AcceptReturn, _AcceptWait, _Actor, _At, _Catch, _CatchResume, _CorActor, _Cormonitor, _Coroutine,
                _Disable, _Else, _Enable, _Event, _Exception, _Finally, _Monitor, _Mutex, _Nomutex, _PeriodicTask, _RealTimeTask,
                _Resume, _ResumeTop, _Select, _SporadicTask, _Task, _Timeout, _When, _With, _Throw},
}

% Go programming language: https://github.com/julienc91/listings-golang/blob/master/listings-golang.sty
\lstdefinelanguage{Golang}{
        morekeywords=[1]{package,import,func,type,struct,return,defer,panic,recover,select,var,const,iota,},
        morekeywords=[2]{string,uint,uint8,uint16,uint32,uint64,int,int8,int16,int32,int64,
                bool,float32,float64,complex64,complex128,byte,rune,uintptr, error,interface},
        morekeywords=[3]{map,slice,make,new,nil,len,cap,copy,close,true,false,delete,append,real,imag,complex,chan,},
        morekeywords=[4]{for,break,continue,range,goto,switch,case,fallthrough,if,else,default,},
        morekeywords=[5]{Println,Printf,Error,},
        sensitive=true,
        morecomment=[l]{//},
        morecomment=[s]{/*}{*/},
        morestring=[b]',
        morestring=[b]",
        morestring=[s]{`}{`},
}

\lstnewenvironment{cfa}[1][]{\lstset{language=CFA,moredelim=**[is][\protect\color{red}]{@}{@}}\lstset{#1}}{}
\lstnewenvironment{C++}[1][]{\lstset{language=C++,moredelim=**[is][\protect\color{red}]{@}{@}}\lstset{#1}}{}
\lstnewenvironment{uC++}[1][]{\lstset{language=uC++,moredelim=**[is][\protect\color{red}]{@}{@}}\lstset{#1}}{}
\lstnewenvironment{Go}[1][]{\lstset{language=Golang,moredelim=**[is][\protect\color{red}]{@}{@}}\lstset{#1}}{}
\lstnewenvironment{python}[1][]{\lstset{language=python,moredelim=**[is][\protect\color{red}]{@}{@}}\lstset{#1}}{}
\lstnewenvironment{java}[1][]{\lstset{language=java,moredelim=**[is][\protect\color{red}]{@}{@}}\lstset{#1}}{}

\newsavebox{\myboxA}
\newsavebox{\myboxB}
\newsavebox{\myboxC}
\newsavebox{\myboxD}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{High-Performance Concurrent Memory Allocation}

\author{Mubeen Zulfiqar}
\email{m3zulfiq@uwaterloo.ca}
\author{Ayelet Wasik}
\email{aisraeli@plg.uwaterloo.ca}
\author{Peter A. Buhr}
\email{pabuhr@uwaterloo.ca}
\orcid{0000-0003-3747-9281}
\affiliation{%
  \institution{University of Waterloo}
  \city{Waterloo}
  \state{Ontario}
  \country{Canada}
}
\author{Dave Dice}
\email{dave.dice@oracle.com}
\orcid{0000-0001-9164-7747}
\affiliation{%
  \institution{Oracle Labs}
  \city{Burlington}
  \state{Massachusetts}
  \country{USA}
}
\author{Bryan Chan}
\email{bryan.chan@huawei.com}
\affiliation{%
  \institution{Huawei Compiler Lab}
  \city{Markham}
  \state{Ontario}
  \country{Canada}
}

\renewcommand{\shortauthors}{Zulfiqar et al.}

% inline code @...@
\lstMakeShortInline@%

\begin{document}

\begin{abstract}
A new C-based concurrent memory-allocator is presented, called llheap (ll $\Rightarrow$ low latency).
It supports C/\CC applications with multiple kernel threads, or it can be embedded into user-threading runtime-systems.
llheap extends the C allocation API with new functions providing orthogonal access to allocation features;
hence, programmers do have to code missing combinations.
llheap also extends the C allocation semantics by remembering multiple aspects of the initial allocation.
These properties can be queried, allowing programmers to write safer programs by preserving these properties in future allocations.
As well, \lstinline{realloc}/\lstinline{reallocarray} preserve initial zero-fill and alignment properties when adjusting storage size, again increasing future allocation safety.
The allocator provides a contention-free statistics gathering mode, and a debugging mode for dynamically checking allocation pre/post conditions and invariants.
These modes are invaluable for understanding and debugging a program's dynamic allocation behaviour, with low enough cost to be used in production code.
An example is presented for condensing the allocation API using advanced type-systems, providing a single type-safe allocation routine using named arguments.
Finally, performance results across a number of benchmarks show llheap is competitive with other modern memory allocators.
\end{abstract}

\begin{CCSXML}
<concept>
<concept_id>10011007.10011006.10011072</concept_id>
<concept_desc>Software and its engineering~Software libraries and repositories</concept_desc>
<concept_significance>500</concept_significance>
</concept>
</ccs2012>

<ccs2012>
<concept>
<concept_id>10010147.10011777.10011014</concept_id>
<concept_desc>Computing methodologies~Concurrent programming languages</concept_desc>
<concept_significance>300</concept_significance>
</concept>
\end{CCSXML}

\ccsdesc[500]{Software and its engineering~Software libraries and repositories}
\ccsdesc[300]{Computing methodologies~Concurrent programming languages}

\keywords{memory allocation, (user-level) concurrency, type-safety, statistics, debugging, high performance}

\received{20 February 2007}
\received[revised]{12 March 2009}
\received[accepted]{5 June 2009}


\maketitle

\section{Introduction}

Memory management services a series of program allocation/deallocation requests and attempts to satisfy them from variable-sized blocks of memory while minimizing total memory usage.
A general-purpose memory allocator cannot anticipate storage requests so its time and space performance cannot be optimal (bin packing).
Each allocator takes advantage of a subset of typical allocation patterns (heuristics) to produce excellent results, both in time and space (similar to LRU paging).
Nevertheless, allocators are a series of compromises, possibly with static or dynamic tuning parameters to optimize specific request patterns.


\subsection{Memory Structure}
\label{s:MemoryStructure}

Figure~\ref{f:ProgramAddressSpace} shows the typical layout of a program's address space (high addresses to low) divided into a number of zones, with free memory surrounding the dynamic code/data~\cite{memlayout}.
Static code and data are placed into memory at load time from the executable and are fixed-sized at runtime.
Dynamic code/data memory is managed by the dynamic loader for libraries loaded at runtime, which is complex especially in a multi-threaded program~\cite{Huang06}.
However, changes to the dynamic code/data space are typically infrequent, most occurring at program startup and are largely outside of a program's control.
Stack memory is managed by the program call/return mechanism using a LIFO technique.
For stackful coroutines and user threads, new stacks are commonly created in the dynamic-allocation memory.
The dynamic-allocation memory is often a contiguous area, which starts empty and grows/shrinks as the program creates/deletes variables with independent lifetime.
The language's runtime manages this area, where management complexity is a function of the mechanism for deleting variables.

\begin{figure}
\centering
\input{AddressSpace.pstex_t}
\vspace{-5pt}
\caption{Program Address Space Divided into Zones}
\label{f:ProgramAddressSpace}
\end{figure}


\subsection{Dynamic Memory-Management}
\label{s:DynamicMemoryManagement}

Modern programming languages provide two forms of storage management: managed or unmanaged.
Both forms have explicit allocation, but managed memory has implicit deallocation (garbage collection~\cite{Wilson92}, GC) and unmanaged memory has some form of explicit deallocation.
Sometimes there are explicit deallocation hints in managed.
Both forms attempt to reuse freed storage in the heap for new allocations.
Unmanaged languages have no information about allocated \newterm{objects}, and hence, use techniques during freeing to detect adjacent unused storage if coalescing.
Conservative GC attempts to find free objects in an unmanaged system by scanning memory and marking anything that \emph{looks} like a live object.
However, \emph{conservative} means some non-objects might be marked as live;
the goal is not to miss any live objects.
Managed languages maintain sufficient information to locate all live objects.
Precise GC is then able to mark just the live objects.
Both approaches then sweep through the unmarked objects looking for adjacent free storage to coalesce.
Precise GC has a further coalescing option of compacting used objects and adjusting the pointers used to find them to the new locations, resulting in a large area of contiguous free storage.
Languages such as Lisp~\cite{CommonLisp}, Java~\cite{Java}, Haskell~\cite{Haskell}, Go~\cite{Go}, are managed and normally implemented using precise GC.
(Both Go~\cite{Go1.3} and Netscape JavaScript~\cite{JavaScriptGC} switched from conservative to precise GC.)
Languages such as C~\cite{C}, \CC~\cite{C++}, Rust~\cite{Rust} and Swift~\cite{swift} (because of explicit management of weak references) are unmanaged but could be used with conservative GC~\cite{Boehm88}.
This work only examines unmanaged memory with \emph{explicit} deallocation.
% While GC is not part this work, some of the results are applicable to the allocation phase in any memory-management approach.

Most programs use a general-purpose allocator, usually the one provided by the programming-language's runtime.
In certain languages, programmers can write specialize allocators for specific needs.
POSIX~\cite{POSIX17} provides for replacement of the default memory allocator in C and \CC through a standard API.
Most industry JVMs provide multiple GCs, from which a user selects one for their workload.
%Jikes RVM MMTk~\cite{MMTk} provides a similar generalization for the Java virtual machine.
As well, new languages support concurrency (kernel/user threading), which must be safely handled by the allocator.
Hence, alternative allocators exist for C/\CC with the goal of scaling in multi-threaded programs~\cite{Berger00,mtmalloc,streamflow,tcmalloc}.
This work examines the design of high-performance allocators for use by kernel and user multi-threaded applications written in C/\CC.


\subsection{Contributions}
\label{s:Contributions}

This work provides the following contributions to the area of explicit concurrent dynamic-allocation.
\begin{enumerate}[leftmargin=18pt,topsep=3pt,itemsep=0pt]
\item
Implementation of a new stand-alone concurrent low-latency memory-allocator, called llheap~\cite{llheap}, ($\approx$1,500 lines of code) for C/\CC programs using kernel threads (1:1 threading), and specialized versions for the concurrent languages \uC~\cite{uC++} and \CFA~\cite{Moss18,Delisle21} using user-level threads running on multiple kernel threads (M:N threading).

\item
Extend the C allocation API with new functions @aalloc@, @amemalign@, @cmemalign@, @resize@, @aligned_resize@, @aligned_realloc@, and @aligned_reallocarray@ to make allocation properties orthogonally accessible.

\item
Extend the C allocation semantics by preserving with each allocation its request size, the amount allocated, whether it is zero fill, and its alignment.

\item
Provide additional query operations @malloc_alignment@, @malloc_zero_fill@, and @malloc_size@ to access allocation information.

\item
Use the preserved zero fill and alignment as \emph{sticky} properties for @realloc@ and @reallocarray@ to zero-fill and align when storage is extended or copied.
Without this extension, it is unsafe to @realloc@ storage if the properties are not preserved when copying.
This silent problem is unintuitive to programmers and difficult to locate because it is transient.

\item
Provide optional extensive, fast, and contention-free allocation statistics to understand allocation behaviour.

\item
Provide runtime checks to validate allocation operations and identify the amount of unfreed storage at program termination.

\item
Build 8 different versions of the allocator: static or dynamic linking, with or without statistics or debugging.
A program may link to any of these 8 versions of the allocator often without recompilation (linking or @LD_PRELOAD@).

\item
Demonstrate how advanced programming-language type-systems can condense the allocation API providing a single type-safe allocation function using named arguments.

\item
Create a benchmark test-suite for comparing allocators, rather than relying on a suite of arbitrary programs.

\item
Run performance experiments using the new benchmark test-suite comparing llheap with six of the best allocators in use today.
The goal is to demonstrate that llheap's performance, both in time and space, is comparable to the best allocators in use today.
\end{enumerate}


\section{Background}

The following is an overview of allocator design options that affect memory usage and performance (see~\cite{Zulfiqar22} for more details).
Dynamic acquires and releases obtain \newterm{object} storage via calls such as @malloc@/@new@ and @free@/@delete@ in C/\CC, respectively.
A \newterm{memory allocator} contains a complex data-structure and code that manages the layout of objects in the dynamic-allocation zone.
% The management goals are to make allocation/deallocation operations as fast as possible while densely packing objects to make efficient use of memory.
Since objects in C/\CC cannot be moved, only adjacent free storage can be \newterm{coalesced} into larger free areas.
The allocator grows or shrinks the dynamic-allocation zone to obtain storage for objects and reduce memory usage using \newterm{operating system} (OS) calls, such as @mmap@ or @sbrk@ in UNIX.


\vspace*{-7pt}
\subsection{Allocator Components}
\label{s:AllocatorComponents}

Figure~\ref{f:AllocatorComponents} shows the two important data components for a memory allocator, management and storage, collectively called the \newterm{heap}.
The \newterm{management data} is a data structure located at a known memory address and contains fixed-sized information in the static-data memory that references components in the dynamic-allocation memory.
For multi-threaded programs, additional management data may exist in \newterm{thread-local storage} (TLS) for each kernel thread executing the program.
The \newterm{storage data} is composed of allocated/freed objects, and \newterm{reserved memory}.
Allocated objects (white) are variable sized, and are allocated and maintained by the program;
\ie only the program knows the location of allocated storage.
Freed objects (light grey) represent memory deallocated by the program, which are linked into one or more lists facilitating location for new allocations.
Reserved memory (dark grey) is one or more blocks of memory obtained from the OS but not yet used by the program;
if there are multiple reserved blocks, they are normally linked together.

\begin{figure}
\centering
\input{AllocatorComponents}
\caption{Allocator Components (Heap)}
\label{f:AllocatorComponents}
\end{figure}

In many allocator designs, allocated objects and reserved blocks have management data embedded within them (see also Section~\ref{s:ObjectContainers}).
Figure~\ref{f:AllocatedObject} shows an allocated object with a header, trailer, and optional spacing around the object.
The header contains information about the object, \eg size, type, \etc.
The trailer may be used to simplify coalescing and/or for safety purposes to mark the end of an object.
An object may be preceded by padding to ensure proper alignment.
Some algorithms quantize allocation requests, resulting in additional space after an object.
When padding and spacing are necessary, neither can be used to satisfy a future allocation request while the current allocation exists.

A free object often contains management data, \eg size, pointers, \etc.
Often the free list is linked internally so it does not consume additional storage, \ie the link fields are placed at known locations in the unused memory blocks.
For internal linking, the amount of management data for a free node defines the minimum allocation size, \eg if 16 bytes are needed for a free-list node, allocation requests less than 16 bytes are rounded up.
Often the minimum storage alignment and free-node size are the same.
The information in an allocated or freed object is overwritten when it transitions from allocated to freed and vice-versa by new program data and/or management information, receptively.
For safety purposes, freed storage may be scrubbed (overwritten) to expose inadvertent bugs, such as assuming variables are zero initialized.

\begin{figure}
\centering
\input{AllocatedObject}
\caption{Allocated Object}
\label{f:AllocatedObject}

\bigskip

\input{IntExtFragmentation}
\caption{Internal and External Fragmentation}
\label{f:InternalExternalFragmentation}
\end{figure}


\subsection{Single-Threaded Memory-Allocator}
\label{s:SingleThreadedMemoryAllocator}

In a sequential (single threaded) program, the program thread performs all allocation operations without direct concurrency issues.
However, interrupts introduce indirect concurrency, if the signal handler performs allocation/deallocation (serially reusable problem~\cite{SeriallyReusable}).
In general, the primary issues in a single-threaded allocator are fragmentation and locality.


\subsubsection{Fragmentation}
\label{s:Fragmentation}

Fragmentation is unused memory requested from the OS.
Figure~\ref{f:InternalExternalFragmentation} shows fragmentation has two forms: \emph{internal} or \emph{external}.

\newterm{Internal fragmentation} is inaccessible \emph{allocated} memory, such as headers, trailers, \etc.
Internal fragmentation is problematic when management space approaches the object size, \eg for objects $<$16 bytes, memory usage doubles.

\newterm{External fragmentation} is memory not allocated in the program~\cite{Wilson95,Lim98,Siebert00}, which includes all external management data, freed objects, and reserved memory.
This memory is problematic resulting in heap blowup and fragmented memory.
\newterm{Blowup} occurs when freed memory becomes a checkerboard of adjacent allocated and free areas, where the free blocks are too small to service requests, leading to unbounded external fragmentation growth~\cite{Berger00}.
Heap blowup is a fundamental problem in unmanaged languages without compaction.

Three basic approaches for controlling fragmentation are identified~\cite{Johnstone99}.
The first approach is \newterm{sequential-fit} with a list of free objects (possibly ordered by size) that is searched for a block large enough to fit a requested object.
Different search policies determine the free object selected, \eg the first free object large enough (first fit) or closest to the requested size (best fit).
Any storage larger than the request can become spacing after the object or split into a smaller free object.

The second approach is \newterm{segregation} or \newterm{binning} with a set of lists for different sized freed objects.
The request size is rounded up to the nearest bin size, often leading to internal fragmentation after the object.
A binning algorithm searches for the smallest bin that covers the request, and selects the first free object, if available.
Fewer bin sizes means more internal fragmentation but increased reuse as more request sizes match the bin size.
More bin sizes has less internal fragmentation size but more external fragmentation as larger bins cannot service smaller requests.
Allowing larger bins to service smaller allocations means the freed object can be returned to the matching or larger bin (some advantages to either scheme).

The third approach is \newterm{splitting} and \newterm{coalescing}.
If there is no matching free storage for allocation, a larger free object is split to get the allocation and the smaller object is put back on the free list.
For example, in the \newterm{buddy system}, a block of free memory is split into equal chunks, splitting continues until a minimal block is created that fits the allocation.
When an object is deallocated, it is coalesced with the objects immediately before/after it in memory, if they are free, creating a larger block.
Coalescing can be done eagerly at each deallocation or lazily when an allocation cannot be fulfilled.
However, coalescing increases allocation latency (unbounded delays), both for allocation and deallocation.
While coalescing does not reduce external fragmentation, the coalesced blocks improve fragmentation quality so future allocations are less likely to cause heap blowup.


\subsubsection{Locality}
\label{s:Locality}

The principle of locality recognizes that programs tend to reference a small set of data, called a \newterm{working set}, for a certain period of time, composed of temporal and spatial accesses~\cite{Denning05}.
% Temporal clustering implies a group of objects are accessed repeatedly within a short time period, while spatial clustering implies a group of objects physically close together (nearby addresses) are accessed repeatedly within a short time period.
% Temporal locality commonly occurs during an iterative computation with a fixed set of disjoint variables, while spatial locality commonly occurs when traversing an array.
Hardware takes advantage of the working set through multiple levels of caching and paging, \ie memory hierarchy.
% When an object is accessed, the memory physically located around the object is also cached with the expectation that the current and nearby objects will be referenced within a short period of time.
% For example, entire cache lines are transferred between cache and memory, and entire virtual-memory pages are transferred between memory and disk.
% A program exhibiting good locality has better performance due to fewer cache misses and page faults\footnote{With the advent of large RAM memory, paging is becoming less of an issue in modern programming.}.

Temporal locality is largely controlled by program accesses to variables~\cite{Feng05}.
An allocator has only indirect influence on temporal locality but largely dictates spatial locality.
For temporal locality, an allocator tries to return recently freed storage for new allocations, as this memory is still \emph{warm} in the memory hierarchy.
For spatial locality, an allocator places objects used together close together in memory, so the working set of the program fits into the fewest possible cache lines and pages.
% However, usage patterns are different for every program as is the underlying hardware memory architecture;
% hence, no general-purpose memory-allocator can provide ideal locality for every program on every computer.

An allocator can easily degrade locality by increasing the working set.
For example, it can access an unbounded number of free objects when matching an allocation or coalescing, causing multiple cache or page misses~\cite{Grunwald93}.
An allocator can spatially separate related data by binning free storage anywhere in memory, so the related objects are highly separated.


\subsection{Multi-Threaded Memory-Allocator}
\label{s:MultiThreadedMemoryAllocator}

In a concurrent program, multiple kernel threads (KT) perform allocations, requiring some form of mutual exclusion.
Along with fragmentation and locality issues, a multi-threaded allocator must deal with false sharing and additional forms of heap blowup.


\subsubsection{Mutual Exclusion}
\label{s:MutualExclusion}

% \newterm{Mutual exclusion} provides sequential access to the shared-management data of the heap.
There are two performance issues for mutual exclusion.
First, the cost of performing atomic instructions every time a shared resource is accessed to provide mutual exclusion.
Solutions using any atomic fence, atomic instruction (lock free), or lock along a fast path, even with zero contention, results in significant slowdown.
Second, \newterm{contention} on simultaneous access, so threads must wait until the resource is released.
Contention can be reduced by:
1) Using multiple fine-grained locks versus few course-gain locks to spread the contention.
2) Using trylock and generating new storage if the lock is busy (classic space versus time tradeoff).
% 3) Using one of the many lock-free approaches for reducing contention on basic data-structure operations~\cite{Fatourou12}.
% However, all approaches have degenerate cases where program contention to the heap is high, which is beyond the allocator's control.
Figure~\ref{f:ThreadHeapRelationship} shows how a multi-threaded allocator reduces contention by subdividing a single heap into multiple heaps.

\begin{figure}
\centering
\subfloat[T:1]{
        \input{SingleHeap}
        \label{f:SingleHeap}
} % subfloat
\vrule
\subfloat[T:H]{
        \input{SharedHeaps}
        \label{f:SharedHeaps}
} % subfloat
\vrule
\subfloat[1:1]{
        \input{PerThreadHeap}
        \label{f:PerThreadHeap}
} % subfloat
\caption{Multiple Heaps, Thread:Heap Relationship}
\label{f:ThreadHeapRelationship}
\end{figure}

\begin{description}[leftmargin=*]
\item[T:1 model (Figure~\ref{f:SingleHeap})] is all threads (T) sharing a single heap (1).
% The arrows indicate memory movement for allocation/deallocation operations.
% Memory is obtained from freed objects, reserved memory, or the OS;
% freed memory can be returned to the OS.
To handle concurrency, a single lock is used for all heap operations or fine-grained (lock-free) locking if operations can be made independent.
As threads perform large numbers of allocations, a single heap becomes a significant source of contention.

\item[T:H model (Figure~\ref{f:SharedHeaps})] is multiple threads (T) sharing multiple heaps (H).
The allocator allocates/deallocates heaps and assigns threads to heaps often based on dynamic contention pressure.
While locking is required for heap access, contention is (normally) reduced as access is spread across the heaps.
Locking can be reduced (eliminated) using the T:C variant, \ie each CPU has a heap, and a thread cannot migrate from the CPU if executing an allocator critical-section, implemented with restartable critical sections~\cite{Desnoyers19,Dice02} (see also Section~\ref{s:UserlevelThreadingSupport}).
% The goal is minimal heaps (storage) and contention per heap (time).
Multiple heaps increase external fragmentation as the ratio of heaps to threads increases, which can lead to heap blowup, where the worst-case scenario is more heaps than threads.
The external fragmentation is now multiplied by the number of heaps, since each heap manages its own free storage and allocates its own reserved memory.
When freeing, objects normally need to be returned to their original heap (see Section~\ref{s:Ownership}).
% Returning storage to the OS may be difficult or impossible, \eg the contiguous @sbrk@ area in Unix.
% In the worst case, a program in which objects are allocated from one heap but deallocated to another heap means these freed objects are never reused.

A shared \newterm{global heap} (G) is often introduced to manage the reserved memory among heaps and centralize interacts with the OS.
Instead of heaps making individual object allocations/deallocations through the global heap, resulting in locking and high contention, the global heap partitions the reserved memory into heap (allocation) buffers, which are given out to heaps for their own suballocations.
Hence, a heap's allocations are temporally and spatially accessed densely in a small set of buffers, rather than spread sparsely across the entire reserve memory.
Buffers are allocated at heap startup, after which allocation often reaches a steady state through free lists.
Allocation buffers may increase external fragmentation, since some memory may never be used.

\item[1:1 model (Figure~\ref{f:PerThreadHeap})] is each thread (1) having its own heap (1), eliminating most contention and locking if threads seldom access another thread's heap (see Section~\ref{s:Ownership}).
A thread's objects are consolidated in its heap, better utilizing the cache and paging during thread execution.
In contrast, the T:H model can spread thread objects over a larger area in different heaps.
%For example, assume page boundaries coincide with cache line boundaries, if a thread heap always acquires pages of memory then no two threads share a page or cache line unless pointers are passed among them.
When a thread terminates, it can free its heap objects to the global heap, or the thread heap is retained as-is and reused for a new thread in the future.
Destroying a heap can reduce external fragmentation sooner, since all free objects in the global heap are available for immediate reuse.
Alternatively, reusing a heap can aid the inheriting thread, if it has a similar allocation pattern, because the heap in primed with freed storage of the right sizes.
\end{description}


\subsubsection{False Sharing}
\label{s:FalseSharing}

False sharing occurs for a read/write or write/write among threads modifying different memory sharing a cache line~\cite{Bolosky93}.
The write invalidates each thread's cache, even though the threads may be uninterested in the other modified object.
False sharing can occur three ways:
1) Thread T$_1$ allocates objects O$_1$ and O$_2$ on the same cache line and passes O$_2$'s reference to thread T$_2$.
2) Thread T$_1$ allocates object O$_1$ and thread T$_2$ allocates O$_2$, where objects O$_1$ and O$_2$ are on the same cache line.
3) T$_2$ deallocates O$_2$, T$_1$ allocates O$_1$ on the same cache line as O$_2$, and T$_2$ reallocated O$_2$ while T$_1$ is using O$_1$.
In all three cases, the false sharing is hidden and possibly transient (non-deterministic), making it extremely difficult to find and fix.
Case 1) occurs in all three allocator models, and is induced by program behaviour, not the allocator.
Case 2) and 3) are allocator induced, and occurs in T:1 and T:H models due to heap sharing, but not 1:1 with private heaps, except possibly at boundary points among heaps.


\subsubsection{Object Containers}
\label{s:ObjectContainers}

Associating header data with every allocation can result in significant internal fragmentation, as shown in Figure~\ref{f:AllocatedObject}.
While the header and object are spatially together in memory, they are generally not accessed temporally together~\cite{Feng05}.
The result is poor cache usage, since only a portion of the cache line is holding useful data from the program's perspective.
% \eg an object is accessed by the program after it is allocated, while the header is accessed by the allocator after it is free.

\begin{figure}
\centering
\input{Container}
\caption{Object Container}
\label{f:ObjectContainer}
\end{figure}

The alternative approach factors common header data to a separate location in memory and organizes associated free storage into blocks called \newterm{object containers} (\newterm{superblocks}~\cite[\S~3]{Berger00}) suballocated from a heap's allocation buffers, as in Figure~\ref{f:ObjectContainer}.
A trailer may also be used at the end of the container.
To find the header from an allocation within the container, the container is aligned on a power of 2 boundary and the lower bits of the object address are truncated (or rounded up, minus the trailer size, to obtain the trailer address).
Container size is a tradeoff between internal and external fragmentation as some portion of a container may not be used and this portion is unusable for other kinds of allocations.
A consequence of this tradeoff is its effect on spatial locality, which can produce positive or negative results depending on the program's access patterns.
Normally, heap ownership applies to its containers.
Without ownership, different objects in a container may be on different heap free-lists.
Finally, containers are linked together for management purposes, and should all objects in a container become free, the container can be repurposed for different sized objects or given to another heap through a global heap.


\subsubsection{Ownership}
\label{s:Ownership}

Object \newterm{ownership} is defined as the heap to which an object is returned upon deallocation~\cite[\S~6.1]{Berger00}.
If a thread returns an object to its originating heap, a heap has ownership of its objects.
Containers force ownership of internal contiguous objects, unless the entire container changes ownership after it becomes empty.
Alternatively, a thread can return an object to the heap it is currently associated with, which can be any heap accessible during a thread's lifetime.
The advantage of ownership is preventing heap blowup by returning storage for reuse by the owner heap.
Ownership prevents the problem of a producer thread allocating from one heap, passing the object to a consumer thread, and the consumer deallocates the object to another heap, hence draining the producer heap of storage.
The disadvantage of ownership is deallocating to another thread's heap requires an atomic operation.

Object ownership can be immediate or delayed, meaning free objects may be batched on a separate free list either by the returning or receiving thread.
The returning thread batches objects to reduce contention by passing multiple objects at once;
however, batching across multiple allocation sizes and heaps is complex and there is no obvious time when to push back to the owner heap.
It is simpler for the returning threads to immediately return to the receiving thread's batch list as the receiving thread has better knowledge when to incorporate the batch list into its free pool.
The receiving thread often delays incorporating returned storage until its local storage in drained.


\subsubsection{User-Level Threading}

Any heap model can be used with user-level (M:N) threading.
However, an important goal of user threads (UT) is for fast operations (creation/termination/context-switching) by not interacting with the OS, allowing large numbers of high-performance interacting threads ($>$ 10,000).
In general, UTs use whatever kernel-level heap-model is provided by the language runtime.
Hence, a UT allocates/deallocates from/to the heap of the KT on which it is executing.

However, there is a subtle concurrency problem with user threading and shared heaps.
With kernel threading, an operation started by a KT is always completed by that thread, even if preempted;
hence, any locking correctness associated with the shared heap is preserved.
However, this correctness property is not preserved for user-level threading.
A UT can start an allocation/deallocation on one KT, be preempted by user-level time slicing, and continue running on a different KT to complete the operation~\cite{Dice02}.
When the UT continues on the new KT, it may have pointers into the previous KT's heap and hold locks associated with it.
To get the same KT safety, time slicing must be disabled/\-enabled around these operations to prevent movement.
However, eagerly disabling time slicing on the allocation/deallocation fast path is expensive, especially as preemption is infrequent (millisecond intervals).
Instead, techniques exist to lazily detect this case in the interrupt handler, abort the preemption, and return to the operation so it completes atomically.
Occasional ignoring a preemption is normally benign;
in the worst case, ignoring preemption results in starvation.
To mitigate starvation, techniques like rolling the preemption forward at the next context switch can be used.


\section{llheap}

This section presents our new stand-alone, concurrent, low-latency memory allocator, called llheap (low-latency heap), fulfilling the GNU C Library allocator API~\cite{GNUallocAPI} for C/\CC programs using KTs, with specialized versions for the programming languages \uC and \CFA using user-level threads running over multiple KTs (M:N threading).
The primary design objective for llheap is low latency across all allocator calls independent of application access-patterns and/or number of threads, \ie very seldom does the allocator delay during an allocator call.
Excluded from the low-latency objective are (large) allocations requiring initialization, \eg zero fill, and/or data copying, along with unbounded delays to acquire storage from the OS or OS scheduling, all of which are outside the allocator's purview.
A direct consequence of this objective is very simple or no storage coalescing;
hence, llheap's design is willing to use more storage to lower latency.
This objective is apropos because systems research and industrial applications are striving for low latency and modern computers have huge amounts of RAM.
Finally, llheap's performance must be comparable with current allocators, both in space and time (see performance comparison in Section~\ref{c:Performance}).


\subsection{llheap Design}

Figure~\ref{f:llheapDesign} shows the design of llheap, which uses the following features:
1:1 allocator model eliminating locking on the fast path,
separate small (@sbrk@) and large object management (@mmap@),
headers per allocation versus containers,
small object binning (buckets) forming lists for different sized freed objects,
optional fast-lookup table for converting allocation requests into bucket sizes,
no coalescing to minimize latency,
optional heap ownership (build time),
reserved memory (buffer pool) per heap obtained from a global pool,
global heap managing freed thread heaps and interacting with the OS to obtained storage,
optional statistic-counters table for accumulating counts of allocation operations and a debugging version for testing (build time).

\begin{figure}
\centering
% \includegraphics[width=0.65\textwidth]{figures/NewHeapStructure.eps}
\input{llheap}
\caption{llheap Design}
\label{f:llheapDesign}
\end{figure}

llheap starts by creating an empty array for $N$ global heaps from storage obtained using @mmap@ that persists for program duration, where $N$ is the number of computer cores.
There is a global last-array pointer and bump-pointer within this array to locate the next free heap storage.
When an array's storage is exhausted, another empty array is allocated.
Terminated threads push their heap onto a global-stack top-pointer, where free heaps are intrusively linked.
When statistics are turned on, there is a global top pointer for a intrusive linked-list to link \emph{all} the heaps (not shown), which is traversed to accumulate statistics counters across heaps when @malloc_stats@ is called.

When a KT starts, it pops heap storage from the heap free-list, or if empty, gets the next free heap-storage.
When a KT terminates, its heap is pushed onto the heap free-list for reuse by a new KT, which prevents unbounded heap growth.
The free heaps are stored in a stack so hot storage is reused first.
Preserving all heaps created during the program lifetime solves the storage lifetime problem when ownership is used.
This approach wastes storage if a large number of KTs are created/terminated at program start and then the program continues sequentially, which is rare.

Each heap uses segregated free-buckets that have free objects distributed across 60 different sizes from 16 to 16M.
All objects in a bucket are the same size.
The number of buckets used is determined dynamically depending on the crossover point from @sbrk@ to @mmap@ allocation, which is specified by calling @mallopt( M_MMAP_THRESHOLD )@, where the cross over must be $\ge$ the page size or $\le$ the largest bucket (16M).
Each cache-aligned bucket has a stack of the same-sized freed objects, where a stack ensures hot storage is reused first.
llheap can be configured with object ownership, where an object is freed to the heap from which it is allocated, or object no-ownership, where an object is freed to the KT's current heap.
For ownership, a shared remote stack is added to the freelist structure, so push/pop operations require locking.
Pushes are eager on each remove free \vs batching, and pops are lazy when there is no cheap storage available, then the entire remote stack is gulped and added to the bucket's free list.

Initial threads are assigned empty heaps from the heap array.
The first thread allocation causes a request for storage from the shared @sbrk@ area.
The size of this request is the maximum of the request size or the @sbrk@-extension-size / 16.
This heuristic means the @sbrk@ area is subdivided into separate heap buffers (HB) per thread, providing no contention and data locality.
A thread does bump allocation in its current buffer, until it starts reusing freed storage or there is insufficient storage, and it obtains another buffer.
Thread buffers are not linked;
only logically connected to the thread through allocated and deallocated storage.
When a thread ends, its heap is returned to the heap array but no storage is released.
A new thread receiving a freed heap starts with it fully populated with freed storage.
The heuristic is that threads often do similar work, so the free storage in the heap is reusable, resulting in less internal fragmentation.
%The heuristic is that threads often do similar work so the free storage in the heap is immediately available.
%The downside is the risk of more external fragmentation, if the freed storage is never reused.
The downside is if the freed storage is never reused creating external fragmentation.

Algorithm~\ref{alg:heapObjectAlloc} shows the allocation outline for an object of size $S$.
The allocation is divided into small (@sbrk@) or large (@mmap@).
For small allocations, $S$ is quantized into a bucket size.
Quantizing is performed using a direct lookup for sizes < 64K or a binary search over the ordered bucket array for $S$ $\ge$ 64K.
Then, the allocation storage is obtained from the following locations, in order of increasing latency: the bucket's free stack, the heap's local buffer, the bucket's remote stack, the global buffer, the OS (@sbrk@).
For large allocations, the storage is directly allocated from the OS using @mmap@.

\begin{algorithm}[t]
\caption{Dynamic object allocation of size $S$}
\label{alg:heapObjectAlloc}
\begin{algorithmic}
\STATE $S \gets S + \text{header-size}$
\IF {$S < \textit{mmap-threshhold}$}
        \STATE $\textit{B} \gets \text{smallest free-bucket} \geq S$
        \IF {$\textit{B's free-list \(\neg\)empty}$}
                \STATE $\textit{O} \gets \text{pop an object from B's free-list}$
        \ELSIF {$\textit{heap's allocation buffer} \ge B$}
                \STATE $\textit{O} \gets \text{bump allocate object of size B from allocation buffer}$
        \ELSIF {$\textit{heap's remote-list \(\neg\)empty}$}
                \STATE $\textit{merge heap's remote-list into free-list}$
                \STATE $\textit{O} \gets \text{pop an object from B's free-list}$
        \ELSE
                \STATE $\textit{O} \gets \text{allocate an object of size B from global pool}$
        \ENDIF
\ELSE
        \STATE $\textit{O} \gets \text{allocate an object of size S using \lstinline{mmap} system-call}$
\ENDIF
\RETURN $\textit{O}$
\end{algorithmic}
\end{algorithm}

Algorithm~\ref{alg:heapObjectFreeOwn} shows the deallocation (free) outline for an object at address $A$ with ownership.
First, the address is divided into small (@sbrk@) or large (@mmap@).
For small allocations, the bucket associated with the request size is retrieved from the allocation header.
If the bucket is local to the thread, the allocation is pushed onto the thread's associated bucket.
If the bucket is not local to the thread, the allocation is pushed onto the owning thread's remote stack.
For large allocations, the storage is unmapped back to the OS.
Without object ownership, the algorithm is the same as for ownership except when the bucket is not local to the thread.
In that case, the corresponding bucket of the owner thread is computed by the deallocating thread, and the allocation is pushed onto the deallocating thread's corresponding bucket, \ie no search is required.

\begin{algorithm}[t]
\caption{Dynamic object free at address $A$ with object ownership}
\label{alg:heapObjectFreeOwn}
\begin{algorithmic}
\IF {$\textit{A heap allocation}$}
        \STATE $\text{B} \gets \textit{O's owner}$
        \IF {$\textit{B's thread = current heap thread}$}
                \STATE $\text{push A to B's free-list}$
        \ELSE
                \STATE $\text{push A to B's remote-list}$
        \ENDIF
\ELSE
        \STATE $\text{return A to system using system call \lstinline{munmap}}$
\ENDIF
\end{algorithmic}
\end{algorithm}

\begin{comment}
\begin{algorithm}
\caption{Dynamic object free at address $A$ without object ownership}
\label{alg:heapObjectFreeNoOwn}
\begin{algorithmic}[1]
\IF {$\textit{A mapped allocation}$}
        \STATE $\text{return A's dynamic memory to system using system call \lstinline{munmap}}$
\ELSE
        \STATE $\text{B} \gets \textit{O's owner}$
        \IF {$\textit{B is thread-local heap's bucket}$}
                \STATE $\text{push A to B's free-list}$
        \ELSE
                \STATE $\text{C} \gets \textit{thread local heap's bucket with same size as B}$
                \STATE $\text{push A to C's free-list}$
        \ENDIF
\ENDIF
\end{algorithmic}
\end{algorithm}
\end{comment}

Finally, the llheap design funnels all allocation/deallocation operations through the @malloc@ and @free@ routines, which are the only routines to directly access and manage the internal data structures of the heap.
Other allocation operations, \eg @calloc@, @memalign@, and @realloc@, are composed of calls to @malloc@ and possibly @free@, and may manipulate header information after storage is allocated.
This design simplifies heap-management code during development and maintenance.


\subsubsection{Bounded Allocation}

The llheap design results in bounded allocation.
For small allocations, once all the buckets have freed objects, storage is recycled.
For large allocations, the storage is directly recycled back to the OS.
When a thread terminates, its heap is recycled to the next new thread and the above process begins for that thread.
The pathological case is threads allocating a large amount of storage, freeing it, and then quiescing, which demonstrates that the bound constant can be large.
This pathological pattern occurs for \emph{immortal} threads, \eg I/O threads with program lifetime and bursts of activity performing many allocations/deallocations.
Hence, independent of external fragmentation in thread heaps, storage cannot grow unbounded unless the program does not free.


\subsubsection{Alignment}

The minimum storage alignment $M$ comes from the architecture application-binary-interface (ABI) based on hardware factors: bus width (32 or 64-bit), largest register (double, long double), largest atomic instruction (double compare-and-swap), or vector data (Intel MMX).
An access with a nonaligned address maybe slow or an error.
A memory allocator must assume the largest hardware requirement because it is unaware of the data type occupying the allocation.
Often the minimum storage alignment is an 8/16-byte boundary on a 32/64-bit computer, respectively.
Alignments larger than $M$ are powers of 2, such as page alignment (4/8K).
Any alignment less than $M$ is raised to the minimal alignment.

llheap aligns its allocation header on an $M$ boundary and its size is $M$, making the following data $M$ aligned.
This pattern means there is no minimal alignment computation along the allocation fast path, \ie new storage and reused storage is always correctly aligned.
An alignment $N$ greater than $M$ is accomplished with a \emph{pessimistic} request for storage that ensures \emph{both} the alignment and size request are satisfied.
\begin{center}
\input{Alignment2}
\end{center}
The amount of storage necessary is $alignment - M + size$, which ensures there is an address, $A$, after the storage returned from @malloc@, $P$, that is a multiple of $alignment$ followed by sufficient storage for the data object.
The approach is pessimistic if $P$ happens to have the correct alignment $N$, and the initial allocation has requested sufficient space to move to the next multiple of $N$.
In this case, there is $alignment - M$ bytes of unused storage after the data object, which could be used by @realloc@.
Note, the address returned by the allocation is $A$, which is subsequently returned for deallocation.
However, the deallocation requires the value $P$, which must be computable from $A$, from which $H$ can be computed $P - M$.
Hence, there must be a mechanism to detect $P$ $\neq$ $A$ and compute $P$ from $A$.

To detect and perform this computation, llheap uses two headers:
the \emph{original} header $H$ associated with the allocation, and a \emph{fake} header $F$ within this storage before the alignment boundary $A$.
\begin{center}
\input{Alignment2Impl}
\end{center}
Since every allocation is aligned at $M$, $P$ $\neq$ $A$ only holds for alignments greater than $M$.
When $P$ $\neq$ $A$, the minimum distance between $P$ and $A$ is $M$ bytes, due to the pessimistic storage allocation.
Therefore, there is always room for an $M$-byte fake header before $A$.
The fake header must supply an indicator to distinguish it from a normal header and the location of address $P$ generated by the allocation.
This information is encoded as an offset from A to P and the initial alignment (discussed in Section~\ref{s:ReallocStickyProperties}).
To distinguish a fake header from a normal header, the least-significant bit of the alignment is set to 1 because the offset participates in multiple calculations, while the alignment is just remembered data.
\begin{center}
\input{FakeHeader}
\end{center}

Note, doing alignment with containers requires a separate container for the aligned fixed-sized objects, so there are more kinds of containers that must be managed.


\subsubsection{\lstinline{realloc} and Sticky Properties}
\label{s:ReallocStickyProperties}

The allocation routine @realloc@ provides a memory management pattern for shrinking/enlarging an existing allocation, while maintaining some or all of the object data.
The realloc pattern is simpler than the suboptimal manual steps.
\begin{flushleft}
\setlength{\tabcolsep}{10pt}
\begin{tabular}{ll}
\multicolumn{1}{c}{\textbf{realloc pattern}} & \multicolumn{1}{c}{\textbf{manual}} \\
\begin{C++}
T * naddr = realloc( oaddr, newSize );



\end{C++}
&
\begin{C++}
T * naddr = (T *)malloc( newSize ); $\C[2in]{// new storage}$
memcpy( naddr, addr, oldSize );  $\C{// copy old bytes}$
free( addr );                           $\C{// free old storage}$
addr = naddr;                           $\C{// change pointer}\CRT$
\end{C++}
\end{tabular}
\end{flushleft}
The manual steps are suboptimal because there may be internal fragmentation at the end of the allocation due to bucket sizes.
If this storage is sufficiently large, it eliminates a new allocation and copying.
Alternatively, if the storage is made smaller, there may be a reasonable crossover point, where just increasing the internal fragmentation eliminates a new allocation and copying.
Hence, using @realloc@ as often as possible can reduce storage management costs.
In fact, if @oaddr@ is @nullptr@, @realloc@ does a @malloc( newSize)@, and if @newSize@ is 0, @realloc@ does a @free( oaddr )@, so all allocation/deallocation can be done with @realloc@.

The hidden problem with this pattern is the effect of zero fill and alignment with respect to reallocation.
For safety, these properties must persist (be ``sticky'') when storage size changes.
Prior to llheap, allocation properties are not preserved across reallocation nor is it possible to query an allocation to maintain these properties manually.
Hence, a random call to @realloc@ that reallocates storage may cause downstream errors, if allocation properties are needed.
This silent problem is unintuitive to programmers, can cause catastrophic failure, and is difficult to debug because it is transient.
To prevent these problems, llheap preserves initial allocation properties within an allocation, allowing them to be queried, and the semantics of @realloc@ preserve these properties on any storage change.
As a result, the realloc pattern is efficient and safe.

Note, @realloc@ has a compile-time disadvantage \vs @malloc@, because @malloc@ simplifies optimization opportunities.
For @malloc@ the compiler knows the new storage address is not aliased, which is not true for @realloc@: the same storage can be returned.
The compiler uses this knowledge to optimize the region of code between the @malloc@ call and the point where the pointer escapes or it finds the matching @free@.
For @realloc@, the compiler must also analyse the code \emph{before} the call and this analysis may fail.

Finally, there is a flaw in @realloc@'s definition: if there is no memory to allocate new storage for an expansion, the original allocation is not freed or moved, @errno@ is set to @ENOMEM@, and a null pointer is returned.
This semantics preserves the original allocation so the data is not lost in a failure case.
However, most calls to @realloc@ are written: @p = realloc( p, size )@, so the original storage is leaked when pointer @p@ is overwritten with null, negating the benefit of not freeing the storage for recovery purposes.
Programmers can follow a coding pattern of:
\begin{C++}
char * p;
...
void * p1 = realloc( p, size );
if ( p1 ) p = (char *)p1;
else // release some storage
\end{C++}
However, most programmers ignore return codes.
A better alternative is to change @realloc@'s interface to be like @posix_memalign@, which returns two results, a return code and a storage address, so the error code is separate from the returned storage.
\begin{C++}
int retcode = realloc( (void **)&p, size );
\end{C++}
which returns 0 or @ENOMEM@, only changes @p@ for expansion, but requires an ugly cast on the call.


\subsubsection{Sticky Test}

Since sticky properties are an important safety feature for @realloc@, an ad-hoc @realloc@ test was created (not shown) to test whether a memory allocator preserves zero-fill from @calloc@ and/or alignment from @memalign@.
The first test @calloc@s a large array (zero fill), sets the array to 42, shortens it, and then enlarges it to the original size.
It does these steps 100 times attempting to get a reused large block of memory that is still set to 42, showing new storage does not preserve zero fill.
The second test @memalign@s storage and @realloc@s it multiple times making it larger until the current storage must be copied into new storage.
The alignment of each storage address returned from @realloc@ is verified with the original alignment.

If a test fails, that sticky properties is not provided;
if the test passes, that sticky property is provided in some form but not necessarily in all forms (test just got lucky).
If an allocator fails these tests, it is unnecessary to perform a manual inspection of the @realloc@ code for sticky properties.
Only llheap passes the test, as its @realloc@ applies sticky properties.


\subsubsection{Header}

To preserve allocation properties requires storing additional information about an allocation.
Figure~\ref{f:llheapHeader} shows llheap captures this information in the per object header, which has two fields (left/right) sized appropriately for 32/64-bit alignment requirements.

\begin{figure}
\centering
\input{Header}
\caption{llheap Header}
\label{f:llheapHeader}
\end{figure}

The left field is a union of three values:
\begin{description}[leftmargin=*,topsep=2pt,itemsep=2pt,parsep=0pt]
\item[bucket pointer]
is for deallocation and points back to the bucket associated with this storage request (see Figure~\ref{f:llheapDesign} for the fields accessible in a bucket).
\item[mapped size]
is for deallocation of mapped storage and is the storage size for unmapping.
\item[next free block]
is an intrusive pointer linking same-size free blocks onto a bucket's stack of free objects.
\end{description}
The low-order 3-bits of these fields are unused for any stored values, due to the minimum aligned of 8-bytes (even for 32-bit addressing).
The 3 unused bits are used to represent mapped allocation, zero filled, and alignment, respectively.
Note, the zero-filled/mapped bits are only used in the normal header and the alignment bit in the fake header.
This implementation allows a fast test if any of the lower 3-bits are on (@&@ and compare).
If no bits are on, it implies a basic allocation, which is handled quickly in the fast path for allocation and free;
otherwise, the bits are analysed and appropriate actions are taken for the complex cases.

The right field remembers the allocation request size versus the allocation (bucket) size, \eg request of 42 bytes is rounded up to 64 bytes.
Since programmers think in request size rather than allocation size, the request size allows better generation of statistics or errors and also helps in memory management.


\subsection{Statistics and Debugging}

llheap can be built to accumulate fast and largely contention-free allocation statistics to help understand dynamic memory behaviour.
Incrementing statistic counters must appear on the allocation fast path.
To make statistics performant enough for use on running systems, each heap has its own set of statistic counters, so statistic operations do not require slow atomic operations.

To locate all statistic counters, heaps are linked together in statistics mode, and this list is locked and traversed to sum all counters across heaps.
Note, the list is locked to prevent errors traversing an active list, which may have nodes added or removed dynamically;
the statistics counters are not locked and can flicker during accumulation.
Hence, printing statistics during program execution is an approximation.
Figure~\ref{f:StatiticsOutput} shows an example of statistics output, which covers all allocation operations and information about deallocating storage not owned by a thread.
No other memory allocator provides as comprehensive statistical information.
These statistics were invaluable during the development of llheap for debugging and verifying correctness, and should be equally valuable to application developers.

\begin{figure}
\begin{C++}
PID: 2167216 Heap statistics: (storage request / allocation)
  malloc    >0 calls 19,938,000,110; 0 calls 2,064,000,000; storage 4,812,152,081,688 / 5,487,040,092,624 bytes
  aalloc    >0 calls 0; 0 calls 0; storage 0 / 0 bytes
  calloc    >0 calls 7; 0 calls 0; storage 1,040 / 1,152 bytes
  memalign  >0 calls 0; 0 calls 0; storage 0 / 0 bytes
  amemalign >0 calls 0; 0 calls 0; storage 0 / 0 bytes
  cmemalign >0 calls 0; 0 calls 0; storage 0 / 0 bytes
  resize    >0 calls 0; 0 calls 0; storage 0 / 0 bytes
  realloc   >0 calls 0; 0 calls 0; storage 0 / 0 bytes
            copies 0; smaller 0; alignment 0; 0 fill 0
  free      !null calls 19,938,000,092; null / 0 calls 4,064,000,004; storage 4,812,152,003,021 / 5,487,040,005,152 bytes
  remote    pushes 4; pulls 0; storage 0 / 0 bytes
  sbrk      calls 1; storage 8,388,608 bytes
  mmap      calls 2,000,000; storage 2,097,152,000,000 / 2,105,344,000,000 bytes
  munmap    calls 2,000,000; storage 2,097,152,000,000 / 2,105,344,000,000 bytes
  remainder calls 0; storage 0 bytes
  threads   started 4; exited 4
  heaps     $new$ 4; reused 0
\end{C++}
\caption{Statistics Output}
\label{f:StatiticsOutput}
\end{figure}

llheap can also be built with debug checking, which inserts many asserts along all allocation paths.
These assertions detect incorrect allocation usage, like double frees, unfreed storage, or memory corruption because internal values (like header fields) are overwritten.
These checks are best effort as opposed to complete allocation checking as in @valgrind@~\cite{valgind}.
Nevertheless, the checks detect many allocation problems.
There is a problem in detecting unfreed storage because some library routines assume their allocations have life-time duration, and hence, do not free their storage.
For example, @printf@ might allocate a 1024-byte buffer on the first call and never delete this buffer.
To prevent a false positive for unfreed storage, it is possible to specify an amount of storage that is never freed (see @malloc_unfreed@ in Section~\ref{s:ExtendedCAPI}), and it is subtracted from the total allocate/free difference.
Determining the amount of never-freed storage is annoying, but once done, any warnings of unfreed storage are application related.
Debugging mode also scrubs each allocation with @0xff@, so assumptions about zero-filled objects generate errors.
Finally, if a program does segment-fault in debug mode, a stack backtrace is printed to help in debugging.

Tests indicate only a 30\% performance decrease when statistics \emph{and} debugging are enabled in programs with 10\% to 15\% allocation cost, and the latency cost for accumulating statistic from each heap is mitigated by limited calls, often only one at the end of the program.


% \subsection{Design Choices}
% 
% llheap's design was reviewed and changed multiple times during its development.
% All designs focused on the allocation/free \newterm{fast path}, \ie the shortest code path for the most common operations.
% The model chosen is 1:1, giving one heap per thread for each kernel thread (KT).
% Hence, immediately after a KT starts, its heap is created and just before a KT terminates, its heap is (logically) deleted.
% Therefore, the majority of heap operations are uncontended, modulo operations on the global heap and ownership.
% 
% Problems:
% \begin{itemize}[leftmargin=*,topsep=3pt,itemsep=2pt,parsep=0pt]
% \item
% Need to know when a KT starts/terminates to create/delete its heap.
% 
% \noindent
% It is possible to leverage constructors/destructors for thread-local objects to get a general handle on when a KT starts/terminates.
% \item
% There is a classic \newterm{memory-reclamation} problem for ownership because storage passed to another thread can be returned to a terminated heap.
% 
% \noindent
% The classic solution only deletes a heap after all referents are returned, which is complex.
% The cheap alternative is for heaps to persist for program duration to handle outstanding referent frees.
% If old referents return storage to a terminated heap, it is handled in the same way as an active heap.
% To prevent heap blowup, terminated heaps can be reused by new KTs, where a reused heap may be populated with free storage from a prior KT (external fragmentation).
% In most cases, heap blowup is not a problem because programs have a small allocation set-size, so the free storage from a prior KT is apropos for a new KT.
% \item
% There can be significant external fragmentation as the number of KTs increases.
% 
% \noindent
% In many concurrent applications, good performance is achieved with the number of KTs proportional to the number of CPUs.
% Since the number of CPUs is relatively small, and a heap is also relatively small, $\approx$10K bytes (not including any associated freed storage), the worst-case external fragmentation is still small compared to the RAM available on large servers with many CPUs.
% \item
% Need to prevent preemption during a dynamic memory operation because of the \newterm{serially-reusable problem}.
% \begin{quote}
% A sequence of code that is guaranteed to run to completion before being invoked to accept another input is called serially-reusable code.~\cite{SeriallyReusable}\label{p:SeriallyReusable}
% \end{quote}
% If a KT is preempted during an allocation operation, the OS can schedule another KT on the same CPU, which can begin an allocation operation before the previous operation associated with this CPU has completed, invalidating heap correctness.
% Note, the serially-reusable problem can occur in sequential programs with preemption, if the signal handler calls the preempted function, unless the function is serially reusable.
% Essentially, the serially-reusable problem is a race condition on an unprotected critical subsection, where the OS is providing the second thread via the signal handler.

% There is the same serially-reusable problem with UTs migrating across KTs.
% \end{itemize}
% Tests showed this design produced the closest performance match with the best current allocators, and code inspection showed most of these allocators use different variations of this approach.


\subsection{Bootstrapping}

There are problems bootstrapping a memory allocator.
Programs can be statically or dynamically linked.
The order in which the linker schedules startup code is poorly supported so it cannot be controlled entirely.
Knowing a KT's start and end independently from the KT code is also difficult.

For static linking, the allocator is loaded with the program.
Hence, allocation calls immediately invoke the allocator operation defined by the loaded allocation library and there is only one memory allocator used in the program.
This approach allows allocator substitution by placing an allocation library before any other in the linked/load path.

Allocator substitution is similar for dynamic linking.
However, the dynamic loader starts first and needs to perform dynamic allocations \emph{before} the substitution allocator is loaded.
As a result, the dynamic loader uses a default allocator until the substitution allocator is loaded, after which all allocation operations are handled by the substitution allocator, including those from the dynamic loader.
Hence, some part of the @sbrk@ area may be used by the default allocator and substitution allocator statistics cannot be correct.
Furthermore, dynamic linking uses an assembler trampoline to call the procedure linkage table resolver, so there is an additional cost along the allocator fast path for all allocation operations.
Testing showed up to a 5\% performance decrease with dynamic linking as compared to static linking, even when using @tls_model( "initial-exec" )@ to obtain tighter binding.

After the allocator is loaded, it needs to be initialized before the first allocation request.
Currently, the only mechanism to control initialization is via constructor routines (see below), each with an integer priority, where the linker calls the constructors in increasing order of priority.
However, there are few conventions for priorities amongst libraries, where constructors with equal priorities are called in arbitrary order.
(Only a transitive closure of references amongst library calls can establish an absolute initialization order.)
As a result, the first call to an allocation routine can occur without initialization.
To deal with this problem, it is necessary to have a global flag that is checked along the allocation fast path to trigger initialization (singleton pattern).

Along these lines, there is a subtle problem is defining when a program starts and ends.
For example, prolog/epilog code outside of the program should not be considered in statistics as the application does not make these calls.
llheap establishes these two points using constructor/destructor routines with initialization priority 100, where system libraries use priorities $\le$ 100 and application programs have priorities $>$ 100.
\begin{flushleft}
\hspace*{\parindentlnth}
\setlength{\tabcolsep}{20pt}
\begin{tabular}{@{}ll@{}}
\begin{C++}
@__attribute__(( constructor( 100 ) ))@
static void startup( void ) {
        // clear statistic counters
        // reset allocUnfreed counter
}

\end{C++}
&
\begin{C++}
@__attribute__(( destructor( 100 ) ))@
static void shutdown( void ) {
        // sum allocUnfreed for all heaps
        // subtract global unfreed storage
        // if allocUnfreed > 0 then print warning message
}
\end{C++}
\end{tabular}
\end{flushleft}
Hence, @startup@ is called after the program prologue but before the application starts, and @shutdown@ is called after the program terminates but before the program epilogue.
By resetting counters in @startup@, prologue allocations are ignored, and checking unfreed storage in @shutdown@ checks only application memory management, ignoring the program epilogue.

Unfortunately, @startup@/@shutdown@ only apply to the program KT, not to any additional KTs created by the program.
However, it is essential for the allocator to know when each KT is started/terminated to initialize/de-initialize the KT's heap.
Initialization can be handled by making the global flag (above) thread-local and then the initialization check along the fast path covers the first allocation by a newly created thread.
De-initialization is handled by registering a destructor routine using @pthread_key_create@ in the initialization code triggered along the fast path, which subsequently calls the destructor at thread termination.


\subsection{User-level Threading Support}
\label{s:UserlevelThreadingSupport}

llheap is the underlying allocator in the user-threading programming languages \uC and \CFA.
These systems have preemptive scheduling, which requires management of timing events through a signal handle (@SIGALRM@).
The complexity in these system is the serially-reusable problem (see Section~\ref{s:SingleThreadedMemoryAllocator}) when UTs are time sliced (language level) independently from KTs (OS level).
The solution is to prevent interrupts resulting in a CPU or KT change during critical operations, eliminating problems like starting a memory operation on one KT and completing it on another when the underlying heaps are different.
% For user-level threading, the serially-reusable problem occurs with time slicing for preemptable user-level scheduling, as the interrupted UT is unlikely to be restarted on the same KT.
However, without time slicing, a long running UT prevents the execution of other UTs (starvation).

The languages modify llheap using two techniques to prevent time slicing during non-interruptible allocation operations.
On the slow path, when executing expensive operations, time-slicing interrupts are disabled/enabled, so the operation completes atomically on the KT.
On the fast path, all non-interruptible allocation/deallocation routines are placed in a separate code segment.
The linker places this segment into a contiguous block of memory. %, but the order of routines within the block is unspecified.
Then the time-slice signal handler compares the program counter at the point of interrupt with the start/end address of the non-interruptible segment, and if executing within the segment, the signal handler returns without context switching.
The llheap funnel design simplifies this implementation so only a few funnel and statistics routines are located in the non-interruptible section.
% This technique is fragile as no mechanism exists to ensure all crucial code along the fast path is placed into the non-interruptible segment.

Interestingly, marking non-interruptible operations by bracketing them with a set/reset of a thread-local flag fails, as read/write is not atomic on some machines.
For example, the ARM processor stores the thread-local pointer in a coprocessor register that cannot perform atomic base-displacement addressing.
Hence, there is a window between loading the kernel-thread-local pointer from the coprocessor register into a normal register and adding the displacement when a time slice can move a UT.
As well, switching to a T:C model with restartable critical sections using @librseq@~\cite{Desnoyers19} was examined (see Section~\ref{s:MutualExclusion}).
However, tests showed that while  @librseq@ can determine the particular CPU quickly, setting up the restartable critical-section along the allocation fast-path produced a significant decrease in performance.
Also, the number of undoable writes in @librseq@ is limited and restartable sequences cannot deal with UT migration across KTs.
For example, UT$_1$ is executing an allocation by KT$_1$ on CPU$_1$ and a time-slice preemption occurs.
The signal handler context switches UT$_1$ onto the user-level ready-queue and starts running UT$_2$ on KT$_1$, which immediately performs an allocation.
Since KT$_1$ is still executing on CPU$_1$, @librseq@ takes no action because it assumes KT$_1$ is still executing the same critical section.
Then UT$_1$ is scheduled onto KT$_2$ by the user-level scheduler, and its allocation operation continues in parallel with UT$_2$ using references into the heap associated with CPU$_1$, which corrupts CPU$_1$'s heap.
If @librseq@ had an @rseq_abort@ which:
\begin{enumerate}[leftmargin=*,topsep=2pt,itemsep=0pt,parsep=0pt]
\item
marks the current restartable critical-section as cancelled so it restarts when attempting to commit.
\item
does nothing if there is no current restartable critical section in progress.
\end{enumerate}
Then @rseq_abort@ could be called on the backside of a user-level context-switching.
A feature similar to this idea might exist for hardware transactional memory.
A significant effort was made to make this approach work but its complexity, lack of robustness, and performance costs resulted in its rejection.


\subsection{C API}

Figure~\ref{f:CDynamicAllocationAPI} shows the C dynamic allocation API, which is neither orthogonal nor complete.
For example, it is possible to zero fill or align an allocation but not both, it is only possible to zero fill an array allocation, and it is not possible to resize a memory allocation without data copying.
As a result, programmers must provide missing alternatives, which is error prone, rightly blaming the C programming language for a poor allocation API.
Furthermore, newer programming languages have better type systems that can provide safer and more powerful APIs for memory allocation.
The following presents llheap API changes.

\begin{figure}
\hspace*{\parindentlnth}
\begin{tabular}{@{}l|l@{}}
\begin{C++}
void * malloc( size_t size );
void * calloc( size_t dimension, size_t size );
void * realloc( void * oaddr, size_t size );
void * reallocarray( void * oaddr, size_t dimension, size_t size );
void free( void * addr );
void * memalign( size_t alignment, size_t size );
void * aligned_alloc( size_t alignment, size_t size );
int posix_memalign( void ** memptr, size_t alignment, size_t size );
void * valloc( size_t size );
void * pvalloc( size_t size );
\end{C++}
&
\begin{C++}
int mallopt( int option, int value );
size_t malloc_usable_size( void * addr );
void malloc_stats( void );
int malloc_info( int options, FILE * fp );

// Unsupported
struct mallinfo mallinfo( void );
int malloc_trim( size_t );
void * malloc_get_state( void );
int malloc_set_state( void * );
\end{C++}
\end{tabular}
\caption{llheap support of C dynamic-allocation API}
\label{f:CDynamicAllocationAPI}
\end{figure}


\subsubsection{Extended C API}
\label{s:ExtendedCAPI}

llheap transparently augments the C dynamic memory API to increase functionality, orthogonality, and safety.
\begin{itemize}[leftmargin=*,topsep=3pt,itemsep=2pt,parsep=0pt]
\item
@malloc@ remembers the original allocation size separate from the actual allocation size.
\item
@calloc@ sets the sticky zero-fill property.
\item
@memalign@, @aligned_alloc@, @posix_memalign@, @valloc@ and @pvalloc@ set the sticky alignment property, remembering the specified alignment size.
\item
@realloc@ and @reallocarray@ preserve sticky properties across copying.
\item
@malloc_stats@ prints detailed statistics of allocation/free operations when linked with a statistic version.
\item
Existence of shell variable @MALLOC_STATS@ implicitly calls @malloc_stats@ at program termination, so precompiled programs do not have to be modified.
\end{itemize}

llheap extends the C dynamic-memory API with new allocation operations with APIs matching existing C counterparts.
\begin{itemize}[leftmargin=*,topsep=3pt,itemsep=1pt,parsep=0pt]
\item
@aalloc@ extends @calloc@ for dynamic array allocation \emph{without} zero-filling the memory (faster than @calloc@).
\item
@resize@ extends @realloc@ for resizing an allocation \emph{without} copying previous data or preserving sticky properties (faster than @realloc@).
\item
@resizearray@ extends @resize@ for an array allocation (faster than @reallocarray@).
\item
@amemalign@ extends @aalloc@ with alignment and sets sticky alignment property.
\item
@cmemalign@ extends @amemalign@ with zero fill and sets sticky zero-fill and alignment property.
\item
@aligned_resize@ extends @resize@ with an alignment.
\item
@aligned_resizearray@ extends @resizearray@ with alignment.
\item
@aligned_realloc@ extends @realloc@ with alignment.
\item
@aligned_reallocarray@ extends @resizearray@ with alignment.
\end{itemize}

llheap extends the C dynamic memory API with new control operations.
The following routines are called \emph{once} during llheap startup to set specific limits \emph{before} an application starts.
Setting these value early is essential because allocations can occur from the dynamic loader and other libraries before application code executes.
To set a value, define a specific routine in an application and return the desired value, \eg
\begin{C++}
size_t malloc_extend() { return 16 * 1024 * 1024; }
\end{C++}
\begin{itemize}[leftmargin=*,topsep=0pt,itemsep=1pt,parsep=0pt]
\item
@malloc_extend@ returns the number of bytes to extend the @sbrk@ area when there is insufficient free storage to service an allocation request.
\item
@malloc_mmap_start@ returns the crossover allocation size from the @sbrk@ area to separate mapped areas, see also @mallopt( M_MMAP_THRESHOLD )@.
\item
@malloc_unfreed@ returns the amount subtracted from the global unfreed program storage to adjust for unreleased storage from routines like @printf@ (debug only).
\end{itemize}

llheap extends the C dynamic-memory API with functions to query object properties.
\begin{itemize}[leftmargin=*,topsep=3pt,itemsep=1pt,parsep=0pt]
\item
@malloc_size@ returns the requested size of a dynamic object, which is updated when an object is resized, similar to @malloc_usable_size@.
\item
@malloc_alignment@ returns the object alignment, where the minimal alignment is 16 bytes.
\item
@malloc_zero_fill@ returns true if the object is zero filled.
\item
@malloc_remote@ returns true if the object is from a remote heap (@OWNERSHIP@ only).
\end{itemize}

llheap extends the C dynamic-memory API with new statistics control.
\begin{itemize}[leftmargin=*,topsep=3pt,itemsep=1pt,parsep=0pt]
\item
@malloc_stats_fd@ sets the file descriptor for @malloc_stats@ writes (default @stdout@).
\item
@malloc_stats_clear@ clears the statistics counters for all thread heaps.
\item
@heap_stats@ extends @malloc_stats@ to only print statistics for the heap associated with the executing thread.
\end{itemize}


\subsubsection{Modern Allocation API}

Modern programming languages have complex type systems that can be used to consolidate the panoply of memory allocation routines and features, providing a simpler programming experience and safety.
The \CFA language is used to demonstrate this capability, because llheap forms the memory allocator for this C variant, but other languages can provide similar APIs.

\CFA polymorphism reduces the allocation API to two overloaded routines allocating a single object or an array of objects.
\begin{cfa}
forall( T & ) {
        T * alloc( /* list of property functions ... */  ) { ... } // singleton allocation
        T * alloc( size_t @dimension@, /* list of property functions ... */  ) { ... } // array allocation
}
\end{cfa}
Because the \CFA type system uses the return type to select overloads (like Ada), this capability is leveraged to remove the object-size parameter and return cast for regular calls to C @malloc@ or @memalign@.
\begin{cfa}
inline T * alloc( ... ) {
        if ( _Alignof(T) <= defaultAlign() ) return @(T *)@malloc( @sizeof(T)@ ); // C allocation
        else return @(T *)@memalign( @_Alignof(T)@, @sizeof(T)@ ); // C allocation
}
\end{cfa}
The calls to these two routine are now much safer than the C equivalents.
\begin{C++}
int * ip = alloc(); $\C[2.75in]{// T => int, sizeof => 4/8, alignment => default}$
double * dp = alloc(); $\C{// T => double, sizeof => 8, alignment => default}$
struct Spinlock { ... } [[aligned(128)]] * sp = alloc(); $\C{// T => Spinlock, sizeof => ..., alignment = 128}$
int * ia = alloc( 10 ); $\C{// T => int, sizeof => 4/8, alignment => default, dimension => 10}\CRT$
\end{C++}
At compile time, each call to @alloc@ extracts the return type @T@ from the left-hand side of the assignment, which is then used in @sizeof@, @_Alignof@, and casting the storage to the correct type.
The @inline@ and constant expression allow the compiler to remove the @if@ statement.
This interface removes all the common allocation-call errors in C and provides a uniform name covering all allocation reducing the cognitive burden.

The property functions are a variable number of routines providing @alloc@ with management details and actions.
The functions are @align@, @fill@, @resize@, and @realloc@, and written in prefix versus postfix notation solely for aesthetic reasons, \eg @3`fill@ $\equiv$ @fill( 3 )@.
The examples are arrays but apply equally to singleton allocations.
\begin{cfa}
int * ip = alloc( 5, @4096`align@, @5`fill@ ); $\C[3in]{// start array on 4096 boundary and initialize elements with 5}$
int * ip2 = alloc( 10, @ip`fill@, @(malloc_alignment( ip ))`align@ ); $\C{// first 5 elements same as ip, same alignment as ip}$
_Complex double * cdp = alloc( 5, @(3.5+4.1i)`fill@ ); $\C{// initialize complex elements with 3.5+4.1i}$
struct S { int i, j; };
S * sp = alloc( 10, @((S){3, 4})`fill@ ); $\C{// initialize structure elements with {3, 4}}$
ip = alloc( 10, @ip`realloc@, @10`fill@ ); $\C{// make array ip larger and initialize new elements with 10}$
double * dp = alloc( 5, @ip2`resize@, @256`align@, @13.5`fill@ ); $\C{// reuse ip2 storage for something else}\CRT$
\end{cfa}
Finally, \CFA has constructors and destructors, like \CC, which are invoked when allocating with @new@ and @delete@.
\begin{cfa}
T * t = new( 3, 4, 5 ); $\C[3in]{// allocate T and call constructor T\{ 3, 4, 5 \}}$
W * w = new( 3.5 ); $\C{// allocate W and call constructor W\{ 3,5 \}}$
delete( t, w ); $\C{// call destructors and free t and w}\CRT$
\end{cfa}
The benefits of high-level API simplifications should not be underestimated with respect to programmer productivity and safety.


\section{Performance}
\label{c:Performance}

This section uses a number of benchmarks to compare the behaviour of currently popular memory allocators with llheap.
The goal is to see if llheap is a competitive memory allocator;
no attempt is made to select a performance winner.


\subsection{Experimental Environment}
\label{s:ExperimentalEnvironment}

The performance experiments are run on three different multi-core architectures, ARM, AMD, and Intel, covering memory models weak order (WO) and total store order (TSO), to determine if there is consistency across architectures:
\begin{description}[leftmargin=*,topsep=3pt,itemsep=2pt,parsep=0pt]
\item[ARM]
Gigabyte E252-P31 128-core socket 3.0 GHz, WO memory model
\item[AMD]
Supermicro AS--1125HS--TNR EPYC 9754 128--core socket, hyper-threading $\times$ 2 sockets (512 processing units) 2.25 GHz, TSO memory model
\item[Intel]
Supermicro SYS-121H-TNR Xeon Gold 6530 32--core, hyper-threading $\times$ 2 sockets (128 processing units) 2.1 GHz, TSO memory model
\end{description}
For the parallel experiments, threads are pinned to cores in a linear fashion, \ie from core $N$ to $N+M$, where $N$ is the start of a socket boundary.
This layout produces the best throughput, as there is little or no communication among threads in the benchmarks, so binding tightly to the cache layout is unnecessary;
hence, there is almost no OS or NUMA effects perturbing the benchmarks.

The compilers are gcc/g++-14.2.0 and gfortran-14.2.0 running on the Linux v6.8.0-52-generic OS, with @LD_PRELOAD@ used to override the default allocator.
To prevent eliding certain code patterns, crucial parts of a test are wrapped by the function @pass@
\begin{uC++}
static inline void * pass( void * v ) {         $\C[2.5in]{// prevent eliding, cheaper than volatile}$
        __asm__  __volatile__( "" : "+r"(v) );  return v;
}
void * vp = pass( malloc( 0 ) );                        $\C{// wrap malloc call to prevent elision}\CRT$
\end{uC++}
The call to @pass@ can prevent a small number of compiler optimizations but this cost is the same for all allocators.


\subsection{Memory Allocators}
\label{s:MemoryAllocators}

Historically, a number of C/\CC, stand-alone, general-purpose memory-allocators, \eg dlmalloc~\cite{dlmalloc}, have been written for use by programming languages providing unmanaged memory.
For this work, 6 of the popular, thread-safe memory-allocators are selected for comparison, along with llheap.

\begin{description}[leftmargin=*,topsep=3pt,itemsep=2pt,parsep=0pt,listparindent=\parindent]
\item[glibc~\cite{glibc}] % https://sourceware.org/glibc/wiki/MallocInternals
is the default glibc allocator, derived from ptmalloc, derived from dlmalloc.
glibc has multiple threads sharing multiple heaps with a global shared heap, header per allocation, free-lists with different organizational criteria and searching, and coalescing of certain adjacent free-areas.
Version Ubuntu GLIBC 2.31-0ubuntu9.7 2.31 compiled by Ubuntu 24.04.

\item[hoard~\cite{hoard}]
has multiple threads sharing multiple heaps with a global shared heap, where each heap is composed of superblocks containing fixed-sized objects, with each super-block having a single header for its objects and reuse of superblocks if empty.
Version 3.13.0, compiled with gcc-14.2.0, default configuration, using command @make@.
Over the past 5 years, hoard development has stopped;
it fails on the ARM architecture, possibly because of the WO memory model.

\item[jemalloc~\cite{Evans06}]
has multiple threads sharing multiple heaps (arenas) composed of same-sized chunks subdivided into regions composed of pages where each page is a container of same-sized objects.
The components are organized into a number of data structures to facilitate allocations, freeing, and coalescing.
Large objects are allocated using @mmap@.
Version jemalloc-5.3.0~\cite{jemalloc}, built with the default configuration, using commands: @autogen.sh; configure; make; make install@.

\item[mimalloc~\cite{Leijen19}]
has a heap per thread composed of a reserved area subdivided into 3-sized page buffers, where each page is a container of same-sized objects.
Each page manages its own internal free list and the free list is build when a page is created so there is no initial bump pointer.
Empty pages are coalesced for reuse.
Uses a fast freelist search for small allocation sizes.
Onwership is handled with a separate remote free-list, and remote frees are batched before pushing to the owner heap.
Version mimalloc-v2.1.2, built with the default configuration, using commands @cmake . ; make@.

\item[tbbmalloc~{\cite[pp.~314--315]{Kukanov07}}] is the allocator shipped with Intel's Threading Building Blocks (TBB).
tbbmalloc has a heap per thread for small allocations, with large allocation handled using a single request.
There is a global heap to acquire and reuse space obtained from the OS;
its reserved space is divided into thread buffers (containers).
A thread heap is composed of linked containers, with binning used to manage the allocations/deallocations within the containers.
Small object space is not returned to the OS.
An allocation has to search its container list to find a partially filled one.
The search is mitigated by moving mostly-free containers to the start of the container list;
free containers are returned to the global heap.
Ownership is handled with a separate remote free-list.
Version @libtbbmalloc.so.2.11@, installed using @apt-get install libtbb-dev@.

\item[tcmalloc~\cite{tcmalloc}] is the allocator shipped with Google's perftools.\footnote{
Currently, there are two versions of tcmalloc: Google's perftools and one experimental version available on GitHub, which is not an officially supported Google product.
We selected the perftools version because it is the most likely choice for users as it installs directly onto multiple OSs.}
tcmalloc has per CPU heaps for small allocations, with large allocation handled with a single request.
CPU heaps require a rollback mechanism, @rseq@, to prevent the serially-reusable problem.
There is a global heap to acquire and reuse space obtained from the OS;
its reserved space is divided into multi-page spans (containers) of fixed sized objects.
A CPU heap uses binning to manage the allocations/deallocations within the containers.
Free containers are returned to the OS.
Version @libtcmalloc_minimal.so.4@, installed using @apt-get install google-perftools@.
\end{description}

Untested allocators:
\begin{description}[leftmargin=*,topsep=3pt,itemsep=2pt,parsep=0pt]
\item[ptmalloc3]
is 8 years old and already integrated into glibc.
\item[rpmalloc]
requires explicit insertion of initialization/finalization calls for handling concurrent kernel threads.
Having to augment programs, like SPEC CPU benchmarks, is deemed outside of normal programmer expectations.
% An allocator should just plugin and work.
\item[lock free] allocators guarantee allocation progress whether threads are delayed or killed using an atomic instruction, often CAS.
The original lock-free allocator~\cite{Michael04} is completely lock-free.
As stated, atomic instructions on the fast path result in a significant performance penalty.
Hence, new allocators are not completely lock free, switching to a combination of synchronization-free, \ie 1:1 allocator model, on the fast path and lock-free on the slow path(s) to manipulate shared data structures~\cite{rpmalloc}.
These allocators are better labelled as \newterm{hybrid locking} rather than lock free, as the lock-free aspect is not contributing to performance.

% We observe that none of the pre-built standard malloc replacement libraries for ubuntu \url{https://launchpad.net/ubuntu/+search?text=malloc} are completely lock-free.
% 1:1 allocators can avoid synchronization (locks, or lock-free techniques with atomic instructions as well as cache coherence overheads) in their critical fast paths, but care must be taken to ensure the the amount of free memory captured in thread-local structures is bounded.

% Another approach to synchronization for allocators is \newterm{Restartable Critical Sections} ~\cite {https://dl.acm.org/doi/10.1145/512429.512451, https://dl.acm.org/doi/pdf/10.5555/1698184, https://doi.org/10.1145/1064979.1064985}, which are available in linux as the \newterm{RSEQ} facility ~\cite{https://www.gnu.org/software/libc/manual/html_node/Restartable-Sequences.html}.
% Restartable Critical Sections  provide obstruction-free progress by means of specially crafted transactions that will be rolled back if they happen to be interrupted by the kernel.
% Restartable Critical Sections transactions can only operate on CPU-specific data, however, which forces a T:C allocator configuration.
% Google's experimental tcmalloc \url{https://google.github.io/tcmalloc/rseq.html} uses RSEQ.  
% SuperMalloc \url{ACM DL is dead at the moment, but it's in ISMM 2015} attempts to use hardware transactional memory for lock elision, but falls back to classic locking if the hardware facility is not present or when a given transactional attempt encounters repeated progress failures.  


\end{description}

Allocator size is an indirect indicator of complexity.
Lines-of-code are computed with command @cloc *.{h,c,cc,cpp}@, except for hoard:
@cloc --exclude-lang="Bourne Shell",SKILL,Markdown,Bazel  Heap-Layers source include@.
\begin{center}
\setlength{\tabcolsep}{13pt}
\begin{tabular}{@{}rrrrrrrr@{}}
llheap & glibc & hoard & jemalloc & mimalloc & tbbmalloc & tcmalloc \\
1,450 & 3,807 & 11,932 & 24,512 & 6,887 & 6,256 & 33,963 \\
\end{tabular}
\end{center}


\section{Benchmarks}
\label{s:Benchmarks}

There are two basic approaches for evaluating computer software: benchmarks and micro-benchmarks.
\begin{description}[leftmargin=*,topsep=3pt,itemsep=2pt,parsep=0pt]
\item[Benchmarks]
are a suite of application programs (SPEC CPU/WEB) that are exercised in a common way (inputs) to find differences among underlying software implementations associated with an application (compiler, memory allocator, web server, \etc).
The applications are supposed to represent common execution patterns that need to perform well with respect to an underlying software implementation.
Benchmarks are often criticized for having overlapping patterns, insufficient patterns, or extraneous code that masks patterns, resulting in little or no information about why an application did or did perform well for the tested software.
\item[Micro-Benchmarks]
attempt to extract the common execution patterns associated with an application and run the pattern independently.
This approach removes any masking from extraneous application code, allows execution pattern to be very precise, and provides an opportunity for the execution pattern to have multiple independent tuning adjustments (knobs).
Micro-benchmarks are often criticized for inadequately representing real-world applications, but that is not their purpose.
\end{description}

While some crucial software components have standard benchmarks, no standard benchmark exists for testing and comparing memory allocators.
In the past, an assortment of applications have been used for benchmarking allocators~\cite{Detlefs93,Berger00,Berger01,berger02reconsidering}: P2C, GS, Espresso/Espresso-2, CFRAC/CFRAC-2, GMake, GCC, Perl/Perl-2, Gawk/Gawk-2, XPDF/XPDF-2, ROBOOP, Lindsay.
As well, an assortment of micro-benchmark have been used for benchmarking allocators~\cite{larson99memory,Berger00,streamflow}: threadtest, shbench, Larson, consume, false sharing.
Many of these benchmark applications and micro-benchmarks are old and do not reflect current application allocation patterns.

Except for the SPEC CPU benchmark, the other performance benchmarks used for testing are micro-benchmarks created for this paper.
All the benchmarks are used solely to extract differences among memory allocators.
The term benchmark in the following discussion means benchmark or micro-benchmark.


\subsection{SPEC CPU 2017}

SPEC CPU 2017 is an industry-standardized suite for measuring and comparing performance of compute-intensive programs.
It contains integer and floating-point tests written in C, \CC, and Fortran, covering throughput and speed, where each test contains multiple benchmarks~\cite{SPECCPU2017}.
All the benchmarks perform dynamic allocation, from light to heavy.
However, the dynamic allocation is relatively small in comparison to the benchmark computation.
Therefore, differences among allocators should be small, unless a particular access pattern triggers a pathological case.
The reason for performing SPEC CPU across the allocators is to prove this hypothesis.
For allocator comparisons, we consider SPEC CPU differences of 5\% as equal and undetectable in general workloads and computing environments.
For compiler comparisons, small differences of 1\% or 2\% are considered significant.

Table~\ref{t:SPEC-CPU-benchmark} shows the elapsed time (inverted throughput) of the SPEC CPU tests condensed to the geomean across the benchmarks for each of the four SPEC tests, intrate, intspeed, fprate, and fpspeed, covering integer and floating-point operations.
The tests are configured with size = ref, intrate/fprate: copies = 1, intspeed: threads = 1, fpspeed: threads = 16;
only fpspeed is concurrent using OpenMP.
Rigorous testing of SPEC CPU often runs many benchmark copies in parallel to completely load all computer cores.
However, these tests quickly run into architectural bottlenecks having little to do with an allocator's behaviour.
Runnning a single program bound to one core means the focus is strictly on allocator differences rather than conjoining transient OS and hardware differences.
The throughputs are ranked with {\color{red}red} lowest time and {\color{blue}blue} highest, where lower is best.
Hoard failed in multiple experiments on the ARM architecture, marked with {\color{purple}*Err*}, making it impossible to report the successful tests.

The results show all allocators do well;
the average, median, and relative standard deviation (right column)\footnote{$rstd = \sigma / \mu \times 100$, where $\sigma =$ standard deviation and $\mu =$ average} proves our hypothesis that the performance difference, 0.6\% to 2.3\%, across allocators is small.
One implementation trend we observed is that two of the integer tests, @omnetpp@ and @xalancbmk@, had an execution pattern that exercised the cache.
For the three allocators using headers-per-allocation, glibc, llheap, and tbbmalloc, performance could be up to 40\% slower, between the best and worst allocator results.
The reason is that the headers consumed part of the cache line, resulting in more cache misses.
These two experiments, disproportionally increased the geomean for these allocators for both integral experiments on all architectures.
Hence, headers-per-allocation are disadvantaged for this specific execution pattern.
The floating-point tests show no trends among the allocators.
The goal for llheap in this experiment is to do well, which is established by it being close to the median result, meaning it is normally in the middle of the allocator results.

\begin{table}
\centering
\caption{SPEC CPU benchmark, 3 hardware architectures, geomean per test in seconds, lower is better}
\label{t:SPEC-CPU-benchmark}
%\setlength{\tabcolsep}{6pt}
\begin{tabular}{@{}p{15pt}@{\hspace{15pt}}r|*{7}{r}|*{3}{r}@{}}
                &       bench/alloc. & glibc & hoard & jemalloc & llheap & mimalloc & tbbmalloc & tcmalloc & avg & med & rstd \\
\cline{2-12}
                &       intrate & {\color{blue}314.4} & {\color{violet}*Err*} & 300.3 & 309.9 & 302.6 & 313 & {\color{red}298.7} & 306.5 & 309.9 & 2\% \\
ARM             &       intspeed & {\color{blue}439.1} & {\color{violet}*Err*} & 417.6 & 431.1 & 419.9 & 436.2 & {\color{red}415.5} & 426.6 & 431.1 & 2.2\% \\
                &       fprate & 347.6 & {\color{violet}*Err*} & {\color{red}333.9} & 352.2 & {\color{blue}356.6} & 345.9 & 344.5 & 346.8 & 347.6 & 2\% \\
                &       fpspeed & 248.4 & {\color{violet}*Err*} & 245.3 & 245.7 & {\color{blue}250.9} & 246.6 & {\color{red}243.8} & 246.8 & 246.6 & 0.93\%
\end{tabular}

\begin{comment}
\bigskip
\begin{tabular}{@{}p{15pt}@{\hspace{15pt}}r|*{7}{r}|*{3}{r}@{}}
                &       bench/alloc. & glibc & hoard & jemalloc & llheap & mimalloc & tbbmalloc & tcmalloc & avg & med & rstd \\
\cline{2-12}
                &       intrate & 251 & 242 & 239 & 249 & 240 & {\color{blue}251} & {\color{red}237} & 244 & 242 & 2.3\% \\
AMD             &       intspeed & 356 & 337 & 335 & 351 & 339 & {\color{blue}356} & {\color{red}333} & 344 & 339 & 2.7\% \\
                &       fprate & 256 & 261 & {\color{red}250} & 257 & {\color{blue}270} & 256 & 254 & 258 & 256 & 2.3\% \\
                &       fpspeed & 340 & {\color{blue}353} & {\color{red}326} & 338 & 348 & 341 & 328 & 339 & 340 & 2.7\%
\end{tabular}
\end{comment}

\bigskip
\begin{tabular}{@{}p{15pt}@{\hspace{15pt}}r|*{7}{r}|*{3}{r}@{}}
                &       bench/alloc. & glibc & hoard & jemalloc & llheap & mimalloc & tbbmalloc & tcmalloc & avg & med & rstd \\
\cline{2-12}
                &       intrate & 251.2 & {\color{red}241.1} & 251.9 & 249.3 & 251.6 & 251.5 & {\color{blue}252.3} & 249.9 & 251.5 & 1.5\% \\
AMD             &       intspeed & {\color{blue}356.1} & {\color{red}337.1} & 355.4 & 351.7 & 355.5 & 355.8 & 355.9 & 352.5 & 355.5 & 1.8\% \\
                &       fprate & {\color{red}253.9} & {\color{blue}259.9} & 254.4 & 255.8 & 254.5 & 254.4 & 254.7 & 255.4 & 254.5 & 0.75\% \\
                &       fpspeed & 329.9 & {\color{blue}339.6} & 330.6 & {\color{red}327.2} & 329.9 & 329.8 & 329.5 & 330.9 & 329.9 & 1.1\%
\end{tabular}

\bigskip
\begin{tabular}{@{}p{15pt}@{\hspace{15pt}}r|*{7}{r}|*{3}{r}@{}}
                &       bench./alloc. & glibc & hoard & jemalloc & llheap & mimalloc & tbbmalloc & tcmalloc & avg & med & rstd \\
\cline{2-12}
                &       intrate & 188.6 & 185.1 & 183.1 & 188.6 & 181.5 & {\color{blue}189.4} & {\color{red}181.2} & 185.4 & 185.1 & 1.8\% \\
Intel   &       intspeed & 271.6 & 264.6 & 263.5 & 270.2 & 261.2 & {\color{blue}272.1} & {\color{red}260.3} & 266.2 & 264.6 & 1.7\% \\
                &       fprate & 202.7 & {\color{red}201.8} & 204.4 & 205.1 & {\color{blue}205.3} & 204.7 & 203.7 & 204 & 204.4 & 0.59\% \\
                &       fpspeed & 237.3 & 235.3 & 234.5 & 235.6 & {\color{blue}244.5} & 236.1 & {\color{red}233.6} & 236.7 & 235.6 & 1.4\%
\end{tabular}
\end{table}


\subsection{Realloc Benchmark}

Some examination of @realloc@ is necessary to encourage its use.
Reallocation can be very efficient (both in space and time) when manipulating variable-sized objects, like strings, multi-precise numbers, or dynamic-sized arrays.
Both X11 (500+ calls) and glibc (300+ calls) use realloc for various purposes.
For example, in \CC:
\begin{C++}
string s = "abc"; // initial allocation and copy new value
s = "gh"; // change size and copy new value
s = "l" + s + "r"; // change size and copy new value
s = s.substr(0,2); // reduce size
\end{C++}
variable @s@ changes size and value multiple times, plus temporary strings are created implicitly, \eg multiple concatenations, all of which requires multiple allocations, copying, and deallocations.
@realloc@ can optimize some of these operations in two ways:
\begin{enumerate}[leftmargin=*]
\item
For decreasing size, Figure~\ref{f:ReallocOptDecreasing} shows a logical truncation of the existing object rather than creating a new object, \ie use a heuristic to decide whether to perform the 3-step procedure (allocate, copy, and free), or pretend the storage is decreased and return the old storage and value, performing zero work but increasing internal fragmentation.
For example, a request to decrease size from 96 to 75 bytes can be implemented two ways:
The 21 bytes of internal fragmentation at the end of the logical reallocation may be unavailable, directly available if the allocator supports @malloc_usable_size@, or indirectly available if put back on the allocator free list.
\item
For increasing size, Figure~\ref{f:ReallocOptIncreasing} takes advantage of the fact that many memory allocators quantize request sizes (binning), often returning slightly more storage than requested (internal fragmentation).
For example, an initial request for 75 bytes may return 96 bytes of storage, giving 21 bytes of internal fragmentation:
For increasing the size up to 21 bytes, realloc can take advantage of this unused space rather than performing the 3-step procedure, which can also result in unused storage.
\end{enumerate}

\begin{figure}
\centering
\subfloat[Decreasing]{\label{f:ReallocOptDecreasing}\input{decreasing}}
\hspace*{5pt}
\vrule
\hspace*{5pt}
\subfloat[Increasing]{\label{f:ReallocOptIncreasing}\raisebox{0.38\totalheight}{\input{increasing}}}
\caption{Realloc Optimizations}
\label{f:ReallocOptimizations}
\end{figure}

Figure~\ref{f:reallocShrinkBenchmark} shows a benchmark to determine if an allocator takes advantage of the first optimization.
The benchmark takes a fixed-size allocation and reduction it by 10\%--90\% in steps of 10\%, checking the storage addresses at each reduction step if the same or new storage is returned.
The fixed-sized allocation is varied between sizes 64--16K in powers of 2.
Hence, both small and large sized storage are reduced.
The following table shows the approximate percentage point where storage is retained on shrinkage, \eg the storage reduction must be greater than 50\% of the prior allocation before a new allocation is performed for the smaller size, data is copied, and prior storage released.
\begin{center}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}ccccccc@{}}
glibc   & hoard & jemalloc      & llheap        & mimalloc      & tbbmalloc & tcmalloc \\
90\%    & 50\%  & 20\%          & 50\%          & 50\%          & 90\%          & 50\%
\end{tabular}
\end{center}
The results show glibc and tbbmalloc do not perform this optimization, while the other allocators do with 50\% as the most popular crossover point.

Figure~\ref{f:reallocGrowBenchmark} shows a benchmark to determine if an allocator takes advantage of the second optimization.
This benchmark creates an array of fixed-sized elements increasing the array size by 1 from 1--10,000 elements.
Then the element size is varied from 32, 64, 128, 256 bytes.
To prevent allocators from doing a bump allocation across the entire benchmark, a small perturbation is introduced where storage is allocated, held, and then released at infrequent points across the experiment.
A companion experiment is a manual simulation of the @realloc@: @malloc@ new storage, copy old data, and free old storage.
Note, the @realloc@ simulation is performing an equivalent perturbation to the @realloc@ benchmark each time through the loop.
The experiment is repeated 10,000 times for @realloc@ and 100 times for the simulation to obtain similar timing ranges.
The performance difference between the @realloc@ and @realloc@-simulation experiments shows if @realloc@ is optimizing unused internal fragmentation at the end of its quantized bucket.

Figure~\ref{f:reallocGrowResults} shows the results for the @realloc@ and @realloc@ simulation benchmarks.
The difference between the benchmarks is two orders of magnitude, \ie all allocators are reusing some internal fragmentation to prevent a reallocation and copy as the array grows.
The large difference is the extra copying in the simulation case, which is expensive.
Within the @realloc@ benchmark, allocators glibc, hoard, jemalloc, and tbbmalloc have higher cost, while the remaining allocators have almost identical results.
Within the @realloc@ simulation benchmark, allocators glibc and tbbmalloc have higher cost, while the remaining allocators have almost identical results.
This benchmark confirms that @realloc@ can provide some level of performance benefit for dynamically growing data structures, \eg strings or arrays.
Therefore, encouraging its use is reasonable, if and only if, it is safe to do so.
Note, this encouragement is apt for container developers, where low-level storage management is performed internally for the benefit of application users.

\begin{figure}
\begin{C++}
for ( size_t p = 10; p <= 100; p += 10 ) {
        for ( size_t s = 64; s < 16 * 1024; s <<= 1 ) {
                bool reuse = false;
                void * prev = pass( malloc( s ) );
                void * curr = pass( realloc( prev, s * p / 100 ) );
                if ( prev == curr ) {  /*  print  */  }
                free( curr );
        }
}
\end{C++}
\vspace*{-10pt}
\caption{\lstinline{realloc} Shrink Benchmark}
\label{f:reallocShrinkBenchmark}

\vspace*{10pt}

%\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}ll@{}}
\multicolumn{1}{c}{\lstinline{realloc}} & \multicolumn{1}{c}{\lstinline{realloc} simulation} \\
\begin{C++}
struct S { size_t ca[DIM]; }; // varied 32, 64, 128, 256
enum { Ssize = sizeof( S ) };
for ( size_t t = 0; t < @10$'$000@; t += 1 ) {
        S * sa = nullptr, * perturb = nullptr;
        for ( size_t i = 0, s = Ssize; i < 10$'$000; i += 1, s += Ssize ) {
                sa = (S *)@realloc( sa, s );@

                sa[i].ca[0] = i;
                if ( i % 1024 == 0 ) perturb = (S *)realloc( perturb, s );
        }
        free( sa );
        free( perturb );
}
\end{C++}
&
\begin{C++}
struct S { size_t ca[DIM]; }; // varied 32, 64, 128, 256
enum { Ssize = sizeof( S ) };
for ( size_t t = 0; t < @100@; t += 1 ) {
        S * sa = nullptr, * so = (S *)malloc( Ssize );
        for ( size_t i = 0, s = Ssize; i < 10$'$000; i += 1, s += Ssize ) {
                sa = (S *)@malloc( s )@;                        // simulate realloc
                memcpy( sa, so, s - Ssize );    // so one smaller
                sa[i].ca[0] = i;
                free( so );
                so = sa;
        }
        free( sa );
}
\end{C++}
\end{tabular}
\caption{\lstinline{realloc} Grow Benchmark}
\label{f:reallocGrowBenchmark}

\vspace*{20pt}

\hspace*{-17pt}
\setlength{\tabcolsep}{-13pt}
\begin{tabular}{@{}l@{\hspace*{-5pt}{\vrule height 1.05in}\hspace*{-5pt}}l@{}}
\begin{tabular}{@{}lll@{}}
\input{prolog.realloc.tex} & \input{swift.realloc.tex} & \input{java.realloc.tex}
\\
\multicolumn{3}{@{}c@{}}{\lstinline{realloc}, 10,000 repetitions}
\end{tabular}
&
\setlength{\tabcolsep}{-10pt}
\begin{tabular}{@{}lll@{}}
\input{prolog.reallocsim.tex} & \input{swift.reallocsim.tex} & \input{java.reallocsim.tex}
\\
\multicolumn{3}{@{}c@{}}{\lstinline{realloc} simulation, 100 repetitions}
\end{tabular}
\end{tabular}

\caption{\lstinline{realloc} Grow Results, x-axis in bytes, lower is better}
\label{f:reallocGrowResults}
\end{figure}


\subsubsection{Cache Benchmark}
\label{s:CacheBenchmark}

The cache benchmarks attempt to look for false sharing (see Section~\ref{s:FalseSharing}).
Unfortunately, testing for allocator-induced false-sharing is difficult, because it is equivalent to searching for randomly conjoined allocations within a large storage space.
Figure~\ref{f:CacheBenchmark} shows a benchmark for program induced false-sharing, where pointers are passed among threads.
As a side effect, this benchmark is indirectly checking which allocator model is being used.
The program main runs the benchmark with 4, 8, 16, and 32 threads, passing each thread a separate array of dynamically allocated storage from its common heap with @ASIZE@ elements.
Each thread then traverse the array adding a value to each element (read and write).
The traversal is repeated T times.
Each thread frees the array at the end.
The experiment is run with a small and medium sized array.
If there is any heap sharing, the small array has a higher probability for false sharing, \eg the first and last array elements for different array can be juxtaposed in memory, and hence appear in the same cache line.

\begin{figure}
\begin{C++}
enum { TIMES = 10$'$000$'$000$'$000, ASIZE = 3 }; $\C{// repetitions, array size 3 or 30}$
void * worker( void * arg ) {           $\C{// array passed from program main}$
        volatile size_t * arr = (size_t *)arg; $\C{// volatile prevents code elision}$
        for ( size_t  t = 0; t < TIMES / ASIZE; t += 1 ) $\C{// repeat experiment N times}$
                for ( size_t r = 0; r < ASIZE; r += 1 ) $\C{// iterate through array}$
                        arr[r] += r;                    $\C{// read/write array elements}$
        free( (void *)arr );                    $\C{// cast away volatile}$
}
\end{C++}
\vspace*{-5pt}
\caption{Cache False-Sharing Benchmark}
\label{f:CacheBenchmark}
\end{figure}

Figure~\ref{f:cacheResults} shows the results for the cache benchmark run with array sizes 3 and 30.
Allocators glibc, llheap, mimalloc, and tbbmalloc show little or no false-sharing issues at both 3 and 30 array sizes, \ie all generate virtually the same result.
Note, on the Intel, there is a rise at 32 cores, because of an L3 cache shift at 16 cores; stepping to 32 cores introduces NUMA effects.
This result correlates with these allocators using a 1:1 allocator model.
Allocators hoard, jemalloc, and tcmalloc show false-sharing issues at both 3 and 30 array sizes, reducing performance by 2 times at size 3.
The @perf@ performance analyzer shows a large number of cache misses for these allocators, indicating false sharing.
This result correlates with these allocators using some form of heap sharing.

\begin{figure}
\setlength{\tabcolsep}{-8pt}
\begin{tabular}{@{}l@{\hspace*{-5pt}{\vrule height 1.05in}\hspace*{-5pt}}l@{}}
\begin{tabular}{@{}lll@{}}
\input{prolog.cacheS.tex} & \input{swift.cacheS.tex} & \input{java.cacheS.tex}
\\
\multicolumn{3}{@{}c@{}}{3 Element Array}
\end{tabular}
&
\begin{tabular}{@{}lll@{}}
\input{prolog.cacheL.tex} & \input{swift.cacheL.tex} & \input{java.cacheL.tex}
\\
\multicolumn{3}{@{}c@{}}{30 Element Array}
\end{tabular}
\end{tabular}
\caption{Cache False-Sharing Results, x-axis in cores, lower is better}
\label{f:cacheResults}
\end{figure}


\subsection{Ownership Benchmark}

% In multi-threaded allocators with H:T or 1:1 structure, one thread can allocation storage, send it to another thread, and the receiving thread deallocates it.
% This raises the question of where the storage is returned: the heap (area) from which it was allocated or a different heap;
% in some cases there is no choice, when storage is bound to its allocation area.
% If storage is returned to its allocation heap, there are concurrency issues if the allocation area is shared.
% If the storage is returned to another heap, there can still be concurrency issues, but the real problem is storage drain in the allocation heap and storage bloat in the deallocation heap, without a secondary mechanism to redistribute storage.
% This choice is the \newterm{ownership problem}.

Historically the Larson benchmark~\cite{larson99memory} is purported to test for ownership issues, but in actuality, the benchmark is a complex simulation of a server environment.
Multiple threads allocate and free a number of random-sized objects within a size range.
Each thread runs for a time period, and at termination, creates a child thread and passes its array of objects as an argument, which does not require synchronization.
The number of thread generations varies with thread speed.
% It calculates memory operations per second as an indicator of the memory allocator's performance.
Because the benchmark performs multiple kinds of tests, it is impossible to extracted just the remote-free rate.

Therefore, a new benchmark is created to measure the asynchronous transfer cost from the deallocating to the allocating thread (remote free).
However, the allocating thread must first asynchronously transferred the allocations to the deallocating thread.
This cost needs to be mitigated so it does not mask the remote-free measurement.
To accomplish this, a thread batches its allocations (lots of 100), and atomically exchanges this batch with a freeing thread, which then individually frees the batch components.
Hence, the cost of the asynchronous allocation transfer is much less than the individual cost of the remote free.

Figure~\ref{f:OwnershipBenchmark} shows the pseudo-code for the benchmark.
There is a global matrix of allocation addresses: one row for each thread and one column for each batch.
Each thread starts at a specific row and fills that row with two different sized allocations.
A thread then loops until it atomically exchanges its row pointer with another thread's row pointer.
The storage in the received batch is then remote freed, the batch row is reset with new allocations, and the process repeats for a timed duration.
As well, after each allocation, an integer is written into the storage, and that integer is read before the deallocation.

Figure~\ref{f:Ownership} (a)--(c) shows the throughput of the ownership benchmark.
The results are divided into three groups.
glibc and tbbmalloc are slowest because of many system calls to @futex@. % and @nano_sleep@.
Figure~\ref{f:Ownership}~(d) shows the system time climbing during scaling on the AMD;
the other architectures are similar.
llheap and mimalloc are next, as these allocators do not batch remote frees, so every free requires locking.
jemalloc, hoard, and tcmalloc are fastest, as these allocators batch remote frees, reducing locking.
For 1:1 allocators, eager remote return makes sense as the returned storage can be reused during the owning thread's lifetime.
For N:T allocators, lazy remote return using batching makes sense as heaps outlive threads so eventually returned storage can be used by any existing or new thread.
Batching is possible for 1:1 allocators, but results in complexity and external fragmentation, which is only warranted in certain cases.

\begin{figure}
\begin{cfa}
void * batches[MaxThread][MaxBatch];                            $\C{// thread global}$
struct Aligned { CALIGN void * * col; };
volatile Aligned allocations[MaxThread];

Aligned batch = { batches[id] };                                        $\C{// thread local}$
size_t cnt = 0, a = 0;
for ( ; ! stop; ) {                                                                     $\C{// loop for T second}$
        for ( ssize_t i = Batch - 1; i >= 0; i -= 1 ) { $\C{// allocations, oppose order from frees}$
                batch.col[i] = malloc( i & 1 ? 42 : 192 );      $\C{// two allocation sizes}$
                *(int *)batch.col[i] = 42;                                      $\C{// write storage}$
        }
        Aligned obatch = batch;
        while ( (batch.col = Fas( allocations[a].col, batch.col )) == obatch.col || batch.col == nullptr ) { // atomic exchange
                if ( stop ) goto fini;
                a = (a + 1) % Threads;                                          $\C{// try another batch}$
        }
        for ( size_t i = 0; i < Batch; i += 1 ) {               $\C{// deallocations}$
                if ( *(int *)batch.col[i] != 42 ) abort();      $\C{// read storage check}$
                free( batch.col[i] );                                           $\C{// remote free}$
        }
        cnt += Batch;                                                                   $\C{// sum allocations/frees}$
        a = (a + 1) % Threads;                                                  $\C{// try another batch}$
}  fini: ;
\end{cfa}
\caption{Ownership Benchmark Outline}
\label{f:OwnershipBenchmark}
\end{figure}

\begin{figure}
\hspace*{-14pt}
\setlength{\tabcolsep}{-13pt}
\begin{tabular}{@{}lll@{\hspace*{-6pt}{\vrule height 2.05in}\hspace*{-6pt}}l@{}}
\input{prolog.ownership.tex}
&
\input{swift.ownership.tex}
&
\input{java.ownership.tex}
&
\input{swift.ownershipres.tex}
\end{tabular}
\caption{Ownership Results, x-axis is cores, (a)--(c) higher is better, (d) lower is better}
\label{f:Ownership}
\end{figure}


\subsection{Delay Benchmark}

The delay benchmark is a torture test of abrupt allocation patterns looking for delays that increase latency.
A flat response across the tests means there are few or no allocator-induced pauses.
The test examines small and large requests, where small requests are handled by the heap (@sbrk@) and large requests are handled by the OS (@mmap@).
Putting large requests in the heap causes external fragmentation when freed, unless an allocator subdivided the space, leading to pauses.
The @mallopt@ function provides the option @M_MMAP_THRESHOLD@ to set the division point in bytes for requests that cannot be satisfied by an allocator's free list.
Each @sbrk@ test in this benchmark is repeated 5,000,000,000 times and each @mmap@ test is performed 1,000,000 times;
the different repetitions result from the high cost of the OS calls making the experiment run too long.
A \emph{long running} experiment, rather than short experiments with averaged results, is searching for blowup scenarios in time and/or space.
Finally, scaling is tested with 4, 8, 16, and 32 pinned threads, where the threads synchronize between tests using a @pthread@ barrier.
In all experiments, allocated storage has its first and last byte assigned a character to simulate usage.

The tests are performed in this order:
\begin{enumerate}[leftmargin=18pt,topsep=3pt,itemsep=2pt,parsep=0pt]
\item
@x = malloc( 0 ) / free( x )@:
handles the pathological case of an zero-sized allocation and free.
The POSIX standard allows two meanings for this case: return @NULL@ or a unique pointer, where both can be freed.
The fastest implementation is to return @NULL@, rather than create a fictitious allocation.
However, this overloads the @malloc@ return-value to mean error or a zero-sized allocation.
To comply with the POSIX standard, the check for running out of memory is:
\begin{uC++}
if ( malloc( 0 ) == NULL && errno == ENOMEM ) ... // no memory
\end{uC++}
Unfortunately, most programmers assume @NULL@ means an error, \eg two tests in the SPEC CPU benchmark fail if @NULL@ is returned for a zero-sized allocation.
Hence, returning @NULL@ for a zero-sized allocation is an impractical allocator option.

\item
@free( NULL )@: handles the pathological case of freeing a non-existent or zero-byte allocation.
Non-existent allocations occur as algorithm base-cases, such as an unused pointer set to @NULL@.
Having the allocator ignore this case eliminates checking for an erroneous @free@ call on a @NULL@ value.
This call should be fast.

\item
\label{expS}
@x = malloc( 42 ) / free( x )@:
handles a fixed-sized allocation and free.

\item
@x[0..100) = malloc( 42 ) / free( x[0..100) )@:
handles a group of fixed-sized allocations and group free.

\item
@x[0..1000) = malloc( 42 ) / free( x[0..1000) )@:
handles a larger group of fixed-sized allocations and group free.

\item
@x[0..100) = malloc( 42 ) / free( x(100..0] )@:
handles a group of fixed-sized allocations and group free in reverse order.

\item
\label{expE}
@x[0..1000) = malloc( 42 ) / free( x(1000..0] )@:
handles a larger group of fixed-sized allocations and group free in reverse order.

\item
@x = malloc( [0..100) ) / free( x )@:
handles a variable-sized allocation and free.

\item
@x[0..100) = malloc( [0..100) ) / free( x[0..100) )@:
handles a group of variable-sized allocations and group free.

\item
@x[0..1000) = malloc( [0..1000) ) / free( x[0..1000) )@:
handles a larger group of variable-sized allocations and group free.

\item
@x[0..100) = malloc( [0..100) ) / free( x(100..0] )@:
handles a group of variable-sized allocations and group free in reverse order.

\item
@x[0..1000) = malloc( [0..1000) ) / free( x(1000..0] )@:
handles a larger group of variable-sized allocations and group free in reverse order.
\end{enumerate}
Experiments \ref{expS}--\ref{expE} are repeated with a fixed-sized allocation of 1,048,576, where @M_MMAP_THRESHOLD@ is set to 524,288 to force the use of @mmap@, resulting in 17 experiments.
Because the @mmap@ experiments test the operating-system memory-management not the allocators, the variable-sized @mmap@ experiments are deemed unnecessary.
A test with random-sized @sbrk@ allocations @malloc( [0..N) random )@ was performed, but the results are the same as fixed sized as all the allocation sizes are quickly accessed over the large number of experiment repetitions.
That is, once the buckets or superblocks for the allocation sizes are created, access order is irrelevant.

Figures~\ref{f:LatencyExpARM}--\ref{f:LatencyExpIntel} show the results of the @sbrk@ and @mmap@ experiments across the seven allocators with parallel scaling.
The average of the N threads is graphed for each experiment and the standard deviation is the error bar.
For the @sbrk@ graphs, a good allocator result should be low (smaller is better), flat across scaling (cores), with no error bars (STD $\approx$ 0) indicating no jitter (pauses) among the threads.
The result patterns across the three hardware architectures are similar, with differences correlating to CPU speed and cache differences.

The key observation across the @sbrk@ graphs is that llheap and mimalloc are always at the bottom (lower is better) and flat with respect to scaling.
The only exception is on the Intel, where all allocators experienced similar non-flat behaviour, because of the L3 cache shift at 16 cores.
Some anomalies are tcmalloc and hoard experiencing large jitter (see error bars) and scaling issues in some experiments, which is correlated with poorer results;
jemalloc has significant scaling issues for experiments 5, 7, 10, and 12, resulting from large numbers of @futex@ calls, possibly related to @madvise@ for returning storage to the OS;
and glibc and tbbmalloc are often slower than the other allocators (symbols are on top of each other).

The key observation across the @mmap@ graphs is that only three allocators, glibc, llheap, and tbbmalloc honoured the @mmap@ threshold request (symbols are on top of each other).
The other allocators made no @mmap@ calls, so their results are extremely low.
The exception is hoard, which did make @mmap@ calls that were uncorrelated with @M_MMAP_THRESHOLD@, and had significant jitter due to a large number of @futex@ calls.
For the allocators using @mmap@, there should be some scaling effect as more threads make more system calls.

\begin{figure}
\input{prolog.tex}
\vspace*{-20pt}
\caption{Delay Results, ARM, x-axis is cores, lower is better}
\label{f:LatencyExpARM}
\end{figure}

\begin{figure}
\input{swift.tex}
\vspace*{-20pt}
\caption{Delay Results, AMD, x-axis is cores, lower is better}
\label{f:LatencyExpAMD}
\end{figure}

\begin{figure}
\input{java.tex}
\vspace*{-20pt}
\caption{Delay Results, Intel, x-axis is cores, lower is better}
\label{f:LatencyExpIntel}
\end{figure}

Figures~\ref{f:LatencyResARM}--\ref{f:LatencyResIntel} show a time/space perspective across the entire experiment.
The user, system, and real times along with the maximum memory usage are presented for the @sbrk@ and @mmap@ experiments.
The result patterns across the three hardware architectures are similar.
If an allocator disappears in a graph, its result is less than 1 on a logarithmic scale.
Surprisingly, there are large (2 orders of magnitude) time differences among the allocators.

\begin{figure}
\hspace*{15pt}
\input{prolog2.tex}
\vspace*{-20pt}
\caption{Delay Results, ARM, x-axis is cores, lower is better}
\label{f:LatencyResARM}

\hspace*{15pt}
\input{swift2.tex}
\vspace*{-20pt}
\caption{Delay Results, AMD, x-axis is cores, lower is better}
\label{f:LatencyResAMD}

\hspace*{15pt}
\input{java2.tex}
\vspace*{-20pt}
\caption{Delay Results, Intel, x-axis is cores, lower is better}
\label{f:LatencyResIntel}
\end{figure}

For @sbrk@ graphs, the user time should be high and scale with cores, the system time very low, the real time constant, and the maximum memory scales with cores.
For user time, llheap and mimalloc, are at the bottom (lower is better) and all allocators have linear scaling as cores increase.
The remaining allocators are slower by one to two orders of magnitude, which correlates with high results in the experiments.
For system time jemalloc has non-trivial system time that scales with cores, caused by a large number of @futex@ calls.
The remaining allocators have virtually zero system time (not on graph).
The exception is a random anomaly where allocators had small amounts of system time, which appeared/disappeared on different experiment runs as if something slightly perturbs the experiment (OS?) over its 20 hour run.
For real time, llheap and mimalloc, take the least overall time and all allocators except jemalloc have flat performance.
For maximum memory, all allocators scale with cores, and there is a rough inverse correlation between user time and memory usage, \ie time \vs speed tradeoff.

For @mmap@ graphs, only used by glibc, llheap, and tbbmalloc, the user time should be low and scale with cores, the system time should be high and scale with cores, the real time constant, and the maximum memory scales with cores.
For user time, glibc, llheap, and tbbmalloc, are at the bottom because there are no @sbrk@ requests.
The remaining allocators all use a non-trivial amount of time handling the large requests, except mimalloc, which handles the large request identically to a small request.
Interestingly, the amount of time varies by one to two orders of magnitude.
For system time, glibc, llheap, and tbbmalloc, are at the top because of the OS calls to @mmap@.
Interestingly, the remaining allocators still use orders of magnitude of system time, except mimalloc ($<$ 1 so invisible).
For real time, all allocators scale linearly with cores, except mimalloc, which is flat.
For maximum memory, all allocators scale with cores, and there is a rough inverse correlation between user time and memory usage, \ie time \vs speed tradeoff.


\subsection{Out of Memory Benchmark}

Figure~\ref{f:OutMemoryBenchmark} show a \CC program with unbounded memory allocation.
The program is run in a shell with restricted data size.
Hence, it quickly runs out of memory, causing @malloc@, which is called by \CC @new@, to return a @nullptr@ with @errno@ set to @ENOMEM@.
Routine @new@ sees the @nullptr@ and calls the handler routine set by @set_new_handler@, which prints a message, and resets the default handler to raise the @bad_alloc@ exception caught in the program main.
Note, to raise an exception requires dynamic allocation, but \CC preallocates a few special exception, like @bad_alloc@, for special cases.

All allocators printed the correct output except hoard, mimalloc, and tcmalloc.
Hoard prints @MAP_FAILED@ and hangs spinning on a spinlock in a complex call chain.
mimalloc aborts the program because it incorrectly attempts to raise the @bad_alloc@ exception itself if and only it is compiled with \CC, whereas it is compiled with C.
The correct design is to return a @nullptr@ with @errno@ set to @ENOMEM@ to \CC @new@, which then raises the exception;
hence, the allocator can be compiled with C or \CC.
tcmalloc prints the correct output but adds ``allocation failed'' messages.

\begin{figure}
\begin{tabular}{@{\hspace*{\parindentlnth}}l@{\hspace*{2\parindentlnth}}l@{}@{}}
\begin{cfa}
static void handler() {
        cout << "Memory allocation failed\n";
        set_new_handler( nullptr );
}


\end{cfa}
&
\begin{cfa}
int main() {
        set_new_handler( handler );
        try {
                for ( ;; ) pass( new char[50] );        // unbounded allocation
        } catch( const bad_alloc & e ) { cout << e.what() << endl; }
}
\end{cfa}
\end{tabular}
\caption{Out of Memory Benchmark}
\label{f:OutMemoryBenchmark}
\end{figure}


\section{Conclusion}

The goal of this work is to build a full-featured, low-latency (or high bandwidth) memory allocator for both KT and UT multi-threading systems that is competitive with the best current memory allocators while extending the feature set of existing and new allocator routines.
The new llheap allocator achieves all of these goals, while maintaining and managing sticky allocation information \emph{without a performance loss}.
Hence, it is possible to use @realloc@ frequently as a safe operation, rather than just occasionally or not at all.
Furthermore, the ability to query sticky properties and other information allows programmers to write safer programs, as it is possible to dynamically match allocation styles from unknown library routines that return allocations.

Extending the C allocation API with @resize@, advanced @realloc@, @aalloc@, @amemalign@, @cmemalign@ and other alignment variations means programmers do not have to generate these allocation operations themselves.
The ability of the type systems in modern languages, \eg \CFA, to condense the allocation API to one routine with completely orthogonal allocation properties shows how far the allocation API can be advanced.
The result is increased safety and a cognitive reduction in performing dynamic allocation.
All of these extensions should eliminate common reasons for C programmers to roll their own memory allocator and/or allocation function, which is a huge safety advantage.

The ability to compile llheap with static/dynamic linking and optional statistics/debugging provides programmers with multiple mechanisms to balance performance and safety.
These allocator versions are easy to use because they can be linked to an application without recompilation.
Providing comprehensive statistics for all allocation operations is invaluable in understanding and debugging a program's dynamic behaviour.
No other memory allocator provides such comprehensive statistics gathering.
This capability was used extensively during the development of llheap to verify its behaviour, and to verify the benchmarks developed for the paper.
As well, the debugging mode, where allocations are checked along with internal pre/post-conditions and invariants, is extremely useful especially for students ($\approx$1,000 students have tested the \uC version of llheap).
While not as powerful as the @valgrind@ interpreter, lheap's debugging mode can detect a large number of allocation mistakes.
The contention-free statistics gathering and debugging have a low enough cost to be used in production code.
Finally, no other memory allocator addresses the needs of user-level threading, which are now available in many modern languages.

Creating a benchmark test-suite for comparing allocators, rather than relying on a suite of arbitrary programs, has been an interesting challenge.
The purpose of these performance tests is not to pick winners and losers among the allocators, because each allocator optimizes a particular set of allocation patterns: there is no optimal memory-allocator.
The goal is to demonstrate that llheap's performance, both in time and space, across some interesting allocation patterns, is comparable to the best allocators in use today.
Admittedly, there are pathological cases where llheap might use significant amounts of memory because it never coalesces or returns storage to the OS.
These pathological cases do not correlate to long running applications, where llheap can perform very well.
In the small set of tested benchmarks, no heap blowup was observed, while some tests caused time blowups in other allocators.
Therefore, llheap is a viable drop-in replacement for many applications and its ancillary features make it safer and more informative.


\subsection{Recommendations}

Substantial work has been put into building a new allocator and benchmarks, plus doing comprehensive performance tests among allocators.
Based on this work, we make two recommendations:
\begin{enumerate}[leftmargin=*, topsep=0pt,itemsep=0pt,parsep=0pt]
\item
Hoard is no longer maintained and did not do well (even broke) in some performance experiments.
We recommend to those doing memory allocation research not to use it.
\item
glibc did not perform as well as other allocators.
Given it is the default memory allocator for many academic and industry applications, this seems unfortunate and skews performance resulting so developers may draw incorrect conclusions.
As such, we recommend the adoption of a newer memory allocator for glibc.
We offer llheap for the reasons given above, but most importantly, its small code base.
glibc maintainers come and go.
Therefore, it is crucial for a new maintainer to on-board quickly and have a thorough understanding of the code base within a month.
The llheap code base is small and can be learned quickly because of its simple design, making it an ideal choice as a substitute allocator.
\end{enumerate}


\section{Acknowledgements}

This research is funded by the NSERC/Waterloo-Huawei (\url{http://www.huawei.com}) Joint Innovation Lab. %, and Peter Buhr is partially funded by the Natural Sciences and Engineering Research Council of Canada.
% Special thanks to Trevor Brown for many helpful discussions.

\bibliographystyle{ACM-Reference-Format}
\bibliography{pl,local}

\end{document}
\endinput

% Local Variables: %
% tab-width: 4 %
% fill-column: 120 %
% compile-command: "make" %
% End: %