commit fb129bba73868a41df74fec87773abd0c6c6cd4a
author Theodore Ts'o <tytso@mit.edu> Fri Oct 05 21:59:40 2012 -0400
committer Theodore Ts'o <tytso@mit.edu> Thu Oct 11 06:30:35 2012 -0400
tree 63d46975bc678393f49ff350067636b4eb04d352
parent 0bcba36f3f90488d2ef7502bd3c4f4920f2c4251

libext2fs: further optimize rb_test_bit

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

diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
index 900c0d3..a42eda1 100644
--- a/lib/ext2fs/blkmap64_rb.c
+++ b/lib/ext2fs/blkmap64_rb.c
@@ -40,6 +40,7 @@
 	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 @@
 		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 @@
 
 	bp->root = RB_ROOT;
 	bp->rcursor = NULL;
+	bp->rcursor_next = NULL;
 	bp->wcursor = NULL;
 
 #ifdef BMAP_STATS_OPS
@@ -306,7 +310,7 @@
 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 @@
 		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 @@
 			return 0;
 		}
 	}
+	bp->rcursor = NULL;
+	bp->rcursor_next = NULL;
 
 	rcursor = bp->wcursor;
 	if (!rcursor)
@@ -352,6 +364,7 @@
 			n = &(*n)->rb_right;
 		else {
 			bp->rcursor = ext;
+			bp->rcursor_next = NULL;
 			return 1;
 		}
 	}
@@ -368,6 +381,7 @@
 	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 @@
 
 	rb_free_tree(&bp->root);
 	bp->rcursor = NULL;
+	bp->rcursor_next = NULL;
 	bp->wcursor = NULL;
 }