]> granicus.if.org Git - postgresql/commit
Add "Slab" MemoryContext implementation for efficient equal-sized allocations.
authorAndres Freund <andres@anarazel.de>
Mon, 27 Feb 2017 11:41:44 +0000 (03:41 -0800)
committerAndres Freund <andres@anarazel.de>
Mon, 27 Feb 2017 11:41:44 +0000 (03:41 -0800)
commit58b25e98106dbe062cec0f3d31d64977bffaa4af
treeb112271d687728227732bb3ccdf03dd39a799708
parentbfd12cccbd72c1846bfa3e4031155c9bd479d70a
Add "Slab" MemoryContext implementation for efficient equal-sized allocations.

The default general purpose aset.c style memory context is not a great
choice for allocations that are all going to be evenly sized,
especially when those objects aren't small, and have varying
lifetimes.  There tends to be a lot of fragmentation, larger
allocations always directly go to libc rather than have their cost
amortized over several pallocs.

These problems lead to the introduction of ad-hoc slab allocators in
reorderbuffer.c. But it turns out that the simplistic implementation
leads to problems when a lot of objects are allocated and freed, as
aset.c is still the underlying implementation. Especially freeing can
easily run into O(n^2) behavior in aset.c.

While the O(n^2) behavior in aset.c can, and probably will, be
addressed, custom allocators for this behavior are more efficient
both in space and time.

This allocator is for evenly sized allocations, and supports both
cheap allocations and freeing, without fragmenting significantly.  It
does so by allocating evenly sized blocks via malloc(), and carves
them into chunks that can be used for allocations.  In order to
release blocks to the OS as early as possible, chunks are allocated
from the fullest block that still has free objects, increasing the
likelihood of a block being entirely unused.

A subsequent commit uses this in reorderbuffer.c, but a further
allocator is needed to resolve the performance problems triggering
this work.

There likely are further potentialy uses of this allocator besides
reorderbuffer.c.

There's potential further optimizations of the new slab.c, in
particular the array of freelists could be replaced by a more
intelligent structure - but for now this looks more than good enough.

Author: Tomas Vondra, editorialized by Andres Freund
Reviewed-By: Andres Freund, Petr Jelinek, Robert Haas, Jim Nasby
Discussion: https://postgr.es/m/d15dff83-0b37-28ed-0809-95a5cc7292ad@2ndquadrant.com
src/backend/utils/mmgr/Makefile
src/backend/utils/mmgr/slab.c [new file with mode: 0644]
src/include/nodes/memnodes.h
src/include/nodes/nodes.h
src/include/utils/memutils.h
src/tools/pgindent/typedefs.list