thr3ads.net - Btrfs devel - [PATCH] Btrfs: add a rb_tree to improve performance of ulist search [Apr 2013]

If this information is useful, please help other people find it:
Share via:

Wang Shilong

2013-Apr-11 05:25 UTC

[PATCH] 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)

Signed-off-by: Wang Shilong <wangsl-fnst@cn.fujitsu.com>
Reviewed-by: Miao Xie <miaox@cn.fujitsu.com>
---
 fs/btrfs/ulist.c |   58 ++++++++++++++++++++++++++++++++++++++++++++++-------
 fs/btrfs/ulist.h |    6 +++++
 2 files changed, 56 insertions(+), 8 deletions(-)

diff --git a/fs/btrfs/ulist.c b/fs/btrfs/ulist.c
index ddc61ca..7b417e2 100644
--- a/fs/btrfs/ulist.c
+++ b/fs/btrfs/ulist.c
@@ -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;
diff --git a/fs/btrfs/ulist.h b/fs/btrfs/ulist.h
index 21a1963..cb5f89d 100644
--- a/fs/btrfs/ulist.h
+++ b/fs/btrfs/ulist.h
@@ -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
 	 */
-- 
1.7.7.6




--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Jan Schmidt

2013-Apr-11 13:25 UTC

head link

Re: [PATCH] Btrfs: add a rb_tree to improve performance of ulist search

On Thu, April 11, 2013 at 07:25 (+0200), Wang Shilong
wrote:> 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)
> 
> Signed-off-by: Wang Shilong <wangsl-fnst@cn.fujitsu.com>
> Reviewed-by: Miao Xie <miaox@cn.fujitsu.com>
> ---
>  fs/btrfs/ulist.c |   58
++++++++++++++++++++++++++++++++++++++++++++++-------
>  fs/btrfs/ulist.h |    6 +++++
>  2 files changed, 56 insertions(+), 8 deletions(-)
> 
> diff --git a/fs/btrfs/ulist.c b/fs/btrfs/ulist.c
> index ddc61ca..7b417e2 100644
> --- a/fs/btrfs/ulist.c
> +++ b/fs/btrfs/ulist.c
> @@ -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;
> diff --git a/fs/btrfs/ulist.h b/fs/btrfs/ulist.h
> index 21a1963..cb5f89d 100644
> --- a/fs/btrfs/ulist.h
> +++ b/fs/btrfs/ulist.h
> @@ -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.
> +
>  /*
>   * 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
>  	 */
> 
Makes a lot of sense. Thanks!

Reviewed-by: Jan Schmidt <list.btrfs@jan-o-sch.net>
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Wang Shilong

2013-Apr-11 13:45 UTC

head link

Re: [PATCH] Btrfs: add a rb_tree to improve performance of ulist search

Hello, Jan

[snip]
>>  
>> +#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>> +
>> /*
>>  * 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
>> 	 */
>> 
> 
> Makes a lot of sense. Thanks!
> 
> Reviewed-by: Jan Schmidt <list.btrfs@jan-o-sch.net>
> --
> To unsubscribe from this list: send the line "unsubscribe
linux-btrfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Btrfs devel - Apr 2013 - [PATCH] Btrfs: add a rb_tree to improve performance of ulist search

[PATCH] Btrfs: add a rb_tree to improve performance of ulist search

Re: [PATCH] Btrfs: add a rb_tree to improve performance of ulist search

Re: [PATCH] Btrfs: add a rb_tree to improve performance of ulist search