[lkml]   [2001]   [Nov]   [17]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: [RFC] tree-based bootmem
    On Sun, Nov 18, 2001 at 12:16:57AM +0100, Martin Mares wrote:
    > I don't understand why does it use segment trees instead of a simple
    > linked list. Bootmem allocations are obviously not going to be time
    > critical and shaving off a couple of ms during the boot process is
    > not worth the extra complexity involved.
    > (Nevertheless, treaps are a very nice structure...)
    > Have a nice fortnight

    Thanks for your comments.

    Your opinions are valid and worthwhile, and I hope you don't mind if I
    Cc: the Linux kernel mailing list in my reply.

    The trees are largely there out of a personal distaste for exhaustive
    search when not strictly necessary. My approach to this was to research
    what data structures were appropriate for the search problem I found,
    and to use that in preference to exhaustive search.

    Some profiling by Jack Steiner prior to the initial post of this patch
    to lkml revealed that it is a very rare system that has any issues with
    the performance of the bitmap-based bootmem, and it's even less likely
    there will be a noticeable difference in absolute terms between a search
    tree structure and a linked list of ranges. While there were some
    performance concerns motivating this, the primary concern was
    interfacing with the callers and requiring less work to set up; that is,
    making it easier to say "This memory belongs to this node." I had hoped
    that in addition to suggestions regarding the mechanics, some suggestions
    about how to make life easier for those who have to call bootmem
    functions might arise from discussions about this.

    Part of the motivation for the RFC is to solicit commentary like this
    regarding the design, and in my responses, to adjust, alter, or even
    entirely rewrite this patch in order to produce something useful and
    desirable to the largest number of people. If linked lists are wanted,
    then they can be used instead.

    Is there a more general consensus regarding this aspect of the design?

    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 13:13    [W:0.247 / U:0.012 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site