Context Navigation

-                      ra885357
+                      r16c795c
 \label{s:MultipleHeaps}
 Figure~\ref{f:ThreadHeapRelationship} shows how a multi-threaded allocator can subdivide a single global heap into multiple heaps to reduce contention among threads.
+Figure~\ref{f:ThreadHeapRelationship} shows how a multi-threaded allocator reduced contention by subdividing a single heap into multiple heaps.
 \begin{figure}
 …
 \begin{description}[leftmargin=*]
 \item[T:1 model (Figure~\ref{f:SingleHeap})] has all threads allocating and deallocating objects from one heap.
+Memory is obtained from the freed objects, or reserved memory in the heap, or from the OS;
+the heap may also return freed memory to the OS.
 The arrows indicate the direction memory moves for each alocation/deallocation operation.
 To safely handle concurrency, a single lock may be used for all heap operations or fine-grained locking for different operations.
 Regardless, a single heap is a significant source of contention for threaded programs with a large amount of memory allocations.
 \item[T:H model (Figure~\ref{f:SharedHeaps})] subdivides the heap independently from the threads.
 The decision to create a heap and which heap a thread allocates/deallocates during its lifetime depends on the allocator design.
 Locking is required within each heap because of multiple tread access, but contention is reduced because fewer threads access a specific heap.
 The goal is to have mininal heaps (storage) and thread contention per heap (time).
 However, the worst case results in more heaps than threads, \eg if the number of threads is large at startup creating a large number of heaps and then the number of threads reduces.
+\item[T:1 model (Figure~\ref{f:SingleHeap})] is all threads (T) sharing a single heap (1).
+The arrows indicate memory movement for allocation/deallocation operations.
+Memory is obtained from freed objects, reserved memory, or the OS;
+freed memory can be returned to the OS.
+To handle concurrency, a single lock is used for all heap operations or fine-grained locking if operations can be made independent.
+As threads perform large numbers of allocations, a single heap becomes a significant source of contention.
+\item[T:H model (Figure~\ref{f:SharedHeaps})] is multiple threads (T) sharing multiple heaps (H).
+The allocator independently allocates/deallocates heaps and assigns threads to heaps based on dynamic contention pressure.
+Locking is required within each heap, but contention is reduced because fewer threads access a specific heap.
+The goal is minimal heaps (storage) and contention per heap (time).
+A worst case is more heaps than threads, \eg many threads at startup create a large number of heaps and then the threads reduce.
 % For 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.
 …
 % Allocated and free objects are labelled by the thread or heap they are associated with.
 % (Links between free objects are removed for simplicity.)
 The management information for multiple heaps in the static zone must be able to locate all heaps.
 The management information for the heaps must reside in the dynamic-allocation zone if there are a variable number.
 Each heap in the dynamic zone is composed of a list of free objects and a pointer to its reserved memory.
 An 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.
 Because multiple threads can allocate/free/reallocate adjacent storage, all forms of false sharing may occur.
 Other storage-management options are to use @mmap@ to set aside (large) areas of virtual memory for each heap and suballocate each heap's storage within that area, pushing part of the storage management complexity back to the OS.
+% The management information for multiple heaps in the static zone must be able to locate all heaps.
+% The management information for the heaps must reside in the dynamic-allocation zone if there are a variable number.
+% Each heap in the dynamic zone is composed of a list of free objects and a pointer to its reserved memory.
+% An 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.
+% Because multiple threads can allocate/free/reallocate adjacent storage, all forms of false sharing may occur.
+% Other storage-management options are to use @mmap@ to set aside (large) areas of virtual memory for each heap and suballocate each heap's storage within that area, pushing part of the storage management complexity back to the OS.
 % \begin{figure}
 …
 In general, the cost is minimal since the majority of memory operations are completed without the use of the global heap.
+\item[1:1 model (Figure~\ref{f:PerThreadHeap})] has each thread with its own heap, eliminating most contention and locking because threads seldom access another thread's heap (see Section~\ref{s:Ownership}).
+An additional benefit of thread heaps is improved locality due to better memory layout.
+As each thread only allocates from its heap, all objects are consolidated in the storage area for that heap, better utilizing each CPUs cache and accessing fewer pages.
+In contrast, the T:H model spreads each thread's objects over a larger area in different heaps.
+Thread heaps can also reduces false-sharing, except at crucial boundaries overlapping memory from another thread's heap.
+For example, assume page boundaries coincide with cache line boundaries, if a thread heap always acquires pages of memory then no two threads share a page or cache line unless pointers are passed among them.
+% Hence, allocator-induced active false-sharing cannot occur because the memory for thread heaps never overlaps.
+When a thread terminates, there are two options for handling its thread heap.
+First is to free all objects in the thread heap to the global heap and destroy the thread heap.
+Second is to place the thread heap on a list of available heaps and reuse it for a new thread in the future.
+Destroying 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.
+Alternatively, reusing thread heaps may improve performance if the inheriting thread makes similar allocation requests as the thread that previously held the thread heap because any unfreed storage is immediately accessible.
+\item[1:1 model (Figure~\ref{f:PerThreadHeap})] is each thread (1) has a heap (1), eliminating most contention and locking if threads seldom access another thread's heap (see Section~\ref{s:Ownership}).
+A thread's objects are consolidated in its heap, better utilizing the cache and paging during thread execution.
+In contrast, the T:H model can spread thread objects over a larger area in different heaps.
+Thread heaps can also reduces false-sharing, unless there are overlapping memory boundaries from another thread's heap.
+%For example, assume page boundaries coincide with cache line boundaries, if a thread heap always acquires pages of memory then no two threads share a page or cache line unless pointers are passed among them.
+When a thread terminates, it can free its heap objects to the global heap, or the thread heap is retained as-is and reused for a new thread in the future.
+Destroying a heap can reduce external fragmentation sooner, since all free objects in the global heap are available for immediate reuse.
+Alternatively, reusing a heap can aid the inheriting thread, if it has a similar allocation pattern because the heap in primed with unfreed storage of the right sizes.
 \end{description}

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 16c795c for doc/papers/llheap

Legend:

doc/papers/llheap/Paper.tex

Download in other formats: