Patchwork [2/2] libext2fs: optimize rb_test_bit

login
register
mail settings
Submitter Theodore Ts'o
Date Oct. 5, 2012, 3:44 a.m.
Message ID <1349408695-11661-2-git-send-email-tytso@mit.edu>
Download mbox | patch
Permalink /patch/189420/
State Accepted
Headers show

Comments

Theodore Ts'o - Oct. 5, 2012, 3:44 a.m.
Optimize testing for a bit in an rbtree-based bitmap for the case
where the calling application is scanning through the bitmap
sequentially.  Previously, we did this for a set of bits which were
inside an allocated extent, but we did not optimize the case where
there was a large number of bits after an allocated extents which were
not in use.

             1111111111111110000000000000000000
             ^ optimized    ^not optimized

In my tests of a roughly half-filled file system, the run time of
e2freefrag was halved, and the cpu time spent in userspace was during
e2fsck's pass 5 was reduced by a factor of 30%.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 lib/ext2fs/blkmap64_rb.c | 16 ++++++++++++++--
 1 file changed, 14 insertions(+), 2 deletions(-)
Lukas Czerner - Oct. 8, 2012, 8:08 a.m.
On Thu, 4 Oct 2012, Theodore Ts'o wrote:

> Date: Thu,  4 Oct 2012 23:44:55 -0400
> 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/2] libext2fs: optimize rb_test_bit
> 
> Optimize testing for a bit in an rbtree-based bitmap for the case
> where the calling application is scanning through the bitmap
> sequentially.  Previously, we did this for a set of bits which were
> inside an allocated extent, but we did not optimize the case where
> there was a large number of bits after an allocated extents which were
> not in use.
> 
>              1111111111111110000000000000000000
>              ^ optimized    ^not optimized
> 
> In my tests of a roughly half-filled file system, the run time of
> e2freefrag was halved, and the cpu time spent in userspace was during
> e2fsck's pass 5 was reduced by a factor of 30%.

Hi Ted,

the patch and the idea behind it look fine, especially when we're
walking the bitmap sequentially not modifying it simultaneously, but
I have one question/suggestion below.

> 
> Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
> ---
>  lib/ext2fs/blkmap64_rb.c | 16 ++++++++++++++--
>  1 file changed, 14 insertions(+), 2 deletions(-)
> 
> diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
> index a83f8ac..c9006f8 100644
> --- a/lib/ext2fs/blkmap64_rb.c
> +++ b/lib/ext2fs/blkmap64_rb.c
> @@ -314,8 +314,8 @@ 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;
> -	struct rb_node *parent = NULL;
> +	struct bmap_rb_extent *rcursor, *next_ext;
> +	struct rb_node *parent = NULL, *next;
>  	struct rb_node **n = &bp->root.rb_node;
>  	struct bmap_rb_extent *ext;
>  
> @@ -330,6 +330,18 @@ 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);
> +		if ((bit >= rcursor->start + rcursor->count) &&
> +		    (bit < next_ext->start)) {

what about using the next_ext once we're holding it to check the bit
? On sequential walk this shout make sense to do so since we
actually should hit this if we're not in rcursor nor between rcursor
and next_ext.

So maybe something like this ?  (untested)

	if (next && (bit >= rcursor->start + rcursor->count)) {
		next_ext = ext2fs_rb_entry(next, struct bmap_rb_extent, node);
		if (bit < next_ext->start)) {
#ifdef BMAP_STATS_OPS
			bp->test_hit++;
#endif
			return 0;
		} else if (bit < next_ext->start + next_ext->count) {
#ifdef BMAP_STATS_OPS
			bp->test_hit++;
#endif
			*bp->rcursor = next_ext;
			return 1;
		}

What do you think ? Maybe it is worth testing, whether
the advantages are higher than additional condition ?

Thanks!
-Lukas


> +	}
> +
>  	rcursor = *bp->wcursor;
>  	if (!rcursor)
>  		goto search_tree;
> 
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Lukas Czerner - Oct. 8, 2012, 8:25 a.m.
On Mon, 8 Oct 2012, Lukáš Czerner wrote:

> Date: Mon, 8 Oct 2012 10:08:54 +0200 (CEST)
> From: Lukáš Czerner <lczerner@redhat.com>
> To: Theodore Ts'o <tytso@mit.edu>
> Cc: Ext4 Developers List <linux-ext4@vger.kernel.org>
> Subject: Re: [PATCH 2/2] libext2fs: optimize rb_test_bit
> 
> On Thu, 4 Oct 2012, Theodore Ts'o wrote:
> 
> > Date: Thu,  4 Oct 2012 23:44:55 -0400
> > 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/2] libext2fs: optimize rb_test_bit
> > 
> > Optimize testing for a bit in an rbtree-based bitmap for the case
> > where the calling application is scanning through the bitmap
> > sequentially.  Previously, we did this for a set of bits which were
> > inside an allocated extent, but we did not optimize the case where
> > there was a large number of bits after an allocated extents which were
> > not in use.
> > 
> >              1111111111111110000000000000000000
> >              ^ optimized    ^not optimized
> > 
> > In my tests of a roughly half-filled file system, the run time of
> > e2freefrag was halved, and the cpu time spent in userspace was during
> > e2fsck's pass 5 was reduced by a factor of 30%.
> 
> Hi Ted,
> 
> the patch and the idea behind it look fine, especially when we're
> walking the bitmap sequentially not modifying it simultaneously, but
> I have one question/suggestion below.

