[patch] ext2: Apply Jack's ext3 speedups

[patch] ext2: Apply Jack's ext3 speedups

[pmeda]

Apply ext3 speedups added by Jan Kara to ext2.
Reference: http://linus.bkbits.net:8080/linux-2.5/gnupatch@41f127f2jwYahmKm0eWTJNpYcSyhPw

Signed-off-by: Prasanna Meda <pmeda@akamai.com>

--- a/fs/ext2/balloc.c	Wed Jan 26 23:04:10 2005
+++ b/fs/ext2/balloc.c	Wed Jan 26 23:04:28 2005
@@ -53,8 +53,8 @@ struct ext2_group_desc * ext2_get_group_
 		return NULL;
 	}
 	
-	group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
-	offset = block_group % EXT2_DESC_PER_BLOCK(sb);
+	group_desc = block_group >> EXT2_DESC_PER_BLOCK_BITS(sb);
+	offset = block_group & (EXT2_DESC_PER_BLOCK(sb) - 1);
 	if (!sbi->s_group_desc[group_desc]) {
 		ext2_error (sb, "ext2_get_group_desc",
 			    "Group descriptor not loaded - "
@@ -575,19 +575,17 @@ block_in_use(unsigned long block, struct
 
 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;
 }
 
 static int ext2_group_sparse(int group)
 {
+	if (group <= 0)
+		return 1;
 	return (test_root(group, 3) || test_root(group, 5) ||
 		test_root(group, 7));
 }
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: [patch] ext2: Apply Jack's ext3 speedups

[Theodore Ts'o]

On Wed, Jan 26, 2005 at 11:22:39PM -0800, pmeda@akamai.com wrote:
> 
> Apply ext3 speedups added by Jan Kara to ext2.
> Reference: http://linus.bkbits.net:8080/linux-2.5/gnupatch@41f127f2jwYahmKm0eWTJNpYcSyhPw
> 

This patch isn't right, as it causes ext2_sparse_group(1) to return 0
instead of 1.  Block groups number 0 and 1 must always contain a
superblock.

>  static int ext2_group_sparse(int group)
>  {
> +	if (group <= 0)
> +		return 1;

Change this to be:

+	if (group <= 1)
+		return 1;

and it should fix the patch (as well as be similar to the ext3
mainline).  With this change,

Acked-by: "Theodore Ts'o" <tytso@mit.edu>

						- Ted
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: [patch] ext2: Apply Jack's ext3 speedups

[Andrew Morton]

"Theodore Ts'o" <tytso@mit.edu> wrote:
>
> On Wed, Jan 26, 2005 at 11:22:39PM -0800, pmeda@akamai.com wrote:
> > 
> > Apply ext3 speedups added by Jan Kara to ext2.
> > Reference: http://linus.bkbits.net:8080/linux-2.5/gnupatch@41f127f2jwYahmKm0eWTJNpYcSyhPw
> > 
> 
> This patch isn't right, as it causes ext2_sparse_group(1) to return 0
> instead of 1.  Block groups number 0 and 1 must always contain a
> superblock.

I'd already queued up the below actually.  It seems to get things right?


From: Matthew Wilcox <matthew@wil.cx>

Port Andreas Dilger's and Jan Kara's patch for ext3 to ext2.  Also some
whitespace changes to get ext2/ext3 closer in sync.

Signed-off-by: Matthew Wilcox <matthew@wil.cx>
Signed-off-by: Andrew Morton <akpm@osdl.org>
---

 25-akpm/fs/ext2/balloc.c |   39 +++++++++++++++++++--------------------
 1 files changed, 19 insertions(+), 20 deletions(-)

diff -puN fs/ext2/balloc.c~minor-ext2-speedup fs/ext2/balloc.c
--- 25/fs/ext2/balloc.c~minor-ext2-speedup	2005-01-25 13:50:20.000000000 -0800
+++ 25-akpm/fs/ext2/balloc.c	2005-01-25 13:50:20.000000000 -0800
@@ -6,7 +6,7 @@
  * Laboratoire MASI - Institut Blaise Pascal
  * Universite Pierre et Marie Curie (Paris VI)
  *
- *  Enhanced block allocation by Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
+ *  Enhanced block allocation by Stephen Tweedie (sct@redhat.com), 1993
  *  Big-endian to little-endian byte-swapping/bitmaps by
  *        David S. Miller (davem@caip.rutgers.edu), 1995
  */
@@ -52,9 +52,9 @@ struct ext2_group_desc * ext2_get_group_
 
 		return NULL;
 	}
-	
-	group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
-	offset = block_group % EXT2_DESC_PER_BLOCK(sb);
+
+	group_desc = block_group >> EXT2_DESC_PER_BLOCK_BITS(sb);
+	offset = block_group & (EXT2_DESC_PER_BLOCK(sb) - 1);
 	if (!sbi->s_group_desc[group_desc]) {
 		ext2_error (sb, "ext2_get_group_desc",
 			    "Group descriptor not loaded - "
@@ -62,7 +62,7 @@ struct ext2_group_desc * ext2_get_group_
 			     block_group, group_desc, offset);
 		return NULL;
 	}
-	
+
 	desc = (struct ext2_group_desc *) sbi->s_group_desc[group_desc]->b_data;
 	if (bh)
 		*bh = sbi->s_group_desc[group_desc];
@@ -236,12 +236,12 @@ do_more:
 
 	for (i = 0, group_freed = 0; i < count; i++) {
 		if (!ext2_clear_bit_atomic(sb_bgl_lock(sbi, block_group),
-					bit + i, (void *) bitmap_bh->b_data))
-			ext2_error (sb, "ext2_free_blocks",
-				      "bit already cleared for block %lu",
-				      block + i);
-		else
+						bit + i, bitmap_bh->b_data)) {
+			ext2_error(sb, __FUNCTION__,
+				"bit already cleared for block %lu", block + i);
+		} else {
 			group_freed++;
+		}
 	}
 
 	mark_buffer_dirty(bitmap_bh);
@@ -569,25 +569,24 @@ unsigned long ext2_count_free_blocks (st
 static inline int
 block_in_use(unsigned long block, struct super_block *sb, unsigned char *map)
 {
-	return ext2_test_bit ((block - le32_to_cpu(EXT2_SB(sb)->s_es->s_first_data_block)) %
+	return ext2_test_bit ((block -
+		le32_to_cpu(EXT2_SB(sb)->s_es->s_first_data_block)) %
 			 EXT2_BLOCKS_PER_GROUP(sb), map);
 }
 
 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;
 }
 
 static int ext2_group_sparse(int group)
 {
+	if (group <= 1)
+		return 1;
 	return (test_root(group, 3) || test_root(group, 5) ||
 		test_root(group, 7));
 }
_

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: [patch] ext2: Apply Jack's ext3 speedups

[Theodore Ts'o]

On Thu, Jan 27, 2005 at 01:11:58PM -0800, Andrew Morton wrote:
> "Theodore Ts'o" <tytso@mit.edu> wrote:
> >
> > On Wed, Jan 26, 2005 at 11:22:39PM -0800, pmeda@akamai.com wrote:
> > > 
> > > Apply ext3 speedups added by Jan Kara to ext2.
> > > Reference: http://linus.bkbits.net:8080/linux-2.5/gnupatch@41f127f2jwYahmKm0eWTJNpYcSyhPw
> > > 
> > 
> > This patch isn't right, as it causes ext2_sparse_group(1) to return 0
> > instead of 1.  Block groups number 0 and 1 must always contain a
> > superblock.
> 
> I'd already queued up the below actually.  It seems to get things right?

Looks good to me.

						- Ted
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: [patch] ext2: Apply Jack's ext3 speedups

[Prasanna Meda]

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

Theodore Ts'o wrote:

> On Wed, Jan 26, 2005 at 11:22:39PM -0800, pmeda@akamai.com wrote:
> >
> > Apply ext3 speedups added by Jan Kara to ext2.
> > Reference: http://linus.bkbits.net:8080/linux-2.5/gnupatch@41f127f2jwYahmKm0eWTJNpYcSyhPw
> >
>
> This patch isn't right, as it causes ext2_sparse_group(1) to return 0
> instead of 1.  Block groups number 0 and 1 must always contain a
> superblock.
>
> >  static int ext2_group_sparse(int group)
> >  {
> > +     if (group <= 0)
> > +             return 1;
>
> Change this to be:
>
> +       if (group <= 1)
> +               return 1;
>
> and it should fix the patch (as well as be similar to the ext3
> mainline).  With this change,
>
> Acked-by: "Theodore Ts'o" <tytso@mit.edu>

 Thanks for correction!  I made one more attempt to improve it.
 Please look at the attached patch.

  - Folded all three root checkings for 3,  5 and 7 into one loop.
  -  Short cut the loop with 3**n < 5 **n < 7**n logic.
  -  Even numbers can be ruled out.

  Tested with  user space programs.


Thanks,
Prasanna.


[-- Attachment #2: ext3_test_root_loops_folding.patch --]
[-- Type: text/plain, Size: 2414 bytes --]



Two changes in test_root algorithm, so that number of multiplications
and loops will become less.
 - Fold the root checking for 3, 5, 7 into a single loop.
 - Exploit the concepts 3**n < 5**n < 7**n, and odd**n is odd number.

Logic: On the whole, folded(new) should perfrom better than unfolded(old).
The advantage with new method is, log7 n is lesser than log3 n.

When a is even number, old: log3 n + log5 n + log7 n, multiplications in new: 0
When a is odd number, and
 When a is exact power of 3, old: log3 n, new: log3 n + log5 n + log7 n.
 When a is exact power of 5, old: log3 n + log5 n, new: 2 * log5 n + log7 n.
 When a is exact power of 7, old: log3 n + log5 n + log7 n, new: 3 * log7 n.
 When it is not exact power, old: log3 n + log5 n + log7 n,
 and the new one is also: log3 n + log5 n + log7 n, I see slight impovement here
 too(did not expect), perhaps because of the result of the loop coding.
 Number of such nonexact numbers in n numbers is n - log3 n - log5 n - log7 n,
 so it is good.

An attempt to summarise the observed results:
 When a is small power of 3, unfolded is 50% better, but when
 a is bigger power of 3, it is around 25% better(log3 n and code dominates
 log7 n). When a is power of 5 or 7, folded is 30 to 60% better.
 When a is not power of 3, 5 or 7, folded is 10 to 30% better.


Signed-off-by: Prasanna Meda <pmeda@akamai.com>


--- a/fs/ext3/balloc.c	Fri Jan 28 12:21:45 2005
+++ b/fs/ext3/balloc.c	Fri Jan 28 14:46:32 2005
@@ -1438,21 +1438,43 @@
 			 EXT3_BLOCKS_PER_GROUP(sb), map);
 }
 
-static inline int test_root(int a, int b)
+/*
+ * Checks power(3,n) == a, or power(5,n) == a or power(7,n) == a for some +ve n.
+ * Hints: power(3,n) < power(5,n) < power(7,n), and power can not be even.
+ */
+static inline int test_root(int a)
 {
-	int num = b;
+	int power3 = 3, power5 = 5, power7 = 7;
 
-	while (a > num)
-		num *= b;
-	return num == a;
+	if  (!(a & 1))
+		return 0;
+
+	if  (power5 == a || power7 == a)
+		return 1;
+
+	while (a > power3) {
+		power3 *= 3;
+
+		if (a < power5)
+			continue;
+		power5 *= 5;
+		if (power5 == a)
+			return 1;
+
+		if (a < power7)
+			continue;
+		power7 *= 7;
+		if (power7 == a)
+			return 1;
+	}
+	return (power3 == a);
 }
 
 static int ext3_group_sparse(int group)
 {
 	if (group <= 1)
 		return 1;
-	return (test_root(group, 3) || test_root(group, 5) ||
-		test_root(group, 7));
+	return (test_root(group));
 }
 
 /**

Re: [patch] ext2: Apply Jack's ext3 speedups

[Prasanna Meda]

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

Prasanna Meda wrote:

>   - Folded all three root checkings for 3,  5 and 7 into one loop.
>   -  Short cut the loop with 3**n < 5 **n < 7**n logic.
>   -  Even numbers can be ruled out.
>
>   Tested with  user space programs.

  Test program and results attached.



Thanks,
Prasanna.

[-- Attachment #2: testroot.c --]
[-- Type: text/plain, Size: 1781 bytes --]

/* 
 * TEST program to test root(a).
 * cc a.c -O3 -Wall -S
 *
 * Fold the root checking for 3, 5, 7 into a single loop
 * and exploit the concepts 3**n < 5**n < 7**n, and odd**n is odd.
 * And also odd power can not be even.
 * So number of multiplications will become less.
 */

#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>

static inline int test_root(int a, int b)
{
	int num = b;

	while(a > num)
		num *= b;

	return (num == a);
}

/* loop algorithm folded, shortcut 3*logn multiplications.  */
static inline int test_root2(int a)
{
	int num3 = 3, num5 = 5, num7 = 7;

	if  (num5 == a || num7 == a)
		return 1;

	if  (!(a & 1))
		return 0;

	while (a > num3) {
		num3 *= 3;

		if (a < num5)
			continue;
		num5 *= 5;
		if (num5 == a)
			return 1;

		if (a < num7)
			continue;
		num7 *= 7;
		if (num7 == a)
			return 1;
	}
	return (num3 == a);
}

/* 6*loglogn multiplications */
int test_root3(int a, int b)
{
	int factor, power = 1, guess = b;

	while (a >= guess)  {
		for (factor = b; a >= guess; factor *= factor) {
			power = guess;
			guess = guess * factor;
		}
		guess = power * b;
	}

	return (power == a);
}

int main(int argc, char *argv[])
{
	int a, b, d, ret = 0;

	if (argc < 3) {
		printf("Usage: %s num1 method\n", argv[0]);
		return 1;
	}
	a = atoi(argv[2]);  b = atoi(argv[1]);
	if (a != 1 && a != 2) {
		printf("%s: Method is one of the 1, 2 or 3.\n", argv[0]);
		return 1;
	}

	for (d = 1; d <10000000; d++) {
		switch(a) {
		case 1:
			ret = test_root(b, 3)
				|| test_root(b, 5)
				|| test_root(b, 7);
			break;
		case 2:
			ret = test_root2(b);
			break;
		}
	}

	switch(a) {
	case 1:
		printf("\nunfolded Alg:");
		break;
	case 2:
		printf("\nfolded   Alg:");
		break;
	}
	printf("%u is %s sparse\n", b, ret?"":"not");
	return 0;
}


[-- Attachment #3: testrootresults.txt --]
[-- Type: text/plain, Size: 1875 bytes --]


# time ./a.out 2401 1; sleep 1; time ./a.out 2401 2

unfolded Alg:2401 is  sparse

real	0m2.485s
user	0m2.334s
sys	0m0.007s

folded   Alg:2401 is  sparse

real	0m1.047s
user	0m0.822s
sys	0m0.003s

# time ./a.out 2400 1; sleep 1; time ./a.out 2400 2 # even before even check.

unfolded Alg:2400 is not sparse

real	0m2.186s
user	0m2.083s
sys	0m0.003s

folded   Alg:2400 is not sparse

real	0m1.640s
user	0m1.418s
sys	0m0.003s

# time ./a.out 2400 2 # after adding even check.

folded   Alg:2400 is not sparse

real	0m0.277s
user	0m0.275s
sys	0m0.002s

# time ./a.out 625 1; sleep 1; time ./a.out 625 2

unfolded Alg:625 is  sparse

real	0m0.901s
user	0m0.715s
sys	0m0.004s

folded   Alg:625 is  sparse

real	0m0.542s
user	0m0.524s
sys	0m0.004s
 
# time ./a.out 243 1; sleep 1; time ./a.out 243 2

unfolded Alg:243 is  sparse

real	0m0.453s
user	0m0.442s
sys	0m0.003s

folded   Alg:243 is  sparse

real	0m0.854s
user	0m0.823s
sys	0m0.004s

# time ./a.out 729 1; sleep 1; time ./a.out 729 2

unfolded Alg:729 is  sparse

real	0m1.077s
user	0m1.062s
sys	0m0.001s

folded   Alg:729 is  sparse

real	0m1.083s
user	0m1.010s
sys	0m0.003s

# time ./a.out 6561 1; sleep 1; time ./a.out 6561 2

unfolded Alg:6561 is  sparse

real	0m1.299s
user	0m1.281s
sys	0m0.001s

folded   Alg:6561 is  sparse

real	0m1.436s
user	0m1.410s
sys	0m0.004s

# time ./a.out 15625 1; sleep 1; time ./a.out 15625 2

unfolded Alg:15625 is  sparse

real	0m2.259s
user	0m2.209s
sys	0m0.002s

folded   Alg:15625 is not sparse

real	0m1.896s
user	0m1.801s
sys	0m0.006s

# time ./a.out 15626 1; sleep 1; time ./a.out 15626 2

unfolded Alg:15626 is not sparse

real	0m2.609s
user	0m2.493s
sys	0m0.002s

folded   Alg:15626 is not sparse

real	0m2.209s
user	0m1.804s
sys	0m0.004s

# time ./a.out 15626 2 # after adding even number check

folded   Alg:15626 is not sparse

real	0m0.283s
user	0m0.276s
sys	0m0.001s

test_root reorder(Re: [patch] ext2: Apply Jack's ext3 speedups)

[Prasanna Meda]

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

Prasanna Meda wrote:

>   - Folded all three root checkings for 3,  5 and 7 into one loop.
>   -  Short cut the loop with 3**n < 5 **n < 7**n logic.
>   -  Even numbers can be ruled out.

Without going to that complicated path, the better performance
is achieved with just reordering  of the tests from 3,5,7 to 7,5.3, so
that average case becomes better. This is more simpler than
 folding  patch.


Thanks,
Prasanna.


[-- Attachment #2: ext3_test_root_reorder.patch --]
[-- Type: text/plain, Size: 524 bytes --]



 Reorder test_root testing from 3,5,7 to 7,5,3 so
 that average case becomes good. Even number check
 is added. 

 Signed-off-by: Prasanna Meda <pmeda@akamai.com>

--- a/fs/ext3/balloc.c	Fri Jan 28 22:21:45 2005
+++ b/fs/ext3/balloc.c	Sat Jan 29 02:51:39 2005
@@ -1451,8 +1451,10 @@
 {
 	if (group <= 1)
 		return 1;
-	return (test_root(group, 3) || test_root(group, 5) ||
-		test_root(group, 7));
+	if (!(group & 1))
+		return 0;
+	return (test_root(group, 7) || test_root(group, 5) ||
+		test_root(group, 3));
 }
 
 /**

Re: test_root reorder(Re: [patch] ext2: Apply Jack's ext3 speedups)

[Jan Kara]

> Prasanna Meda wrote:
> 
> >   - Folded all three root checkings for 3,  5 and 7 into one loop.
> >   -  Short cut the loop with 3**n < 5 **n < 7**n logic.
> >   -  Even numbers can be ruled out.
> 
> Without going to that complicated path, the better performance
> is achieved with just reordering  of the tests from 3,5,7 to 7,5.3, so
> that average case becomes better. This is more simpler than
>  folding  patch.
  I like a bit more just to reorder the tests (though I agree that your
joined tests for 3,5,7 are probably faster) - it looks much more
readable...

>  Reorder test_root testing from 3,5,7 to 7,5,3 so
>  that average case becomes good. Even number check
>  is added. 
> 
>  Signed-off-by: Prasanna Meda <pmeda@akamai.com>
> 
> --- a/fs/ext3/balloc.c	Fri Jan 28 22:21:45 2005
> +++ b/fs/ext3/balloc.c	Sat Jan 29 02:51:39 2005
> @@ -1451,8 +1451,10 @@
>  {
>  	if (group <= 1)
>  		return 1;
> -	return (test_root(group, 3) || test_root(group, 5) ||
> -		test_root(group, 7));
> +	if (!(group & 1))
> +		return 0;
> +	return (test_root(group, 7) || test_root(group, 5) ||
> +		test_root(group, 3));
>  }
>  
>  /**

								Honza

-- 
Jan Kara <jack@suse.cz>
SuSE CR Labs
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: test_root reorder(Re: [patch] ext2: Apply Jack's ext3 speedups)

[Prasanna Meda]

Jan Kara wrote:

> > Prasanna Meda wrote:
> >
> > >   - Folded all three root checkings for 3,  5 and 7 into one loop.
> > >   -  Short cut the loop with 3**n < 5 **n < 7**n logic.
> > >   -  Even numbers can be ruled out.
> >
> > Without going to that complicated path, the better performance
> > is achieved with just reordering  of the tests from 3,5,7 to 7,5.3, so
> > that average case becomes better. This is more simpler than
> >  folding  patch.
>   I like a bit more just to reorder the tests (though I agree that your
> joined tests for 3,5,7 are probably faster) - it looks much more
> readable...

Yes, Also reordering is almost same as folding aproach in
experimental  test. So, there is no need of going to that complicated
 path. Just  reorder 7, 5 and 3 and check for evenness.


Thanks,
Prasanna.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>