Re: ext3_group_sparse slow?

[Andreas Dilger <adilger@clusterfs.com>]

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

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
> 100485   23.2633  __copy_to_user_ll
> 54497    12.6166  __copy_from_user_ll
> 34702     8.0339  acpi_processor_idle
> 15107     3.4974  link_path_walk
> 8229      1.9051  __d_lookup
> 6540      1.5141  ext3_group_sparse
> 6490      1.5025  __might_sleep
> 4972      1.1511  sysenter_past_esp
> 3981      0.9216  kmem_cache_alloc
> 3797      0.8790  ext3_readdir
> 3617      0.8374  find_get_page
> 3615      0.8369  ext3_get_group_desc
> 3589      0.8309  ext3_do_update_inode
> ...
> 
> ext3_get_group_desc() take so much time.

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 - "
 
> 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 (untested patch below).
The ext3_list_backups() function is in ext3/resize.c, so may need an
entry in a header somewhere.

It may be as good to use a table lookup since the number of groups with
backup superblocks in a filesystem is actually very small but given that
CPU speeds are growing much faster than memory speed it might be faster
to do a few multiples (at most 20 for a 16TB filesystem) than to have a
cache miss.

===== fs/ext3/balloc.c 1.27 vs edited =====
--- 1.27/fs/ext3/balloc.c	2004-11-11 01:34:33 -07:00
+++ edited/fs/ext3/balloc.c	2005-01-11 11:27:04 -07:00
@@ -1433,23 +1433,21 @@
 			 EXT3_BLOCKS_PER_GROUP(sb), map);
 }
 
-static inline int test_root(int a, int b)
+int ext3_group_sparse(int group)
 {
-	if (a == 0)
+	unsigned int three = 1, five = 5, seven = 7;
+	unsigned int grp;
+
+	if (!(fs->flags & FL_SPARSE))
 		return 1;
-	while (1) {
-		if (a == 1)
-			return 1;
-		if (a % b)
-			return 0;
-		a = a / b;
-	}
-}
 
-int ext3_group_sparse(int group)
-{
-	return (test_root(group, 3) || test_root(group, 5) ||
-		test_root(group, 7));
+	if (group == 0)
+		return 1;
+
+	while ((grp = ext3_list_backups(fs, &three, &five, &seven)) < group)
+		/* do nothing */;
+
+	return (grp == group);
 }
 
 /**

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