On 2018/8/23 上午3:51, Liu Bo wrote: > Several structs in btrfs are using rb_first() in a while loop, it'd be > more efficient to do this with rb_first_cached() which has the O(1) > complexity.
I'm a little curious about such rb_first() inside loop usage. What I can find is mostly deletion + iteration code for rb_tree. Like btrfs_free_qgroup_config() or btrfs_qgroup_account_extents(). I'm wondering if there is any special way to do it faster for such usage. Or rb_tree_cached is the only solution here. Thanks, Qu > > This patch set updates five structs which may have a large rb tree in > practice > > Liu Bo (5): > Btrfs: href_root: use rb_first_cached > Btrfs: href->ref_tree: use rb_first_cached > Btrfs: delayed_items: use rb_first_cached > Btrfs: extent_map: use rb_first_cached > Btrfs: preftree: use rb_first_cached > > fs/btrfs/backref.c | 34 +++++++++++++------------- > fs/btrfs/delayed-inode.c | 29 +++++++++++++---------- > fs/btrfs/delayed-inode.h | 4 ++-- > fs/btrfs/delayed-ref.c | 50 > +++++++++++++++++++++++---------------- > fs/btrfs/delayed-ref.h | 4 ++-- > fs/btrfs/disk-io.c | 8 +++---- > fs/btrfs/extent-tree.c | 19 ++++++++------- > fs/btrfs/extent_map.c | 27 +++++++++++---------- > fs/btrfs/extent_map.h | 2 +- > fs/btrfs/inode.c | 4 ++-- > fs/btrfs/tests/extent-map-tests.c | 4 ++-- > fs/btrfs/transaction.c | 5 ++-- > fs/btrfs/volumes.c | 5 ++-- > 13 files changed, 107 insertions(+), 88 deletions(-) >
signature.asc
Description: OpenPGP digital signature