From patchwork Fri Mar 1 11:53:05 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peter Lieven X-Patchwork-Id: 224292 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 45A4B2C02A3 for ; Fri, 1 Mar 2013 22:53:23 +1100 (EST) Received: from localhost ([::1]:57196 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UBOWe-0006ue-SG for incoming@patchwork.ozlabs.org; Fri, 01 Mar 2013 06:53:20 -0500 Received: from eggs.gnu.org ([208.118.235.92]:47161) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UBOWM-0006tu-Df for qemu-devel@nongnu.org; Fri, 01 Mar 2013 06:53:06 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UBOWJ-0002oi-SH for qemu-devel@nongnu.org; Fri, 01 Mar 2013 06:53:02 -0500 Received: from ssl.dlhnet.de ([91.198.192.8]:54657 helo=ssl.dlh.net) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UBOWJ-0002oS-Lu for qemu-devel@nongnu.org; Fri, 01 Mar 2013 06:52:59 -0500 Received: from localhost (localhost [127.0.0.1]) by ssl.dlh.net (Postfix) with ESMTP id E166514DB62; Fri, 1 Mar 2013 12:52:57 +0100 (CET) X-Virus-Scanned: Debian amavisd-new at ssl.dlh.net Received: from ssl.dlh.net ([127.0.0.1]) by localhost (ssl.dlh.net [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id PzHtTG6R7bBH; Fri, 1 Mar 2013 12:52:57 +0100 (CET) Received: from [172.21.12.60] (unknown [82.141.1.226]) by ssl.dlh.net (Postfix) with ESMTPSA id 863F214DACC; Fri, 1 Mar 2013 12:52:57 +0100 (CET) Message-ID: <513096A1.8020008@dlhnet.de> Date: Fri, 01 Mar 2013 12:53:05 +0100 From: Peter Lieven User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130221 Thunderbird/17.0.3 MIME-Version: 1.0 To: "qemu-devel@nongnu.org" X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 91.198.192.8 Cc: Orit Wasserman Subject: [Qemu-devel] [PATCH] page_cache: use multiplicative hash for page position calculation X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org 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; }