Also for this kind of usage it might actually make sense to have
something like:

get_next_zero_bit
get_next_set_bit

which would be much more effective than testing single bits, but it
would require actually using this in e2fsprogs tools.

Thanks!
-Lukas

> 
> > 
> > Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
> > ---
> >  lib/ext2fs/blkmap64_rb.c | 16 ++++++++++++++--
> >  1 file changed, 14 insertions(+), 2 deletions(-)
> > 
> > diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
> > index a83f8ac..c9006f8 100644
> > --- a/lib/ext2fs/blkmap64_rb.c
> > +++ b/lib/ext2fs/blkmap64_rb.c
> > @@ -314,8 +314,8 @@ 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;
> > -	struct rb_node *parent = NULL;
> > +	struct bmap_rb_extent *rcursor, *next_ext;
> > +	struct rb_node *parent = NULL, *next;
> >  	struct rb_node **n = &bp->root.rb_node;
> >  	struct bmap_rb_extent *ext;
> >  
> > @@ -330,6 +330,18 @@ 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);
> > +		if ((bit >= rcursor->start + rcursor->count) &&
> > +		    (bit < next_ext->start)) {
> 
> what about using the next_ext once we're holding it to check the bit
> ? On sequential walk this shout make sense to do so since we
> actually should hit this if we're not in rcursor nor between rcursor
> and next_ext.
> 
> So maybe something like this ?  (untested)
> 
> 	if (next && (bit >= rcursor->start + rcursor->count)) {
> 		next_ext = ext2fs_rb_entry(next, struct bmap_rb_extent, node);
> 		if (bit < next_ext->start)) {
> #ifdef BMAP_STATS_OPS
> 			bp->test_hit++;
> #endif
> 			return 0;
> 		} else if (bit < next_ext->start + next_ext->count) {
> #ifdef BMAP_STATS_OPS
> 			bp->test_hit++;
> #endif
> 			*bp->rcursor = next_ext;
> 			return 1;
> 		}
> 
> What do you think ? Maybe it is worth testing, whether
> the advantages are higher than additional condition ?
> 
> Thanks!
> -Lukas
> 
> 
> > +	}
> > +
> >  	rcursor = *bp->wcursor;
> >  	if (!rcursor)
> >  		goto search_tree;
> > 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>
Theodore Ts'o - Oct. 8, 2012, 6:17 p.m.
On Mon, Oct 08, 2012 at 10:25:19AM +0200, Lukáš Czerner wrote:
> > the patch and the idea behind it look fine, especially when we're
> > walking the bitmap sequentially not modifying it simultaneously, but
> > I have one question/suggestion below.
> 
> Also for this kind of usage it might actually make sense to have
> something like:
> 
> get_next_zero_bit
> get_next_set_bit
> 
> which would be much more effective than testing single bits, but it
> would require actually using this in e2fsprogs tools.

Yes, I thought about that, and in fact we already have find_first_zero
(which takes a starting offset, so works for both find_first and
find_next).  When we introduced this, though, we accidentally
introduced a bug at first.

At some point I agree it would be good to implement find_first_set(),
and writing new unit tests, and then modify e2freefrag, e2fsck, and
dumpe2fs to use it.  But in the applications is actually pretty
tricky, and I didn't have the time I figured would be necessary to
really do the changes right, and validate/test them properly.

So yes, I agree this would be much more effective, and ultimately
would result in further speedups in e2fsck and e2freefrag in
particular.  It would also allow us to take out the test_bit
optimizations which do have a slight cost for random access reads ---
and this is measurable when looking at the results of the CPU time for
e2fsck pass 4 in particular.  It's just that the performance hit for
the random access test_bit case is very tiny compared with the huge
wins in the sequential scan case.

> > what about using the next_ext once we're holding it to check the bit
> > ? On sequential walk this shout make sense to do so since we
> > actually should hit this if we're not in rcursor nor between rcursor
> > and next_ext.

Yes, I implemented that in the 2/3 commit in the follow-on patch
series.

Cheers!

						 - Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Patch

diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
index a83f8ac..c9006f8 100644
--- a/lib/ext2fs/blkmap64_rb.c
+++ b/lib/ext2fs/blkmap64_rb.c
@@ -314,8 +314,8 @@  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;
-	struct rb_node *parent = NULL;
+	struct bmap_rb_extent *rcursor, *next_ext;
+	struct rb_node *parent = NULL, *next;
 	struct rb_node **n = &bp->root.rb_node;
 	struct bmap_rb_extent *ext;
 
@@ -330,6 +330,18 @@  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);
+		if ((bit >= rcursor->start + rcursor->count) &&
+		    (bit < next_ext->start)) {
+#ifdef BMAP_STATS_OPS
+			bp->test_hit++;
+#endif
+			return 0;
+		}
+	}
+
 	rcursor = *bp->wcursor;
 	if (!rcursor)
 		goto search_tree;