Re: [RFC PATCH] greatly reduce SLOB external fragmentation

[Matt Mackall <mpm@selenic.com>]

On Thu, 2008-01-10 at 00:43 +0200, Pekka J Enberg wrote:
> Hi Matt,
> 
> On Wed, 9 Jan 2008, Matt Mackall wrote:
> > I kicked this around for a while, slept on it, and then came up with
> > this little hack first thing this morning:
> > 
> > ------------
> > slob: split free list by size
> > 
> 
> [snip]
> 
> > And the results are fairly miraculous, so please double-check them on
> > your setup. The resulting statistics change to this:
> 
> [snip]
>  
> > So the average jumped by 714k from before the patch, became much more
> > stable, and beat SLUB by 287k. There are also 7 perfectly filled pages
> > now, up from 1 before. And we can't get a whole lot better than this:
> > we're using 259 pages for 244 pages of actual data, so our total
> > overhead is only 6%! For comparison, SLUB's using about 70 pages more
> > for the same data, so its total overhead appears to be about 35%.
> 
> Unfortunately I only see a slight improvement to SLOB (but it still gets 
> beaten by SLUB):
> 
> [ the minimum, maximum, and average are captured from 10 individual runs ]
> 
>                                  Free (kB)             Used (kB)
>                     Total (kB)   min   max   average   min  max  average
>   SLUB (no debug)   26536        23868 23892 23877.6   2644 2668 2658.4
>   SLOB (patched)    26548        23456 23708 23603.2   2840 3092 2944.8
>   SLOB (vanilla)    26548        23472 23640 23579.6   2908 3076 2968.4
>   SLAB (no debug)   26544        23316 23364 23343.2   3180 3228 3200.8
>   SLUB (with debug) 26484        23120 23136 23127.2   3348 3364 3356.8

With your kernel config and my lguest+busybox setup, I get:

SLUB:
MemFree:         24208 kB
MemFree:         24212 kB
MemFree:         24212 kB
MemFree:         24212 kB
MemFree:         24216 kB
MemFree:         24216 kB
MemFree:         24220 kB
MemFree:         24220 kB
MemFree:         24224 kB
MemFree:         24232 kB
avg:             24217.2

SLOB with two lists:
MemFree:         24204 kB
MemFree:         24260 kB
MemFree:         24260 kB
MemFree:         24276 kB
MemFree:         24288 kB
MemFree:         24292 kB
MemFree:         24312 kB
MemFree:         24320 kB
MemFree:         24336 kB
MemFree:         24396 kB
avg:             24294.4

Not sure why this result is so different from yours.

Hacked this up to three lists to experiment and we now have:
MemFree:         24348 kB
MemFree:         24372 kB
MemFree:         24372 kB
MemFree:         24372 kB
MemFree:         24372 kB
MemFree:         24380 kB
MemFree:         24384 kB
MemFree:         24404 kB
MemFree:         24404 kB
MemFree:         24408 kB
avg:             24344.4

Even the last version is still using about 250 pages of storage for 209
pages of data, so it's got about 20% overhead still.



-- 
Mathematics is the supreme nostalgia of our time.