slab allocator performance issues

Hi,

I just tried to use the slab allocator for a case where aset.c was
bloating memory usage substantially. First: It worked wonders for memory
usage, nearly eliminating overhead.

But it turned out to cause a *substantial* slowdown. With aset the
allocator is barely in the profile. With slab the profile is dominated
by allocator performance.

slab:
NOTICE: 00000: 100000000 ordered insertions in 5.216287 seconds, 19170724/sec
LOCATION: bfm_test_insert_bulk, radix.c:2880
Overhead Command Shared Object Symbol

+ 28.27% postgres postgres [.] SlabAlloc
+ 9.64% postgres bdbench.so [.] bfm_delete
+ 9.03% postgres bdbench.so [.] bfm_set
+ 8.39% postgres bdbench.so [.] bfm_lookup
+ 8.36% postgres bdbench.so [.] bfm_set_leaf.constprop.0
+ 8.16% postgres libc-2.31.so [.] __memmove_avx_unaligned_erms
+ 6.88% postgres bdbench.so [.] bfm_delete_leaf
+ 3.24% postgres libc-2.31.so [.] _int_malloc
+ 2.58% postgres bdbench.so [.] bfm_tests
+ 2.33% postgres postgres [.] SlabFree
+ 1.29% postgres libc-2.31.so [.] _int_free
+ 1.09% postgres libc-2.31.so [.] unlink_chunk.constprop.0

aset:

NOTICE: 00000: 100000000 ordered insertions in 2.082602 seconds, 48016848/sec
LOCATION: bfm_test_insert_bulk, radix.c:2880

+ 16.43% postgres bdbench.so [.] bfm_lookup
+ 15.38% postgres bdbench.so [.] bfm_delete
+ 12.82% postgres libc-2.31.so [.] __memmove_avx_unaligned_erms
+ 12.65% postgres bdbench.so [.] bfm_set
+ 12.15% postgres bdbench.so [.] bfm_set_leaf.constprop.0
+ 10.57% postgres bdbench.so [.] bfm_delete_leaf
+ 4.05% postgres bdbench.so [.] bfm_tests
+ 2.93% postgres [kernel.vmlinux] [k] clear_page_erms
+ 1.59% postgres postgres [.] AllocSetAlloc
+ 1.15% postgres bdbench.so [.] memmove(at)plt
+ 1.06% postgres bdbench.so [.] bfm_grow_leaf_16

OS:
NOTICE: 00000: 100000000 ordered insertions in 2.089790 seconds, 47851690/sec
LOCATION: bfm_test_insert_bulk, radix.c:2880

That is somewhat surprising - part of the promise of a slab allocator is
that it's fast...

This is caused by multiple issues, I think. Some of which seems fairly easy to
fix.

1) If allocations are short-lived slab.c, can end up constantly
freeing/initializing blocks. Which requires fairly expensively iterating over
all potential chunks in the block and initializing it. Just to then free that
memory again after a small number of allocations. The extreme case of this is
when there are phases of alloc/free of a single allocation.

I "fixed" this by adding a few && slab->nblocks > 1 in SlabFree() and the
problem vastly reduced. Instead of a 0.4x slowdown it's 0.88x. Of course that
only works if the problem is with the only, so it's not a great
approach. Perhaps just keeping the last allocated block around would work?

2) SlabChunkIndex() in SlabFree() is slow. It requires a 64bit division, taking
up ~50% of the cycles in SlabFree(). A 64bit div, according to [1] , has a
latency of 35-88 cycles on skylake-x (and a reverse throughput of 21-83,
i.e. no parallelism). While it's getting a bit faster on icelake / zen 3, it's
still slow enough there to be very worrisome.

I don't see a way to get around the division while keeping the freelist
structure as is. But:

ISTM that we only need the index because of the free-chunk list, right? Why
don't we make the chunk list use actual pointers? Is it concern that that'd
increase the minimum allocation size? If so, I see two ways around that:
First, we could make the index just the offset from the start of the block,
that's much cheaper to calculate. Second, we could store the next pointer in
SlabChunk->slab/block instead (making it a union) - while on the freelist we
don't need to dereference those, right?

I suspect both would also make the block initialization a bit cheaper.

That should also accelerate SlabBlockGetChunk(), which currently shows up as
an imul, which isn't exactly fast either (and uses a lot of execution ports).

3) Every free/alloc needing to unlink from slab->freelist[i] and then relink
shows up prominently in profiles. That's ~tripling the number of cachelines
touched in the happy path, with unpredictable accesses to boot.

Perhaps we could reduce the precision of slab->freelist indexing to amortize
that cost? I.e. not have one slab->freelist entry for each nfree, but instead
have an upper limit on the number of freelists?

4) Less of a performance, and more of a usability issue: The constant
block size strikes me as problematic. Most users of an allocator can
sometimes be used with a small amount of data, and sometimes with a
large amount.

Greetings,

Andres Freund

[1] https://www.agner.org/optimize/instruction_tables.pdf