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

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

[Nick Piggin]

[-- Attachment #1: Type: text/plain, Size: 321 bytes --]

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?

-- 
SUSE Labs, Novell Inc.

[-- Attachment #2: radix-tree-tag_get-fix.patch --]
[-- Type: text/plain, Size: 761 bytes --]

Index: rtth/radix-tree.c
===================================================================
--- rtth.orig/radix-tree.c	2006-04-22 18:40:38.000000000 +1000
+++ rtth/radix-tree.c	2006-04-23 04:46:15.000000000 +1000
@@ -458,9 +458,8 @@ EXPORT_SYMBOL(radix_tree_tag_clear);
  *
  * Return values:
  *
- *  0: tag not present
+ *  0: tag not set or not present
  *  1: tag present, set
- * -1: tag present, unset
  */
 int radix_tree_tag_get(struct radix_tree_root *root,
 			unsigned long index, unsigned int tag)
@@ -494,7 +493,7 @@ int radix_tree_tag_get(struct radix_tree
 			int ret = tag_get(slot, tag, offset);
 
 			BUG_ON(ret && saw_unset_tag);
-			return ret ? 1 : -1;
+			return ret;
 		}
 		slot = slot->slots[offset];
 		shift -= RADIX_TREE_MAP_SHIFT;

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

[Nick Piggin]

[-- Attachment #1: Type: text/plain, Size: 373 bytes --]

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.

[-- Attachment #2: radix-small.patch --]
[-- Type: text/plain, Size: 651 bytes --]

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

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

[Matt Mackall]

On Mon, Apr 24, 2006 at 01:46:24AM +1000, Nick Piggin wrote:
> 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.

I like it.

-- 
Mathematics is the supreme nostalgia of our time.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>