Skip to contentSkip to conversation

radix-tree: small data structure

RFC PATCH In review Nick Piggin 2 participants 3 messages Apr 23, 2006

Subsystems (2)
Memory management Library code
lore
Share & tools
lore

Nick Piggin

author
#0 lore raw

RFC PATCH 1/1 radix-tree: small data structure

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?

Signature · 1 line
SUSE Labs, Novell Inc.
radix-tree.c +2 -3
Index: rtth/radix-tree.c
===================================================================
@@ -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;
author
#1 lore raw
Quoted 7 lines · Nick Piggin

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.

Signature · 1 line
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.

lib/radix-tree.c +1 -1
Index: 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
#2 lore raw
Quoted 10 lines · Nick Piggin
Quoted 7 lines · Nick Piggin

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.

Signature · 7 lines
Mathematics is the supreme nostalgia of our time.

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