Btrfs: Switch the extent buffer rbtree into a radix tree
authorMiao Xie <miaox@cn.fujitsu.com>
Wed, 27 Oct 2010 00:57:29 +0000 (20:57 -0400)
committerChris Mason <chris.mason@oracle.com>
Fri, 29 Oct 2010 15:25:45 +0000 (11:25 -0400)
commit19fe0a8b787d7c7f9318975b5a8c6e7e5e54e925
tree78aea56ede5735ae3183f2c4b846773b8fd8155b
parent897ca6e9b4fef86d5dfb6b31fd9f592ce6a47a42
Btrfs: Switch the extent buffer rbtree into a radix tree

This patch reduces the CPU time spent in the extent buffer search by using the
radix tree instead of the rbtree and using the rcu lock instead of the spin
lock.

I did a quick test by the benchmark tool[1] and found the patch improve the
file creation/deletion performance problem that I have reported[2].

Before applying this patch:
Create files:
Total files: 50000
Total time: 0.971531
Average time: 0.000019
Delete files:
Total files: 50000
Total time: 1.366761
Average time: 0.000027

After applying this patch:
Create files:
Total files: 50000
Total time: 0.927455
Average time: 0.000019
Delete files:
Total files: 50000
Total time: 1.292280
Average time: 0.000026

[1] http://marc.info/?l=linux-btrfs&m=128212635122920&q=p3
[2] http://marc.info/?l=linux-btrfs&m=128212635122920&w=2

Signed-off-by: Miao Xie <miaox@cn.fujitsu.com>
Signed-off-by: Chris Mason <chris.mason@oracle.com>
fs/btrfs/extent_io.c
fs/btrfs/extent_io.h