lkml.org 
[lkml]   [2008]   [Jan]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [RFC PATCH] greatly reduce SLOB external fragmentation


    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
    --
    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/

    \
     
     \ /
      Last update: 2008-01-10 17:17    [W:3.543 / U:0.556 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site