Re: [rfc][patch] radix-tree: small data structure

From: Nick Piggin
Date: Sun Apr 23 2006 - 11:50:43 EST


Nick Piggin wrote:
With the previous patch, the radix_tree_node budget on my 64-bit
desktop is cut from 20MB to 10MB. This patch should cut it again
by nearly a factor of 4 (haven't verified, but 98ish % of files
are under 64K).

I wonder if this would be of any interest for those who enable
CONFIG_BASE_SMALL?

Bah, wrong patch.

--
SUSE Labs, Novell Inc.
This patch reduces radix tree node memory usage by about a factor of 4
on many small files (< 64K) scenarios, and results in perfect packing of
the index range into 32 and 64 bits. There are pointer traversal and
memory usage costs for large files with dense pagecache.

Index: linux-2.6/lib/radix-tree.c
===================================================================
--- linux-2.6.orig/lib/radix-tree.c
+++ linux-2.6/lib/radix-tree.c
@@ -33,7 +33,7 @@


#ifdef __KERNEL__
-#define RADIX_TREE_MAP_SHIFT 6
+#define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6)
#else
#define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */
#endif