diff options
| author | Wang Shilong | 2013-04-12 14:12:17 +0200 |
|---|---|---|
| committer | Josef Bacik | 2013-05-06 21:54:44 +0200 |
| commit | f7f82b81d2c297a5864dcfd0a205917d3e753aba (patch) | |
| tree | d5208b93d07ce88b5b66e646da7241fff45ce143 /fs/btrfs/ulist.h | |
| parent | Btrfs: allow omitting stream header and end-cmd for btrfs send (diff) | |
| download | kernel-qcow2-linux-f7f82b81d2c297a5864dcfd0a205917d3e753aba.tar.gz kernel-qcow2-linux-f7f82b81d2c297a5864dcfd0a205917d3e753aba.tar.xz kernel-qcow2-linux-f7f82b81d2c297a5864dcfd0a205917d3e753aba.zip | |
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>
Reviewed-by: Jan Schmidt <list.btrfs@jan-o-sch.net>
Signed-off-by: Josef Bacik <jbacik@fusionio.com>
Diffstat (limited to 'fs/btrfs/ulist.h')
| -rw-r--r-- | fs/btrfs/ulist.h | 6 |
1 files changed, 6 insertions, 0 deletions
diff --git a/fs/btrfs/ulist.h b/fs/btrfs/ulist.h index 21a1963439c3..fb36731074b5 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 */ |