Re: [Qemu-devel] [Qemu-block] [PATCH 5/7] qcow2: use a hash to look for entries in the L2 cache

[Max Reitz <mreitz@redhat.com>]

On 06.05.2015 15:39, 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 <berto@igalia.com>
> ---
>   block/qcow2-cache.c | 9 +++++++--
>   1 file changed, 7 insertions(+), 2 deletions(-)

So it's a direct-mapped cache, unless the entry has been used, in which 
case it becomes a fully associative cache...

Let's assume the cache is full. Now this hash algorithm (direct mapped 
cache) basically becomes futile, because the LRU algorithm (fully 
associative cache) takes over, and any entry (the LRU entry) is 
replaced, independently of the cache. Thus, the entry will most probably 
not be placed at its hashed position. So once the cache is full, I guess 
this algorithm doesn't help a lot, does it?

(I'm sorry if you had this discussion before...)

Max