[PATCH v1] memory: reduce large allocations for small pools

[Avi Kivity]

Small pools provide small objects by allocating large spans and
dividing them. Those spans, however, are too generous, resulting in
waste if only a small number of objects are allocated, and in vulnerability
to fragmentation as the largest span is half a megabyte in size.

This patch changes the search for the optimal span size to no longer
require a power-of-two span size, and to reduce the minimum number of
objects per span from 32 to 4 (reducing amortization somewhat). The largest
span size is now 64kB.

Before:

objsz spansz usedobj memory wst%
1 4096 0 0 0.0
1 4096 0 0 0.0
1 4096 0 0 0.0
1 4096 0 0 0.0
2 4096 0 0 0.0
2 4096 0 0 0.0
3 4096 0 0 0.0
3 4096 0 0 0.0
4 4096 0 0 0.0
5 4096 0 0 0.0
6 4096 0 0 0.0
7 4096 0 0 0.0
8 4096 12299 106496 7.6
10 4096 1738 24576 29.1
12 4096 171 8192 74.9
14 4096 0 8192 99.8
16 4096 1726 32768 15.7
20 4096 1692 36864 7.8
24 4096 2718 69632 5.9
28 4096 1286 40960 11.9
32 4096 2959 102400 7.5
40 4096 2779 118784 6.0
48 4096 1505 77824 6.8
56 4096 3631 208896 2.5
64 4096 6814 442368 1.4
80 4096 3374 274432 1.3
96 4096 1480 151552 4.7
112 4096 543 69632 11.1
128 4096 580 86016 13.7
160 8192 1619 270336 3.8
192 8192 525 114688 10.5
224 8192 280 81920 21.9
256 8192 203 73728 29.5
320 16384 364 147456 20.6
384 16384 92 65536 44.5
448 16384 178 114688 28.9
512 16384 328826 168394752 0.0
640 32768 59 98304 61.2
768 32768 260 262144 22.3
896 32768 49 98304 53.8
1024 32768 55 98304 42.7
1280 65536 145 262144 28.8
1536 65536 79 262144 52.1
1792 65536 204 524288 28.7
2048 65536 67 196608 30.2
2560 131072 9 262144 90.8
3072 131072 74 262144 11.7
3584 131072 32 393216 69.3
4096 131072 32 393216 66.7
5120 262144 8 524288 91.8
6144 262144 77 1048576 53.3
7168 262144 45 786432 57.4
8192 262144 116 1572864 39.6
10240 524288 35 1048576 65.4
12288 524288 8 1048576 89.1
14336 524288 34 1572864 67.4
16384 524288 97 3145728 49.5

After:

Small pools:
objsz spansz usedobj memory wst%
1 4096 0 0 0.0
1 4096 0 0 0.0
1 4096 0 0 0.0
1 4096 0 0 0.0
2 4096 0 0 0.0
2 4096 0 0 0.0
3 4096 0 0 0.0
3 4096 0 0 0.0
4 4096 0 0 0.0
5 4096 0 0 0.0
6 4096 0 0 0.0
7 4096 0 0 0.0
8 4096 171 8192 83.3
10 4096 1 8192 99.7
12 4096 171 8192 74.9
14 4096 0 8192 99.8
16 4096 1632 32768 20.3
20 4096 1248 32768 23.4
24 4096 2263 61440 11.2
28 4096 789 28672 22.8
32 4096 2375 81920 7.2
40 4096 2598 110592 5.6
48 4096 1083 57344 9.0
56 4096 2450 143360 4.1
64 4096 5886 380928 1.1
80 4096 2680 221184 2.7
96 4096 945 98304 6.2
112 4096 246 36864 23.7
128 4096 367 57344 18.1
160 4096 1396 229376 0.3
192 4096 354 81920 15.5
224 4096 108 40960 39.4
256 4096 97 45056 44.9
320 8192 147 73728 33.9
384 8192 74 32768 11.7
448 4096 40 36864 49.8
512 4096 327335 167624704 0.0
640 12288 59 49152 22.1
768 12288 229 245760 28.4
896 8192 20 73728 74.1
1024 4096 49 77824 35.5
1280 20480 115 204800 28.1
1536 12288 90 245760 43.8
1792 16384 9 147456 87.5
2048 8192 67 155648 11.8
2560 20480 8 204800 90.0
3072 12288 71 466944 53.3
3584 28672 1 286720 98.8
4096 16384 32 311296 57.9
5120 20480 8 389120 89.5
6144 24576 29 466944 61.8
7168 28672 12 544768 84.2
8192 32768 66 622592 13.2
10240 40960 2 778240 97.4
12288 49152 6 933888 92.1
14336 57344 2 1089536 97.4
16384 65536 2 1245184 97.4
---
core/memory.cc | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/core/memory.cc b/core/memory.cc
index b4ceceb67..329c2bcc5 100644
--- a/core/memory.cc
+++ b/core/memory.cc
@@ -1074,12 +1074,12 @@ void cpu_pages::set_min_free_pages(size_t pages) {

small_pool::small_pool(unsigned object_size) noexcept
: _object_size(object_size), _span_size(1) {
while (_object_size > span_bytes()
|| (_span_size < 32 && waste() > 0.05)
- || (span_bytes() / object_size < 32)) {
- _span_size *= 2;
+ || (span_bytes() / object_size < 4)) {
+ ++_span_size;
}
_max_free = std::max<unsigned>(100, span_bytes() * 2 / _object_size);
_min_free = _max_free / 2;
}

--
2.13.5

[Pekka Enberg]

On Sat, Aug 19, 2017 at 7:49 PM, Avi Kivity <a...@scylladb.com> wrote:

Small pools provide small objects by allocating large spans and
dividing them.  Those spans, however, are too generous, resulting in
waste if only a small number of objects are allocated, and in vulnerability
to fragmentation as the largest span is half a megabyte in size.

This patch changes the search for the optimal span size to no longer
require a power-of-two span size, and to reduce the minimum number of
objects per span from 32 to 4 (reducing amortization somewhat). The largest
span size is now 64kB.

Looks good to me.

Unrelated:

 

Before:

objsz spansz    usedobj       memory  wst%
    1   4096          0            0   0.0
    1   4096          0            0   0.0
    1   4096          0            0   0.0
    1   4096          0            0   0.0
    2   4096          0            0   0.0
    2   4096          0            0   0.0
    3   4096          0            0   0.0
    3   4096          0            0   0.0
    4   4096          0            0   0.0
    5   4096          0            0   0.0
    6   4096          0            0   0.0
    7   4096          0            0   0.0

I think we can just drop object sizes below sizeof(void*) because classes and structs are going to be aligned to that anyway.

- Pekka

[Avi Kivity]

It's legal to allocate a byte.

[Pekka Enberg]

Sure, but as seen above, it doesn't really happen that often. The overhead of allocating from a larger bucket is therefore negligible. 

- Pekka 

[Avi Kivity]

But why add an extra check? An unused bucket costs just a few bytes (sizeof small_pool).

btw notice how there are 4 buckets for size-1 and 2 buckets for sizes 2 and 3 (a side effect from our overhead reduction logic for larger objects).

[Commit Bot]

From: Avi Kivity <a...@scylladb.com>
Committer: Pekka Enberg <pen...@scylladb.com>
Branch: master

memory: reduce large allocations for small pools

Message-Id: <201708191649...@scylladb.com>

---
diff --git a/core/memory.cc b/core/memory.cc
--- a/core/memory.cc
+++ b/core/memory.cc
@@ -1057,8 +1057,8 @@ small_pool::small_pool(unsigned object_size) noexcept