[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-block] [PATCH 5/7] qcow2: use a hash to look for entries in th
From: |
Stefan Hajnoczi |
Subject: |
Re: [Qemu-block] [PATCH 5/7] qcow2: use a hash to look for entries in the L2 cache |
Date: |
Thu, 7 May 2015 11:18:41 +0100 |
User-agent: |
Mutt/1.5.23 (2014-03-12) |
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 <address@hidden>
> ---
> block/qcow2-cache.c | 9 +++++++--
> 1 file changed, 7 insertions(+), 2 deletions(-)
Reviewed-by: Stefan Hajnoczi <address@hidden>
pgpZXlXv8Jrj_.pgp
Description: PGP signature
- [Qemu-block] [PATCH 2/7] qcow2: simplify qcow2_cache_put() and qcow2_cache_entry_mark_dirty(), (continued)
- [Qemu-block] [PATCH 2/7] qcow2: simplify qcow2_cache_put() and qcow2_cache_entry_mark_dirty(), Alberto Garcia, 2015/05/06
- [Qemu-block] [PATCH 7/7] qcow2: style fixes in qcow2-cache.c, Alberto Garcia, 2015/05/06
- [Qemu-block] [PATCH 4/7] qcow2: remove qcow2_cache_find_entry_to_replace(), Alberto Garcia, 2015/05/06
- [Qemu-block] [PATCH 5/7] qcow2: use a hash to look for entries in the L2 cache, Alberto Garcia, 2015/05/06
- [Qemu-block] [PATCH 6/7] qcow2: make qcow2_cache_put() a void function, Alberto Garcia, 2015/05/06
- [Qemu-block] [PATCH 3/7] qcow2: use an LRU algorithm to replace entries from the L2 cache, Alberto Garcia, 2015/05/06