Changeset 2341e9a in git


Ignore:
Timestamp:
Sep 28, 2022, 4:59:26 PM (19 months ago)
Author:
Hans Schoenemann <hannes@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
787035145f531ce249dde09cbb3656225517b252
Parents:
1291fb4c2054a2414ab193f6b00166905b065f986386dd1edc45f589c6150f9bb200ee0e74fd6520
git-author:
Hans Schoenemann <hannes@mathematik.uni-kl.de>2022-09-28 16:59:26+02:00
git-committer:
GitHub <noreply@github.com>2022-09-28 16:59:26+02:00
Message:
Merge pull request #1153 from fchapoton/some_typos_in_doc

some typos in doc
Location:
doc
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • doc/memory/OMALLOC.texi

    r1291fb r2341e9a  
    5656
    5757@table @strong
    58 @item (1) allocation/deallocation of (small) memory blocks must be extremly fast
     58@item (1) allocation/deallocation of (small) memory blocks must be extremely fast
    5959If the allocation/deallocation of a memory blocks requires more than a
    6060couple of machine instructions it would become the bottleneck of the
    … …  
    6363@item (2) consecutive memory blocks in linked lists must have a high locality of reference
    6464Compared with the performed operations on list elements, cache misses
    65 (or, even worse, page misses) of memory blocks are extremly expensive:
     65(or, even worse, page misses) of memory blocks are extremely expensive:
    6666we estimate that one cache miss of a memory block costs at least ten
    6767or more list element operations. Hence, if the addresses of consecutive
    6868list elements are not physically closed to each other (i.e., if
    6969the linked lists have a low locality of reference), then resolving
    70 chache (or, page) misses would become the bottleneck of computations.
     70cache (or, page) misses would become the bottleneck of computations.
    7171@end table
    7272
    … …  
    103103@heading Principles of omalloc
    104104
    105 @code{omalloc} is a stand-alone, general-purpose memory managment
     105@code{omalloc} is a stand-alone, general-purpose memory management
    106106library which can be used by any program. Its major design goals were
    107107derived from the memory management requirements of @sc{Singular} (see above).
    … …  
    112112
    113113@code{omalloc} is specialized in the management of small memory
    114 blocks. The managment of large memory blocks, i.e., of memory blocks which
     114blocks. The management of large memory blocks, i.e., of memory blocks which
    115115are larger than "one fourth of the page size of the system" (usually
    116116appr. 1KByte) are (almost) left entirely to the underlying
    … …  
    132132on the  used memory allocation mechanism and its arguments (see
    133133below). The counter of the page is incremented, and the provided memory
    134 block is dequed from the free-list of the page.
     134block is dequeued from the free-list of the page.
    135135
    136136On @strong{memory deallocation}, the address of the memory block is used to
    … …  
    139139enqued into the free-list. If decrementing the counter yields zero,
    140140i.e., if there are no more used memory blocks in this page, then this
    141 page is dequed from its Bin and put back into a global pool of unused pages.
     141page is dequeued from its Bin and put back into a global pool of unused pages.
    142142
    143143
    … …  
    175175exclusive. When in its debugging mode, @code{omalloc} is set out to
    176176catch more than 20 errors in the usage of its API. And, of course, all
    177 the common and classical errors are among those which are cought by
     177the common and classical errors are among those which are caught by
    178178@code{omalloc}. Error reporting can either be directe3d to log files or to
    179179@code{stderr}. On some platforms, the error reporting does not only
    … …  
    184184@heading Requirement evaluation of @code{omalloc}
    185185After explaining its princples of @code{omalloc} let us evaluate
    186 @code{omalloc} w.r.t. the requirments stated above.
     186@code{omalloc} w.r.t. the requirements stated above.
    187187
    188188@table @strong
    … …  
    194194that this is optimal, i.e., as fast as one  possibly could implement
    195195these operations.
    196 @*The other interface levels incure the additional overhead of the
     196@*The other interface levels incur the additional overhead of the
    197197determination of the appropriate Bin (using a table lookup); and, for the
    198198function interface level, the additional overhead of function
    … …  
    202202@item (2) locality of reference
    203203Based on its design principles @code{omalloc} provides  an
    204 extremly high locality of reference (especially for consecutive elements
     204extremely high locality of reference (especially for consecutive elements
    205205of linked-list like structures). To realize this, recall that
    206206@itemize
    … …  
    210210when it becomes full or empty).
    211211@item
    212 the probabilty that consecutively allocated memory blocks are also
     212the probability that consecutively allocated memory blocks are also
    213213physically consecutive (i.e., that their physical addresses are consecutive)
    214214is rather high, since memory pages are spooled-back into the
    215215pool of unused pages as often as possible, and, hence, are reinitialized
    216 as often as possible (notice that allocationg from a freshly initialized
     216as often as possible (notice that allocating from a freshly initialized
    217217page assures that the physical addresses of consecutively allocated
    218218memory blocks are also consecutive).
    … …  
    225225long-lived, often traversed-over data.
    226226
    227 @item (3) small maintainance size overhead
     227@item (3) small maintenance size overhead
    228228
    229229Since @code{omalloc} manages small memory blocks on a per-page basis, there is
    230 no maintainance-overhead on a per-block basis, but only on a per-page
     230no maintenance-overhead on a per-block basis, but only on a per-page
    231231basis. This overhead amounts to 24 Bytes per memory
    232 page, i.e., we only need 24 Bytes maintanance overhead per 4096 Bytes,
     232page, i.e., we only need 24 Bytes maintenance overhead per 4096 Bytes,
    233233or 0.6%.
    234234@*For larger memory blocks, this overhead grows since there might
    235235be "leftovers" from the division of a memory page into equally-sized
    236236chunks of memory blocks. Furthermore, there is the additional (but
    237 rather small) overhead of keeping Bins and other "global" maintance
     237rather small) overhead of keeping Bins and other "global" maintenance
    238238structures.
    239 @*Nevertheless, on average, we observed a maintanance overhead of
     239@*Nevertheless, on average, we observed a maintenance overhead of
    240240appr. 1% of the total memory usage, which, to the best of our knowldege,
    241241is unsurpassed by any existing, general-purpose, memory manager.
    … …  
    251251efficienc/flexibility.
    252252
    253 W.r.t. the debugging mode has our experience shown that it is extremly
     253W.r.t. the debugging mode has our experience shown that it is extremely
    254254useful to be able to fine-tune the granularity of the debugging under both,
    255255a lexical, per-file base scope, and under a dynamic scope set at
    … …  
    259259no recompilations of @code{omalloc} are required to enable one or the other
    260260mode. As a summary @code{omalloc} debugging features can at least be
    261 compared with available memory managment debugging libraries (like
     261compared with available memory management debugging libraries (like
    262262@uref{http://dmalloc.com/,dmalloc}) -- our experience has furthermore
    263263showh that the features are suitable and appropriate for most practical
    … …  
    271271@heading Performance evaluation of @code{omalloc}
    272272
    273 We have no (yet) thouroughly  measured the performance of
    274 @code{omalloc} in comparison to other memory managment
     273We have no (yet) thoroughly  measured the performance of
     274@code{omalloc} in comparison to other memory management
    275275systems. Nevertheless, our first experiments yielded the following:
    276276@itemize
    … …  
    282282
    283283@item
    284 We expect that for programs/computations with similar compuational
     284We expect that for programs/computations with similar computational
    285285characteristics like those of @sc{Singular} (e.g., multivariate
    286286polynomial computations, sparse matrix computations, etc), the speed
    … …  
    296296@heading Status/Copyright of @code{omalloc}
    297297
    298 @code{omalloc} is a fully-functional, mature memory managment
     298@code{omalloc} is a fully-functional, mature memory management
    299299library. It still has a TODO list, with more or less only one major
    300300point: Create a detailed technical reference manual (in texinfo),
Note: See TracChangeset for help on using the changeset viewer.