Btrfs: add a rb_tree to improve performance of ulist search
PATCH 1/1 Btrfs: add a rb_tree to improve performance of ulist search
Walking backref tree and btrfs quota rely on ulist very much. This patch tries to use rb_tree to speed up search time.
The original code always checks whether an element exists before adding a new element, however it costs O(n).
I try to add a rb_tree in the ulist,this is only used to speed up search. I also do some measurements with quota enabled.
fsstress -p 4 -n 10000
Without this path:
real 0m51.058s 2m4.745s 1m28.222s 1m5.137s user 0m0.035s 0m0.041s 0m0.105s 0m0.100s sys 0m12.009s 0m11.246s 0m10.901s 0m10.999s 0m11.287s
With this path:
real 0m55.295s 0m50.960s 1m2.214s 0m48.273s user 0m0.053s 0m0.095s 0m0.135s 0m0.107s sys 0m7.766s 0m6.013s 0m6.319s 0m6.030s 0m6.532s
After applying the patch,the execute time is down by ~42%.(11.287s->6.532s)
--- fs/btrfs/ulist.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++------- fs/btrfs/ulist.h | 6 +++++ 2 files changed, 56 insertions(+), 8 deletions(-)
fs/btrfs/ulist.c +50 -8
@@ -53,6 +53,7 @@ void ulist_init(struct ulist *ulist) ulist->nnodes =0 ; ulist->nodes = ulist->int_nodes; ulist->nodes_alloced =ULIST_SIZE ; + ulist->root =RB_ROOT ; }EXPORT_SYMBOL (ulist_init);
@@ -72,6 +73,7 @@ void ulist_fini(struct ulist *ulist)if (ulist->nodes_alloced >ULIST_SIZE )kfree (ulist->nodes); ulist->nodes_alloced =0 ;/* in case ulist_fini is called twice */ + ulist->root =RB_ROOT ; }EXPORT_SYMBOL (ulist_fini);
@@ -123,6 +125,45 @@ void ulist_free(struct ulist *ulist) }EXPORT_SYMBOL (ulist_free); +static struct ulist_node *ulist_rbtree_search (struct ulist *ulist,u64 val) +{ +struct rb_node *n = ulist->root.rb_node; +struct ulist_node *u =NULL ; + +while (n) { + u = rb_entry(n, struct ulist_node, rb_node); +if (u->val < val) + n = n->rb_right; +else if (u->val > val) + n = n->rb_left; +else +return u; + } +return NULL ; +} + +static int ulist_rbtree_insert (struct ulist *ulist,struct ulist_node *ins) +{ +struct rb_node **p = &ulist->root.rb_node; +struct rb_node *parent =NULL ; +struct ulist_node *cur =NULL ; + +while (*p) { + parent = *p; + cur = rb_entry(parent, struct ulist_node, rb_node); + +if (cur->val < ins->val) + p = &(*p)->rb_right; +else if (cur->val > ins->val) + p = &(*p)->rb_left; +else +return -EEXIST ; + } +rb_link_node (&ins->rb_node, parent, p); +rb_insert_color (&ins->rb_node, &ulist->root); +return 0 ; +} +/** * ulist_add - add an element to the ulist * @ulist: ulist to add the element to
@@ -151,14 +192,13 @@ int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask)int ulist_add_merge (struct ulist *ulist,u64 val,u64 aux,u64 *old_aux,gfp_t gfp_mask) { -int i; - -for (i =0 ; i < ulist->nnodes; ++i) { -if (ulist->nodes[i].val == val) { -if (old_aux) - *old_aux = ulist->nodes[i].aux; -return 0 ; - } +int ret =0 ; +struct ulist_node *node =NULL ; + node =ulist_rbtree_search (ulist, val); +if (node) { +if (old_aux) + *old_aux = node->aux; +return 0 ; }if (ulist->nnodes >= ulist->nodes_alloced) {
@@ -187,6 +227,8 @@ int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, } ulist->nodes[ulist->nnodes].val = val; ulist->nodes[ulist->nnodes].aux = aux; + ret =ulist_rbtree_insert (ulist, &ulist->nodes[ulist->nnodes]); +BUG_ON (ret); ++ulist->nnodes;return 1 ;
fs/btrfs/ulist.h +6 -0
@@ -8,6 +8,9 @@#ifndef __ULIST__#define __ULIST__ +#include <linux/list.h> +#include <linux/rbtree.h> +/* * ulist is a generic data structure to hold a collection of unique u64 * values. The only operations it supports is adding to the list and
@@ -34,6 +37,7 @@ struct ulist_iterator {struct ulist_node {u64 val;/* value to store */ u64 aux;/* auxiliary value saved along with the val */ +struct rb_node rb_node;/* used to speed up search */ };struct ulist {
@@ -54,6 +58,8 @@ struct ulist {*/ struct ulist_node *nodes; +struct rb_root root; +/* * inline storage space for the first ULIST_SIZE entries */
Signature · 1 line
1.7.7.6
Quoted 132 lines · Wang Shilong
Walking backref tree and btrfs quota rely on ulist very much. This patch tries to use
rb_treeto speed up search time.The original code always checks whether an element exists before adding a new element, however it costs O(n).
I try to add a
rb_treein the ulist,this is only used to speed up search. I also do some measurements with quota enabled.fsstress -p 4 -n 10000
Without this path:
real 0m51.058s 2m4.745s 1m28.222s 1m5.137s user 0m0.035s 0m0.041s 0m0.105s 0m0.100s sys 0m12.009s 0m11.246s 0m10.901s 0m10.999s 0m11.287sWith this path:
real 0m55.295s 0m50.960s 1m2.214s 0m48.273s user 0m0.053s 0m0.095s 0m0.135s 0m0.107s sys 0m7.766s 0m6.013s 0m6.319s 0m6.030s 0m6.532sAfter applying the patch,the execute time is down by ~42%.(11.287s->6.532s)
Signed-off-by Wang Shilong <[email protected]>Reviewed-by Miao Xie <[email protected]>--- fs/btrfs/ulist.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++------- fs/btrfs/ulist.h | 6 +++++ 2 files changed, 56 insertions(+), 8 deletions(-)fs/btrfs/ulist.c +50
-8@@ -53,6 +53,7 @@ void ulist_init(struct ulist *ulist) ulist->nnodes =0 ; ulist->nodes = ulist->int_nodes; ulist->nodes_alloced =ULIST_SIZE ; + ulist->root =RB_ROOT ; }EXPORT_SYMBOL (ulist_init);@@ -72,6 +73,7 @@ void ulist_fini(struct ulist *ulist)if (ulist->nodes_alloced >ULIST_SIZE )kfree (ulist->nodes); ulist->nodes_alloced =0 ;/* in case ulist_fini is called twice */ + ulist->root =RB_ROOT ; }EXPORT_SYMBOL (ulist_fini);@@ -123,6 +125,45 @@ void ulist_free(struct ulist *ulist) }EXPORT_SYMBOL (ulist_free); +static struct ulist_node *ulist_rbtree_search (struct ulist *ulist,u64 val) +{ +struct rb_node *n = ulist->root.rb_node; +struct ulist_node *u =NULL ; + +while (n) { + u = rb_entry(n, struct ulist_node, rb_node); +if (u->val < val) + n = n->rb_right; +else if (u->val > val) + n = n->rb_left; +else +return u; + } +return NULL ; +} + +static int ulist_rbtree_insert (struct ulist *ulist,struct ulist_node *ins) +{ +struct rb_node **p = &ulist->root.rb_node; +struct rb_node *parent =NULL ; +struct ulist_node *cur =NULL ; + +while (*p) { + parent = *p; + cur = rb_entry(parent, struct ulist_node, rb_node); + +if (cur->val < ins->val) + p = &(*p)->rb_right; +else if (cur->val > ins->val) + p = &(*p)->rb_left; +else +return -EEXIST ; + } +rb_link_node (&ins->rb_node, parent, p); +rb_insert_color (&ins->rb_node, &ulist->root); +return 0 ; +} +/** * ulist_add - add an element to the ulist * @ulist: ulist to add the element to @@ -151,14 +192,13 @@ int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask)int ulist_add_merge (struct ulist *ulist,u64 val,u64 aux,u64 *old_aux,gfp_t gfp_mask) { -int i; - -for (i =0 ; i < ulist->nnodes; ++i) { -if (ulist->nodes[i].val == val) { -if (old_aux) - *old_aux = ulist->nodes[i].aux; -return 0 ; - } +int ret =0 ; +struct ulist_node *node =NULL ; + node =ulist_rbtree_search (ulist, val); +if (node) { +if (old_aux) + *old_aux = node->aux; +return 0 ; }if (ulist->nnodes >= ulist->nodes_alloced) {@@ -187,6 +227,8 @@ int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, } ulist->nodes[ulist->nnodes].val = val; ulist->nodes[ulist->nnodes].aux = aux; + ret =ulist_rbtree_insert (ulist, &ulist->nodes[ulist->nnodes]); +BUG_ON (ret); ++ulist->nnodes;return 1 ;fs/btrfs/ulist.h +0
-0
fs/btrfs/ulist.h line 12
Quoted 5 lines
fs/btrfs/ulist.h +2
-0@@ -8,6 +8,9 @@#ifndef __ULIST__#define __ULIST__ +#include <linux/list.h> +#include <linux/rbtree.h>
I didn't expect the space after "#include" being optional. If it compiles, I'm fine with it. With a space, it would look more familiar, though.
Quoted 14 lines
fs/btrfs/ulist.h +2
-0+/* * ulist is a generic data structure to hold a collection of unique u64 * values. The only operations it supports is adding to the list and @@ -34,6 +37,7 @@ struct ulist_iterator {struct ulist_node {u64 val;/* value to store */ u64 aux;/* auxiliary value saved along with the val */ +struct rb_node rb_node;/* used to speed up search */ };struct ulist {
fs/btrfs/ulist.h struct ulist { · line 65
Quoted 8 lines
fs/btrfs/ulist.h +2
-0@@ -54,6 +58,8 @@ struct ulist {*/ struct ulist_node *nodes; +struct rb_root root; +/* * inline storage space for the first ULIST_SIZE entries */
Makes a lot of sense. Thanks!
Hello, Jan
[snip]
Quoted 6 lines
fs/btrfs/ulist.h line 12
Quoted 3 lines
fs/btrfs/ulist.h +2
-0+#include <linux/list.h> +#include <linux/rbtree.h> I didn't expect the space after "#include" being optional. If it compiles, I'm fine with it. With a space, it would look more familiar, though.
I am happy to send V2 to correct this coding style problem. Thanks very much for reviewing it so carefully!
Thanks,
Wang
Quoted 30 lines
Quoted 14 lines
+
/*
* ulist is a generic data structure to hold a collection of unique u64
* values. The only operations it supports is adding to the list andfs/btrfs/ulist.h +1
-0@@ -34,6 +37,7 @@ struct ulist_iterator {struct ulist_node {u64 val;/* value to store */ u64 aux;/* auxiliary value saved along with the val */ +struct rb_node rb_node;/* used to speed up search */ };struct ulist {fs/btrfs/ulist.h struct ulist { · line 65
Quoted 8 lines
fs/btrfs/ulist.h +2
-0@@ -54,6 +58,8 @@ struct ulist {*/ struct ulist_node *nodes; +struct rb_root root; +/* * inline storage space for the first ULIST_SIZE entries */ Makes a lot of sense. Thanks!
Reviewed-by Jan Schmidt <[email protected]>--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html