Messages in this thread | | | Date | Tue, 10 Dec 2002 01:51:18 -0800 | From | William Lee Irwin III <> | Subject | Re: [PATCH 3/3] High-res-timers part 3 (posix to hrposix) take 20 |
| |
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 - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |