Changes in / [11f92fac:de8a0a4b]

Files:

• doc/bibliography/pl.bib (modified) (2 diffs)
• doc/papers/llheap/Paper.tex (modified) (19 diffs)
• doc/theses/fangren_yu_MMath/.gitignore (modified) (1 diff)
• doc/theses/fangren_yu_MMath/intro.tex (modified) (28 diffs)
• tools/cforall.el (deleted)

doc/bibliography/pl.bib

@@ -1 @@
-
 % Conventions: uncross-referenced entries appear first, then
 %    cross-referenced entries.  In both groups, entries are sorted by their
@@ -3931 +3930 @@
 
 @article{Boehm88,
-    keywords    = {conservative garbage collection, C},
+    keywords    = {conservative garbage collection, C, storage management, debugging},
     contributer = {gjditchfield@plg},
     author      = {Hans-Juergen Boehm and Mark Weiser},

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.

doc/theses/fangren_yu_MMath/.gitignore

@@ -1 @@
-# Intermediate Results:
-build/
-
-# Final Files:
+# generated by latex
+build/*
 *.pdf
 *.ps
 
-# The Makefile here is not generated.
-!Makefile
+# generated by xfig
+*.bak

doc/theses/fangren_yu_MMath/intro.tex

@@ -6 +6 @@
 \begin{cfa}
 T sum( T a[$\,$], size_t size ) {
-        @T@ total = { @0@ };  // size, 0 for type T
+        @T@ total = { @0@ };  $\C[1.75in]{// size, 0 for type T}$
         for ( size_t i = 0; i < size; i += 1 )
-                total @+=@ a@[@i@]@; // + and subscript for T
+                total @+=@ a@[@i@]@; $\C{// + and subscript for T}\CRT$
         return total;
 }
@@ -22 +22 @@
 All computers have multiple types because computer architects optimize the hardware around a few basic types with well defined (mathematical) operations: boolean, integral, floating-point, and occasionally strings.
 A programming language and its compiler present ways to declare types that ultimately map into the ones provided by the underlying hardware.
-These language types are thrust upon programmers, with their syntactic and semantic rules and restrictions.
-These rules are used to transform a language expression to a hardware expression.
+These language types are thrust upon programmers with their syntactic/semantic rules and restrictions.
+These rules are then used to transform a language expression to a hardware expression.
 Modern programming-languages allow user-defined types and generalize across multiple types using polymorphism.
 Type systems can be static, where each variable has a fixed type during execution and an expression's type is determined once at compile time, or dynamic, where each variable can change type during execution and so an expression's type is reconstructed on each evaluation.
@@ -31 +31 @@
 \section{Overloading}
 
-Overloading allows programmers to use the most meaningful names without fear of name clashes within a program or from external sources, like include files.
 \begin{quote}
 There are only two hard things in Computer Science: cache invalidation and \emph{naming things}. --- Phil Karlton
 \end{quote}
+Overloading allows programmers to use the most meaningful names without fear of name clashes within a program or from external sources, like include files.
 Experience from \CC and \CFA developers is that the type system implicitly and correctly disambiguates the majority of overloaded names, \ie it is rare to get an incorrect selection or ambiguity, even among hundreds of overloaded (variables and) functions.
 In many cases, a programmer has no idea there are name clashes, as they are silently resolved, simplifying the development process.
-Depending on the language, any ambiguous cases are resolved using some form of qualification and/or casting.
+Depending on the language, any ambiguous cases are resolved explicitly using some form of qualification and/or cast.
 
 
@@ -45 +45 @@
 Like \CC, \CFA maps operators to named functions and allows these operators to be overloaded with user-defined types.
 The syntax for operator names uses the @'?'@ character to denote a parameter, \eg left and right unary operators: @?++@ and @++?@, and binary operators @?+?@ and @?<=?@.
-Here, a user-defined type is extended with an addition operation with the same syntax as builtin types.
+Here, a user-defined type is extended with an addition operation with the same syntax as a builtin type.
 \begin{cfa}
 struct S { int i, j };
@@ -55 +55 @@
 The type system examines each call site and selects the best matching overloaded function based on the number and types of arguments.
 If there are mixed-mode operands, @2 + 3.5@, the type system attempts (safe) conversions, like in C/\CC, converting the argument type(s) to the parameter type(s).
-Conversions are necessary because the hardware rarely supports mix-mode operations, so both operands must be the same type.
-Note, without implicit conversions, programmers must write an exponential number of functions covering all possible exact-match cases among all possible types.
+Conversions are necessary because the hardware rarely supports mix-mode operations, so both operands must be converted to a common type.
+Like overloading, the majority of mixed-mode conversions are silently resolved, simplifying the development process.
+Without implicit conversions, programmers must write an exponential number of functions covering all possible exact-match cases among all possible types.
 This approach does not match with programmer intuition and expectation, regardless of any \emph{safety} issues resulting from converted values.
+Depending on the language, mix-mode conversions can be explicitly controlled using some form of cast.
 
 
@@ -81 +83 @@
 double d = f( 3 );              $\C{// select (2)}\CRT$
 \end{cfa}
-Alternatively, if the type system looks at the return type, there is an exact match for each call, which again matches with programmer intuition and expectation.
-This capability can be taken to the extreme, where there are no function parameters.
+Alternatively, if the type system uses the return type, there is an exact match for each call, which again matches with programmer intuition and expectation.
+This capability can be taken to the extreme, where the only differentiating factor is the return type.
 \begin{cfa}
 int random( void );             $\C[2in]{// (1); overloaded on return type}$
@@ -90 +92 @@
 \end{cfa}
 Again, there is an exact match for each call.
-If there is no exact match, a set of minimal, safe conversions can be added to find a best match, as for operator overloading.
+As for operator overloading, if there is no exact match, a set of minimal, an implicit conversion can be added to find a best match.
+\begin{cfa}
+short int = random();   $\C[2in]{// select (1), unsafe}$
+long double = random(); $\C{// select (2), safe}\CRT$
+\end{cfa}
 
 
@@ -96 +102 @@
 
 Unlike most programming languages, \CFA has variable overloading within a scope, along with shadow overloading in nested scopes.
-(Shadow overloading is also possible for functions, if a language supports nested function declarations, \eg \CC named, nested, lambda functions.)
+Shadow overloading is also possible for functions, in languages supporting nested-function declarations, \eg \CC named, nested, lambda functions.
 \begin{cfa}
 void foo( double d );
@@ -109 +115 @@
 \end{cfa}
 It is interesting that shadow overloading is considered a normal programming-language feature with only slight software-engineering problems.
-However, variable overloading within a scope is often considered extremely dangerous, without any evidence to corroborate this claim.
+However, variable overloading within a scope is considered extremely dangerous, without any evidence to corroborate this claim.
 In contrast, function overloading in \CC occurs silently within the global scope from @#include@ files all the time without problems.
 
-In \CFA, the type system simply treats overloaded variables as an overloaded function returning a value with no parameters.
-Hence, no significant effort is required to support this feature by leveraging the return type to disambiguate as variables have no parameters.
+In \CFA, the type system simply treats an overloaded variable as an overloaded function returning a value with no parameters.
+Hence, no effort is required to support this feature as it is available for differentiating among overloaded functions with no parameters.
 \begin{cfa}
 int MAX = 2147483647;   $\C[2in]{// (1); overloaded on return type}$
@@ -125 +131 @@
 The result is a significant reduction in names to access typed constants.
 
-As an aside, C has a separate namespace for type and variables allowing overloading between the namespaces, using @struct@ (qualification) to disambiguate.
+As an aside, C has a separate namespace for types and variables allowing overloading between the namespaces, using @struct@ (qualification) to disambiguate.
 \begin{cfa}
 void S() {
@@ -133 +139 @@
 }
 \end{cfa}
+Here the name @S@ is an aggregate type and field, and a variable and parameter of type @S@.
 
 
@@ -145 +152 @@
 for ( ; x; --x )   =>    for ( ; x @!= 0@; x @-= 1@ )
 \end{cfa}
-To generalize this feature, both constants are given types @zero_t@ and @one_t@ in \CFA, which allows overloading various operations for new types that seamlessly work with the special @0@ and @1@ contexts.
+To generalize this feature, both constants are given types @zero_t@ and @one_t@ in \CFA, which allows overloading various operations for new types that seamlessly work within the special @0@ and @1@ contexts.
 The types @zero_t@ and @one_t@ have special builtin implicit conversions to the various integral types, and a conversion to pointer types for @0@, which allows standard C code involving @0@ and @1@ to work.
 \begin{cfa}
@@ -176 +183 @@
 \end{cfa}
 For type-only, the programmer specifies the initial type, which remains fixed for the variable's lifetime in statically typed languages.
-For type-and-initialization, the specified and initialization types may not agree.
+For type-and-initialization, the specified and initialization types may not agree requiring an implicit/explicit conversion.
 For initialization-only, the compiler may select the type by melding programmer and context information.
 When the compiler participates in type selection, it is called \newterm{type inferencing}.
-Note, type inferencing is different from type conversion: type inferencing \emph{discovers} a variable's type before setting its value, whereas conversion has two typed values and performs a (possibly lossy) action to convert one value to the type of the other variable.
+Note, type inferencing is different from type conversion: type inferencing \emph{discovers} a variable's type before setting its value, whereas conversion has two typed variables and performs a (possibly lossy) value conversion from one type to the other.
 Finally, for assignment, the current variable and expression types may not agree.
 Discovering a variable or function type is complex and has limitations.
-The following covers these issues, and why some schemes are not amenable with the \CFA type system.
+The following covers these issues, and why this scheme is not amenable with the \CFA type system.
 
 One of the first and powerful type-inferencing system is Hindley--Milner~\cite{Damas82}.
@@ -203 +210 @@
 \end{cfa}
 In both overloads of @f@, the type system works from the constant initializations inwards and/or outwards to determine the types of all variables and functions.
-Note, like template meta programming, there could be a new function generated for the second @f@ depending on the types of the arguments, assuming these types are meaningful in the body of @f@.
+Like template meta-programming, there can be a new function generated for the second @f@ depending on the types of the arguments, assuming these types are meaningful in the body of @f@.
 Inferring type constraints, by analysing the body of @f@ is possible, and these constraints must be satisfied at each call site by the argument types;
 in this case, parametric polymorphism can allow separate compilation.
@@ -246 +253 @@
 This issue is exaggerated with \CC templates, where type names are 100s of characters long, resulting in unreadable error messages.
 \item
-Ensuring the type of secondary variables, match a primary variable(s).
+Ensuring the type of secondary variables, match a primary variable.
 \begin{cfa}
 int x; $\C{// primary variable}$
@@ -252 +259 @@
 \end{cfa}
 If the type of @x@ changes, the type of the secondary variables correspondingly updates.
+There can be strong software-engineering reasons for binding the types of these variables.
 \end{itemize}
 Note, the use of @typeof@ is more restrictive, and possibly safer, than general type-inferencing.
@@ -269 +277 @@
 
 A restriction is the conundrum in type inferencing of when to \emph{brand} a type.
-That is, when is the type of the variable/function more important than the type of its initialization expression.
-For example, if a change is made in an initialization expression, it can cause cascading type changes and/or errors.
-At some point, a variable's type needs to remain constant and the initializing expression needs to be modified or in error when it changes.
+That is, when is the type of the variable/function more important than the type of its initialization expression(s).
+For example, if a change is made in an initialization expression, it can cascade type changes producing many other changes and/or errors.
+At some point, a variable's type needs to remain constant and the initializing expression needs to be modified or be in error when it changes.
 Often type-inferencing systems allow restricting (\newterm{branding}) a variable or function type, so the complier can report a mismatch with the constant initialization.
 \begin{cfa}
@@ -283 +291 @@
 In Haskell, it is common for programmers to brand (type) function parameters.
 
-A confusion is large blocks of code where all declarations are @auto@, as is now common in \CC.
+A confusion is blocks of code where all declarations are @auto@, as is now common in \CC.
 As a result, understanding and changing the code becomes almost impossible.
 Types provide important clues as to the behaviour of the code, and correspondingly to correctly change or add new code.
@@ -299 +307 @@
 In this situation, having the type name or its short alias is essential.
 
-The \CFA's type system tries to prevent type-resolution mistakes by relying heavily on the type of the left-hand side of assignment to pinpoint the right types within an expression.
+\CFA's type system tries to prevent type-resolution mistakes by relying heavily on the type of the left-hand side of assignment to pinpoint the right types within an expression.
 Type inferencing defeats this goal because there is no left-hand type.
 Fundamentally, type inferencing tries to magic away variable types from the programmer.
@@ -308 +316 @@
 The entire area of Computer-Science data-structures is obsessed with time and space, and that obsession should continue into regular programming.
 Understanding space and time issues is an essential part of the programming craft.
-Given @typedef@ and @typeof@ in \CFA, and the strong desire to use the left-hand type in resolution, implicit type-inferencing is unsupported.
-Should a significant need arise, this feature can be revisited.
+Given @typedef@ and @typeof@ in \CFA, and the strong desire to use the left-hand type in resolution, the decision was made not to support implicit type-inferencing in the type system.
+Should a significant need arise, this decision can be revisited.
 
 
@@ -334 +342 @@
 
 To constrain polymorphic types, \CFA uses \newterm{type assertions}~\cite[pp.~37-44]{Alphard} to provide further type information, where type assertions may be variable or function declarations that depend on a polymorphic type variable.
-For example, the function @twice@ works for any type @T@ with a matching addition operator.
+Here, the function @twice@ works for any type @T@ with a matching addition operator.
 \begin{cfa}
 forall( T @| { T ?+?(T, T); }@ ) T twice( T x ) { return x @+@ x; }
 int val = twice( twice( 3 ) );  $\C{// val == 12}$
 \end{cfa}
-For example. parametric polymorphism and assertions occurs in existing type-unsafe (@void *@) C @qsort@ to sort an array.
+Parametric polymorphism and assertions occur in existing type-unsafe (@void *@) C functions, like @qsort@ for sorting an array of unknown values.
 \begin{cfa}
 void qsort( void * base, size_t nmemb, size_t size, int (*cmp)( const void *, const void * ) );
@@ -386 +394 @@
 }
 // select type and size from left-hand side
-int * ip = malloc();  double * dp = malloc();  $@$[aligned(64)] struct S {...} * sp = malloc();
+int * ip = malloc();  double * dp = malloc();  [[aligned(64)]] struct S {...} * sp = malloc();
 \end{cfa}
 The @sized@ assertion passes size and alignment as a data object has no implicit assertions.
 Both assertions are used in @malloc@ via @sizeof@ and @_Alignof@.
-
-These mechanism are used to construct type-safe wrapper-libraries condensing hundreds of existing C functions into tens of \CFA overloaded functions.
-Hence, existing C legacy code is leveraged as much as possible;
+In practise, this polymorphic @malloc@ is unwrapped by the C compiler and the @if@ statement is elided producing a type-safe call to @malloc@ or @memalign@.
+
+This mechanism is used to construct type-safe wrapper-libraries condensing hundreds of existing C functions into tens of \CFA overloaded functions.
+Here, existing C legacy code is leveraged as much as possible;
 other programming languages must build supporting libraries from scratch, even in \CC.
 
@@ -422 +431 @@
 \end{tabular}
 \end{cquote}
-Traits are simply flatten at the use point, as if written in full by the programmer, where traits often contain overlapping assertions, \eg operator @+@.
+Traits are implemented by flatten them at use points, as if written in full by the programmer.
+Flattening often results in overlapping assertions, \eg operator @+@.
 Hence, trait names play no part in type equivalence.
-Note, the type @T@ is an object type, and hence, has the implicit internal trait @otype@.
+In the example, type @T@ is an object type, and hence, has the implicit internal trait @otype@.
 \begin{cfa}
 trait otype( T & | sized(T) ) {
@@ -433 +443 @@
 };
 \end{cfa}
-The implicit routines are used by the @sumable@ operator @?+=?@ for the right side of @?+=?@ and return.
+These implicit routines are used by the @sumable@ operator @?+=?@ for the right side of @?+=?@ and return.
 
 If the array type is not a builtin type, an extra type parameter and assertions are required, like subscripting.
@@ -445 +455 @@
 \begin{enumerate}[leftmargin=*]
 \item
-Write bespoke data structures for each context they are needed.
+Write bespoke data structures for each context.
 While this approach is flexible and supports integration with the C type checker and tooling, it is tedious and error prone, especially for more complex data structures.
 \item
@@ -452 +462 @@
 \item
 Use preprocessor macros, similar to \CC @templates@, to generate code that is both generic and type checked, but errors may be difficult to interpret.
-Furthermore, writing and using preprocessor macros is difficult and inflexible.
+Furthermore, writing and using complex preprocessor macros is difficult and inflexible.
 \end{enumerate}
 
 \CC, Java, and other languages use \newterm{generic types} to produce type-safe abstract data-types.
 \CFA generic types integrate efficiently and naturally with the existing polymorphic functions, while retaining backward compatibility with C and providing separate compilation.
-However, for known concrete parameters, the generic-type definition can be inlined, like \CC templates.
+For concrete parameters, the generic-type definition can be inlined, like \CC templates, if its definition appears in a header file (\eg @static inline@).
 
 A generic type can be declared by placing a @forall@ specifier on a @struct@ or @union@ declaration and instantiated using a parenthesized list of types after the type name.
@@ -484 +494 @@
 \end{cquote}
 \CFA generic types are \newterm{fixed} or \newterm{dynamic} sized.
-Fixed-size types have a fixed memory layout regardless of type parameters, whereas dynamic types vary in memory layout depending on their type parameters.
+Fixed-size types have a fixed memory layout regardless of type parameters, whereas dynamic types vary in memory layout depending on the type parameters.
 For example, the type variable @T *@ is fixed size and is represented by @void *@ in code generation;
 whereas, the type variable @T@ is dynamic and set at the point of instantiation.
 The difference between fixed and dynamic is the complexity and cost of field access.
 For fixed, field offsets are computed (known) at compile time and embedded as displacements in instructions.
-For dynamic, field offsets are computed at compile time at the call site, stored in an array of offset values, passed as a polymorphic parameter, and added to the structure address for each field dereference within a polymorphic routine.
+For dynamic, field offsets are compile-time computed at the call site, stored in an array of offset values, passed as a polymorphic parameter, and added to the structure address for each field dereference within a polymorphic routine.
 See~\cite[\S~3.2]{Moss19} for complete implementation details.
 
@@ -517 +527 @@
 \section{Contributions}
 
+The \CFA compiler performance and type capability have been greatly improved through my development work.
 \begin{enumerate}
-\item The \CFA compiler performance and capability have been greatly improved through recent development. The compilation time of various \CFA library units and test programs have been reduced from the order of minutes down to 10-20 seconds, which made it possible to develop and test more complicated \CFA programs that utilize sophisticated type system features. The details of compiler optimization work are covered in a previous technical report.
-\item The thesis presents a systematic review of the new features that have been added to the \CFA language and its type system. Some of the more recent inclusions to \CFA such as tuples and generic structure types were not well tested when they were being developed, due to the limitation of compiler performance. Several issues coming from the interactions of various language features are identified and discussed in this thesis; some of them are now fully resolved, while others are given temporary fixes and need to be reworked in the future.
-\item Finally, this thesis provides constructive ideas of fixing the outstanding issues in \CFA language design and implementation, and gives a path for future improvements to \CFA language and compiler.
+\item
+The compilation time of various \CFA library units and test programs has been reduced by an order of magnitude, from minutes to seconds \see{\VRef[Table]{t:SelectedFileByCompilerBuild}}, which made it possible to develop and test more complicated \CFA programs that utilize sophisticated type system features.
+The details of compiler optimization work are covered in a previous technical report~\cite{Yu20}, which essentially forms part of this thesis.
+\item
+The thesis presents a systematic review of the new features added to the \CFA language and its type system.
+Some of the more recent inclusions to \CFA, such as tuples and generic structure types, were not well tested during development due to the limitation of compiler performance.
+Several issues coming from the interactions of various language features are identified and discussed in this thesis;
+some of them I have resolved, while others are given temporary fixes and need to be reworked in the future.
+\item
+Finally, this thesis provides constructive ideas for fixing a number of high-level issues in the \CFA language design and implementation, and gives a path for future improvements to the language and compiler.
 \end{enumerate}