• Wang Shilong's avatar
    Btrfs: add a rb_tree to improve performance of ulist search · f7f82b81
    Wang Shilong authored
    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: default avatarWang Shilong <wangsl-fnst@cn.fujitsu.com>
    Reviewed-by: default avatarMiao Xie <miaox@cn.fujitsu.com>
    Reviewed-by: default avatarJan Schmidt <list.btrfs@jan-o-sch.net>
    Signed-off-by: default avatarJosef Bacik <jbacik@fusionio.com>
    f7f82b81
ulist.h 1.98 KB