| 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
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
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 >
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;
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(-)