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

From: William Lee Irwin III (
Date: Tue Dec 10 2002 - 04:51:18 EST

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.

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

This archive was generated by hypermail 2b29 : Sun Dec 15 2002 - 22:00:17 EST