[PATCH][RFC] radix-tree.c

[PATCH][RFC] radix-tree.c

[Szabolcs Berecz]

With the following patch maxindex is taken from an array instead of
recalculating it all the time.

Comments?

Bye,
Szabi


--- linux-2.5.60/lib/radix-tree.c.orig	Sat Jan 25 19:28:22 2003
+++ linux-2.5.60/lib/radix-tree.c	Fri Feb 14 22:16:34 2003
@@ -46,6 +46,8 @@
 #define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
 #define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)

+static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH];
+
 /*
  * Radix tree node cache.
  */
@@ -126,12 +128,9 @@
  */
 static inline unsigned long radix_tree_maxindex(unsigned int height)
 {
-	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
-	unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
-
-	if (tmp >= RADIX_TREE_INDEX_BITS)
-		index = ~0UL;
-	return index;
+	if (unlikely(height >= RADIX_TREE_MAX_PATH))
+		return ~0UL;
+	return height_to_maxindex[height];
 }

 /*
@@ -402,6 +401,24 @@
 	memset(node, 0, sizeof(struct radix_tree_node));
 }

+static __init unsigned long __maxindex(unsigned int height)
+{
+	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
+	unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
+
+	if (tmp >= RADIX_TREE_INDEX_BITS)
+		index = ~0UL;
+	return index;
+}
+
+static __init void radix_tree_init_maxindex(void)
+{
+	unsigned int i;
+
+	for (i = 0; i < RADIX_TREE_MAX_PATH; i++)
+		height_to_maxindex[i] = __maxindex(i);
+}
+
 void __init radix_tree_init(void)
 {
 	radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
@@ -409,4 +426,5 @@
 			0, radix_tree_node_ctor, NULL);
 	if (!radix_tree_node_cachep)
 		panic ("Failed to create radix_tree_node cache\n");
+	radix_tree_init_maxindex();
 }

Re: [PATCH][RFC] radix-tree.c

[Andrew Morton]

Szabolcs Berecz <szabi@mplayerhq.hu> wrote:
>
> 
> With the following patch maxindex is taken from an array instead of
> recalculating it all the time.

Looks good to me.

> +static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH];
> +
>  /*
>   * Radix tree node cache.
>   */
> @@ -126,12 +128,9 @@
>   */
>  static inline unsigned long radix_tree_maxindex(unsigned int height)
>  {
> -	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
> -	unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
> -
> -	if (tmp >= RADIX_TREE_INDEX_BITS)
> -		index = ~0UL;
> -	return index;
> +	if (unlikely(height >= RADIX_TREE_MAX_PATH))
> +		return ~0UL;
> +	return height_to_maxindex[height];

If you make height_to_maxindex[] a bit bigger, and fill it up with ~0UL's,
this comparison can be removed too.

I rather hope that height cannot be larger than RADIX_TREE_MAX_PATH anyway...

Re: [PATCH][RFC] radix-tree.c

[Szabolcs Berecz]

On Fri, 14 Feb 2003, Andrew Morton wrote:

> If you make height_to_maxindex[] a bit bigger, and fill it up with ~0UL's,
> this comparison can be removed too.
>
> I rather hope that height cannot be larger than RADIX_TREE_MAX_PATH anyway...

I simply removed the check, because the height can be larger than
RADIX_TREE_MAX_PATH only when the return value is compared against
a long long. If I'm right long long is never used in the kernel.

Bye,
Szabi

--- linux-2.5.60/lib/radix-tree.c.orig	Sat Jan 25 19:28:22 2003
+++ linux-2.5.60/lib/radix-tree.c	Sat Feb 15 00:28:04 2003
@@ -46,6 +46,8 @@
 #define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
 #define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)

+static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH];
+
 /*
  * Radix tree node cache.
  */
@@ -126,12 +128,7 @@
  */
 static inline unsigned long radix_tree_maxindex(unsigned int height)
 {
-	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
-	unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
-
-	if (tmp >= RADIX_TREE_INDEX_BITS)
-		index = ~0UL;
-	return index;
+	return height_to_maxindex[height];
 }

 /*
@@ -402,6 +399,24 @@
 	memset(node, 0, sizeof(struct radix_tree_node));
 }

+static __init unsigned long __maxindex(unsigned int height)
+{
+	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
+	unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
+
+	if (tmp >= RADIX_TREE_INDEX_BITS)
+		index = ~0UL;
+	return index;
+}
+
+static __init void radix_tree_init_maxindex(void)
+{
+	unsigned int i;
+
+	for (i = 0; i < RADIX_TREE_MAX_PATH; i++)
+		height_to_maxindex[i] = __maxindex(i);
+}
+
 void __init radix_tree_init(void)
 {
 	radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
@@ -409,4 +424,5 @@
 			0, radix_tree_node_ctor, NULL);
 	if (!radix_tree_node_cachep)
 		panic ("Failed to create radix_tree_node cache\n");
+	radix_tree_init_maxindex();
 }