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. > > By using a hash of the offset as the starting point, lookups are > faster and independent from the array size. > > The hash is computed using the cluster number of the table, multiplied > by 4 to make it perform better when there are collisions. > > In my tests, using a cache with 2048 entries, this reduces the average > number of comparisons per lookup from 430 to 2.5. > > Signed-off-by: Alberto Garcia <be...@igalia.com> > --- > block/qcow2-cache.c | 9 +++++++-- > 1 file changed, 7 insertions(+), 2 deletions(-)
Reviewed-by: Stefan Hajnoczi <stefa...@redhat.com>
pgpwDYzprsil5.pgp
Description: PGP signature
