Re: [patch 09/10] Remove the SLOB allocator for 2.6.23

[Matt Mackall <mpm@selenic.com>]

On Mon, Jul 09, 2007 at 06:51:51PM -0700, Christoph Lameter wrote:
> On Tue, 10 Jul 2007, Nick Piggin wrote:
> 
> > > O(n) memory savings? What is that?
> > 
> > Allocate n things and your memory waste is proportional to n (well that's
> > O(n) waste, so I guess by savings I mean that SLOB's memory saving compared
> > to SLUB are proportional to n).
> 
> n is the size of the object?
> 
> Its linear correlated to the object size. It does not grow 
> exponentially as object size grows. Waste in the kmalloc array in the 
> worst case is < objsize.

N is the number of objects.

So, for large N, the overhead of SLUB of allocations of size m, where
m % alignment == 0 (for simplicity):

 kmem_cache_alloc case:

  (PAGE_SIZE % m) / m

 kmalloc case:

  nextpowerof2(m) - m

And for SLOB (with Nick's improvements):

 kmem_cache_alloc case:

  0 (the remainder of the page is usable for other allocs)

 kmalloc case:

  2 bytes (or whatever the minimal arch alignment is)

SLUB wins by two bytes on kmallocs that happen to be a power of two,
ties on kmem_cache_allocs that happen to evenly divide PAGE_SIZE and
kmallocs 2 bytes smaller than a power of 2, and loses everywhere else.

It also loses whenever a particular type/size has both short-lived and
long-lived objects because of pinning. This effect is worse on small
machines as it's easier to pin all of memory.

The downsides of current SLOB are:

 - single lock
 - potentially long walks to find free blocks

The average case walk has been shortened quite a bit by Nick's
patches. The combinatorics here are enough to make Knuth hand-wave,
but we can in theory get close to O(1) performance when we don't have
much memory pressure. Needs some serious benchmarking. When we DO have
memory pressure, both SLOB and SLUB will degrade to forcing the kernel
to walk a bunch of pages.

-- 
Mathematics is the supreme nostalgia of our time.