Re: ext3_group_sparse slow?

[Andreas Dilger <adilger@clusterfs.com>]

[-- Attachment #1: Type: text/plain, Size: 2853 bytes --]

On Jan 12, 2005  15:18 +0100, Jan Kara wrote:
> > On Jan 11, 2005  15:48 +0100, Jan Kara wrote:
> > >   I've been profiling dbench load on ext3 on my laptop and it looks as
> > > follows:
> > > CPU: CPU with timer interrupt, speed 0 MHz (estimated)
> > > Profiling through timer interrupt
> > > samples  %        symbol name
> > > 6540      1.5141  ext3_group_sparse
> > > 3615      0.8369  ext3_get_group_desc
> > 
> > The ext3_get_group_desc() code is using a div and mod, which may be
> > what is slowing things down there.  These could easily be changed to
> > shift and mask.  The ext3_group_desc struct is an on-disk struct and isn't
> > changing size any time soon (ever?) and is also a power of two in size.
> > We already even have s_desc_per_block_bits...  Totally untested patch:
> > 
> > --- 1.27/fs/ext3/balloc.c	2004-11-11 01:34:33 -07:00
> > +++ edited/fs/ext3/balloc.c	2005-01-11 11:04:55 -07:00
> > @@ -56,8 +56,8 @@
> >  	}
> >  	smp_rmb();
> >  
> > -	group_desc = block_group / EXT3_DESC_PER_BLOCK(sb);
> > -	desc = block_group % EXT3_DESC_PER_BLOCK(sb);
> > +	group_desc = block_group >> EXT3_DESC_PER_BLOCK_BITS(sb);
> > +	desc = block_group & (EXT3_DESC_PER_BLOCK(sb) - 1);
> >  	if (!EXT3_SB(sb)->s_group_desc[group_desc]) {
> >  		ext3_error (sb, "ext3_get_group_desc",
> >  			    "Group descriptor not loaded - "
>   This looks OK.
> 
> > > ext3_group_sparse()
> > 
> > As for ext3_group_sparse() this code is very inefficient for large
> > filesystems as it repeatedly does div and mod operations.  Far better
> > is to use an incremental method using multiplies
>
>   I agree with the idea but would not be the following solution better?
> It's simplier, you save the function call etc..
> 
> --- linux-2.6.10.orig/fs/ext3/balloc.c	2005-01-05 17:19:33.000000000 +0100
> +++ linux-2.6.10-ext3speedup/fs/ext3/balloc.c	2005-01-12 13:07:48.000000000 +0100
> @@ -1435,19 +1435,17 @@
>  
>  static inline int test_root(int a, int b)
>  {
> -	if (a == 0)
> -		return 1;
> -	while (1) {
> -		if (a == 1)
> -			return 1;
> -		if (a % b)
> -			return 0;
> -		a = a / b;
> -	}
> +	int num = b;
> +
> +	while (a > num)
> +		num *= b;
> +	return num == a;
>  }
>  
>  int ext3_group_sparse(int group)
>  {
> +	if (group <= 1)
> +		return 1;
>  	return (test_root(group, 3) || test_root(group, 5) ||
>  		test_root(group, 7));
>  }
> 
> I profiled your first patch + the above one and ext3_group_sparse()
> takes now 0.27% and ext3_get_group_desc() 0.33% which seems much better
> :) If you agree I can submit it to Andrew.

Sure, you can add my Signed-off-by: Andreas Dilger <adilger@clusterfs.com>

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://members.shaw.ca/adilger/             http://members.shaw.ca/golinux/


[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]