Re: [RFC PATCH] greatly reduce SLOB external fragmentation

Linus Torvalds
2008-01-10T16:14:47Z

On Thu, 10 Jan 2008, Pekka J Enberg wrote:
>
> We probably don't have the same version of GCC which perhaps affects
> memory layout (struct sizes) and thus allocation patterns?

No, struct sizes will not change with compiler versions - that would
create binary incompatibilities for libraries etc.

So apart from the kernel itself working around some old gcc bugs by making
spinlocks have different size depending on the compiler version, sizes of
structures should be the same (as long as the configuration is the same,
of course).

However, a greedy first-fit allocator will be *very* sensitive to
allocation pattern differences, so timing will probably make a big
difference. In contrast, SLUB and SLAB both use fixed sizes per allocation
queue, which makes them almost totally impervious to any allocation
pattern from different allocation sizes (they still end up caring about
the pattern *within* one size, but those tend to be much stabler).

There really is a reason why traditional heaps with first-fit are almost
never used for any real loads.

(I'm not a fan of slabs per se - I think all the constructor/destructor
crap is just that: total crap - but the size/type binning is a big deal,
and I think SLOB was naïve to think a pure first-fit makes any sense. Now
you guys are size-binning by just two or three bins, and it seems to make
a difference for some loads, but compared to SLUB/SLAB it's a total hack).

I would suggest that if you guys are really serious about memory use, try
to do a size-based heap thing, and do best-fit in that heap. Or just some
really simple size-based binning, eg

if (size > 2*PAGE_SIZE)
goto page_allocator;
bin = lookup_bin[(size+31) >> 5];

or whatever. Because first-fit is *known* to be bad.

At try to change it to address-ordered first-fit or something (which is
much more complex than just plain LIFO, but hey, that's life).

I haven't checked much, but I *think* SLOB is just basic first-fit
(perhaps the "next-fit" variation?) Next-fit is known to be EVEN WORSE
than the simple first-fit when it comes to fragmentation (so no, Knuth was
not always right - let's face it, much of Knuth is simply outdated).

Linus