Re: [RFC] tree-based bootmem

[William Lee Irwin III <wli@holomorphy.com>]

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?


Thanks,
Bill