[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [PULL 09/22] qcow2: use a hash to look for entries in the L
From: |
Kevin Wolf |
Subject: |
[Qemu-devel] [PULL 09/22] qcow2: use a hash to look for entries in the L2 cache |
Date: |
Fri, 22 May 2015 17:26:27 +0200 |
From: Alberto Garcia <address@hidden>
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>
Reviewed-by: Stefan Hajnoczi <address@hidden>
Signed-off-by: Kevin Wolf <address@hidden>
---
block/qcow2-cache.c | 9 +++++++--
1 file changed, 7 insertions(+), 2 deletions(-)
diff --git a/block/qcow2-cache.c b/block/qcow2-cache.c
index 2035cd8..121e6e9 100644
--- a/block/qcow2-cache.c
+++ b/block/qcow2-cache.c
@@ -248,6 +248,7 @@ static int qcow2_cache_do_get(BlockDriverState *bs,
Qcow2Cache *c,
BDRVQcowState *s = bs->opaque;
int i;
int ret;
+ int lookup_index;
uint64_t min_lru_counter = UINT64_MAX;
int min_lru_index = -1;
@@ -255,7 +256,8 @@ static int qcow2_cache_do_get(BlockDriverState *bs,
Qcow2Cache *c,
offset, read_from_disk);
/* Check if the table is already cached */
- for (i = 0; i < c->size; i++) {
+ i = lookup_index = (offset / s->cluster_size * 4) % c->size;
+ do {
const Qcow2CachedTable *t = &c->entries[i];
if (t->offset == offset) {
goto found;
@@ -264,7 +266,10 @@ static int qcow2_cache_do_get(BlockDriverState *bs,
Qcow2Cache *c,
min_lru_counter = t->lru_counter;
min_lru_index = i;
}
- }
+ if (++i == c->size) {
+ i = 0;
+ }
+ } while (i != lookup_index);
if (min_lru_index == -1) {
/* This can't happen in current synchronous code, but leave the check
--
1.8.3.1
- [Qemu-devel] [PULL 00/22] Block layer core and image format patches, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 02/22] nvme: support NVME_VOLATILE_WRITE_CACHE feature, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 04/22] vmdk: Fix overflow if l1_size is 0x20000000, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 03/22] vmdk: Fix next_cluster_sector for compressed write, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 01/22] qcow2: Flush pending discards before allocating cluster, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 06/22] qcow2: simplify qcow2_cache_put() and qcow2_cache_entry_mark_dirty(), Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 05/22] qcow2: use one single memory block for the L2/refcount cache tables, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 07/22] qcow2: use an LRU algorithm to replace entries from the L2 cache, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 08/22] qcow2: remove qcow2_cache_find_entry_to_replace(), Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 11/22] qcow2: style fixes in qcow2-cache.c, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 09/22] qcow2: use a hash to look for entries in the L2 cache,
Kevin Wolf <=
- [Qemu-devel] [PULL 12/22] qemu-io: Use getopt() correctly, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 10/22] qcow2: make qcow2_cache_put() a void function, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 13/22] block: Detect multiplication overflow in bdrv_getlength, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 14/22] qemu-iotests: qemu-img info on afl VMDK image with a huge capacity, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 18/22] util: allow \n to terminate password input, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 16/22] qcow2/qcow: protect against uninitialized encryption key, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 17/22] util: move read_password method out of qemu-img into osdep/oslib, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 20/22] tests: add test case for encrypted qcow2 read/write, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 15/22] qemu-iotests: Make debugging python tests easier, Kevin Wolf, 2015/05/22
- [Qemu-devel] [PULL 21/22] MAINTAINERS: Add header files to Block Layer Core section, Kevin Wolf, 2015/05/22