From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([208.118.235.92]:56800) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UHzjA-0005jY-6g for qemu-devel@nongnu.org; Tue, 19 Mar 2013 12:49:36 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UHzj8-0005M0-ME for qemu-devel@nongnu.org; Tue, 19 Mar 2013 12:49:32 -0400 Received: from mx1.redhat.com ([209.132.183.28]:30927) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UHzj8-0005Lq-EW for qemu-devel@nongnu.org; Tue, 19 Mar 2013 12:49:30 -0400 Message-ID: <51489715.7050103@redhat.com> Date: Tue, 19 Mar 2013 10:49:25 -0600 From: Eric Blake MIME-Version: 1.0 References: <1363362619-3190-1-git-send-email-pl@kamp.de> <1363362619-3190-5-git-send-email-pl@kamp.de> In-Reply-To: <1363362619-3190-5-git-send-email-pl@kamp.de> Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="----enig2VBTXCGBFXETAKJWRCWDH" Subject: Re: [Qemu-devel] [PATCHv2 4/9] bitops: use vector algorithm to optimize find_next_bit() List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Peter Lieven Cc: qemu-devel@nongnu.org This is an OpenPGP/MIME signed message (RFC 4880 and 3156) ------enig2VBTXCGBFXETAKJWRCWDH Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On 03/15/2013 09:50 AM, Peter Lieven wrote: > this patch adds the usage of buffer_find_nonzero_offset() > to skip large areas of zeroes. >=20 > compared to loop unrolling presented in an earlier > patch this adds another 50% performance benefit for > skipping large areas of zeroes. loop unrolling alone > added close to 100% speedup. >=20 > Signed-off-by: Peter Lieven > --- > util/bitops.c | 26 +++++++++++++++++++++++--- > 1 file changed, 23 insertions(+), 3 deletions(-) > + while (size >=3D BITS_PER_LONG) { > + if ((tmp =3D *p)) { > + goto found_middle; > + } > + if (((uintptr_t) p) % sizeof(VECTYPE) =3D=3D 0=20 > + && size >=3D BITS_PER_BYTE * sizeof(VECTYPE) > + * BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) { Another instance where a helper function to check for alignment would be nice. Except this time you have a BITS_PER_BYTE factor, so you would be calling something like buffer_can_use_vectors(buf, size / BITS_PER_BYTE) > + unsigned long tmp2 =3D > + buffer_find_nonzero_offset(p, ((size / BITS_PER_BYTE) = &=20 > + ~(BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR = *=20 > + sizeof(VECTYPE) - 1))); Type mismatch - buffer_find_nonzero_offset returns size_t, which isn't necessarily the same size as unsigned long. I'm not sure if it can bite you. > + result +=3D tmp2 * BITS_PER_BYTE; > + size -=3D tmp2 * BITS_PER_BYTE; > + p +=3D tmp2 / sizeof(unsigned long); > + if (!size) { > + return result; > + } > + if (tmp2) { Do you really need this condition, or would it suffice to just 'continue;' the loop? Once buffer_find_nonzero_offset returns anything that leaves size as non-zero, we are guaranteed that the loop will goto found_middle without any further calls to buffer_find_nonzero_offset. > + if ((tmp =3D *p)) { > + goto found_middle; > + } > + } > } > + p++; > result +=3D BITS_PER_LONG; > size -=3D BITS_PER_LONG; > } >=20 --=20 Eric Blake eblake redhat com +1-919-301-3266 Libvirt virtualization library http://libvirt.org ------enig2VBTXCGBFXETAKJWRCWDH Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.13 (GNU/Linux) Comment: Public key at http://people.redhat.com/eblake/eblake.gpg Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQEcBAEBCAAGBQJRSJcVAAoJEKeha0olJ0NqUO8H/jW62zbVRxdDpBfxEre7Aarc TZUHzB3Qk3SnwDomkBZUR9UlMD8MzAWJz7goqbSdF52XUJ4Tn0nSh/OkhWq68ykK WO0N7OBfk8jL/XkELhmbqMno7eGpQwCKtH3kHmNIItWrAMZjA3EERdmgUFJBvNue eT/yzIt4XpfHK6QRIViSV8lV+6Tafa2wpvL8FiL9UlR0fqfdRRqgX+X9qa76OHlt yuMqXV9job3nRv3mUOivTovSLPzkRU3cglFRnufp3JiX1DDToJWWnedepI5gwh5D v4pVrpuSYfvhWJCCz1MOrnV1EPJpiaFB9NN/jkIeavVdV9u06PAn3vhjQvruCvs= =DXyF -----END PGP SIGNATURE----- ------enig2VBTXCGBFXETAKJWRCWDH--