Re: [PATCH 2/2] libext2fs: optimize rb_test_bit

["Lukáš Czerner" <lczerner@redhat.com>]

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