Messages in this thread | | | Date | Mon, 9 Jul 2007 21:32:05 -0500 | From | Matt Mackall <> | Subject | Re: [patch 09/10] Remove the SLOB allocator for 2.6.23 |
| |
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. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |