From nobody Tue Feb 10 09:40:59 2026 Delivered-To: importer@patchew.org Received-SPF: pass (zoho.com: domain of gnu.org designates 208.118.235.17 as permitted sender) client-ip=208.118.235.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zoho.com: domain of gnu.org designates 208.118.235.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=linaro.org Return-Path: Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) by mx.zohomail.com with SMTPS id 1537987175003992.5389243430274; Wed, 26 Sep 2018 11:39:35 -0700 (PDT) Received: from localhost ([::1]:60168 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1g5Eij-0003YC-Ji for importer@patchew.org; Wed, 26 Sep 2018 14:39:33 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:53678) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1g5Ego-0001ip-4e for qemu-devel@nongnu.org; Wed, 26 Sep 2018 14:37:36 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1g5Egm-0007R3-LO for qemu-devel@nongnu.org; Wed, 26 Sep 2018 14:37:34 -0400 Received: from mail-pf1-x431.google.com ([2607:f8b0:4864:20::431]:46617) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1g5Egm-0007QT-Az for qemu-devel@nongnu.org; Wed, 26 Sep 2018 14:37:32 -0400 Received: by mail-pf1-x431.google.com with SMTP id d8-v6so6931572pfo.13 for ; Wed, 26 Sep 2018 11:37:32 -0700 (PDT) Received: from cloudburst.twiddle.net (97-113-8-179.tukw.qwest.net. [97.113.8.179]) by smtp.gmail.com with ESMTPSA id b14-v6sm9735952pfc.178.2018.09.26.11.37.29 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Wed, 26 Sep 2018 11:37:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=gUr4Rg30kEa57DsN+a3e5NMAEgxvwTzfEYRCfyICEQw=; b=G464ZV8e20L2YVHWR7RatP/R8NfmkPYLSHM+PbuHSVbqb6OUVWqx2QZIDWjonPxaeF ztNhvEwJEexjIwGvtDdgvCxOdWmXMbIoaURgLhMUBev6EFo2zG9P/PHd3V3SS2xZU13x ZUsxoaELB86KaIQtezhKMJXtAMlSLXujPBkto= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=gUr4Rg30kEa57DsN+a3e5NMAEgxvwTzfEYRCfyICEQw=; b=lYmjQKY+zDdrcnfNNCzQWJshkAPFM3gFYQ1IDqAWzj1/3mBRPuR+Kzym4KwiWWTwDM DxeSy7BvaBz/aA6QKakilwB16fGDZLYhAygjPrNgEMilS00HVwtGvVAK2QpaBinz71EM PA0ufDrp2YB043qGaHmp5rSZOXUlv7hGvC0KEVckAoPrE37+ED/WUUctY+LBfPiFATKJ 6qCfB3d8y3ZSwvUxRYWjeElvS7qShqJM8YNNSUkgiexI4aGMKL7bRlcRp6MYNEIWRmVo JuNOUnujK4N0FvLBfVftnUX+OKY4j+KmQr4jmKrt0a0PwbN6sSHmHoc3ktHf28JK310p ZdDw== X-Gm-Message-State: ABuFfogwUsYx9dLmVgEFJ9kmMp0mDHDQlLgd2NRXWrj4+Cd6OHskNtZL hwqU+VKH1KS++60u0jNHNtMLl4O2cEQ= X-Google-Smtp-Source: ACcGV61Ykt6EFgcPeEpT5CSgVtppZBcmiAMRGTNQSJKxyexu9TjS1ktMLsbSCuwaWU7l/y5r0I5SdA== X-Received: by 2002:a17:902:40d:: with SMTP id 13-v6mr7288339ple.257.1537987050911; Wed, 26 Sep 2018 11:37:30 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Date: Wed, 26 Sep 2018 11:37:08 -0700 Message-Id: <20180926183709.21293-13-richard.henderson@linaro.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180926183709.21293-1-richard.henderson@linaro.org> References: <20180926183709.21293-1-richard.henderson@linaro.org> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2607:f8b0:4864:20::431 Subject: [Qemu-devel] [PULL 12/13] qht-bench: add -p flag to precompute hash values X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: peter.maydell@linaro.org, "Emilio G. Cota" Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: fail (Header signature does not verify) X-ZohoMail: RDMRC_1 RDKM_2 RSF_0 Z_629925259 SPT_0 Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" From: "Emilio G. Cota" Precomputing the hash values allows us to perform more frequent accesses to the hash table, thereby reaching higher throughputs. We keep the old behaviour by default, since (1) we might confuse users if they measured a speedup without changing anything in the QHT implementation, and (2) benchmarking the hash function "on line" is also valuable. Before: $ taskset -c 0 tests/qht-bench -n 1 Throughput: 38.18 MT/s After: $ taskset -c 0 tests/qht-bench -n 1 Throughput: 38.16 MT/s After (with precomputing): $ taskset -c 0 tests/qht-bench -n 1 -p Throughput: 50.87 MT/s Signed-off-by: Emilio G. Cota Signed-off-by: Richard Henderson --- tests/qht-bench.c | 26 ++++++++++++++++++++------ 1 file changed, 20 insertions(+), 6 deletions(-) diff --git a/tests/qht-bench.c b/tests/qht-bench.c index f492b3a20a..2089e2bed1 100644 --- a/tests/qht-bench.c +++ b/tests/qht-bench.c @@ -53,6 +53,7 @@ static unsigned long resize_delay =3D 1000; static double resize_rate; /* 0.0 to 1.0 */ static unsigned int n_rz_threads =3D 1; static QemuThread *rz_threads; +static bool precompute_hash; =20 static double update_rate; /* 0.0 to 1.0 */ static uint64_t update_threshold; @@ -101,11 +102,18 @@ static bool is_equal(const void *ap, const void *bp) return *a =3D=3D *b; } =20 -static inline uint32_t h(unsigned long v) +static uint32_t h(unsigned long v) { return tb_hash_func7(v, 0, 0, 0, 0); } =20 +static uint32_t hval(unsigned long v) +{ + return v; +} + +static uint32_t (*hfunc)(unsigned long v) =3D h; + /* * From: https://en.wikipedia.org/wiki/Xorshift * This is faster than rand_r(), and gives us a wider range (RAND_MAX is o= nly @@ -149,7 +157,7 @@ static void do_rw(struct thread_info *info) bool read; =20 p =3D &keys[info->r & (lookup_range - 1)]; - hash =3D h(*p); + hash =3D hfunc(*p); read =3D qht_lookup(&ht, p, hash); if (read) { stats->rd++; @@ -158,7 +166,7 @@ static void do_rw(struct thread_info *info) } } else { p =3D &keys[info->r & (update_range - 1)]; - hash =3D h(*p); + hash =3D hfunc(*p); if (info->write_op) { bool written =3D false; =20 @@ -289,7 +297,9 @@ static void htable_init(void) /* avoid allocating memory later by allocating all the keys now */ keys =3D g_malloc(sizeof(*keys) * n); for (i =3D 0; i < n; i++) { - keys[i] =3D populate_offset + i; + long val =3D populate_offset + i; + + keys[i] =3D precompute_hash ? h(val) : hval(val); } =20 /* some sanity checks */ @@ -321,7 +331,7 @@ static void htable_init(void) =20 r =3D xorshift64star(r); p =3D &keys[r & (init_range - 1)]; - hash =3D h(*p); + hash =3D hfunc(*p); if (qht_insert(&ht, p, hash, NULL)) { break; } @@ -412,7 +422,7 @@ static void parse_args(int argc, char *argv[]) int c; =20 for (;;) { - c =3D getopt(argc, argv, "d:D:g:k:K:l:hn:N:o:r:Rs:S:u:"); + c =3D getopt(argc, argv, "d:D:g:k:K:l:hn:N:o:pr:Rs:S:u:"); if (c < 0) { break; } @@ -451,6 +461,10 @@ static void parse_args(int argc, char *argv[]) case 'o': populate_offset =3D atol(optarg); break; + case 'p': + precompute_hash =3D true; + hfunc =3D hval; + break; case 'r': update_range =3D pow2ceil(atol(optarg)); break; --=20 2.17.1