Re: [PATCH 3/3] High-res-timers part 3 (posix to hrposix) take 20

[William Lee Irwin III]

On Tue, Dec 10, 2002 at 01:24:33AM -0800, Andrew Morton wrote:
> A simple way of doing the "find an empty slot" is to descend the
> tree, following the trail of nodes which have `count < 64' until
> you hit the bottom.  At each node you'll need to walk the slots[]
> array to locate the first empty one.
> That's quite a few cache misses.  It can be optimised by adding
> a 64-bit DECLARE_BITMAP to struct radix_tree_node.  This actually
> obsoletes `count', because you can just replace the test for
> zero count with a test for `all 64 bits are zero'.

I found that ffz() to find the index of the not-fully-populated child
node to search was efficient enough to provide a precisely K == 2*levels
constant within the O(1) for accesses in all non-failure cases.
Measuring by cachelines it would have been superior to provide a
cacheline-sized node at each level and perform ffz by hand.

On Tue, Dec 10, 2002 at 01:24:33AM -0800, Andrew Morton wrote:
> Such a search would be an extension to or variant of radix_tree_gang_lookup.
> Something like the (old, untested) code below.
> But it's a big job.  First thing to do is to write a userspace
> test harness for the radix-tree code.  That's something I need to
> do anyway, because radix_tree_gang_lookup fails for offests beyond
> the 8TB mark, and it's such a pita fixing that stuff in-kernel.

Userspace test harnesses are essential for this kind of work. They
were for several of mine.

Bill