Changeset 765ee42


Ignore:
Timestamp:
Jan 27, 2024, 11:27:34 PM (3 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
master
Children:
baa1d5d
Parents:
dd1ebb1
Message:

some updates on the llheap paper

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/papers/llheap/Paper.tex

    rdd1ebb1 r765ee42  
    7777\lstset{
    7878columns=fullflexible,
    79 basicstyle=\linespread{0.9}\sf,                                                 % reduce line spacing and use sanserif font
    80 stringstyle=\tt,                                                                                % use typewriter font
    81 tabsize=5,                                                                                              % N space tabbing
    82 xleftmargin=\parindentlnth,                                                             % indent code to paragraph indentation
    83 %mathescape=true,                                                                               % LaTeX math escape in CFA code $...$
    84 escapechar=\$,                                                                                  % LaTeX escape in CFA code
    85 keepspaces=true,                                                                                %
    86 showstringspaces=false,                                                                 % do not show spaces with cup
    87 showlines=true,                                                                                 % show blank lines at end of code
    88 aboveskip=4pt,                                                                                  % spacing above/below code block
    89 belowskip=3pt,
    90 moredelim=**[is][\color{red}]{`}{`},
     79basicstyle=\linespread{0.9}\sf,                 % reduce line spacing and use sanserif font
     80stringstyle=\small\tt,                                  % use typewriter font
     81tabsize=5,                                                              % N space tabbing
     82xleftmargin=\parindentlnth,                             % indent code to paragraph indentation
     83escapechar=\$,                                                  % LaTeX escape in CFA code
     84%mathescape=true,                                               % LaTeX math escape in CFA code $...$
     85keepspaces=true,                                                %
     86showstringspaces=false,                                 % do not show spaces with cup
     87showlines=true,                                                 % show blank lines at end of code
     88aboveskip=4pt,                                                  % spacing above/below code block
     89belowskip=2pt,
     90numberstyle=\footnotesize\sf,                   % numbering style
     91moredelim=**[is][\color{red}]{@}{@},
    9192}% lstset
    9293
     
    10821083
    10831084The 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.
    1084 (Large allocations requiring initialization, \eg zero fill, and/or copying are not covered by the low-latency objective.)
     1085Excluded from the low-latency objective are (large) allocations requiring initialization, \eg zero fill, and/or data copying, which are outside the allocator's purview.
    10851086A direct consequence of this objective is very simple or no storage coalescing;
    10861087hence, llheap's design is willing to use more storage to lower latency.
    10871088This objective is apropos because systems research and industrial applications are striving for low latency and computers have huge amounts of RAM memory.
    1088 Finally, llheap's performance should be comparable with the current best allocators (see performance comparison in Section~\ref{c:Performance}).
     1089Finally, llheap's performance should be comparable with the current best allocators, both in space and time (see performance comparison in Section~\ref{c:Performance}).
    10891090
    10901091% The objective of llheap's new design was to fulfill following requirements:
     
    12051206% \label{s:AllocationFastpath}
    12061207
    1207 llheap's design was reviewed and changed multiple times during its development.  Only the final design choices are
    1208 discussed in this paper.
     1208llheap's design was reviewed and changed multiple times during its development, with the final choices are discussed here.
    12091209(See~\cite{Zulfiqar22} for a discussion of alternate choices and reasons for rejecting them.)
    12101210All designs were analyzed for the allocation/free \newterm{fastpath}, \ie when an allocation can immediately return free storage or returned storage is not coalesced.
    1211 The heap model choosen is 1:1, which is the T:H model with T = H, where there is one thread-local heap for each KT.
     1211The 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.
    12121212(See Figure~\ref{f:THSharedHeaps} but with a heap bucket per KT and no bucket or local-pool lock.)
    12131213Hence, immediately after a KT starts, its heap is created and just before a KT terminates, its heap is (logically) deleted.
     
    14261426
    14271427
    1428 Algorithm~\ref{alg:heapObjectFreeOwn} shows the de-allocation (free) outline for an object at address $A$ with ownership.
     1428Algorithm~\ref{alg:heapObjectFreeOwn} shows the deallocation (free) outline for an object at address $A$ with ownership.
    14291429First, the address is divided into small (@sbrk@) or large (@mmap@).
    14301430For large allocations, the storage is unmapped back to the OS.
     
    14331433If the bucket is not local to the thread, the allocation is pushed onto the owning thread's associated away stack.
    14341434
    1435 Algorithm~\ref{alg:heapObjectFreeNoOwn} shows the de-allocation (free) outline for an object at address $A$ without ownership.
     1435Algorithm~\ref{alg:heapObjectFreeNoOwn} shows the deallocation (free) outline for an object at address $A$ without ownership.
    14361436The algorithm is the same as for ownership except if the bucket is not local to the thread.
    14371437Then the corresponding bucket of the owner thread is computed for the deallocating thread, and the allocation is pushed onto the deallocating thread's bucket.
     
    17921792The C dynamic-memory API is extended with the following routines:
    17931793
    1794 \paragraph{\lstinline{void * aalloc( size_t dim, size_t elemSize )}}
    1795 extends @calloc@ for allocating a dynamic array of objects without calculating the total size of array explicitly but \emph{without} zero-filling the memory.
    1796 @aalloc@ is significantly faster than @calloc@, which is the only alternative given by the standard memory-allocation routines.
    1797 
    1798 \noindent\textbf{Usage}
    1799 @aalloc@ takes two parameters.
    1800 \begin{itemize}[topsep=3pt,itemsep=2pt,parsep=0pt]
    1801 \item
    1802 @dim@: number of array objects
    1803 \item
    1804 @elemSize@: size of array object
    1805 \end{itemize}
     1794\medskip\noindent
     1795\lstinline{void * aalloc( size_t dim, size_t elemSize )}
     1796extends @calloc@ for allocating a dynamic array of objects with total size @dim@ $\times$ @elemSize@ but \emph{without} zero-filling the memory.
     1797@aalloc@ is significantly faster than @calloc@, which is the only alternative given by the standard memory-allocation routines for array allocation.
    18061798It returns the address of the dynamic array or @NULL@ if either @dim@ or @elemSize@ are zero.
    18071799
    1808 \paragraph{\lstinline{void * resize( void * oaddr, size_t size )}}
    1809 extends @realloc@ for resizing an existing allocation \emph{without} copying previous data into the new allocation or preserving sticky properties.
     1800\medskip\noindent
     1801\lstinline{void * resize( void * oaddr, size_t size )}
     1802extends @realloc@ for resizing an existing allocation, @oaddr@, to the new @size@ (smaller or larger than previous) \emph{without} copying previous data into the new allocation or preserving sticky properties.
    18101803@resize@ is significantly faster than @realloc@, which is the only alternative.
    1811 
    1812 \noindent\textbf{Usage}
    1813 @resize@ takes two parameters.
    1814 \begin{itemize}[topsep=3pt,itemsep=2pt,parsep=0pt]
    1815 \item
    1816 @oaddr@: address to be resized
    1817 \item
    1818 @size@: new allocation size (smaller or larger than previous)
    1819 \end{itemize}
    18201804It returns the address of the old or new storage with the specified new size or @NULL@ if @size@ is zero.
    18211805
    1822 \paragraph{\lstinline{void * amemalign( size_t alignment, size_t dim, size_t elemSize )}}
    1823 extends @aalloc@ and @memalign@ for allocating an aligned dynamic array of objects.
     1806\medskip\noindent
     1807\lstinline{void * amemalign( size_t alignment, size_t dim, size_t elemSize )}
     1808extends @aalloc@ and @memalign@ for allocating a dynamic array of objects with the starting address on the @alignment@ boundary.
    18241809Sets sticky alignment property.
    1825 
    1826 \noindent\textbf{Usage}
    1827 @amemalign@ takes three parameters.
    1828 \begin{itemize}[topsep=3pt,itemsep=2pt,parsep=0pt]
    1829 \item
    1830 @alignment@: alignment requirement
    1831 \item
    1832 @dim@: number of array objects
    1833 \item
    1834 @elemSize@: size of array object
    1835 \end{itemize}
    18361810It returns the address of the aligned dynamic-array or @NULL@ if either @dim@ or @elemSize@ are zero.
    18371811
    1838 \paragraph{\lstinline{void * cmemalign( size_t alignment, size_t dim, size_t elemSize )}}
     1812\medskip\noindent
     1813\lstinline{void * cmemalign( size_t alignment, size_t dim, size_t elemSize )}
    18391814extends @amemalign@ with zero fill and has the same usage as @amemalign@.
    18401815Sets sticky zero-fill and alignment property.
    18411816It returns the address of the aligned, zero-filled dynamic-array or @NULL@ if either @dim@ or @elemSize@ are zero.
    18421817
    1843 \paragraph{\lstinline{size_t malloc_alignment( void * addr )}}
    1844 returns the alignment of the dynamic object for use in aligning similar allocations.
    1845 
    1846 \noindent\textbf{Usage}
    1847 @malloc_alignment@ takes one parameter.
    1848 \begin{itemize}[topsep=3pt,itemsep=2pt,parsep=0pt]
    1849 \item
    1850 @addr@: address of an allocated object.
    1851 \end{itemize}
    1852 It returns the alignment of the given object, where objects not allocated with alignment return the minimal allocation alignment.
    1853 
    1854 \paragraph{\lstinline{bool malloc_zero_fill( void * addr )}}
    1855 returns true if the object has the zero-fill sticky property for use in zero filling similar allocations.
    1856 
    1857 \noindent\textbf{Usage}
    1858 @malloc_zero_fill@ takes one parameters.
    1859 
    1860 \begin{itemize}[topsep=3pt,itemsep=2pt,parsep=0pt]
    1861 \item
    1862 @addr@: address of an allocated object.
    1863 \end{itemize}
    1864 It returns true if the zero-fill sticky property is set and false otherwise.
    1865 
    1866 \paragraph{\lstinline{size_t malloc_size( void * addr )}}
    1867 returns the request size of the dynamic object (updated when an object is resized) for use in similar allocations.
    1868 See also @malloc_usable_size@.
    1869 
    1870 \noindent\textbf{Usage}
    1871 @malloc_size@ takes one parameters.
    1872 \begin{itemize}[topsep=3pt,itemsep=2pt,parsep=0pt]
    1873 \item
    1874 @addr@: address of an allocated object.
    1875 \end{itemize}
    1876 It returns the request size or zero if @addr@ is @NULL@.
    1877 
    1878 \paragraph{\lstinline{int malloc_stats_fd( int fd )}}
    1879 changes the file descriptor where @malloc_stats@ writes statistics (default @stdout@).
    1880 
    1881 \noindent\textbf{Usage}
    1882 @malloc_stats_fd@ takes one parameters.
    1883 \begin{itemize}[topsep=3pt,itemsep=2pt,parsep=0pt]
    1884 \item
    1885 @fd@: file descriptor.
    1886 \end{itemize}
    1887 It returns the previous file descriptor.
    1888 
    1889 \paragraph{\lstinline{size_t malloc_expansion()}}
     1818\medskip\noindent
     1819\lstinline{size_t malloc_alignment( void * addr )}
     1820returns the object alignment, where objects not allocated with alignment return the minimal allocation alignment.
     1821For use in aligning similar allocations.
     1822
     1823\medskip\noindent
     1824\lstinline{bool malloc_zero_fill( void * addr )}
     1825returns true if the objects zero-fill sticky property is set and false otherwise.
     1826For use in zero filling similar allocations.
     1827
     1828\medskip\noindent
     1829\lstinline{size_t malloc_size( void * addr )}
     1830returns the object's request size, which is updated when an object is resized or zero if @addr@ is @NULL@ (see also @malloc_usable_size@).
     1831For use in similar allocations.
     1832
     1833\medskip\noindent
     1834\lstinline{int malloc_stats_fd( int fd )}
     1835changes the file descriptor where @malloc_stats@ writes statistics (default @stdout@) and returns the previous file descriptor.
     1836
     1837\medskip\noindent
     1838\lstinline{size_t malloc_expansion()}
    18901839\label{p:malloc_expansion}
    18911840set the amount (bytes) to extend the heap when there is insufficient free storage to service an allocation request.
    18921841It 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.
    18931842
    1894 \paragraph{\lstinline{size_t malloc_mmap_start()}}
     1843\medskip\noindent
     1844\lstinline{size_t malloc_mmap_start()}
    18951845set the crossover between allocations occurring in the @sbrk@ area or separately mapped.
    18961846It returns the crossover point used throughout a program, \ie called once at heap initialization.
    18971847
    1898 \paragraph{\lstinline{size_t malloc_unfreed()}}
     1848\medskip\noindent
     1849\lstinline{size_t malloc_unfreed()}
    18991850\label{p:malloc_unfreed}
    19001851amount subtracted to adjust for unfreed program storage (debug only).
    1901 It returns the new subtraction amount and called by @malloc_stats@.
     1852It returns the new subtraction amount and called by @malloc_stats@ (discussed in Section~\ref{}).
    19021853
    19031854
     
    19061857The following extensions take advantage of overload polymorphism in the \CC type-system.
    19071858
    1908 \paragraph{\lstinline{void * resize( void * oaddr, size_t nalign, size_t size )}}
    1909 extends @resize@ with an alignment re\-quirement.
    1910 
    1911 \noindent\textbf{Usage}
    1912 takes three parameters.
    1913 \begin{itemize}[topsep=3pt,itemsep=2pt,parsep=0pt]
    1914 \item
    1915 @oaddr@: address to be resized
    1916 \item
    1917 @nalign@: alignment requirement
    1918 \item
    1919 @size@: new allocation size (smaller or larger than previous)
    1920 \end{itemize}
     1859\medskip\noindent
     1860\lstinline{void * resize( void * oaddr, size_t nalign, size_t size )}
     1861extends @resize@ with an alignment requirement, @nalign@.
    19211862It returns the address of the old or new storage with the specified new size and alignment, or @NULL@ if @size@ is zero.
    19221863
    1923 \paragraph{\lstinline{void * realloc( void * oaddr, size_t nalign, size_t size )}}
    1924 extends @realloc@ with an alignment re\-quirement and has the same usage as aligned @resize@.
     1864\medskip\noindent
     1865\lstinline{void * realloc( void * oaddr, size_t nalign, size_t size )}
     1866extends @realloc@ with an alignment requirement, @nalign@.
     1867It returns the address of the old or new storage with the specified new size and alignment, or @NULL@ if @size@ is zero.
    19251868
    19261869
     
    19791922object size: like the \CFA's C-interface, programmers do not have to specify object size or cast allocation results.
    19801923\end{itemize}
    1981 Note, postfix function call is an alternative call syntax, using backtick @`@, where the argument appears before the function name, \eg
     1924Note, postfix function call is an alternative call syntax, using backtick @`@, so the argument appears before the function name, \eg
    19821925\begin{cfa}
    19831926duration ?@`@h( int h );                // ? denote the position of the function operand
     
    19871930\end{cfa}
    19881931
    1989 \paragraph{\lstinline{T * alloc( ... )} or \lstinline{T * alloc( size_t dim, ... )}}
     1932The following extensions take advantage of overload polymorphism in the \CC type-system.
     1933
     1934\medskip\noindent
     1935\lstinline{T * alloc( ... )} or \lstinline{T * alloc( size_t dim, ... )}
    19901936is overloaded with a variable number of specific allocation operations, or an integer dimension parameter followed by a variable number of specific allocation operations.
    19911937These allocation operations can be passed as named arguments when calling the \lstinline{alloc} routine.
     
    19961942
    19971943The allocation property functions are:
    1998 \subparagraph{\lstinline{T_align ?`align( size_t alignment )}}
     1944
     1945\medskip\noindent
     1946\lstinline{T_align ?`align( size_t alignment )}
    19991947to align the allocation.
    2000 The alignment parameter must be $\ge$ the default alignment (@libAlign()@ in \CFA) and a power of two, \eg:
     1948The alignment parameter must be $\ge$ the default alignment (@libAlign()@ in \CFA) and a power of two.
     1949The following example returns a dynamic object and object array aligned on a 4096-byte boundary.
    20011950\begin{cfa}
    20021951int * i0 = alloc( @4096`align@ );  sout | i0 | nl;
     
    200619550x555555574000 0x555555574000 0x555555574004 0x555555574008
    20071956\end{cfa}
    2008 returns a dynamic object and object array aligned on a 4096-byte boundary.
    2009 
    2010 \subparagraph{\lstinline{S_fill(T) ?`fill ( /* various types */ )}}
     1957
     1958\medskip\noindent
     1959\lstinline{S_fill(T) ?`fill ( /* various types */ )}
    20111960to initialize storage.
    20121961There are three ways to fill storage:
    2013 \begin{enumerate}
     1962\begin{enumerate}[itemsep=0pt,parsep=0pt]
    20141963\item
    20151964A char fills each byte of each object.
     
    20201969\end{enumerate}
    20211970For example:
    2022 \begin{cfa}[numbers=left]
     1971\begin{cfa}[numbers=left,xleftmargin=2.5\parindentlnth]
    20231972int * i0 = alloc( @0n`fill@ );  sout | *i0 | nl;  // disambiguate 0
    20241973int * i1 = alloc( @5`fill@ );  sout | *i1 | nl;
     
    20291978int * i6 = alloc( 5, @[i3, 3]`fill@ );  for ( i; 5 ) sout | i6[i]; sout | nl;
    20301979\end{cfa}
    2031 \begin{lstlisting}[numbers=left]
     1980\begin{lstlisting}[numbers=left,xleftmargin=2.5\parindentlnth]
    203219810
    203319825
     
    20411990Examples 4 to 7 fill an array of objects with values, another array, or part of an array.
    20421991
    2043 \subparagraph{\lstinline{S_resize(T) ?`resize( void * oaddr )}}
     1992\medskip\noindent
     1993\lstinline{S_resize(T) ?`resize( void * oaddr )}
    20441994used to resize, realign, and fill, where the old object data is not copied to the new object.
    20451995The old object type may be different from the new object type, since the values are not used.
    20461996For example:
    2047 \begin{cfa}[numbers=left]
     1997\begin{cfa}[numbers=left,xleftmargin=2.5\parindentlnth]
    20481998int * i = alloc( @5`fill@ );  sout | i | *i;
    20491999i = alloc( @i`resize@, @256`align@, @7`fill@ );  sout | i | *i;
    20502000double * d = alloc( @i`resize@, @4096`align@, @13.5`fill@ );  sout | d | *d;
    20512001\end{cfa}
    2052 \begin{lstlisting}[numbers=left]
     2002\begin{lstlisting}[numbers=left,xleftmargin=2.5\parindentlnth]
    205320030x55555556d5c0 5
    205420040x555555570000 7
     
    20572007Examples 2 to 3 change the alignment, fill, and size for the initial storage of @i@.
    20582008
    2059 \begin{cfa}[numbers=left]
     2009\begin{cfa}[numbers=left,xleftmargin=2.5\parindentlnth]
    20602010int * ia = alloc( 5, @5`fill@ );  for ( i; 5 ) sout | ia[i]; sout | nl;
    20612011ia = alloc( 10, @ia`resize@, @7`fill@ ); for ( i; 10 ) sout | ia[i]; sout | nl;
     
    20632013ia = alloc( 3, @ia`resize@, @4096`align@, @2`fill@ );  sout | ia; for ( i; 3 ) sout | &ia[i] | ia[i]; sout | nl;
    20642014\end{cfa}
    2065 \begin{lstlisting}[numbers=left]
     2015\begin{lstlisting}[numbers=left,xleftmargin=2.5\parindentlnth]
    206620165 5 5 5 5
    206720177 7 7 7 7 7 7 7 7 7
     
    20712021Examples 2 to 4 change the array size, alignment and fill for the initial storage of @ia@.
    20722022
    2073 \subparagraph{\lstinline{S_realloc(T) ?`realloc( T * a ))}}
     2023\medskip\noindent
     2024\lstinline{S_realloc(T) ?`realloc( T * a ))}
    20742025used to resize, realign, and fill, where the old object data is copied to the new object.
    20752026The old object type must be the same as the new object type, since the value is used.
    20762027Note, for @fill@, only the extra space after copying the data from the old object is filled with the given parameter.
    20772028For example:
    2078 \begin{cfa}[numbers=left]
     2029\begin{cfa}[numbers=left,xleftmargin=2.5\parindentlnth]
    20792030int * i = alloc( @5`fill@ );  sout | i | *i;
    20802031i = alloc( @i`realloc@, @256`align@ );  sout | i | *i;
    20812032i = alloc( @i`realloc@, @4096`align@, @13`fill@ );  sout | i | *i;
    20822033\end{cfa}
    2083 \begin{lstlisting}[numbers=left]
     2034\begin{lstlisting}[numbers=left,xleftmargin=2.5\parindentlnth]
    208420350x55555556d5c0 5
    208520360x555555570000 5
     
    20892040The @13`fill@ in example 3 does nothing because no extra space is added.
    20902041
    2091 \begin{cfa}[numbers=left]
     2042\begin{cfa}[numbers=left,xleftmargin=2.5\parindentlnth]
    20922043int * ia = alloc( 5, @5`fill@ );  for ( i; 5 ) sout | ia[i]; sout | nl;
    20932044ia = alloc( 10, @ia`realloc@, @7`fill@ ); for ( i; 10 ) sout | ia[i]; sout | nl;
     
    20952046ia = alloc( 3, @ia`realloc@, @4096`align@, @2`fill@ );  sout | ia; for ( i; 3 ) sout | &ia[i] | ia[i]; sout | nl;
    20962047\end{cfa}
    2097 \begin{lstlisting}[numbers=left]
     2048\begin{lstlisting}[numbers=left,xleftmargin=2.5\parindentlnth]
    209820495 5 5 5 5
    209920505 5 5 5 5 7 7 7 7 7
Note: See TracChangeset for help on using the changeset viewer.