From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from eggs.gnu.org ([2001:4830:134:3::10]:52326)
	by lists.gnu.org with esmtp (Exim 4.71)
	(envelope-from <stefanha@gmail.com>) id 1YqItE-0001bo-5O
	for qemu-devel@nongnu.org; Thu, 07 May 2015 06:18:49 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
	(envelope-from <stefanha@gmail.com>) id 1YqIt9-0005a9-Pi
	for qemu-devel@nongnu.org; Thu, 07 May 2015 06:18:48 -0400
Date: Thu, 7 May 2015 11:18:41 +0100
From: Stefan Hajnoczi <stefanha@gmail.com>
Message-ID: <20150507101841.GI13985@stefanha-thinkpad.redhat.com>
References: <cover.1430919406.git.berto@igalia.com>
	<38be38957aff5457fd811db71706a6f645df5c7e.1430919406.git.berto@igalia.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha1;
	protocol="application/pgp-signature"; boundary="VkVuOCYP9O7H3CXI"
Content-Disposition: inline
In-Reply-To: <38be38957aff5457fd811db71706a6f645df5c7e.1430919406.git.berto@igalia.com>
Subject: Re: [Qemu-devel] [Qemu-block] [PATCH 5/7] qcow2: use a hash to look
 for entries in the L2 cache
List-Id: <qemu-devel.nongnu.org>
List-Unsubscribe: <https://lists.nongnu.org/mailman/options/qemu-devel>,
	<mailto:qemu-devel-request@nongnu.org?subject=unsubscribe>
List-Archive: <http://lists.nongnu.org/archive/html/qemu-devel>
List-Post: <mailto:qemu-devel@nongnu.org>
List-Help: <mailto:qemu-devel-request@nongnu.org?subject=help>
List-Subscribe: <https://lists.nongnu.org/mailman/listinfo/qemu-devel>,
	<mailto:qemu-devel-request@nongnu.org?subject=subscribe>
To: Alberto Garcia <berto@igalia.com>
Cc: Stefan Hajnoczi <stefanha@redhat.com>, qemu-devel@nongnu.org, qemu-block@nongnu.org


--VkVuOCYP9O7H3CXI
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Wed, May 06, 2015 at 04:39:29PM +0300, Alberto Garcia wrote:
> The current cache algorithm traverses the array starting always from
> the beginning, so the average number of comparisons needed to perform
> a lookup is proportional to the size of the array.
>=20
> By using a hash of the offset as the starting point, lookups are
> faster and independent from the array size.
>=20
> The hash is computed using the cluster number of the table, multiplied
> by 4 to make it perform better when there are collisions.
>=20
> In my tests, using a cache with 2048 entries, this reduces the average
> number of comparisons per lookup from 430 to 2.5.
>=20
> Signed-off-by: Alberto Garcia <berto@igalia.com>
> ---
>  block/qcow2-cache.c | 9 +++++++--
>  1 file changed, 7 insertions(+), 2 deletions(-)

Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com>

--VkVuOCYP9O7H3CXI
Content-Type: application/pgp-signature

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQEcBAEBAgAGBQJVSzwBAAoJEJykq7OBq3PINysH/jvQUgi8V7wgb/dG+vEEILQH
hujvB6N26HLHoBNGu17NMnUPVlqOOgfnnsW907fMzw8FX2wpCf1vap1oYOsulb5f
1uavYUr/93Io/7Xub8sHX17LesXLnAwIhXc4BXIHv9GIk9J9sIwLD4jdzqi7+LWk
Lu0Qjlt6QkwbdME9cToGVWdHxlvxBMsbL5BsyYG8C5hEuDQb6I40nlmbN/JNZ4W0
lGxtBSkMwUb3W2cxIKu5Dw1HdFnevbD7Pn7FhhTLUOnD2Tp8j55XufHPt+XRlJdg
FH6/2kXJs1G5s3nOmG77IcyeVGC3sRdVfzix6GbSTvq/2udggA2wrkbhsKKi4Yo=
=RXe9
-----END PGP SIGNATURE-----

--VkVuOCYP9O7H3CXI--