Re: [RFC] tree-based bootmem

[Robert Love <rml@tech9.net>]

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...)

I think there is merit in using segment trees here.  Previously I have
replied demonstrating the benefit of the finer granularity in
addressing, which results in a couple KB increase in total memory on my
machines.  This is not the greatest benefit, IMO.

What really stands out to me is the design; and I think segment trees
are applicable here.  While I doubt performance of the bootmem allocator
is ever a _terrible_ concern, it probably does have tight spots.

The beauty is in the implementation.  With a linked list implementation,
you have an exhaustive search and and at-worst O(n) insertion and
searching complexity.  We also don't end up with any clean way to say
"memory a belongs to x".  This is where the segment tree comes in, a
segment tree stores intervals: it is a binary tree where each node
represents an interval from a to b.  We only need to store nodes that
have allocated intervals of memory, and insertion is O(log n). 
Searching is even easier as you just walk the intervals until we get to
what we want.  Searching would be O(log(n+s)) where s is the number of
segments we had to walk.  OK, you know this, but my point is its is
quite applicable.  Besides a performance boost, we end up with a nice
way to interface with other code to work with bootmem and I think that
is the main benefit here.

Of course, the downside would be "good lord the complexity here is
grossly overkill" but I think this doesn't have that problem.

just my two bits, 

	Robert Love