[Tux3] [PATCH] Fix bugs in group split when there are more than one extent per entry

Daniel Phillips phillips at phunq.net
Sun Aug 3 14:59:33 PDT 2008

Applied, looks right.  Can be fiddled to be a little more readable.

I think this is equivalent:

   unsigned count = (group - 1)->count;
   group - 1)->count -= group->count = (count + 1) / 2;
   for (int i = group->count + 1; i <= count; i++)

You probably noticed this, but the (count + 1) / 2 is about putting the
even part of a split for odd grouplim into the predecessor group, which
increases group fullness by one for the common case where entries are
inserted sequentially.  Group fullness ends up as ceiling of half the
grouplim in this case, which is just fine because it allows for plenty
of random insertion later without causing more splits.  It does double
the number of groups though, slightly increasing the lookup time for
files with more than 128 entries, because the groups are sequentially
searched with up to six (cheap) tests per step.

A 128 entry file is roughly

   2^7 entries * 2^6 maxextent * 2^12 blocksize = 32 MB

below which the file has only one group (unless heavily versioned) so I
do not think we care at all about the few extra tests that kick in
after the file gets its second group.

Setting grouplim to 7 or so tests the boundary conditions heavily.  Not
that I have really done much of that yet ;-)



Tux3 mailing list
Tux3 at tux3.org

More information about the Tux3 mailing list