• Andres Freund's avatar
    Add "Slab" MemoryContext implementation for efficient equal-sized allocations. · 58b25e98
    Andres Freund authored
    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
    58b25e98
memnodes.h 3.62 KB