From 0cdabd2d489133e3cea8a00bdb9a986b24e57a66 Mon Sep 17 00:00:00 2001
From: Jason Evans <je@fb.com>
Date: Tue, 14 Oct 2014 22:19:21 -0700
Subject: Update size class documentation.
---
doc/jemalloc.xml.in | 110 +++++++++++++++++++++++++++++++++++++++-------------
1 file changed, 84 insertions(+), 26 deletions(-)
diff --git a/doc/jemalloc.xml.in b/doc/jemalloc.xml.in
index 8111fc1..fc01ad1 100644
--- a/doc/jemalloc.xml.in
+++ b/doc/jemalloc.xml.in
@@ -501,13 +501,11 @@ for (i = 0; i < nbins; i++) {
possible to find metadata for user objects very quickly.</para>
<para>User objects are broken into three categories according to size:
- small, large, and huge. Small objects are smaller than one page. Large
- objects are smaller than the chunk size. Huge objects are a multiple of
- the chunk size. Small and large objects are managed entirely by arenas;
- huge objects are additionally aggregated in a single data structure that is
- shared by all threads. Huge objects are typically used by applications
- infrequently enough that this single data structure is not a scalability
- issue.</para>
+ small, large, and huge. Small and large objects are managed entirely by
+ arenas; huge objects are additionally aggregated in a single data structure
+ that is shared by all threads. Huge objects are typically used by
+ applications infrequently enough that this single data structure is not a
+ scalability issue.</para>
<para>Each chunk that is managed by an arena tracks its contents as runs of
contiguous pages (unused, backing a set of small objects, or backing one
@@ -516,18 +514,18 @@ for (i = 0; i < nbins; i++) {
allocations in constant time.</para>
<para>Small objects are managed in groups by page runs. Each run maintains
- a frontier and free list to track which regions are in use. Allocation
- requests that are no more than half the quantum (8 or 16, depending on
- architecture) are rounded up to the nearest power of two that is at least
- <code language="C">sizeof(<type>double</type>)</code>. All other small
- object size classes are multiples of the quantum, spaced such that internal
- fragmentation is limited to approximately 25% for all but the smallest size
- classes. Allocation requests that are larger than the maximum small size
- class, but small enough to fit in an arena-managed chunk (see the <link
- linkend="opt.lg_chunk"><mallctl>opt.lg_chunk</mallctl></link> option), are
- rounded up to the nearest run size. Allocation requests that are too large
- to fit in an arena-managed chunk are rounded up to the nearest multiple of
- the chunk size.</para>
+ a bitmap to track which regions are in use. Allocation requests that are no
+ more than half the quantum (8 or 16, depending on architecture) are rounded
+ up to the nearest power of two that is at least <code
+ language="C">sizeof(<type>double</type>)</code>. All other object size
+ classes are multiples of the quantum, spaced such that there are four size
+ classes for each doubling in size, which limits internal fragmentation to
+ approximately 20% for all but the smallest size classes. Small size classes
+ are smaller than four times the page size, large size classes are smaller
+ than the chunk size (see the <link
+ linkend="opt.lg_chunk"><mallctl>opt.lg_chunk</mallctl></link> option), and
+ huge size classes extend from the chunk size up to one size class less than
+ the full address space size.</para>
<para>Allocations are packed tightly together, which can be an issue for
multi-threaded applications. If you need to assure that allocations do not
@@ -554,13 +552,13 @@ for (i = 0; i < nbins; i++) {
</thead>
<tbody>
<row>
- <entry morerows="6">Small</entry>
+ <entry morerows="8">Small</entry>
<entry>lg</entry>
<entry>[8]</entry>
</row>
<row>
<entry>16</entry>
- <entry>[16, 32, 48, ..., 128]</entry>
+ <entry>[16, 32, 48, 64, 80, 96, 112, 128]</entry>
</row>
<row>
<entry>32</entry>
@@ -580,17 +578,77 @@ for (i = 0; i < nbins; i++) {
</row>
<row>
<entry>512</entry>
- <entry>[2560, 3072, 3584]</entry>
+ <entry>[2560, 3072, 3584, 4096]</entry>
+ </row>
+ <row>
+ <entry>1 KiB</entry>
+ <entry>[5 KiB, 6 KiB, 7 KiB, 8 KiB]</entry>
+ </row>
+ <row>
+ <entry>2 KiB</entry>
+ <entry>[10 KiB, 12 KiB, 14 KiB]</entry>
+ </row>
+ <row>
+ <entry morerows="8">Large</entry>
+ <entry>2 KiB</entry>
+ <entry>[16 KiB]</entry>
</row>
<row>
- <entry>Large</entry>
<entry>4 KiB</entry>
- <entry>[4 KiB, 8 KiB, 12 KiB, ..., 4072 KiB]</entry>
+ <entry>[20 KiB, 24 KiB, 28 KiB, 32 KiB]</entry>
+ </row>
+ <row>
+ <entry>8 KiB</entry>
+ <entry>[40 KiB, 48 KiB, 54 KiB, 64 KiB]</entry>
+ </row>
+ <row>
+ <entry>16 KiB</entry>
+ <entry>[80 KiB, 96 KiB, 112 KiB, 128 KiB]</entry>
+ </row>
+ <row>
+ <entry>32 KiB</entry>
+ <entry>[160 KiB, 192 KiB, 224 KiB, 256 KiB]</entry>
+ </row>
+ <row>
+ <entry>64 KiB</entry>
+ <entry>[320 KiB, 384 KiB, 448 KiB, 512 KiB]</entry>
+ </row>
+ <row>
+ <entry>128 KiB</entry>
+ <entry>[640 KiB, 768 KiB, 896 KiB, 1024 KiB]</entry>
+ </row>
+ <row>
+ <entry>256 KiB</entry>
+ <entry>[1280 KiB, 1536 KiB, 1792 KiB, 2048 KiB]</entry>
+ </row>
+ <row>
+ <entry>512 KiB</entry>
+ <entry>[2560 KiB, 3072 KiB, 3584 KiB]</entry>
+ </row>
+ <row>
+ <entry morerows="5">Huge</entry>
+ <entry>512 KiB</entry>
+ <entry>[4 MiB]</entry>
+ </row>
+ <row>
+ <entry>1 MiB</entry>
+ <entry>[5 MiB, 6 MiB, 7 MiB, 8 MiB]</entry>
+ </row>
+ <row>
+ <entry>2 MiB</entry>
+ <entry>[10 MiB, 12 MiB, 14 MiB, 16 MiB]</entry>
</row>
<row>
- <entry>Huge</entry>
<entry>4 MiB</entry>
- <entry>[4 MiB, 8 MiB, 12 MiB, ...]</entry>
+ <entry>[20 MiB, 24 MiB, 28 MiB, 32 MiB]</entry>
+ </row>
+ <row>
+ <entry>8 MiB</entry>
+ <entry>[40 MiB, 48 MiB, 56 MiB, 64 MiB]</entry>
+ </row>
+ <row>
+ <entry>...</entry>
+ <entry>...</entry>
</row>
</tbody>
</tgroup>
--
cgit v0.12