* ext3_group_sparse slow? @ 2005-01-11 14:48 Jan Kara 2005-01-11 18:37 ` Andreas Dilger 0 siblings, 1 reply; 4+ messages in thread From: Jan Kara @ 2005-01-11 14:48 UTC (permalink / raw) To: linux-fsdevel Hello! 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 ... What caught my eye is that ext3_group_sparse() and also ext3_get_group_desc() take so much time. OK, it's only 1.51 and 0.84 percent of the processor time and it is clearly pretty much dominated by the IO but anyway I think we need not spend so much processor time by such trivial operations :) Do you think it would be worth improving? Honza -- Jan Kara <jack@suse.cz> SuSE CR Labs ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: ext3_group_sparse slow? 2005-01-11 14:48 ext3_group_sparse slow? Jan Kara @ 2005-01-11 18:37 ` Andreas Dilger 2005-01-12 14:18 ` Jan Kara 0 siblings, 1 reply; 4+ messages in thread From: Andreas Dilger @ 2005-01-11 18:37 UTC (permalink / raw) To: Jan Kara; +Cc: linux-fsdevel [-- 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 --] ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: ext3_group_sparse slow? 2005-01-11 18:37 ` Andreas Dilger @ 2005-01-12 14:18 ` Jan Kara 2005-01-12 18:23 ` Andreas Dilger 0 siblings, 1 reply; 4+ messages in thread From: Jan Kara @ 2005-01-12 14:18 UTC (permalink / raw) To: Andreas Dilger, linux-fsdevel > 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 - " 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 (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. 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. Honza -- Jan Kara <jack@suse.cz> SuSE CR Labs ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: ext3_group_sparse slow? 2005-01-12 14:18 ` Jan Kara @ 2005-01-12 18:23 ` Andreas Dilger 0 siblings, 0 replies; 4+ messages in thread From: Andreas Dilger @ 2005-01-12 18:23 UTC (permalink / raw) To: Jan Kara; +Cc: linux-fsdevel [-- 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 --] ^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2005-01-12 20:23 UTC | newest] Thread overview: 4+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2005-01-11 14:48 ext3_group_sparse slow? Jan Kara 2005-01-11 18:37 ` Andreas Dilger 2005-01-12 14:18 ` Jan Kara 2005-01-12 18:23 ` Andreas Dilger
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).