diff options
| author | Alberto Garcia | 2015-05-11 14:54:57 +0200 |
|---|---|---|
| committer | Kevin Wolf | 2015-05-22 17:08:01 +0200 |
| commit | 812e4082cae73e12fd425cace4fd3a715a7c1d32 (patch) | |
| tree | d7405b5a8c87135628ea2d72a7ba93786969f96f /include | |
| parent | qcow2: remove qcow2_cache_find_entry_to_replace() (diff) | |
| download | qemu-812e4082cae73e12fd425cace4fd3a715a7c1d32.tar.gz qemu-812e4082cae73e12fd425cace4fd3a715a7c1d32.tar.xz qemu-812e4082cae73e12fd425cace4fd3a715a7c1d32.zip | |
qcow2: use a hash to look for entries in the L2 cache
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>
Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com>
Signed-off-by: Kevin Wolf <kwolf@redhat.com>
Diffstat (limited to 'include')
0 files changed, 0 insertions, 0 deletions