[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [PATCH] page_cache: use multiplicative hash for page positi
From: |
Peter Lieven |
Subject: |
[Qemu-devel] [PATCH] page_cache: use multiplicative hash for page position calculation |
Date: |
Fri, 01 Mar 2013 12:53:05 +0100 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130221 Thunderbird/17.0.3 |
instead of a linear mapping we use a multiplicative hash
with the golden ratio to derive the cache bucket from the
address. this helps to reduce collisions if memory positions
are multiple of the cache size and it avoids a division
in the position calculation.
Signed-off-by: Peter Lieven <address@hidden>
---
page_cache.c | 5 ++++-
1 file changed, 4 insertions(+), 1 deletion(-)
diff --git a/page_cache.c b/page_cache.c
index 376f1db..45d769a 100644
--- a/page_cache.c
+++ b/page_cache.c
@@ -24,6 +24,7 @@
#include <strings.h>
#include "qemu-common.h"
+#include "qemu/host-utils.h"
#include "migration/page_cache.h"
#ifdef DEBUG_CACHE
@@ -48,6 +49,7 @@ struct PageCache {
int64_t max_num_items;
uint64_t max_item_age;
int64_t num_items;
+ uint64_t hash_shift_bits;
};
PageCache *cache_init(int64_t num_pages, unsigned int page_size)
@@ -72,6 +74,7 @@ PageCache *cache_init(int64_t num_pages, unsigned int
page_size)
cache->num_items = 0;
cache->max_item_age = 0;
cache->max_num_items = num_pages;
+ cache->hash_shift_bits = clz64(num_pages-1);
DPRINTF("Setting cache buckets to %" PRId64 "\n", cache->max_num_items);
@@ -108,7 +111,7 @@ static size_t cache_get_cache_pos(const PageCache *cache,
size_t pos;
g_assert(cache->max_num_items);
- pos = (address / cache->page_size) & (cache->max_num_items - 1);
+ pos = (address * 0x9e3779b97f4a7c13) >> cache->hash_shift_bits;
return pos;
}
--
1.7.9.5
- [Qemu-devel] [PATCH] page_cache: use multiplicative hash for page position calculation,
Peter Lieven <=