From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([208.118.235.92]:36742) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UBPur-0005qr-4K for qemu-devel@nongnu.org; Fri, 01 Mar 2013 08:22:28 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UBPuo-00030V-4h for qemu-devel@nongnu.org; Fri, 01 Mar 2013 08:22:25 -0500 Received: from ssl.dlhnet.de ([91.198.192.8]:55410 helo=ssl.dlh.net) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UBPun-00030G-V0 for qemu-devel@nongnu.org; Fri, 01 Mar 2013 08:22:22 -0500 Message-ID: <5130AB93.8020101@dlhnet.de> Date: Fri, 01 Mar 2013 14:22:27 +0100 From: Peter Lieven MIME-Version: 1.0 References: <513096A1.8020008@dlhnet.de> <5130A419.9020903@redhat.com> In-Reply-To: <5130A419.9020903@redhat.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Subject: Re: [Qemu-devel] [PATCH] page_cache: use multiplicative hash for page position calculation List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Laszlo Ersek Cc: Orit Wasserman , "qemu-devel@nongnu.org" On 01.03.2013 13:50, Laszlo Ersek wrote: > On 03/01/13 12:53, Peter Lieven wrote: >> 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 >> --- >> 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 >> >> #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; >> } >> > > According to , > the multiplier "is chosen as the integer that is relatively prime to" > 2^64 "which is closest to" (sqrt(5)-1)/2 * 2^64. > > (sqrt(5)-1)/2 * 2^64 ~= 11400714819323198485.86699842797038469120 > > hence the constant would be a=0x9e3779b97f4a7c15. Any reason why a-2 is > used in the patch? no, actually I only googled this value and did not calculate it myself. Peter