Changeset 29d8c02


Ignore:
Timestamp:
May 20, 2022, 10:36:32 AM (2 years ago)
Author:
m3zulfiq <m3zulfiq@…>
Branches:
ADT, ast-experimental, master, pthread-emulation, qualifiedEnum
Children:
74ec742
Parents:
d8075d28
Message:

made corrections in thesis as per feedback from the readers

Location:
doc/theses/mubeen_zulfiqar_MMath
Files:
7 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/mubeen_zulfiqar_MMath/allocator.tex

    rd8075d28 r29d8c02  
    2929llheap's design was reviewed and changed multiple times throughout the thesis.
    3030Some of the rejected designs are discussed because they show the path to the final design (see discussion in \VRef{s:MultipleHeaps}).
    31 Note, a few simples tests for a design choice were compared with the current best allocators to determine the viability of a design.
     31Note, a few simple tests for a design choice were compared with the current best allocators to determine the viability of a design.
    3232
    3333
    … …  
    3737These designs look at the allocation/free \newterm{fastpath}, \ie when an allocation can immediately return free storage or returned storage is not coalesced.
    3838\paragraph{T:1 model}
    39 \VRef[Figure]{f:T1SharedBuckets} shows one heap accessed by multiple kernel threads (KTs) using a bucket array, where smaller bucket sizes are N-shared across KTs.
    40 This design leverages the fact that 95\% of allocation requests are less than 1024 bytes and there are only 3--5 different request sizes.
     39\VRef[Figure]{f:T1SharedBuckets} shows one heap accessed by multiple kernel threads (KTs) using a bucket array, where smaller bucket sizes are shared among N KTs.
     40This design leverages the fact that usually the allocation requests are less than 1024 bytes and there are only a few different request sizes.
    4141When KTs $\le$ N, the common bucket sizes are uncontented;
    4242when KTs $>$ N, the free buckets are contented and latency increases significantly.
    … …  
    6464
    6565\paragraph{T:H model}
    66 \VRef[Figure]{f:THSharedHeaps} shows a fixed number of heaps (N), each a local free pool, where the heaps are sharded across the KTs.
     66\VRef[Figure]{f:THSharedHeaps} shows a fixed number of heaps (N), each a local free pool, where the heaps are sharded (distributed) across the KTs.
    6767A KT can point directly to its assigned heap or indirectly through the corresponding heap bucket.
    68 When KT $\le$ N, the heaps are uncontented;
     68When KT $\le$ N, the heaps might be uncontented;
    6969when KTs $>$ N, the heaps are contented.
    7070In all cases, a KT must acquire/release a lock, contented or uncontented along the fast allocation path because a heap is shared.
    71 By adjusting N upwards, this approach reduces contention but increases storage (time versus space);
     71By increasing N, this approach reduces contention but increases storage (time versus space);
    7272however, picking N is workload specific.
    7373
    … …  
    138138(See \VRef[Figure]{f:THSharedHeaps} but with a heap bucket per KT and no bucket or local-pool lock.)
    139139Hence, immediately after a KT starts, its heap is created and just before a KT terminates, its heap is (logically) deleted.
    140 Heaps are uncontended for a KTs memory operations to its heap (modulo operations on the global pool and ownership).
     140\PAB{Heaps are uncontended for a KTs memory operations as every KT has its own thread-local heap which is not shared with any other KT (modulo operations on the global pool and ownership).}
    141141
    142142Problems:
    143143\begin{itemize}
    144144\item
    145 Need to know when a KT is starts/terminates to create/delete its heap.
     145Need to know when a KT starts/terminates to create/delete its heap.
    146146
    147147\noindent
    … …  
    161161\noindent
    162162In many concurrent applications, good performance is achieved with the number of KTs proportional to the number of CPUs.
    163 Since the number of CPUs is relatively small, >~1024, and a heap relatively small, $\approx$10K bytes (not including any associated freed storage), the worst-case external fragmentation is still small compared to the RAM available on large servers with many CPUs.
     163Since the number of CPUs is relatively small, and a heap is also relatively small, $\approx$10K bytes (not including any associated freed storage), the worst-case external fragmentation is still small compared to the RAM available on large servers with many CPUs.
    164164\item
    165165There is the same serially-reusable problem with UTs migrating across KTs.
    … …  
    171171\noindent
    172172The conclusion from this design exercise is: any atomic fence, atomic instruction (lock free), or lock along the allocation fastpath produces significant slowdown.
    173 For the T:1 and T:H models, locking must exist along the allocation fastpath because the buckets or heaps maybe shared by multiple threads, even when KTs $\le$ N.
     173For 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.
    174174For the T:H=CPU and 1:1 models, locking is eliminated along the allocation fastpath.
    175175However, T:H=CPU has poor operating-system support to determine the CPU id (heap id) and prevent the serially-reusable problem for KTs.
    176176More operating system support is required to make this model viable, but there is still the serially-reusable problem with user-level threading.
    177 Leaving the 1:1 model with no atomic actions along the fastpath and no special operating-system support required.
     177So the 1:1 model had no atomic actions along the fastpath and no special operating-system support requirements.
    178178The 1:1 model still has the serially-reusable problem with user-level threading, which is addressed in \VRef{s:UserlevelThreadingSupport}, and the greatest potential for heap blowup for certain allocation patterns.
    179179
    … …  
    212212Ideally latency is $O(1)$ with a small constant.
    213213
    214 To obtain $O(1)$ internal latency means no searching on the allocation fastpath, largely prohibits coalescing, which leads to external fragmentation.
     214To obtain $O(1)$ internal latency means no searching on the allocation fastpath and largely prohibits coalescing, which leads to external fragmentation.
    215215The 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).
    216216
    … …  
    257257llheap starts by creating an array of $N$ global heaps from storage obtained using @mmap@, where $N$ is the number of computer cores, that persists for program duration.
    258258There is a global bump-pointer to the next free heap in the array.
    259 When this array is exhausted, another array is allocated.
    260 There is a global top pointer for a heap intrusive link to chain free heaps from terminated threads.
    261 When statistics are turned on, there is a global top pointer for a heap intrusive link to chain \emph{all} the heaps, which is traversed to accumulate statistics counters across heaps using @malloc_stats@.
     259When this array is exhausted, another array of heaps is allocated.
     260There is a global top pointer for a intrusive linked-list to chain free heaps from terminated threads.
     261When statistics are turned on, there is a global top pointer for a intrusive linked-list to chain \emph{all} the heaps, which is traversed to accumulate statistics counters across heaps using @malloc_stats@.
    262262
    263263When a KT starts, a heap is allocated from the current array for exclusive use by the KT.
    264 When a KT terminates, its heap is chained onto the heap free-list for reuse by a new KT, which prevents unbounded growth of heaps.
    265 The free heaps is a stack so hot storage is reused first.
    266 Preserving all heaps created during the program lifetime, solves the storage lifetime problem, when ownership is used.
     264When a KT terminates, its heap is chained onto the heap free-list for reuse by a new KT, which prevents unbounded growth of number of heaps.
     265The free heaps are stored on stack so hot storage is reused first.
     266Preserving all heaps, created during the program lifetime, solves the storage lifetime problem when ownership is used.
    267267This approach wastes storage if a large number of KTs are created/terminated at program start and then the program continues sequentially.
    268268llheap can be configured with object ownership, where an object is freed to the heap from which it is allocated, or object no-ownership, where an object is freed to the KT's current heap.
    269269
    270270Each heap uses segregated free-buckets that have free objects distributed across 91 different sizes from 16 to 4M.
     271\PAB{All objects in a bucket are of the same size.}
    271272The number of buckets used is determined dynamically depending on the crossover point from @sbrk@ to @mmap@ allocation using @mallopt( M_MMAP_THRESHOLD )@, \ie small objects managed by the program and large objects managed by the operating system.
    272273Each free bucket of a specific size has the following two lists:
    … …  
    286287Quantizing is performed using a binary search over the ordered bucket array.
    287288An optional optimization is fast lookup $O(1)$ for sizes < 64K from a 64K array of type @char@, where each element has an index to the corresponding bucket.
    288 (Type @char@ restricts the number of bucket sizes to 256.)
     289The @char@ type restricts the number of bucket sizes to 256.
    289290For $S$ > 64K, a binary search is used.
    290291Then, the allocation storage is obtained from the following locations (in order), with increasing latency.
    … …  
    381382Then the corresponding bucket of the owner thread is computed for the deallocating thread, and the allocation is pushed onto the deallocating thread's bucket.
    382383
    383 Finally, the llheap design funnels \label{p:FunnelRoutine} all allocation/deallocation operations through routines @malloc@/@free@, which are the only routines to directly access and manage the internal data structures of the heap.
     384Finally, the llheap design funnels \label{p:FunnelRoutine} all allocation/deallocation operations through the @malloc@ and @free@ routines, which are the only routines to directly access and manage the internal data structures of the heap.
    384385Other allocation operations, \eg @calloc@, @memalign@, and @realloc@, are composed of calls to @malloc@ and possibly @free@, and may manipulate header information after storage is allocated.
    385386This design simplifies heap-management code during development and maintenance.
    … …  
    388389\subsection{Alignment}
    389390
    390 All dynamic memory allocations must have a minimum storage alignment for the contained object(s).
     391Most dynamic memory allocations have a minimum storage alignment for the contained object(s).
    391392Often 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).
    392393In general, the minimum storage alignment is 8/16-byte boundary on 32/64-bit computers.
    393394For consistency, the object header is normally aligned at this same boundary.
    394 Larger alignments must be a power of 2, such page alignment (4/8K).
     395Larger alignments must be a power of 2, such as page alignment (4/8K).
    395396Any alignment request, N, $\le$ the minimum alignment is handled as a normal allocation with minimal alignment.
    396397
    … …  
    400401\end{center}
    401402The storage between @E@ and @H@ is chained onto the appropriate free list for future allocations.
    402 This approach is also valid within any sufficiently large free block, where @E@ is the start of the free block, and any unused storage before @H@ or after the allocated object becomes free storage.
     403\PAB{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.
    403404In 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.
    404405However, if there are a large number of aligned requests, this approach leads to memory fragmentation from the small free areas around the aligned object.
    … …  
    407408Finally, 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.
    408409
    409 Instead, llheap alignment is accomplished by making a \emph{pessimistically} allocation request for sufficient storage to ensure that \emph{both} the alignment and size request are satisfied, \eg:
     410Instead, 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:
    410411\begin{center}
    411412\input{Alignment2}
    … …  
    424425\input{Alignment2Impl}
    425426\end{center}
    426 Since @malloc@ has a minimum alignment of @M@, @P@ $\neq$ @A@ only holds for alignments of @M@ or greater.
     427Since @malloc@ has a minimum alignment of @M@, @P@ $\neq$ @A@ only holds for alignments greater than @M@.
    427428When @P@ $\neq$ @A@, the minimum distance between @P@ and @A@ is @M@ bytes, due to the pessimistic storage-allocation.
    428429Therefore, there is always room for an @M@-byte fake header before @A@.
    … …  
    439440\label{s:ReallocStickyProperties}
    440441
    441 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.
     442The 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.
    442443\begin{flushleft}
    443444\begin{tabular}{ll}
    … …  
    460461The realloc pattern leverages available storage at the end of an allocation due to bucket sizes, possibly eliminating a new allocation and copying.
    461462This pattern is not used enough to reduce storage management costs.
    462 In fact, if @oaddr@ is @nullptr@, @realloc@ does a @malloc@, so even the initial @malloc@ can be a @realloc@ for consistency in the pattern.
     463In fact, if @oaddr@ is @nullptr@, @realloc@ does a @malloc@, so even the initial @malloc@ can be a @realloc@ for consistency in the allocation pattern.
    463464
    464465The hidden problem for this pattern is the effect of zero fill and alignment with respect to reallocation.
    465466Are these properties transient or persistent (``sticky'')?
    466 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.
    467 That is, if @realloc@ logically extends storage into unused bucket space or allocates new storage to satisfy a size change, are initial allocation properties preserve?
     467For 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?
     468That is, if @realloc@ logically extends storage into unused bucket space or allocates new storage to satisfy a size change, are initial allocation properties preserved?
    468469Currently, 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.
    469470This silent problem is unintuitive to programmers and difficult to locate because it is transient.
    … …  
    475476
    476477To preserve allocation properties requires storing additional information with an allocation,
    477 The only available location is the header, where \VRef[Figure]{f:llheapNormalHeader} shows the llheap storage layout.
     478The best available option is the header, where \VRef[Figure]{f:llheapNormalHeader} shows the llheap storage layout.
    478479The header has two data field sized appropriately for 32/64-bit alignment requirements.
    479480The first field is a union of three values:
    … …  
    487488\end{description}
    488489The second field remembers the request size versus the allocation (bucket) size, \eg request 42 bytes which is rounded up to 64 bytes.
    489 Since programmers think in request sizes rather than allocation sizes, the request size allows better generation of statistics or errors.
     490\PAB{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.}
    490491
    491492\begin{figure}
    … …  
    496497\end{figure}
    497498
    498 The low-order 3-bits of the first field are \emph{unused} for any stored values, whereas the second field may use all of its bits.
     499\PAB{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.}
    499500The 3 unused bits are used to represent mapped allocation, zero filled, and alignment, respectively.
    500501Note, the alignment bit is not used in the normal header and the zero-filled/mapped bits are not used in the fake header.
    … …  
    502503If no bits are on, it implies a basic allocation, which is handled quickly;
    503504otherwise, the bits are analysed and appropriate actions are taken for the complex cases.
    504 Since most allocations are basic, this implementation results in a significant performance gain along the allocation and free fastpath.
     505Since most allocations are basic, they will take significantly less time as the memory operations will be done along the allocation and free fastpath.
    505506
    506507
    … …  
    514515To locate all statistic counters, heaps are linked together in statistics mode, and this list is locked and traversed to sum all counters across heaps.
    515516Note, the list is locked to prevent errors traversing an active list;
    516 the statistics counters are not locked and can flicker during accumulation, which is not an issue with atomic read/write.
     517\PAB{the statistics counters are not locked and can flicker during accumulation.}
    517518\VRef[Figure]{f:StatiticsOutput} shows an example of statistics output, which covers all allocation operations and information about deallocating storage not owned by a thread.
    518519No other memory allocator studied provides as comprehensive statistical information.
    519 Finally, these statistics were invaluable during the development of this thesis for debugging and verifying correctness, and hence, should be equally valuable to application developers.
     520Finally, these statistics were invaluable during the development of this thesis for debugging and verifying correctness and should be equally valuable to application developers.
    520521
    521522\begin{figure}
    … …  
    547548Nevertheless, the checks detect many allocation problems.
    548549There is an unfortunate problem in detecting unfreed storage because some library routines assume their allocations have life-time duration, and hence, do not free their storage.
    549 For example, @printf@ allocates a 1024 buffer on first call and never deletes this buffer.
     550For example, @printf@ allocates a 1024-byte buffer on the first call and never deletes this buffer.
    550551To prevent a false positive for unfreed storage, it is possible to specify an amount of storage that is never freed (see @malloc_unfreed@ \VPageref{p:malloc_unfreed}), and it is subtracted from the total allocate/free difference.
    551552Determining the amount of never-freed storage is annoying, but once done, any warnings of unfreed storage are application related.
    552553
    553 Tests indicate only a 30\% performance increase when statistics \emph{and} debugging are enabled, and the latency cost for accumulating statistic is mitigated by limited calls, often only one at the end of the program.
     554Tests indicate only a 30\% performance decrease when statistics \emph{and} debugging are enabled, and the latency cost for accumulating statistic is mitigated by limited calls, often only one at the end of the program.
    554555
    555556
    … …  
    558559
    559560The serially-reusable problem (see \VRef{s:AllocationFastpath}) occurs for kernel threads in the ``T:H model, H = number of CPUs'' model and for user threads in the ``1:1'' model, where llheap uses the ``1:1'' model.
    560 The solution is to prevent interrupts that can result in CPU or KT change during operations that are logically critical sections.
     561\PAB{The solution is to prevent interrupts that can result in CPU or KT change during operations that are logically critical sections such as moving free storage from public heap to the private heap.}
    561562Locking these critical sections negates any attempt for a quick fastpath and results in high contention.
    562563For user-level threading, the serially-reusable problem appears with time slicing for preemptable scheduling, as the signal handler context switches to another user-level thread.
    563 Without time slicing, a user thread performing a long computation can prevent execution (starve) other threads.
    564 To prevent starvation for an allocation-active thread, \ie the time slice always triggers in an allocation critical-section for one thread, a thread-local \newterm{rollforward} flag is set in the signal handler when it aborts a time slice.
     564Without time slicing, a user thread performing a long computation can prevent the execution of (starve) other threads.
     565\PAB{To prevent starvation for a memory-allocation-intensive thread, \ie the time slice always triggers in an allocation critical-section for one thread so the thread never gets time sliced, a thread-local \newterm{rollforward} flag is set in the signal handler when it aborts a time slice.}
    565566The rollforward flag is tested at the end of each allocation funnel routine (see \VPageref{p:FunnelRoutine}), and if set, it is reset and a volunteer yield (context switch) is performed to allow other threads to execute.
    566567
    567 llheap uses two techniques to detect when execution is in a allocation operation or routine called from allocation operation, to abort any time slice during this period.
    568 On the slowpath when executing expensive operations, like @sbrk@ or @mmap@, interrupts are disabled/enabled by setting thread-local flags so the signal handler aborts immediately.
    569 On the fastpath, disabling/enabling interrupts is too expensive as accessing thread-local storage can be expensive and not thread-safe.
     568llheap uses two techniques to detect when execution is in an allocation operation or routine called from allocation operation, to abort any time slice during this period.
     569On the slowpath when executing expensive operations, like @sbrk@ or @mmap@,
     570\PAB{interrupts are disabled/enabled by setting kernel-thread-local flags so the signal handler aborts immediately.}
     571\PAB{On the fastpath, disabling/enabling interrupts is too expensive as accessing kernel-thread-local storage can be expensive and not user-thread-safe.}
    570572For example, the ARM processor stores the thread-local pointer in a coprocessor register that cannot perform atomic base-displacement addressing.
    571 Hence, there is a window between loading the thread-local pointer from the coprocessor register into a normal register and adding the displacement when a time slice can move a thread.
    572 
    573 The fast technique defines a special code section and places all non-interruptible routines in this section.
     573\PAB{Hence, there is a window between loading the kernel-thread-local pointer from the coprocessor register into a normal register and adding the displacement when a time slice can move a thread.}
     574
     575The fast technique (with lower run time cost) is to define a special code section and places all non-interruptible routines in this section.
    574576The linker places all code in this section into a contiguous block of memory, but the order of routines within the block is unspecified.
    575577Then, the signal handler compares the program counter at the point of interrupt with the the start and end address of the non-interruptible section, and aborts if executing within this section and sets the rollforward flag.
    … …  
    577579Hence, for correctness, this approach requires inspection of generated assembler code for routines placed in the non-interruptible section.
    578580This issue is mitigated by the llheap funnel design so only funnel routines and a few statistics routines are placed in the non-interruptible section and their assembler code examined.
    579 These techniques are used in both the \uC and \CFA versions of llheap, where both of these systems have user-level threading.
     581These techniques are used in both the \uC and \CFA versions of llheap as both of these systems have user-level threading.
    580582
    581583
    … …  
    587589Programs can be statically or dynamically linked.
    588590\item
    589 The order the linker schedules startup code is poorly supported.
     591\PAB{The order in which the linker schedules startup code is poorly supported so cannot be controlled entirely.}
    590592\item
    591593Knowing a KT's start and end independently from the KT code is difficult.
    … …  
    600602Hence, some part of the @sbrk@ area may be used by the default allocator and statistics about allocation operations cannot be correct.
    601603Furthermore, dynamic linking goes through trampolines, so there is an additional cost along the allocator fastpath for all allocation operations.
    602 Testing showed up to a 5\% performance increase for dynamic linking over static linking, even when using @tls_model("initial-exec")@ so the dynamic loader can obtain tighter binding.
     604Testing showed up to a 5\% performance decrease with dynamic linking as compared to static linking, even when using @tls_model("initial-exec")@ so the dynamic loader can obtain tighter binding.
    603605
    604606All allocator libraries need to perform startup code to initialize data structures, such as the heap array for llheap.
    605 The problem is getting initialized done before the first allocator call.
     607The problem is getting initialization done before the first allocator call.
    606608However, there does not seem to be mechanism to tell either the static or dynamic loader to first perform initialization code before any calls to a loaded library.
     609\PAB{Also, initialization code of other libraries and run-time envoronment may call memory allocation routines such as \lstinline{malloc}.
     610So, this creates an even more difficult situation as there is no mechanism to tell either the static or dynamic loader to first perform initialization code of memory allocator before any other initialization that may involve a dynamic memory allocation call.}
    607611As a result, calls to allocation routines occur without initialization.
    608612To deal with this problem, it is necessary to put a conditional initialization check along the allocation fastpath to trigger initialization (singleton pattern).
    … …  
    641645Therefore, the constructor is useless for knowing when a KT starts because the KT must reference it, and the allocator does not control the application KT.
    642646Fortunately, the singleton pattern needed for initializing the program KT also triggers KT allocator initialization, which can then reference @pgm_thread@ to call @threadManager@'s constructor, otherwise its destructor is not called.
    643 Now when a KT terminates, @~ThreadManager@ is called to chained it onto the global-heap free-stack, where @pgm_thread@ is set to true only for the program KT.
     647Now when a KT terminates, @~ThreadManager@ is called to chain it onto the global-heap free-stack, where @pgm_thread@ is set to true only for the program KT.
    644648The conditional destructor call prevents closing down the program heap, which must remain available because epilogue code may free more storage.
    645649
    … …  
    660664bool traceHeapOff();                    $\C{// stop printing allocation/free calls}$
    661665\end{lstlisting}
    662 This kind of API is necessary to allow concurrent runtime systems to interact with difference memory allocators in a consistent way.
     666This kind of API is necessary to allow concurrent runtime systems to interact with different memory allocators in a consistent way.
    663667
    664668%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    … …  
    712716Most allocators use @nullptr@ to indicate an allocation failure, specifically out of memory;
    713717hence the need to return an alternate value for a zero-sized allocation.
    714 A different approach allowed by the C API is to abort a program when out of memory and return @nullptr@ for a zero-sized allocation.
     718A different approach allowed by @C API@ is to abort a program when out of memory and return @nullptr@ for a zero-sized allocation.
    715719In theory, notifying the programmer of memory failure allows recovery;
    716720in practice, it is almost impossible to gracefully recover when out of memory.
    … …  
    736740\paragraph{\lstinline{void * aalloc( size_t dim, size_t elemSize )}}
    737741extends @calloc@ for allocating a dynamic array of objects without calculating the total size of array explicitly but \emph{without} zero-filling the memory.
    738 @aalloc@ is significantly faster than @calloc@, which is the only alternative.
     742@aalloc@ is significantly faster than @calloc@, \PAB{which is the only alternative given by the memory allocation routines}.
    739743
    740744\noindent\textbf{Usage}
    … …  
    825829\begin{itemize}
    826830\item
    827 @fd@: files description.
     831@fd@: file descriptor.
    828832\end{itemize}
    829833It returns the previous file descriptor.
    … …  
    832836\label{p:malloc_expansion}
    833837set the amount (bytes) to extend the heap when there is insufficient free storage to service an allocation request.
    834 It returns the heap extension size used throughout a program, \ie called once at heap initialization.
     838It returns the heap extension size used throughout a program when requesting more memory from the system using @sbrk@ system-call, \ie called once at heap initialization.
    835839
    836840\paragraph{\lstinline{size_t malloc_mmap_start()}}
    … …  
    915919\begin{itemize}
    916920\item
    917 naming: \CFA regular and @ttype@ polymorphism is used to encapsulate a wide range of allocation functionality into a single routine name, so programmers do not have to remember multiple routine names for different kinds of dynamic allocations.
    918 \item
    919 named arguments: individual allocation properties are specified using postfix function call, so programmers do have to remember parameter positions in allocation calls.
    920 \item
    921 object size: like the \CFA C-style interface, programmers do not have to specify object size or cast allocation results.
     921naming: \CFA regular and @ttype@ polymorphism (@ttype@ polymorphism in \CFA is similar to \CC variadic templates) is used to encapsulate a wide range of allocation functionality into a single routine name, so programmers do not have to remember multiple routine names for different kinds of dynamic allocations.
     922\item
     923named arguments: individual allocation properties are specified using postfix function call, so the programmers do not have to remember parameter positions in allocation calls.
     924\item
     925object size: like the \CFA's C-interface, programmers do not have to specify object size or cast allocation results.
    922926\end{itemize}
    923927Note, postfix function call is an alternative call syntax, using backtick @`@, where the argument appears before the function name, \eg
    … …  
    928932duration dur = 3@`@h + 42@`@m + 17@`@s;
    929933\end{cfa}
    930 @ttype@ polymorphism is similar to \CC variadic templates.
    931934
    932935\paragraph{\lstinline{T * alloc( ... )} or \lstinline{T * alloc( size_t dim, ... )}}
    933 is overloaded with a variable number of specific allocation routines, or an integer dimension parameter followed by a variable number specific allocation routines.
     936is overloaded with a variable number of specific allocation operations, or an integer dimension parameter followed by a variable number of specific allocation operations.
     937\PAB{These allocation operations can be passed as positional arguments when calling \lstinline{alloc} routine.}
    934938A call without parameters returns a dynamically allocated object of type @T@ (@malloc@).
    935939A call with only the dimension (dim) parameter returns a dynamically allocated array of objects of type @T@ (@aalloc@).
    … …  
    9809845 5 5 -555819298 -555819298  // two undefined values
    981985\end{lstlisting}
    982 Examples 1 to 3, fill an object with a value or characters.
    983 Examples 4 to 7, fill an array of objects with values, another array, or part of an array.
     986Examples 1 to 3 fill an object with a value or characters.
     987Examples 4 to 7 fill an array of objects with values, another array, or part of an array.
    984988
    985989\subparagraph{\lstinline{S_resize(T) ?`resize( void * oaddr )}}
    … …  
    10151019\subparagraph{\lstinline{S_realloc(T) ?`realloc( T * a ))}}
    10161020used to resize, realign, and fill, where the old object data is copied to the new object.
    1017 The old object type must be the same as the new object type, since the values used.
     1021The old object type must be the same as the new object type, since the value is used.
    10181022Note, for @fill@, only the extra space after copying the data from the old object is filled with the given parameter.
    10191023For example:
    … …  
    10291033\end{lstlisting}
    10301034Examples 2 to 3 change the alignment for the initial storage of @i@.
    1031 The @13`fill@ for example 3 does nothing because no extra space is added.
     1035The @13`fill@ in example 3 does nothing because no extra space is added.
    10321036
    10331037\begin{cfa}[numbers=left]
    … …  
    10441048\end{lstlisting}
    10451049Examples 2 to 4 change the array size, alignment and fill for the initial storage of @ia@.
    1046 The @13`fill@ for example 3 does nothing because no extra space is added.
     1050The @13`fill@ in example 3 does nothing because no extra space is added.
    10471051
    10481052These \CFA allocation features are used extensively in the development of the \CFA runtime.

  • doc/theses/mubeen_zulfiqar_MMath/background.tex

    rd8075d28 r29d8c02  
    3636The management data starts with fixed-sized information in the static-data memory that references components in the dynamic-allocation memory.
    3737The \newterm{storage data} is composed of allocated and freed objects, and \newterm{reserved memory}.
    38 Allocated objects (light grey) are variable sized, and allocated and maintained by the program;
    39 \ie only the program knows the location of allocated storage, not the memory allocator.
     38Allocated objects (light grey) are variable sized, and are allocated and maintained by the program;
     39\PAB{\ie only the memory allocator knows the location of allocated storage, not the program.}
    4040\begin{figure}[h]
    4141\centering
    … …  
    4949if there are multiple reserved blocks, they are also chained together, usually internally.
    5050
    51 Allocated and freed objects typically have additional management data embedded within them.
     51\PAB{In some allocator designs, allocated and freed objects have additional management data embedded within them.}
    5252\VRef[Figure]{f:AllocatedObject} shows an allocated object with a header, trailer, and alignment padding and spacing around the object.
    5353The header contains information about the object, \eg size, type, etc.
    … …  
    104104\VRef[Figure]{f:MemoryFragmentation} shows an example of how a small block of memory fragments as objects are allocated and deallocated over time.
    105105Blocks of free memory become smaller and non-contiguous making them less useful in serving allocation requests.
    106 Memory is highly fragmented when the sizes of most free blocks are unusable.
     106\PAB{Memory is highly fragmented when most free blocks are unusable because of their sizes.}
    107107For example, \VRef[Figure]{f:Contiguous} and \VRef[Figure]{f:HighlyFragmented} have the same quantity of external fragmentation, but \VRef[Figure]{f:HighlyFragmented} is highly fragmented.
    108108If there is a request to allocate a large object, \VRef[Figure]{f:Contiguous} is more likely to be able to satisfy it with existing free memory, while \VRef[Figure]{f:HighlyFragmented} likely has to request more memory from the operating system.
    … …  
    137137The fewer bin-sizes, the fewer lists need to be searched and maintained;
    138138however, the bin sizes are less likely to closely fit the requested object size, leading to more internal fragmentation.
    139 The more bin-sizes, the longer the search and the less likely free objects are to be reused, leading to more external fragmentation and potentially heap blowup.
     139The more bin sizes, the longer the search and the less likely free objects are to be reused, leading to more external fragmentation and potentially heap blowup.
    140140A variation of the binning algorithm allows objects to be allocated to the requested size, but when an object is freed, it is placed on the free list of the next smallest or equal bin-size.
    141141For example, with bin sizes of 8 and 16 bytes, a request for 12 bytes allocates only 12 bytes, but when the object is freed, it is placed on the 8-byte bin-list.
    … …  
    157157The principle of locality recognizes that programs tend to reference a small set of data, called a working set, for a certain period of time, where a working set is composed of temporal and spatial accesses~\cite{Denning05}.
    158158Temporal clustering implies a group of objects are accessed repeatedly within a short time period, while spatial clustering implies a group of objects physically close together (nearby addresses) are accessed repeatedly within a short time period.
    159 Temporal locality commonly occurs during an iterative computation with a fix set of disjoint variables, while spatial locality commonly occurs when traversing an array.
     159Temporal locality commonly occurs during an iterative computation with a fixed set of disjoint variables, while spatial locality commonly occurs when traversing an array.
    160160
    161161Hardware takes advantage of temporal and spatial locality through multiple levels of caching, \ie memory hierarchy.
    … …  
    328328For example, multiple heaps are managed in a pool, starting with a single or a fixed number of heaps that increase\-/decrease depending on contention\-/space issues.
    329329At creation, a thread is associated with a heap from the pool.
    330 When the thread attempts an allocation and its associated heap is locked (contention), it scans for an unlocked heap in the pool.
     330\PAB{In some implementations of this model, when the thread attempts an allocation and its associated heap is locked (contention), it scans for an unlocked heap in the pool.}
    331331If an unlocked heap is found, the thread changes its association and uses that heap.
    332332If all heaps are locked, the thread may create a new heap, use it, and then place the new heap into the pool;
    … …  
    347347The management information in the static zone must be able to locate all heaps in the dynamic zone.
    348348The management information for the heaps must reside in the dynamic-allocation zone if there are a variable number.
    349 Each heap in the dynamic zone is composed of a list of a free objects and a pointer to its reserved memory.
     349Each heap in the dynamic zone is composed of a list of free objects and a pointer to its reserved memory.
    350350An alternative implementation is for all heaps to share one reserved memory, which requires a separate lock for the reserved storage to ensure mutual exclusion when acquiring new memory.
    351351Because multiple threads can allocate/free/reallocate adjacent storage, all forms of false sharing may occur.
    … …  
    361361Multiple heaps increase external fragmentation as the ratio of heaps to threads increases, which can lead to heap blowup.
    362362The external fragmentation experienced by a program with a single heap is now multiplied by the number of heaps, since each heap manages its own free storage and allocates its own reserved memory.
    363 Additionally, objects freed by one heap cannot be reused by other threads, except indirectly by returning free memory to the operating system, which can be expensive.
    364 (Depending on how the operating system provides dynamic storage to an application, returning storage may be difficult or impossible, \eg the contiguous @sbrk@ area in Unix.)
     363\PAB{Additionally, objects freed by one heap cannot be reused by other threads without increasing the cost of the memory operations, except indirectly by returning free memory to the operating system, which can be expensive.}
     364Depending on how the operating system provides dynamic storage to an application, returning storage may be difficult or impossible, \eg the contiguous @sbrk@ area in Unix.
    365365In the worst case, a program in which objects are allocated from one heap but deallocated to another heap means these freed objects are never reused.
    366366
    … …  
    384384In contrast, the T:H model spreads each thread's objects over a larger area in different heaps.
    385385Thread heaps can also eliminate allocator-induced active false-sharing, if memory is acquired so it does not overlap at crucial boundaries with memory for another thread's heap.
    386 For example, assume page boundaries coincide with cache line boundaries, then if a thread heap always acquires pages of memory, no two threads share a page or cache line unless pointers are passed among them.
     386For example, assume page boundaries coincide with cache line boundaries, if a thread heap always acquires pages of memory then no two threads share a page or cache line unless pointers are passed among them.
    387387Hence, allocator-induced active false-sharing in \VRef[Figure]{f:AllocatorInducedActiveFalseSharing} cannot occur because the memory for thread heaps never overlaps.
    388388
    389 When a thread terminates, there are two options for handling its heap.
    390 First is to free all objects in the heap to the global heap and destroy the thread heap.
     389When a thread terminates, there are two options for handling its thread heap.
     390First is to free all objects in the thread heap to the global heap and destroy the thread heap.
    391391Second is to place the thread heap on a list of available heaps and reuse it for a new thread in the future.
    392392Destroying the thread heap immediately may reduce external fragmentation sooner, since all free objects are freed to the global heap and may be reused by other threads.
    … …  
    417417When the user thread continues on the new kernel thread, it may have pointers into the previous kernel-thread's heap and hold locks associated with it.
    418418To get the same kernel-thread safety, time slicing must be disabled/\-enabled around these operations, so the user thread cannot jump to another kernel thread.
    419 However, eagerly disabling/enabling time-slicing on the allocation/deallocation fast path is expensive, because preemption is rare (10--100 milliseconds).
     419However, eagerly disabling/enabling time-slicing on the allocation/deallocation fast path is expensive, because preemption does not happen that frequently.
    420420Instead, techniques exist to lazily detect this case in the interrupt handler, abort the preemption, and return to the operation so it can complete atomically.
    421421Occasionally ignoring a preemption should be benign, but a persistent lack of preemption can result in both short and long term starvation.
    … …  
    448448
    449449\VRef[Figure]{f:MultipleHeapStorageOwnership} shows the effect of ownership on storage layout.
    450 (For simplicity assume the heaps all use the same size of reserves storage.)
     450(For simplicity, assume the heaps all use the same size of reserves storage.)
    451451In contrast to \VRef[Figure]{f:MultipleHeapStorage}, each reserved area used by a heap only contains free storage for that particular heap because threads must return free objects back to the owner heap.
    452452Again, because multiple threads can allocate/free/reallocate adjacent storage in the same heap, all forms of false sharing may occur.
    … …  
    473473While the returning thread can batch objects, batching across multiple heaps is complex and there is no obvious time when to push back to the owner heap.
    474474It is better for returning threads to immediately return to the receiving thread's batch list as the receiving thread has better knowledge when to incorporate the batch list into its free pool.
    475 Batching leverages the fact that most allocation patterns use the contention-free fast-path so locking on the batch list is rare for both the returning and receiving threads.
    476 
    477 It is possible for heaps to steal objects rather than return them and reallocating these objects when storage runs out on a heap.
     475Batching leverages the fact that most allocation patterns use the contention-free fast-path, so locking on the batch list is rare for both the returning and receiving threads.
     476
     477It is possible for heaps to steal objects rather than return them and then reallocate these objects again when storage runs out on a heap.
    478478However, stealing can result in passive false-sharing.
    479479For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, Object$_2$ may be deallocated to Thread$_2$'s heap initially.
    … …  
    485485
    486486Bracketing every allocation with headers/trailers can result in significant internal fragmentation, as shown in \VRef[Figure]{f:ObjectHeaders}.
    487 Especially if the headers contain redundant management information, \eg object size may be the same for many objects because programs only allocate a small set of object sizes.
     487Especially if the headers contain redundant management information \PAB{then storing that information is a waste of storage}, \eg object size may be the same for many objects because programs only allocate a small set of object sizes.
    488488As well, it can result in poor cache usage, since only a portion of the cache line is holding useful information from the program's perspective.
    489489Spatial locality can also be negatively affected leading to poor cache locality~\cite{Feng05}:
    … …  
    660660With local free-lists in containers, as in \VRef[Figure]{f:LocalFreeListWithinContainers}, the container is simply removed from one heap's free list and placed on the new heap's free list.
    661661Thus, when using local free-lists, the operation of moving containers is reduced from $O(N)$ to $O(1)$.
    662 The cost is adding information to a header, which increases the header size, and therefore internal fragmentation.
     662\PAB{The cost that we have to pay for it is to add information to a header, which increases the header size, and therefore internal fragmentation.}
    663663
    664664\begin{figure}
    … …  
    689689The main goal of the hybrid approach is to eliminate locking on thread-local allocation/deallocation, while providing ownership to prevent heap blowup.
    690690In the hybrid approach, a thread first allocates from its private heap and second from its public heap if no free memory exists in the private heap.
    691 Similarly, a thread first deallocates an object its private heap, and second to the public heap.
     691Similarly, a thread first deallocates an object to its private heap, and second to the public heap.
    692692Both private and public heaps can allocate/deallocate to/from the global heap if there is no free memory or excess free memory, although an implementation may choose to funnel all interaction with the global heap through one of the heaps.
    693693Note, deallocation from the private to the public (dashed line) is unlikely because there is no obvious advantages unless the public heap provides the only interface to the global heap.

  • doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex

    rd8075d28 r29d8c02  
    1212\item[Benchmarks]
    1313are a suite of application programs (SPEC CPU/WEB) that are exercised in a common way (inputs) to find differences among underlying software implementations associated with an application (compiler, memory allocator, web server, \etc).
    14 The applications are suppose to represent common execution patterns that need to perform well with respect to an underlying software implementation.
     14The applications are supposed to represent common execution patterns that need to perform well with respect to an underlying software implementation.
    1515Benchmarks are often criticized for having overlapping patterns, insufficient patterns, or extraneous code that masks patterns.
    1616\item[Micro-Benchmarks]
    … …  
    2626
    2727This thesis designs and examines a new set of micro-benchmarks for memory allocators that test a variety of allocation patterns, each with multiple tuning parameters.
    28 The aim of the micro-benchmark suite is to create a set of programs that can evaluate a memory allocator based on the key performance matrices such as speed, memory overhead, and cache performance.
     28The aim of the micro-benchmark suite is to create a set of programs that can evaluate a memory allocator based on the key performance metrics such as speed, memory overhead, and cache performance.
    2929% These programs can be taken as a standard to benchmark an allocator's basic goals.
    3030These programs give details of an allocator's memory overhead and speed under certain allocation patterns.
    31 The allocation patterns are configurable (adjustment knobs) to observe an allocator's performance across a spectrum of events for a desired allocation pattern, which is seldom possible with benchmark programs.
     31The allocation patterns are configurable (adjustment knobs) to observe an allocator's performance across a spectrum allocation patterns, which is seldom possible with benchmark programs.
    3232Each micro-benchmark program has multiple control knobs specified by command-line arguments.
    3333
    34 The new micro-benchmark suite measures performance by allocating dynamic objects and measuring specific matrices.
     34The new micro-benchmark suite measures performance by allocating dynamic objects and measuring specific metrics.
    3535An allocator's speed is benchmarked in different ways, as are issues like false sharing.
    3636
    … …  
    4040Modern memory allocators, such as llheap, must handle multi-threaded programs at the KT and UT level.
    4141The following multi-threaded micro-benchmarks are presented to give a sense of prior work~\cite{Berger00} at the KT level.
    42 None of the prior work address multi-threading at the UT level.
     42None of the prior work addresses multi-threading at the UT level.
    4343
    4444
    … …  
    4747This benchmark stresses the ability of the allocator to handle different threads allocating and deallocating independently.
    4848There is no interaction among threads, \ie no object sharing.
    49 Each thread repeatedly allocate 100,000 \emph{8-byte} objects then deallocates them in the order they were allocated.
    50 Runtime of the benchmark evaluates its efficiency.
     49Each thread repeatedly allocates 100,000 \emph{8-byte} objects then deallocates them in the order they were allocated.
     50\PAB{Execution time of the benchmark evaluates its efficiency.}
    5151
    5252
    … …  
    6363Before the thread terminates, it passes its array of 10,000 objects to a new child thread to continue the process.
    6464The number of thread generations varies depending on the thread speed.
    65 It calculates memory operations per second as an indicator of memory allocator's performance.
     65It calculates memory operations per second as an indicator of the memory allocator's performance.
    6666
    6767
    … …  
    7777The churn benchmark measures the runtime speed of an allocator in a multi-threaded scenerio, where each thread extensively allocates and frees dynamic memory.
    7878Only @malloc@ and @free@ are used to eliminate any extra cost, such as @memcpy@ in @calloc@ or @realloc@.
    79 Churn simulates a memory intensive program that can be tuned to create different scenarios.
     79Churn simulates a memory intensive program and can be tuned to create different scenarios.
    8080
    8181\VRef[Figure]{fig:ChurnBenchFig} shows the pseudo code for the churn micro-benchmark.
    … …  
    141141Each worker thread allocates an object and intensively reads/writes it for M times to possible invalidate cache lines that may interfere with other threads sharing the same cache line.
    142142Each thread repeats this for N times.
    143 The main thread measures the total time taken to for all worker threads to complete.
    144 Worker threads sharing cache lines with each other will take longer.
     143The main thread measures the total time taken for all worker threads to complete.
     144Worker threads sharing cache lines with each other are expected to take longer.
    145145
    146146\begin{figure}
    … …  
    156156        signal workers to free
    157157        ...
    158         print addresses from each $thread$
    159158Worker Thread$\(_1\)$
    160         allocate, write, read, free
    161         warmup memory in chunkc of 16 bytes
    162         ...
    163         malloc N objects
    164         ...
    165         free objects
    166         return object address to Main Thread
     159        warm up memory in chunks of 16 bytes
     160        ...
     161        For N
     162                malloc an object
     163                read/write the object M times
     164                free the object
     165        ...
    167166Worker Thread$\(_2\)$
    168167        // same as Worker Thread$\(_1\)$
    … …  
    191190
    192191The cache-scratch micro-benchmark measures allocator-induced passive false-sharing as illustrated in \VRef{s:AllocatorInducedPassiveFalseSharing}.
    193 As for cache thrash, if memory is allocated for multiple threads on the same cache line, this can significantly slow down program performance.
     192As with cache thrash, if memory is allocated for multiple threads on the same cache line, this can significantly slow down program performance.
    194193In this scenario, the false sharing is being caused by the memory allocator although it is started by the program sharing an object.
    195194
    … …  
    202201Cache scratch tries to create a scenario that leads to false sharing and should make the memory allocator preserve the program-induced false sharing, if it does not return a freed object to its owner thread and, instead, re-uses it instantly.
    203202An allocator using object ownership, as described in section \VRef{s:Ownership}, is less susceptible to allocator-induced passive false-sharing.
    204 If the object is returned to the thread who owns it, then the thread that gets a new object is less likely to be on the same cache line.
     203\PAB{If the object is returned to the thread that owns it, then the new object that the thread gets is less likely to be on the same cache line.}
    205204
    206205\VRef[Figure]{fig:benchScratchFig} shows the pseudo code for the cache-scratch micro-benchmark.
    … …  
    224223        signal workers to free
    225224        ...
    226         print addresses from each $thread$
    227225Worker Thread$\(_1\)$
    228         allocate, write, read, free
    229         warmup memory in chunkc of 16 bytes
    230         ...
    231         for ( N )
    232                 free an object passed by Main Thread
     226        warmup memory in chunks of 16 bytes
     227        ...
     228        free the object passed by the Main Thread
     229        For N
    233230                malloc new object
    234         ...
    235         free objects
    236         return new object addresses to Main Thread
     231                read/write the object M times
     232                free the object
     233        ...
    237234Worker Thread$\(_2\)$
    238235        // same as Worker Thread$\(_1\)$
    … …  
    332329\VRef[Figure]{fig:MemoryBenchFig} shows the pseudo code for the memory micro-benchmark.
    333330It creates a producer-consumer scenario with K producer threads and each producer has M consumer threads.
    334 A producer has a separate buffer for each consumer and allocates N objects of random sizes following a settable distribution for each consumer.
     331A producer has a separate buffer for each consumer and allocates N objects of random sizes following a configurable distribution for each consumer.
    335332A consumer frees these objects.
    336333After every memory operation, program memory usage is recorded throughout the runtime.

  • doc/theses/mubeen_zulfiqar_MMath/conclusion.tex

    rd8075d28 r29d8c02  
    1717% ====================
    1818
    19 The goal of this thesis was to build a low-latency memory allocator for both KT and UT multi-threads systems, which is competitive with the best current memory allocators, while extending the feature set of existing and new allocator routines.
     19The goal of this thesis was to build a low-latency (or high bandwidth) memory allocator for both KT and UT multi-threading systems that is competitive with the best current memory allocators while extending the feature set of existing and new allocator routines.
    2020The new llheap memory-allocator achieves all of these goals, while maintaining and managing sticky allocation information without a performance loss.
    2121Hence, it becomes possible to use @realloc@ frequently as a safe operation, rather than just occasionally.
    2222Furthermore, the ability to query sticky properties and information allows programmers to write safer programs, as it is possible to dynamically match allocation styles from unknown library routines that return allocations.
    2323
    24 Extending the C allocation API with @resize@, advanced @realloc@, @aalloc@, @amemalign@, and @cmemalign@ means programmers do not make mistakes writing theses useful allocation operations.
     24Extending the C allocation API with @resize@, advanced @realloc@, @aalloc@, @amemalign@, and @cmemalign@ means programmers do not have to do these useful allocation operations themselves.
    2525The ability to use \CFA's advanced type-system (and possibly \CC's too) to have one allocation routine with completely orthogonal sticky properties shows how far the allocation API can be pushed, which increases safety and greatly simplifies programmer's use of dynamic allocation.
    2626
    2727Providing comprehensive statistics for all allocation operations is invaluable in understanding and debugging a program's dynamic behaviour.
    28 No other memory allocator provides comprehensive statistics gathering.
     28No other memory allocator provides such comprehensive statistics gathering.
    2929This capability was used extensively during the development of llheap to verify its behaviour.
    3030As well, providing a debugging mode where allocations are checked, along with internal pre/post conditions and invariants, is extremely useful, especially for students.
    31 While not as powerful as the @valgrind@ interpreter, a large number of allocations mistakes are detected.
     31While not as powerful as the @valgrind@ interpreter, a large number of allocation mistakes are detected.
    3232Finally, contention-free statistics gathering and debugging have a low enough cost to be used in production code.
    3333
    … …  
    3636
    3737Starting a micro-benchmark test-suite for comparing allocators, rather than relying on a suite of arbitrary programs, has been an interesting challenge.
    38 The current micro-benchmarks allow some understand of allocator implementation properties without actually looking at the implementation.
     38The current micro-benchmarks allow some understanding of allocator implementation properties without actually looking at the implementation.
    3939For example, the memory micro-benchmark quickly identified how several of the allocators work at the global level.
    4040It was not possible to show how the micro-benchmarks adjustment knobs were used to tune to an interesting test point.
    … …  
    4545
    4646A careful walk-though of the allocator fastpath should yield additional optimizations for a slight performance gain.
    47 In particular, looking at the implementation of rpmalloc, which is often the fastest allocator,
     47In particular, analysing the implementation of rpmalloc, which is often the fastest allocator,
    4848
    49 The micro-benchmarks project requires more testing and analysis.
    50 Additional allocations patterns are needed to extract meaningful information about allocators, and within allocation patterns, what are the best tuning knobs.
     49The micro-benchmark project requires more testing and analysis.
     50Additional allocation patterns are needed to extract meaningful information about allocators, and within allocation patterns, what are the most useful tuning knobs.
    5151Also, identifying ways to visualize the results of the micro-benchmarks is a work in progress.
    5252
    53 After llheap is made available on gitHub, interacting with its users to locate problems and improvements, will make llbench a more robust memory allocator.
    54 As well, feedback from the \uC and \CFA projects, which have adopted llheap for their memory allocator, will provide additional feedback.
     53After llheap is made available on GitHub, interacting with its users to locate problems and improvements will make llbench a more robust memory allocator.
     54As well, feedback from the \uC and \CFA projects, which have adopted llheap for their memory allocator, will provide additional information.

  • doc/theses/mubeen_zulfiqar_MMath/intro.tex

    rd8075d28 r29d8c02  
    5353When this allocator proves inadequate, programmers often write specialize allocators for specific needs.
    5454C and \CC allow easy replacement of the default memory allocator with an alternative specialized or general-purpose memory-allocator.
    55 (Jikes RVM MMTk~\cite{MMTk} provides a similar generalization for the Java virtual machine.)
     55Jikes RVM MMTk~\cite{MMTk} provides a similar generalization for the Java virtual machine.
    5656However, high-performance memory-allocators for kernel and user multi-threaded programs are still being designed and improved.
    5757For this reason, several alternative general-purpose allocators have been written for C/\CC with the goal of scaling in a multi-threaded program~\cite{Berger00,mtmalloc,streamflow,tcmalloc}.
    … …  
    6565\begin{enumerate}[leftmargin=*]
    6666\item
    67 Implementation of a new stand-lone concurrent low-latency memory-allocator ($\approx$1,200 lines of code) 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).
    68 
    69 \item
    70 Adopt @nullptr@ return for a zero-sized allocation, rather than an actual memory address, which can be passed to @free@.
     67Implementation 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 of the allocator for the programming languages \uC and \CFA using user-level threads running over multiple kernel threads (M:N threading).
    7168
    7269\item
    … …  
    104101
    105102\item
    106 Provide additional heap wrapper functions in \CFA creating an orthogonal set of allocation operations and properties.
     103Provide additional heap wrapper functions in \CFA creating a more usable set of allocation operations and properties.
    107104
    108105\item
    … …  
    111108\item
    112109@malloc_alignment( addr )@ returns the alignment of the allocation pointed-to by @addr@.
    113 If the allocation is not aligned or @addr@ is the @nulladdr@, the minimal alignment is returned.
     110If the allocation is not aligned or @addr@ is the @NULL@, the minimal alignment is returned.
    114111\item
    115112@malloc_zero_fill( addr )@ returns a boolean result indicating if the memory pointed-to by @addr@ is allocated with zero fill, e.g., by @calloc@/@cmemalign@.
    … …  
    119116@malloc_usable_size( addr )@ returns the usable (total) size of the memory pointed-to by @addr@, i.e., the bin size containing the allocation, where @malloc_size( addr )@ $\le$ @malloc_usable_size( addr )@.
    120117\end{itemize}
    121 
    122 \item
    123 Provide mostly contention-free allocation and free operations via a heap-per-kernel-thread implementation.
    124118
    125119\item
    … …  
    136130
    137131\item
    138 Provide extensive runtime checks to valid allocation operations and identify the amount of unfreed storage at program termination.
     132Provide extensive runtime checks to validate allocation operations and identify the amount of unfreed storage at program termination.
    139133
    140134\item

  • doc/theses/mubeen_zulfiqar_MMath/performance.tex

    rd8075d28 r29d8c02  
    33
    44This chapter uses the micro-benchmarks from \VRef[Chapter]{s:Benchmarks} to test a number of current memory allocators, including llheap.
    5 The goal is to see if llheap is competitive with the current best memory allocators.
     5The goal is to see if llheap is competitive with the currently popular memory allocators.
    66
    77
    … …  
    1111\begin{itemize}
    1212\item
     13\textbf{Algol} Huawei ARM TaiShan 2280 V2 Kunpeng 920, 24-core socket $\times$ 4, 2.6 GHz, GCC version 9.4.0
     14\item
    1315\textbf{Nasus} AMD EPYC 7662, 64-core socket $\times$ 2, 2.0 GHz, GCC version 9.3.0
    14 \item
    15 \textbf{Algol} Huawei ARM TaiShan 2280 V2 Kunpeng 920, 24-core socket $\times$ 4, 2.6 GHz, GCC version 9.4.0
    1616\end{itemize}
    1717
    … …  
    3131
    3232\paragraph{glibc (\textsf{glc})}
    33 \cite{glibc} is the default gcc thread-safe allocator.
     33\cite{glibc} is the default glibc thread-safe allocator.
    3434\\
    3535\textbf{Version:} Ubuntu GLIBC 2.31-0ubuntu9.7 2.31\\
    … …  
    4646
    4747\paragraph{hoard (\textsf{hrd})}
    48 \cite{hoard} is a thread-safe allocator that is multi-threaded and using a heap layer framework. It has per-thread heaps that have thread-local free-lists, and a global shared heap.
     48\cite{hoard} is a thread-safe allocator that is multi-threaded and uses a heap layer framework. It has per-thread heaps that have thread-local free-lists, and a global shared heap.
    4949\\
    5050\textbf{Version:} 3.13\\
    … …  
    7878
    7979\paragraph{tbb malloc (\textsf{tbb})}
    80 \cite{tbbmalloc} is a thread-safe allocator that is multi-threaded and uses private heap for each thread.
     80\cite{tbbmalloc} is a thread-safe allocator that is multi-threaded and uses a private heap for each thread.
    8181Each private-heap has multiple bins of different sizes. Each bin contains free regions of the same size.
    8282\\
    … …  
    9090\section{Experiments}
    9191
    92 The each micro-benchmark is configured and run with each of the allocators,
    93 The less time an allocator takes to complete a benchmark the better, so lower in the graphs is better.
     92Each micro-benchmark is configured and run with each of the allocators,
     93\PAB{The less time an allocator takes to complete a benchmark the better so lower in the graphs is better, except for the Memory micro-benchmark graphs.}
    9494All graphs use log scale on the Y-axis, except for the Memory micro-benchmark (see \VRef{s:MemoryMicroBenchmark}).
    9595
    … …  
    231231Second is the low-performer group, which includes the rest of the memory allocators.
    232232These memory allocators have significant program-induced passive false-sharing, where \textsf{hrd}'s is the worst performing allocator.
    233 All of the allocator's in this group are sharing heaps among threads at some level.
    234 
    235 Interestingly, allocators such as \textsf{hrd} and \textsf{glc} performed well in micro-benchmark cache thrash (see \VRef{sec:cache-thrash-perf}).
    236 But, these allocators are among the low performers in the cache scratch.
    237 It suggests these allocators do not actively produce false-sharing but preserve program-induced passive false sharing.
     233All of the allocators in this group are sharing heaps among threads at some level.
     234
     235Interestingly, allocators such as \textsf{hrd} and \textsf{glc} performed well in micro-benchmark cache thrash (see \VRef{sec:cache-thrash-perf}), but, these allocators are among the low performers in the cache scratch.
     236It suggests these allocators do not actively produce false-sharing, but preserve program-induced passive false sharing.
    238237
    239238%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  • doc/theses/mubeen_zulfiqar_MMath/uw-ethesis-frontpgs.tex

    rd8075d28 r29d8c02  
    1313        \vspace*{1.0cm}
    1414
    15         {\Huge\bf \CFA Memory Allocation}
     15        {\Huge\bf High-Performance Concurrent Memory Allocation}
    1616
    1717        \vspace*{1.0cm}
    … …  
    136136
    137137The goal of this thesis is to build a low-latency memory allocator for both kernel and user multi-threaded systems, which is competitive with the best current memory allocators, while extending the feature set of existing and new allocator routines.
    138 A new llheap memory-allocator is created that achieves all of these goals, while maintaining and managing sticky allocation properties for zero-fill and alignment allocations without a performance loss.
     138A new llheap memory-allocator is created that achieves all of these goals, while maintaining and managing sticky allocation properties for zero-filled and aligned allocations without a performance loss.
    139139Hence, it becomes possible to use @realloc@ frequently as a safe operation, rather than just occasionally, because it preserves sticky properties when enlarging storage requests.
    140140Furthermore, the ability to query sticky properties and information allows programmers to write safer programs, as it is possible to dynamically match allocation styles from unknown library routines that return allocations.
    141141The C allocation API is also extended with @resize@, advanced @realloc@, @aalloc@, @amemalign@, and @cmemalign@ so programmers do not make mistakes writing theses useful allocation operations.
    142142llheap is embedded into the \uC and \CFA runtime systems, both of which have user-level threading.
    143 The ability to use \CFA's advanced type-system (and possibly \CC's too) to have one allocation routine with completely orthogonal sticky properties shows how far the allocation API can be pushed, which increases safety and greatly simplifies programmer's use of dynamic allocation.
     143\PAB{The ability to use \CFA's advanced type-system (and possibly \CC's too) to have one allocation routine with advanced memory operations as positional arguments shows how far the allocation API can be pushed, which increases safety and greatly simplifies programmer's use of dynamic allocation.}
    144144
    145145The llheap allocator also provides comprehensive statistics for all allocation operations, which are invaluable in understanding and debugging a program's dynamic behaviour.
    146 No other memory allocator examined in the thesis provides comprehensive statistics gathering.
    147 As well, llheap provides a debugging mode where allocations are checked, along with internal pre/post conditions and invariants, is extremely useful, especially for students.
     146No other memory allocator examined in the thesis provides such comprehensive statistics gathering.
     147As well, llheap provides a debugging mode where allocations are checked with internal pre/post conditions and invariants. It is extremely useful, especially for students.
    148148While not as powerful as the @valgrind@ interpreter, a large number of allocations mistakes are detected.
    149149Finally, contention-free statistics gathering and debugging have a low enough cost to be used in production code.
    150150
    151 A micro-benchmark test-suite is started for comparing allocators, rather than relying on a suite of arbitrary programs, has been an interesting challenge.
     151A micro-benchmark test-suite is started for comparing allocators, rather than relying on a suite of arbitrary programs. It has been an interesting challenge.
    152152These micro-benchmarks have adjustment knobs to simulate allocation patterns hard-coded into arbitrary test programs.
    153 Existing memory allocators, glibc, dlmalloc, hoard, jemalloc, ptmalloc3, rpmalloc, tbmalloc and the new allocator llheap are all compared using the new micro-benchmark test-suite.
     153Existing memory allocators, glibc, dlmalloc, hoard, jemalloc, ptmalloc3, rpmalloc, tbmalloc, and the new allocator llheap are all compared using the new micro-benchmark test-suite.
    154154\cleardoublepage
    155155
Note: See TracChangeset for help on using the changeset viewer.