lib : make radix_tree_delete() faster
Subsystems (2)
PATCH 1/1 lib : make radix_tree_delete() faster
From: Huang Shijie <[email protected]>
radix_tree_delete() calls radix_tree_tag_clear() to
clear the tag along the path of the index. The radix_tree_tag_clear() will lookup and create the path which has been created by the radix_tree_delete() already.
I introduce radix_tree_tag_clear_path() to do the clear for the
path. The radix_tree_delete() calls radix_tree_tag_clear_path() instead of radix_tree_tag_clear(), and this will save the CPU by RADIX_TREE_MAX_TAGS*lookup. This makes the radix_tree_delete() faster.
Signed-off-by Huang Shijie <[email protected]>
--- lib/radix-tree.c | 30 +++++++++++++++++++++--------- 1 files changed, 21 insertions(+), 9 deletions(-)
lib/radix-tree.c +21 -9
@@ -495,6 +495,24 @@ void *radix_tree_tag_set(struct radix_tree_root *root, }EXPORT_SYMBOL (radix_tree_tag_set); +/* +* Return 0 on succeeding to clear all the tag along the path, +* else return 1. +*/ +static inline int radix_tree_tag_clear_path (struct radix_tree_path *pathp, +struct radix_tree_path *path_start,unsigned int tag) +{ +while (pathp->node && pathp > path_start) { +if (!tag_get (pathp->node, tag, pathp->offset)) +return 1 ; +tag_clear (pathp->node, tag, pathp->offset); +if (any_tag_set (pathp->node, tag)) +return 1 ; + pathp--; + } +return 0 ; +} +/** * radix_tree_tag_clear - clear a tag on a radix tree node * @root: radix tree root
@@ -546,14 +564,8 @@ void *radix_tree_tag_clear(struct radix_tree_root *root,if (slot ==NULL ) goto out; -while (pathp->node) { -if (!tag_get (pathp->node, tag, pathp->offset)) - goto out; -tag_clear (pathp->node, tag, pathp->offset); -if (any_tag_set (pathp->node, tag)) - goto out; - pathp--; - } +if (radix_tree_tag_clear_path (pathp, path, tag)) + goto out;/* clear the root's tag bit */ if (root_tag_get (root, tag))
@@ -1134,7 +1146,7 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)*/ for (tag =0 ; tag <RADIX_TREE_MAX_TAGS ; tag++) {if (tag_get (pathp->node, tag, pathp->offset)) -radix_tree_tag_clear (root, index, tag); +radix_tree_tag_clear_path (pathp, path, tag); } to_free =NULL ;
Signature · 7 lines
1.6.0.6 -- 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>