2018-09-09 13:32:14

by wanglong

Subject: [PATCH] radix-tree: optimization for radix_tree_init_maxnodes

if i == 0, height_to_maxnodes[i] = 0,
if i >= 1, height_to_maxnodes[i] = height_to_maxnodes[i-1]
+ __maxindex(i-1) + 1.

so delete height_to_maxindex and optimize the calculation of
height_to_maxnodes array.

Signed-off-by: Wang Long <[email protected]>
---
lib/radix-tree.c | 13 +++++--------
1 file changed, 5 insertions(+), 8 deletions(-)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index bc03ecc..af02b2c 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -2242,14 +2242,11 @@ static __init unsigned long __maxindex(unsigned int height)

static __init void radix_tree_init_maxnodes(void)
{
- unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1];
- unsigned int i, j;
-
- for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
- height_to_maxindex[i] = __maxindex(i);
- for (i = 0; i < ARRAY_SIZE(height_to_maxnodes); i++) {
- for (j = i; j > 0; j--)
- height_to_maxnodes[i] += height_to_maxindex[j - 1] + 1;
+ unsigned int i;
+
+ for (i = 1; i < ARRAY_SIZE(height_to_maxnodes); i++) {
+ height_to_maxnodes[i] = height_to_maxnodes[i - 1]
+ + __maxindex(i - 1) + 1;
}
}

--
1.8.3.1

2018-09-09 19:08:44

by Matthew Wilcox

Subject: Re: [PATCH] radix-tree: optimization for radix_tree_init_maxnodes

On Sun, Sep 09, 2018 at 09:21:00PM +0800, Wang Long wrote:
> if i == 0, height_to_maxnodes[i] = 0,
> if i >= 1, height_to_maxnodes[i] = height_to_maxnodes[i-1]
> + __maxindex(i-1) + 1.
>
> so delete height_to_maxindex and optimize the calculation of
> height_to_maxnodes array.

Thanks for your patch. Unfortunately, this entire function is scheduled
for deletion, so I won't be applying it.

If you're interested in the radix tree, I'd recommend looking at its
replacement, the XArray. The current version is at
http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/xarray
but I'll be pushing another version out in the next few days.