Changeset fa59c40

Timestamp:

Jan 18, 2025, 3:32:44 PM (8 months ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

master

Children:

8e90fd6

Parents:

9ae4f5f

Message:

updates on llheap paper

File:

• doc/papers/llheap/Paper.tex (modified) (19 diffs)

doc/papers/llheap/Paper.tex

@@ -187 +187 @@
 \author[1]{Peter A. Buhr*}
 \author[2]{Bryan Chan}
+\author[3]{Dave Dice}
 \authormark{ZULFIQAR \textsc{et al.}}
 
 \address[1]{\orgdiv{Cheriton School of Computer Science}, \orgname{University of Waterloo}, \orgaddress{\state{Waterloo, ON}, \country{Canada}}}
 \address[2]{\orgdiv{Huawei Compiler Lab}, \orgname{Huawei}, \orgaddress{\state{Markham, ON}, \country{Canada}}}
+\address[3]{\orgdiv{Oracle Labs}, \orgname{Oracle}, \orgaddress{\state{Burlington, MA}, \country{USA}}}
+
 
 \corres{*Peter A. Buhr, Cheriton School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, ON N2L 3G1, Canada. \email{pabuhr{\char`\@}uwaterloo.ca}}
@@ -201 +204 @@
 llheap extends the feature set of existing C allocation by remembering zero-filled (\lstinline{calloc}) and aligned properties (\lstinline{memalign}) in an allocation.
 These properties can be queried, allowing programmers to write safer programs by preserving these properties in future allocations.
-As well, \lstinline{realloc} preserves these properties when adjusting storage size, again increasing future allocation safety.
+As well, \lstinline{realloc}/\lstinline{reallocarray} preserve these properties when adjusting storage size, again increasing future allocation safety.
 llheap also extends the C allocation API with \lstinline{aalloc}, \lstinline{amemalign}, \lstinline{cmemalign}, \lstinline{resize}, and extended \lstinline{realloc}, providing orthogonal access to allocation features;
 hence, programmers do have to code missing combinations.
@@ -226 +229 @@
 \section{Introduction}
 
-Memory management services a series of program allocation/deallocation requests and attempts to satisfy them from a variable-sized block of memory, while minimizing total memory usage.
-A general-purpose dynamic-allocation algorithm cannot anticipate allocation requests so its time and space performance is rarely optimal.
-However, allocators take advantage of regular allocation patterns in typical programs to produce excellent results, both in time and space (similar to LRU paging).
-Allocators use a number of similar techniques, but each optimizes specific allocation patterns.
-Nevertheless, allocators are a series of compromises, occasionally with some static or dynamic tuning parameters to optimize specific program-request patterns.
+Memory management services a series of program allocation/deallocation requests and attempts to satisfy them from a variable-sized block(s) of memory, while minimizing total memory usage.
+A general-purpose dynamic-allocation algorithm cannot anticipate allocation requests so its time and space performance is rarely optimal (bin packing).
+However, allocators take advantage of allocation patterns in typical programs (heuristics) to produce excellent results, both in time and space (similar to LRU paging).
+Allocators use similar techniques, but each optimizes specific allocation patterns.
+Nevertheless, allocators are a series of compromises, occasionally with some static or dynamic tuning parameters to optimize specific request patterns.
 
 
@@ -283 +286 @@
 \begin{enumerate}[leftmargin=*,itemsep=0pt]
 \item
-Implementation of a new stand-alone concurrent low-latency memory-allocator ($\approx$1,200 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).
+Implementation of a new stand-alone concurrent low-latency memory-allocator ($\approx$1,400 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
@@ -289 +292 @@
 
 \item
-Use the preserved zero fill and alignment as \emph{sticky} properties for @realloc@ to zero-fill and align when storage is extended or copied.
+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 these allocations if the properties are not preserved when copying.
 This silent problem is unintuitive to programmers and difficult to locate because it is transient.
@@ -295 +298 @@
 \item
 Provide additional heap operations to make allocation properties orthogonally accessible.
-\begin{itemize}[topsep=2pt,itemsep=2pt,parsep=0pt]
-\item
-@aalloc( dim, elemSize )@ same as @calloc@ except memory is \emph{not} zero filled.
-\item
-@amemalign( alignment, dim, elemSize )@ same as @aalloc@ with memory alignment.
-\item
-@cmemalign( alignment, dim, elemSize )@ same as @calloc@ with memory alignment.
+\begin{itemize}[topsep=0pt,itemsep=0pt,parsep=0pt]
+\item
+@aalloc( dimension, elemSize )@ same as @calloc@ except memory is \emph{not} zero filled, which is significantly faster than @calloc@.
+\item
+@amemalign( alignment, dimension, elemSize )@ same as @aalloc@ with memory alignment.
+\item
+@cmemalign( alignment, dimension, elemSize )@ same as @calloc@ with memory alignment.
 \item
 @resize( oaddr, size )@ re-purpose an old allocation for a new type \emph{without} preserving fill or alignment.
 \item
-@resize( oaddr, alignment, size )@ re-purpose an old allocation with new alignment but \emph{without} preserving fill.
-\item
-@realloc( oaddr, alignment, size )@ same as @realloc@ but adding or changing alignment.
+@aligned_resize( oaddr, alignment, size )@ re-purpose an old allocation with new alignment but \emph{without} preserving fill.
+\item
+@aligned_realloc( oaddr, alignment, size )@ same as @realloc@ but adding or changing alignment.
+\item
+@aligned_reallocarray( oaddr, alignment, dimension, elemSize )@ same as @reallocarray@ but adding or changing alignment.
 \end{itemize}
 
 \item
 Provide additional query operations to access information about an allocation:
-\begin{itemize}[topsep=3pt,itemsep=2pt,parsep=0pt]
+\begin{itemize}[topsep=0pt,itemsep=0pt,parsep=0pt]
 \item
 @malloc_alignment( addr )@ returns the alignment of the allocation.
 If the allocation is not aligned or @addr@ is @NULL@, the minimal alignment is returned.
 \item
-@malloc_zero_fill( addr )@ returns a boolean result indicating if the memory is allocated with zero fill, e.g., by @calloc@/@cmemalign@.
+@malloc_zero_fill( addr )@ returns a boolean result indicating if the memory is allocated with zero fill, \eg by @calloc@/@cmemalign@.
 \item
 @malloc_size( addr )@ returns the size of the memory allocation.
 \item
-@malloc_usable_size( addr )@ returns the usable (total) size of the memory, i.e., the bin size containing the allocation, where @malloc_size( addr )@ $\le$ @malloc_usable_size( addr )@.
+@malloc_usable_size( addr )@ returns the usable (total) size of the memory, \ie the bin size containing the allocation, where @malloc_size( addr )@ $\le$ @malloc_usable_size( addr )@.
 \end{itemize}
 
 \item
 Provide optional extensive, fast, and contention-free allocation statistics to understand allocation behaviour, accessed by:
-\begin{itemize}[topsep=3pt,itemsep=2pt,parsep=0pt]
+\begin{itemize}[topsep=0pt,itemsep=0pt,parsep=0pt]
 \item
 @malloc_stats()@ print memory-allocation statistics on the file-descriptor set by @malloc_stats_fd@ (default @stderr@).
@@ -359 +364 @@
 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 to aid the packing process, 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 via operating-system calls, such as @mmap@ or @sbrk@ in UNIX.
+The allocator grows or shrinks the dynamic-allocation zone to obtain storage for objects and reduce memory usage via OS calls, such as @mmap@ or @sbrk@ in UNIX.
 
 
@@ -984 +989 @@
 That is, rather than requesting new storage for a single object, an entire buffer is requested from which multiple objects are allocated later.
 Any heap may use an allocation buffer, resulting in allocation from the buffer before requesting objects (containers) from the global heap or OS, respectively.
-The allocation buffer reduces contention and the number of global/operating-system calls.
+The allocation buffer reduces contention and the number of global/OS calls.
 For coalescing, a buffer is split into smaller objects by allocations, and recomposed into larger buffer areas during deallocations.
 
@@ -1021 +1026 @@
 
 
-\section{Allocator}
-\label{c:Allocator}
-
-This section presents a new stand-alone concurrent low-latency memory-allocator ($\approx$1,200 lines of code), called llheap (low-latency heap), for C/\CC programs using kernel threads (1:1 threading), and specialized versions of the allocator for the programming languages \uC and \CFA using user-level threads running over multiple kernel threads (M:N threading).
-The new allocator fulfills the GNU C Library allocator API~\cite{GNUallocAPI}.
-
-
-\subsection{llheap}
-
-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 have a delay during an allocator call.
+\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 kernel threads (1:1 threading), with specialized versions for the programming languages \uC and \CFA using user-level threads running over multiple kernel threads (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, 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 computers have huge amounts of RAM memory.
+This objective is apropos because systems research and industrial applications are striving for low latency and modern computers have huge amounts of RAM memory.
 Finally, llheap's performance should be comparable with the current best allocators, both in space and time (see performance comparison in Section~\ref{c:Performance}).
 
-% The objective of llheap's new design was to fulfill following requirements:
-% \begin{itemize}
-% \item It should be concurrent and thread-safe for multi-threaded programs.
-% \item It should avoid global locks, on resources shared across all threads, as much as possible.
-% \item It's performance (FIX ME: cite performance benchmarks) should be comparable to the commonly used allocators (FIX ME: cite common allocators).
-% \item It should be a lightweight memory allocator.
-% \end{itemize}
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 \subsection{Design Choices}
 
-% Some of the rejected designs are discussed because they show the path to the final design (see discussion in Section~\ref{s:MultipleHeaps}).
-% Note, a few simple tests for a design choice were compared with the current best allocators to determine the viability of a design.
-
-
-% \paragraph{T:1 model}
-% Figure~\ref{f:T1SharedBuckets} shows one heap accessed by multiple kernel threads (KTs) using a bucket array, where smaller bucket sizes are shared among N KTs.
-% This design leverages the fact that usually the allocation requests are less than 1024 bytes and there are only a few different request sizes.
-% When KTs $\le$ N, the common bucket sizes are uncontented;
-% when KTs $>$ N, the free buckets are contented and latency increases significantly.
-% In all cases, a KT must acquire/release a lock, contented or uncontented, along the fast allocation path because a bucket is shared.
-% Therefore, while threads are contending for a small number of buckets sizes, the buckets are distributed among them to reduce contention, which lowers latency;
-% however, picking N is workload specific.
-% 
-% \begin{figure}
-% \centering
-% \input{AllocDS1}
-% \caption{T:1 with Shared Buckets}
-% \label{f:T1SharedBuckets}
-% \end{figure}
-% 
-% Problems:
-% \begin{itemize}
-% \item
-% Need to know when a KT is created/destroyed to assign/unassign a shared bucket-number from the memory allocator.
-% \item
-% When no thread is assigned a bucket number, its free storage is unavailable.
-% \item
-% All KTs contend for the global-pool lock for initial allocations, before free-lists get populated.
-% \end{itemize}
-% Tests showed having locks along the allocation fast-path produced a significant increase in allocation costs and any contention among KTs produces a significant spike in latency.
-
-% \paragraph{T:H model}
-% Figure~\ref{f:THSharedHeaps} shows a fixed number of heaps (N), each a local free pool, where the heaps are sharded (distributed) across the KTs.
-% A KT can point directly to its assigned heap or indirectly through the corresponding heap bucket.
-% When KT $\le$ N, the heaps might be uncontented;
-% when KTs $>$ N, the heaps are contented.
-% In all cases, a KT must acquire/release a lock, contented or uncontented along the fast allocation path because a heap is shared.
-% By increasing N, this approach reduces contention but increases storage (time versus space);
-% however, picking N is workload specific.
-% 
-% \begin{figure}
-% \centering
-% \input{AllocDS2}
-% \caption{T:H with Shared Heaps}
-% \label{f:THSharedHeaps}
-% \end{figure}
-% 
-% Problems:
-% \begin{itemize}
-% \item
-% Need to know when a KT is created/destroyed to assign/unassign a heap from the memory allocator.
-% \item
-% When no thread is assigned to a heap, its free storage is unavailable.
-% \item
-% Ownership issues arise (see Section~\ref{s:Ownership}).
-% \item
-% All KTs contend for the local/global-pool lock for initial allocations, before free-lists get populated.
-% \end{itemize}
-% Tests showed having locks along the allocation fast-path produced a significant increase in allocation costs and any contention among KTs produces a significant spike in latency.
-
-% \paragraph{T:H model, H = number of CPUs}
-% This design is the T:H model but H is set to the number of CPUs on the computer or the number restricted to an application, \eg via @taskset@.
-% (See Figure~\ref{f:THSharedHeaps} but with a heap bucket per CPU.)
-% Hence, each CPU logically has its own private heap and local pool.
-% A memory operation is serviced from the heap associated with the CPU executing the operation.
-% This approach removes fastpath locking and contention, regardless of the number of KTs mapped across the CPUs, because only one KT is running on each CPU at a time (modulo operations on the global pool and ownership).
-% This approach is essentially an M:N approach where M is the number if KTs and N is the number of CPUs.
-% 
-% Problems:
-% \begin{itemize}
-% \item
-% Need to know when a CPU is added/removed from the @taskset@.
-% \item
-% Need a fast way to determine the CPU a KT is executing on to access the appropriate heap.
-% \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.
-% 
-% Library @librseq@~\cite{librseq} was used to perform a fast determination of the CPU and to ensure all memory operations complete on one CPU using @librseq@'s restartable sequences, which restart the critical subsection after undoing its writes, if the critical subsection is preempted.
-% \end{itemize}
-% Tests showed that @librseq@ can determine the particular CPU quickly but setting up the restartable critical-subsection along the allocation fast-path produced a significant increase in allocation costs.
-% Also, the number of undoable writes in @librseq@ is limited and restartable sequences cannot deal with user-level thread (UT) migration across KTs.
-% For example, UT$_1$ is executing a memory operation 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 calls a memory operation.
-% Since KT$_1$ is still executing on CPU$_1$, @librseq@ takes no action because it assumes KT$_1$ is still executing the same critical subsection.
-% Then UT$_1$ is scheduled onto KT$_2$ by the user-level scheduler, and its memory 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}
-% \item
-% Marked the current restartable critical-subsection as cancelled so it restarts when attempting to commit.
-% \item
-% Do nothing if there is no current restartable critical subsection 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.
-
-% \subsubsection{Allocation Fastpath}
-% \label{s:AllocationFastpath}
-
-llheap's design was reviewed and changed multiple times during its development, with the final choices are discussed here.
-(See~\cite{Zulfiqar22} for a discussion of alternate choices and reasons for rejecting them.)
-All designs were analyzed for the allocation/free \newterm{fastpath}, \ie when an allocation can immediately return free storage or returned storage is not coalesced.
-The heap model chosen is 1:1, which is the T:H model with T = H, where there is one thread-local heap for each KT.
+llheap's design was reviewed and changed multiple times during its development, with the final choices discussed here.
+All designs focused on the allocation/free \newterm{fastpath}, \ie the shortest code path for the most common operations, \eg when an allocation can immediately return free storage or returned storage is not coalesced.
+The model chosen is 1:1, so there is one thread-local heap for each KT.
 (See Figure~\ref{f:THSharedHeaps} but with a heap bucket per KT and no bucket or local-pool lock.)
 Hence, immediately after a KT starts, its heap is created and just before a KT terminates, its heap is (logically) deleted.
-Heaps are uncontended for a KTs memory operations as every KT has its own thread-local heap, modulo operations on the global pool and ownership.
+Therefore, heaps are uncontended for a KTs memory operations as every KT has its own thread-local heap, modulo operations on the global pool and ownership.
 
 Problems:
@@ -1205 +1089 @@
 For the T:1 and T:H models, locking must exist along the allocation fastpath because the buckets or heaps might be shared by multiple threads, even when KTs $\le$ N.
 For the T:H=CPU and 1:1 models, locking is eliminated along the allocation fastpath.
-However, T:H=CPU has poor operating-system support to determine the CPU id (heap id) and prevent the serially-reusable problem for KTs.
+However, T:H=CPU has poor OS support to determine the CPU id (heap id) and prevent the serially-reusable problem for KTs.
 More OS support is required to make this model viable, but there is still the serially-reusable problem with user-level threading.
-So the 1:1 model had no atomic actions along the fastpath and no special operating-system support requirements.
+So the 1:1 model had no atomic actions along the fastpath and no special OS support requirements.
 The 1:1 model still has the serially-reusable problem with user-level threading, which is addressed in Section~\ref{s:UserlevelThreadingSupport}, and the greatest potential for heap blowup for certain allocation patterns.
 
@@ -1241 +1125 @@
 A primary goal of llheap is low latency, hence the name low-latency heap (llheap).
 Two forms of latency are internal and external.
-Internal latency is the time to perform an allocation, while external latency is time to obtain/return storage from/to the OS.
+Internal latency is the time to perform an allocation, while external latency is time to obtain or return storage from or to the OS.
 Ideally latency is $O(1)$ with a small constant.
 
-To obtain $O(1)$ internal latency means no searching on the allocation fastpath and largely prohibits coalescing, which leads to external fragmentation.
-The mitigating factor is that most programs have well behaved allocation patterns, where the majority of allocation operations can be $O(1)$, and heap blowup does not occur without coalescing (although the allocation footprint may be slightly larger).
-
-To obtain $O(1)$ external latency means obtaining one large storage area from the OS and subdividing it across all program allocations, which requires a good guess at the program storage high-watermark and potential large external fragmentation.
-Excluding real-time operating-systems, operating-system operations are unbounded, and hence some external latency is unavoidable.
-The mitigating factor is that operating-system calls can often be reduced if a programmer has a sense of the storage high-watermark and the allocator is capable of using this information (see @malloc_expansion@ \pageref{p:malloc_expansion}).
-Furthermore, while operating-system calls are unbounded, many are now reasonably fast, so their latency is tolerable and infrequent.
+$O(1)$ internal latency means no open searching on the allocation fastpath, which largely prohibits coalescing.
+The mitigating factor is that most programs have a small, fixed, allocation pattern, where the majority of allocation operations can be $O(1)$ and heap blowup does not occur without coalescing (although the allocation footprint may be slightly larger).
+Modern computers have large memories so a slight increase in program footprint is not a problem.
+
+$O(1)$ external latency means obtaining one large storage area from the OS and subdividing it across all program allocations, which requires a good guess at the program storage high-watermark and potential large external fragmentation.
+Excluding real-time OSs, OS operations are unbounded, and hence some external latency is unavoidable.
+The mitigating factor is that OS calls can often be reduced if a programmer has a sense of the storage high-watermark and the allocator is capable of using this information (see @malloc_expansion@ \pageref{p:malloc_expansion}).
+Furthermore, while OS calls are unbounded, many are now reasonably fast, so their latency is tolerable because it occurs infrequently.
 
 
@@ -1392 +1277 @@
 \subsubsection{Alignment}
 
-Most dynamic memory allocations have a minimum storage alignment for the contained object(s).
-Often the minimum memory alignment, M, is the bus width (32 or 64-bit) or the largest register (double, long double) or largest atomic instruction (DCAS) or vector data (MMMX).
-In general, the minimum storage alignment is 8/16-byte boundary on 32/64-bit computers.
-For consistency, the object header is normally aligned at this same boundary.
-Larger alignments must be a power of 2, such as page alignment (4/8K).
-Any alignment request, N, $\le$ the minimum alignment is handled as a normal allocation with minimal alignment.
-
-For alignments greater than the minimum, the obvious approach for aligning to address @A@ is: compute the next address that is a multiple of @N@ after the current end of the heap, @E@, plus room for the header before @A@ and the size of the allocation after @A@, moving the end of the heap to @E'@.
-\begin{center}
-\input{Alignment1}
-\end{center}
-The storage between @E@ and @H@ is chained onto the appropriate free list for future allocations.
-The same approach is used for sufficiently large free blocks, where @E@ is the start of the free block, and any unused storage before @H@ or after the allocated object becomes free storage.
-In this approach, the aligned address @A@ is the same as the allocated storage address @P@, \ie @P@ $=$ @A@ for all allocation routines, which simplifies deallocation.
-However, if there are a large number of aligned requests, this approach leads to memory fragmentation from the small free areas around the aligned object.
-As well, it does not work for large allocations, where many memory allocators switch from program @sbrk@ to operating-system @mmap@.
-The reason is that @mmap@ only starts on a page boundary, and it is difficult to reuse the storage before the alignment boundary for other requests.
-Finally, this approach is incompatible with allocator designs that funnel allocation requests through @malloc@ as it directly manipulates management information within the allocator to optimize the space/time of a request.
-
-Instead, llheap alignment is accomplished by making a \emph{pessimistic} allocation request for sufficient storage to ensure that \emph{both} the alignment and size request are satisfied, \eg:
+Allocators have a different minimum storage alignment from the hardware's basic types.
+Often the minimum allocator alignment, $M$, is the bus width (32 or 64-bit), the largest register (double, long double), largest atomic instruction (DCAS), or vector data (MMMX).
+The reason for this larger requirement is the lack of knowledge about the data type occupying the allocation.
+Hence, an allocator assumes the worst-case scenario for the start of data and the compiler correctly aligns items within this data because it knows their types.
+Often the minimum storage alignment is an 8/16-byte boundary on a 32/64-bit computer.
+Alignments larger than $M$ are normally a power of 2, such as page alignment (4/8K).
+Any alignment less than $M$ is raised to the minimal alignment.
+
+llheap aligns its header at the $M$ boundary and its size is $M$;
+hence, data following the header is aligned at $M$.
+This pattern means there is no minimal alignment computation along the allocation fastpath, \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, \eg:
 \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 because if @P@ already has the correct alignment @N@, the initial allocation has already requested sufficient space to move to the next multiple of @N@.
-For this special case, there is @alignment - M@ bytes of unused storage after the data object, which subsequently can be used by @realloc@.
-
-Note, the address returned is @A@, which is subsequently returned to @free@.
-However, to correctly free the allocated object, the value @P@ must be computable, since that is the value generated by @malloc@ and returned within @memalign@.
-Hence, there must be a mechanism to detect when @P@ $\neq$ @A@ and how to compute @P@ from @A@.
-
-The llheap approach uses two headers:
-the \emph{original} header associated with a memory allocation from @malloc@, and a \emph{fake} header within this storage before the alignment boundary @A@, which is returned from @memalign@, e.g.:
+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 to @free@.
+To correctly free the object, the value $P$ must be computable from $A$, since that is the actual start of the allocation, from which $H$ can be computed $P - M$.
+Hence, there must be a mechanism to detect when $P$ $\neq$ $A$ and then 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$, e.g.:
 \begin{center}
 \input{Alignment2Impl}
 \end{center}
-Since @malloc@ has a minimum alignment of @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 @malloc@.
+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 initialize alignment (discussed in Section~\ref{s:ReallocStickyProperties}).
 To distinguish a fake header from a normal header, the least-significant bit of the alignment is used because the offset participates in multiple calculations, while the alignment is just remembered data.
@@ -1443 +1318 @@
 \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, rather than performing the following steps manually.
+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 manually steps.
 \begin{flushleft}
 \begin{tabular}{ll}
@@ -1455 +1331 @@
 &
 \begin{lstlisting}
-T * naddr = (T *)malloc( newSize ); $\C[2.4in]{// new storage}$
+T * naddr = (T *)malloc( newSize ); $\C[2in]{// new storage}$
 memcpy( naddr, addr, oldSize );  $\C{// copy old bytes}$
 free( addr );                           $\C{// free old storage}$
@@ -1462 +1338 @@
 \end{tabular}
 \end{flushleft}
-The realloc pattern leverages available storage at the end of an allocation due to bucket sizes, possibly eliminating a new allocation and copying.
-This pattern is not used enough to reduce storage management costs.
-In fact, if @oaddr@ is @nullptr@, @realloc@ does a @malloc@, so even the initial @malloc@ can be a @realloc@ for consistency in the allocation pattern.
-
-The hidden problem for this pattern is the effect of zero fill and alignment with respect to reallocation.
-Are these properties transient or persistent (``sticky'')?
-For example, when memory is initially allocated by @calloc@ or @memalign@ with zero fill or alignment properties, respectively, what happens when those allocations are given to @realloc@ to change size?
-That is, if @realloc@ logically extends storage into unused bucket space or allocates new storage to satisfy a size change, are initial allocation properties preserved?
-Currently, allocation properties are not preserved, so subsequent use of @realloc@ storage may cause inefficient execution or errors due to lack of zero fill or alignment.
-This silent problem is unintuitive to programmers and difficult to locate because it is transient.
-To prevent these problems, llheap preserves initial allocation properties for the lifetime of an allocation and the semantics of @realloc@ are augmented to preserve these properties, with additional query routines.
-This change makes the realloc pattern efficient and safe.
+The manual steps are suboptimal because there may be sufficient internal fragmentation at the end of the allocation due to bucket sizes.
+If this storage is large enough, 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.
+This pattern should be used more frequently to 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, we argue these properties should be persistent (``sticky'') and not transient.
+For example, when memory is initially allocated by @calloc@ or @memalign@ with zero fill or alignment properties, any subsequent reallocations of this storage must preserve these properties.
+Currently, allocation properties are not preserved nor is it possible to query an allocation to maintain these properties manually.
+Hence, subsequent use of @realloc@ storage that assumes any initially properties may cause errors.
+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.
 
 
 \subsubsection{Header}
 
-To preserve allocation properties requires storing additional information with an allocation,
-The best available option is the header, where Figure~\ref{f:llheapNormalHeader} shows the llheap storage layout.
-The header has two data field sized appropriately for 32/64-bit alignment requirements.
-The first field is a union of three values:
+To preserve allocation properties requires storing additional information about an allocation.
+Figure~\ref{f:llheapHeader} shows llheap captures this information in the 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}
 \item[bucket pointer]
-is for allocated storage and points back to the bucket associated with this storage requests (see Figure~\ref{f:llheapStructure} for the fields accessible in a bucket).
+is for deallocated of heap storage and points back to the bucket associated with this storage requests (see Figure~\ref{f:llheapStructure} for the fields accessible in a bucket).
 \item[mapped size]
-is for mapped storage and is the storage size for use in unmapping.
+is for deallocation of mapped storage and is the storage size for unmapping.
 \item[next free block]
-is for free storage and is an intrusive pointer chaining same-size free blocks onto a bucket's free stack.
+is for freed storage and is an intrusive pointer chaining same-size free blocks onto a bucket's stack of free objects.
 \end{description}
-The second field remembers the request size versus the allocation (bucket) size, \eg request 42 bytes which is rounded up to 64 bytes.
+The low-order 3-bits of this field are unused for any stored values as these values are at least 8-byte aligned.
+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 fastpath for allocation and free;
+otherwise, the bits are analysed and appropriate actions are taken for the complex cases.
+
+The right field remembers the request size versus the allocation (bucket) size, \eg request of 42 bytes is rounded up to 64 bytes.
 Since programmers think in request sizes rather than allocation sizes, the request size allows better generation of statistics or errors and also helps in memory management.
 
-\begin{figure}
-\centering
-\input{Header}
-\caption{llheap Normal Header}
-\label{f:llheapNormalHeader}
-\end{figure}
-
-The low-order 3-bits of the first field are \emph{unused} for any stored values as these values are 16-byte aligned by default, whereas the second field may use all of its bits.
-The 3 unused bits are used to represent mapped allocation, zero filled, and alignment, respectively.
-Note, the alignment bit is not used in the normal header and the zero-filled/mapped bits are not used 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;
-otherwise, the bits are analysed and appropriate actions are taken for the complex cases.
-Since most allocations are basic, they will take significantly less time as the memory operations will be done along the allocation and free fastpath.
-
 
 \subsection{Statistics and Debugging}
 
-llheap can be built to accumulate fast and largely contention-free allocation statistics to help understand allocation behaviour.
+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 fastpath.
 As noted, any atomic operation along the fastpath produces a significant increase in allocation costs.
@@ -1741 +1618 @@
 
 \medskip\noindent
-\lstinline{void * aalloc( size_t dim, size_t elemSize )}
+\lstinline{void * aalloc( size_t dimension, size_t elemSize )}
 extends @calloc@ for allocating a dynamic array of objects with total size @dim@ $\times$ @elemSize@ but \emph{without} zero-filling the memory.
 @aalloc@ is significantly faster than @calloc@, which is the only alternative given by the standard memory-allocation routines for array allocation.
@@ -1753 +1630 @@
 
 \medskip\noindent
-\lstinline{void * amemalign( size_t alignment, size_t dim, size_t elemSize )}
+\lstinline{void * amemalign( size_t alignment, size_t dimension, size_t elemSize )}
 extends @aalloc@ and @memalign@ for allocating a dynamic array of objects with the starting address on the @alignment@ boundary.
 Sets sticky alignment property.
@@ -1759 +1636 @@
 
 \medskip\noindent
-\lstinline{void * cmemalign( size_t alignment, size_t dim, size_t elemSize )}
+\lstinline{void * cmemalign( size_t alignment, size_t dimension, size_t elemSize )}
 extends @amemalign@ with zero fill and has the same usage as @amemalign@.
 Sets sticky zero-fill and alignment property.
@@ -1881 +1758 @@
 
 \medskip\noindent
-\lstinline{T * alloc( ... )} or \lstinline{T * alloc( size_t dim, ... )}
+\lstinline{T * alloc( ... )} or \lstinline{T * alloc( size_t dimension, ... )}
 is overloaded with a variable number of specific allocation operations, or an integer dimension parameter followed by a variable number of specific allocation operations.
 These allocation operations can be passed as named arguments when calling the \lstinline{alloc} routine.