From: Theodore Ts'o <tytso@mit.edu>
To: Ext4 Developers List <linux-ext4@vger.kernel.org>
Cc: Theodore Ts'o <tytso@mit.edu>
Subject: [PATCH 2/3] libext2fs: further optimize rb_test_bit
Date: Fri, 5 Oct 2012 22:04:11 -0400 [thread overview]
Message-ID: <1349489052-18657-2-git-send-email-tytso@mit.edu> (raw)
In-Reply-To: <1349489052-18657-1-git-send-email-tytso@mit.edu>
Profiling shows that rb_test_bit() is now calling ext2fs_rb_next() a
lot, and this function is now the hot spot when running e2freefrag.
If we cache the results of ext2fs_rb_next(), we can eliminate those
extra calls, which further speeds up both e2freefrag and e2fsck by
reducing the amount of CPU time spent in userspace.
Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
lib/ext2fs/blkmap64_rb.c | 23 +++++++++++++++++++----
1 file changed, 19 insertions(+), 4 deletions(-)
diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
index 900c0d3..40d982f 100644
--- a/lib/ext2fs/blkmap64_rb.c
+++ b/lib/ext2fs/blkmap64_rb.c
@@ -40,6 +40,7 @@ struct ext2fs_rb_private {
struct rb_root root;
struct bmap_rb_extent *wcursor;
struct bmap_rb_extent *rcursor;
+ struct bmap_rb_extent *rcursor_next;
#ifdef BMAP_STATS_OPS
__u64 mark_hit;
__u64 test_hit;
@@ -152,6 +153,8 @@ static void rb_free_extent(struct ext2fs_rb_private *bp,
bp->wcursor = NULL;
if (bp->rcursor == ext)
bp->rcursor = NULL;
+ if (bp->rcursor_next == ext)
+ bp->rcursor_next = NULL;
ext2fs_free_mem(&ext);
}
@@ -166,6 +169,7 @@ static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap bitmap)
bp->root = RB_ROOT;
bp->rcursor = NULL;
+ bp->rcursor_next = NULL;
bp->wcursor = NULL;
#ifdef BMAP_STATS_OPS
@@ -306,7 +310,7 @@ static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap,
inline static int
rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
{
- struct bmap_rb_extent *rcursor, *next_ext;
+ struct bmap_rb_extent *rcursor, *next_ext = NULL;
struct rb_node *parent = NULL, *next;
struct rb_node **n = &bp->root.rb_node;
struct bmap_rb_extent *ext;
@@ -322,9 +326,15 @@ rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
return 1;
}
- next = ext2fs_rb_next(&rcursor->node);
- if (next) {
- next_ext = ext2fs_rb_entry(next, struct bmap_rb_extent, node);
+ next_ext = bp->rcursor_next;
+ if (!next_ext) {
+ next = ext2fs_rb_next(&rcursor->node);
+ if (next)
+ next_ext = ext2fs_rb_entry(next, struct bmap_rb_extent,
+ node);
+ bp->rcursor_next = next_ext;
+ }
+ if (next_ext) {
if ((bit >= rcursor->start + rcursor->count) &&
(bit < next_ext->start)) {
#ifdef BMAP_STATS_OPS
@@ -333,6 +343,8 @@ rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
return 0;
}
}
+ bp->rcursor = NULL;
+ bp->rcursor_next = NULL;
rcursor = bp->wcursor;
if (!rcursor)
@@ -352,6 +364,7 @@ search_tree:
n = &(*n)->rb_right;
else {
bp->rcursor = ext;
+ bp->rcursor_next = 0;
return 1;
}
}
@@ -368,6 +381,7 @@ static int rb_insert_extent(__u64 start, __u64 count,
struct bmap_rb_extent *ext;
int retval = 0;
+ bp->rcursor_next = NULL;
ext = bp->wcursor;
if (ext) {
if (start >= ext->start &&
@@ -738,6 +752,7 @@ static void rb_clear_bmap(ext2fs_generic_bitmap bitmap)
rb_free_tree(&bp->root);
bp->rcursor = NULL;
+ bp->rcursor_next = NULL;
bp->wcursor = NULL;
}
--
1.7.12.rc0.22.gcdd159b
next prev parent reply other threads:[~2012-10-06 2:04 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-10-05 3:44 [PATCH 1/2] e2freefrag: use 64-bit rbtree bitmaps Theodore Ts'o
2012-10-05 3:44 ` [PATCH 2/2] libext2fs: optimize rb_test_bit Theodore Ts'o
2012-10-06 2:04 ` [PATCH 1/3] libext2fs: remove pointless indirection in rbtree bitmaps Theodore Ts'o
2012-10-06 2:04 ` Theodore Ts'o [this message]
2012-10-06 2:04 ` [PATCH 3/3] Fix makefiles to compile e2freefrag with profiling Theodore Ts'o
2012-10-06 15:54 ` Eric Sandeen
2012-10-06 15:52 ` [PATCH 1/3] libext2fs: remove pointless indirection in rbtree bitmaps Eric Sandeen
2012-10-08 8:08 ` [PATCH 2/2] libext2fs: optimize rb_test_bit Lukáš Czerner
2012-10-08 8:25 ` Lukáš Czerner
2012-10-08 18:17 ` Theodore Ts'o
2012-10-09 7:18 ` Lukáš Czerner
2012-10-09 19:55 ` Theodore Ts'o
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1349489052-18657-2-git-send-email-tytso@mit.edu \
--to=tytso@mit.edu \
--cc=linux-ext4@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).