From mboxrd@z Thu Jan 1 00:00:00 1970 From: Andreas Dilger Subject: Re: ext3_group_sparse slow? Date: Tue, 11 Jan 2005 11:37:03 -0700 Message-ID: <20050111183703.GE8098@schnapps.adilger.int> References: <20050111144843.GG15061@atrey.karlin.mff.cuni.cz> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="VV4b6MQE+OnNyhkM" Cc: linux-fsdevel@vger.kernel.org Return-path: Received: from moraine.clusterfs.com ([66.96.26.190]:52197 "EHLO moraine.clusterfs.com") by vger.kernel.org with ESMTP id S261498AbVAKShG (ORCPT ); Tue, 11 Jan 2005 13:37:06 -0500 To: Jan Kara Content-Disposition: inline In-Reply-To: <20050111144843.GG15061@atrey.karlin.mff.cuni.cz> Sender: linux-fsdevel-owner@vger.kernel.org List-Id: linux-fsdevel.vger.kernel.org --VV4b6MQE+OnNyhkM Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable 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 > ... >=20 > 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(); =20 - group_desc =3D block_group / EXT3_DESC_PER_BLOCK(sb); - desc =3D block_group % EXT3_DESC_PER_BLOCK(sb); + group_desc =3D block_group >> EXT3_DESC_PER_BLOCK_BITS(sb); + desc =3D 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 - " =20 > 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. =3D=3D=3D=3D=3D fs/ext3/balloc.c 1.27 vs edited =3D=3D=3D=3D=3D --- 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); } =20 -static inline int test_root(int a, int b) +int ext3_group_sparse(int group) { - if (a =3D=3D 0) + unsigned int three =3D 1, five =3D 5, seven =3D 7; + unsigned int grp; + + if (!(fs->flags & FL_SPARSE)) return 1; - while (1) { - if (a =3D=3D 1) - return 1; - if (a % b) - return 0; - a =3D a / b; - } -} =20 -int ext3_group_sparse(int group) -{ - return (test_root(group, 3) || test_root(group, 5) || - test_root(group, 7)); + if (group =3D=3D 0) + return 1; + + while ((grp =3D ext3_list_backups(fs, &three, &five, &seven)) < group) + /* do nothing */; + + return (grp =3D=3D group); } =20 /** Cheers, Andreas -- Andreas Dilger http://sourceforge.net/projects/ext2resize/ http://members.shaw.ca/adilger/ http://members.shaw.ca/golinux/ --VV4b6MQE+OnNyhkM Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.3 (GNU/Linux) iD8DBQFB5BzPpIg59Q01vtYRAh0KAJ9+i7HdxuvARc/2aZ/x0BT6bwOKOQCfTWoS ct/r1i8J50dpcRsx+3+ehX0= =A4Lt -----END PGP SIGNATURE----- --VV4b6MQE+OnNyhkM--