From patchwork Fri May 26 21:16:23 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 9751203 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id A57A260249 for ; Fri, 26 May 2017 21:23:08 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 8A0A628449 for ; Fri, 26 May 2017 21:23:08 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 7B78628459; Fri, 26 May 2017 21:23:08 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 8B75228449 for ; Fri, 26 May 2017 21:23:07 +0000 (UTC) Received: from localhost ([::1]:38543 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dEMhO-0006Qv-44 for patchwork-qemu-devel@patchwork.kernel.org; Fri, 26 May 2017 17:23:06 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:40560) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dEMbT-0000fx-U2 for qemu-devel@nongnu.org; Fri, 26 May 2017 17:17:01 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1dEMbS-0008L4-DB for qemu-devel@nongnu.org; Fri, 26 May 2017 17:16:59 -0400 Received: from mail-qk0-x243.google.com ([2607:f8b0:400d:c09::243]:35448) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1dEMbS-0008Kv-7h for qemu-devel@nongnu.org; Fri, 26 May 2017 17:16:58 -0400 Received: by mail-qk0-x243.google.com with SMTP id k74so2660614qke.2 for ; Fri, 26 May 2017 14:16:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=sender:from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=kwzLLNiTp1S0cI7SNAFu5LlATQLWK5nsL2E85V/0Oqo=; b=jT3/g8bPJ3zfD5bvQLQ95l4gth9A5hVDlEAwDPwTzVnXAn5WLSifQKu2SIonPTBjjh SJCqpIvToiEf9s5I6P7KEf2YOpFD0i4BHpCF5D4Sn6JBRbsnGEb4q6lZoLP8+zU+RN96 211eDpY8s5ns4kVcu+e4Zr3Qc8yapzuln386aC5zoC83R/nq9GG76G5cZW2/YBarWQTX 8s1g+010KFLG3OpCpPLCHbMztVkKGUYD80PAI1vg7TGhT8b4gq4saEByickearvxFKk5 /WADCBzdV91taReaUlLSWPLZwQCaVtfkleayA5nD3GVLGGHoRogIftGTskLDfJFfKiER 56Zw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:from:to:cc:subject:date:message-id :in-reply-to:references:mime-version:content-transfer-encoding; bh=kwzLLNiTp1S0cI7SNAFu5LlATQLWK5nsL2E85V/0Oqo=; b=qxV6BSF2UNcthRiV8Yy/XqHgzUGGeJGjptRkvCXlQXk/BrP1uNwzInbHIK+SZe3JA1 /+Bd7ZDOpUEemVkSMwJpFFN8eQ6DRmXgc9eEfQOmnovlnO/RPepTuFaz492Nm4Op/e3b zEh3zfTDLIfN8PnAGOEgBIHwE61EfqHcgN+JCrnGDIl7x6K4wsicj3wVo3gfny2oFsle AYbU98Z3oSQLQZ8lh7T+WlDoTC9JkrNTCzq+ZG6fMK79KXwn4w/dDPf4mcK2ylhkyrI3 yXGcGdTmc/6mJrwoQ7KvtHXbUry3qpiCfQHvk2dp/lxvE+Pb1c2n6FncTwWgDLPqbdKy j1eg== X-Gm-Message-State: AODbwcDwxSkiSOYXrPfqkszTTfArv2bcWkSY4zHzOylDyNVWut9dw8TO +TJR6KRF+cPLtUI51zk= X-Received: by 10.55.113.199 with SMTP id m190mr4239066qkc.176.1495833417392; Fri, 26 May 2017 14:16:57 -0700 (PDT) Received: from bigtime.twiddle.net.com ([2602:47:d954:1500:5e51:4fff:fe40:9c64]) by smtp.gmail.com with ESMTPSA id u19sm1262380qtc.64.2017.05.26.14.16.56 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 26 May 2017 14:16:56 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Date: Fri, 26 May 2017 14:16:23 -0700 Message-Id: <20170526211638.32301-12-rth@twiddle.net> X-Mailer: git-send-email 2.9.4 In-Reply-To: <20170526211638.32301-1-rth@twiddle.net> References: <20170526211638.32301-1-rth@twiddle.net> MIME-Version: 1.0 X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2607:f8b0:400d:c09::243 Subject: [Qemu-devel] [PATCH v7 11/26] tb-hash: improve tb_jmp_cache hash function in user mode 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: "Emilio G. Cota" Errors-To: qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org Sender: "Qemu-devel" X-Virus-Scanned: ClamAV using ClamSMTP From: "Emilio G. Cota" Optimizations to cross-page chaining and indirect branches make performance more sensitive to the hit rate of tb_jmp_cache. The constraint of reserving some bits for the page number lowers the achievable quality of the hashing function. However, user-mode does not have this requirement. Thus, with this change we use for user-mode a hashing function that is both faster and of better quality than the previous one. Measurements: Note: baseline (i.e. speedup == 1x) is QEMU v2.9.0. - SPECint06 (test set), x86_64-linux-user. Host: Intel i7-6700K @ 4.00GHz 2.2x +-+--------------------------------------------------------------------------------------------------------------+-+ | | | jr | 2x +jr+multhash +....................................................+++++...................................+-+ | jr+hash |$$$ | | |$+$ | | ### $ | 1.8x +-+......................................................................#|#.$...................................+-+ | ++#+# $ | | |# # $ | 1.6x +-+....................................................................***.#.$....................++$$$..........+-+ | $$$ *+* # $ |$+$ | | ++$$$ ### $ * * # $ +++|$ $ | | ++###+$ # # $ * * # $ ### ****## $ | 1.4x +-+...................***+#.$.........***.#.$..........................*.*.#.$...........#+#$$.*++*|#.$..........+-+ | *+* # $ * * # $ * * # $ # # $ * *+# $ | | * * # $ +++++ * * # $ * * # $ *** # $ * * # $ ###$$ | 1.2x +-+...................*.*.#.$.***##$$.*.*.#.$..........................*.*.#.$.........*.*.#.$.*..*.#.$.***+#+$..+-+ | * * # $ *+* # $ * * # $ +++ * * # $ ++###$$ * * # $ * * # $ * * # $ | | ***##$$ * * # $ * * # $ * * # $ ***##$$ ++### * * # $ *** #+$ * * # $ * * # $ * * # $ | | *+*+#+$ ***##$$$ * * # $ * * # $ * * # $ *+* # $ ++####$$ ***+# * * # $ * * # $ * * # $ * * # $ * * # $ | 1x +-++-*+*+#+$+*+*+#-+$+*+*-#+$+*+*+#+$+*+*+#+$+*-*+#+$+***++#+$+*+*+#$$+*+*+#+$+*+*+#+$+*+*-#+$+*+-*+#+$+*+*+#+$-++-+ | * * # $ * * # $ * * # $ * * # $ * * # $ * * # $ * * # $ * * # $ * * # $ * * # $ * * # $ * * # $ * * # $ | | * * # $ * * # $ * * # $ * * # $ * * # $ * * # $ * * # $ * * # $ * * # $ * * # $ * * # $ * * # $ * * # $ | 0.8x +-+--***##$$-***##$$$-***##$$-***##$$-***##$$-***##$$-***###$$-***##$$-***##$$-***##$$-***##$$-****##$$-***##$$--+-+ astar bzip2 gcc gobmk h264ref hmmlibquantum mcf omnetpperlbench sjengxalancbmk hmean png: http://imgur.com/4UXTrEc Here I also tried the hash function suggested by Paolo ("multhash"): return ((uint64_t) (pc * 2654435761) >> 32) & (TB_JMP_CACHE_SIZE - 1); As you can see it is just as good as the other new function ("hash"), which is what I ended up going with. - SPECint06 (train set), x86_64-linux-user. Host: Intel i7-6700K @ 4.00GHz 2.6x +-+--------------------------------------------------------------------------------------------------------------+-+ | | | jr ### | 2.4x +jr+hash...........................................................................................#.#...........+-+ | # # | | # # | 2.2x +-+................................................................................................#.#...........+-+ | # # | | # # | 2x +-+................................................................................................#.#...........+-+ | **** # | | * * # | 1.8x +-+.............................................................................................*..*.#...........+-+ | +++ * * # | | #### #### * * # | 1.6x +-+......................................####.............................#..#.****..#..........*..*.#...........+-+ | +++ #++# **** # * * # #### * * # | | ### # # * * # * * # # # * * # | 1.4x +-+...................****+#..........****..#..........................*..*..#.*..*..#....#..#..*..*.#...........+-+ | *++* # * * # * * # * * # *** # * * # #### | | * * # #### * * # * * # * * # * * # * * # **** # | 1.2x +-+...................*..*.#..****++#.*..*..#..........................*..*..#.*..*..#..*.*..#..*..*.#..*..*..#..+-+ | ****### * * # * * # * * # * * # * * # * * # * * # * * # | | * * # ***### * * # * * # * * # ****## * * # * * # * * # * * # * * # | 1x +-+--****###--***###--****##--****###-****###--***###--***###--****##--****###-****###--***###--****##--****###--+-+ astar bzip2 gcc gobmk h264ref hmmlibquantum mcf omnetpperlbench sjengxalancbmk hmean png: http://imgur.com/ArCbHqo - NBench, x86_64-linux-user. Host: Intel i7-6700K @ 4.00GHz 1.12x +-+-------------------------------------------------------------------------------------------------------------+-+ | | | jr +++ | 1.1x +jr+hash...........................................................####.........................................+-+ | +++#| # | | | #++# | 1.08x +-+................................+++................+++.+++..*****..#.........................................+-+ | | +++ | | * | * # | | | | | | *+++* # | 1.06x +-+................................****###.............|...|...*...*..#.........................+++.............+-+ | *| * |# ****### * * # | | | *| *++# *| * |# * * # #### | 1.04x +-+................................*++*..#............*|.*.|#..*...*..#........................#.|#.............+-+ | * * # *++*++# * * # +++#++# | | * * # * * # * * # | # # +++#### | 1.02x +-+................................*..*..#......+++...*..*..#..*...*..#.....................****..#..*****++#...+-+ | +++ * * # +++ | * * # * * # +++ *| * # *+++* # | | +++ | +++ +++ ++++++ * * # *****### * * # * * # | +++ ++++++ *++* # * * # | 1x +-++-+++++####++****###++++-+####+-*++*++#-+*+++*-+#++*++*++#++*+-+*++#+-+++####-+*****###++*++*++#++*+-+*++#+-++-+ | *****| # *++* |# *****| # * * # * *++# * * # * * # **** |# * * # * * # * * # | | * | *| # * *++# * | *++# * * # * * # * * # * * # *| *++# * * # * * # * * # | 0.98x +-+...*.|.*++#..*..*..#..*+++*..#..*..*..#..*...*..#..*..*..#..*...*..#..*++*..#..*...*..#..*..*..#..*...*..#...+-+ | *+++* # * * # * * # * * # * * # * * # * * # * * # * * # * * # * * # | | * * # * * # * * # * * # * * # * * # * * # * * # * * # * * # * * # | 0.96x +-+---*****###--****###--*****###--****###--*****###--****###--*****###--****###--*****###--****###--*****###---+-+ ASSIGNMENT BITFIELD FOURFP EMULATION HUFFMAN LU DECOMPOSITIONEURAL NNUMERIC SOSTRING SORT hmean png: http://imgur.com/ZXFX0hJ - NBench, arm-linux-user. Host: Intel i7-4790K @ 4.00GHz 1.3x +-+-------------------------------------------------------------------------------------------------------------+-+ | #### | | jr # # +++ | 1.25x +jr+hash.....................#..#...........................................####................................+-+ | # # # # | | # # # # | 1.2x +-+..........................#..#...........................................#..#................................+-+ | # # # # | | # # # # | 1.15x +-+..........................#..#...........................................#..#................................+-+ | # # #### # # | | # # # # # # | 1.1x +-+..........................#..#..................................#..#.....#..#................................+-+ | # # # # # # +++ | | # # #### # # # # #### | 1.05x +-+..........................#..#...............#..#.....####......#..#.....#..#.........................#..#...+-+ | # # # # # # # # # # +++ # # | | +++ ***** # #### ***** # # # +++# # **** # ****### # # | 1x +-++-+*****###++****+++++*+-+*++#+-****++#-+*+++*-+#+++++#++#++*****++#+-*++*++#-+*****-++++*++*++#++*****++#+-++-+ | * * # * * | * * # * * # * * # **** # * * # * * # * *### * *++# * * # | | * * # * *### * * # * * # * * # * * # * * # * * # * * # * * # * * # | 0.95x +-+...*...*..#..*..*.|#..*...*..#..*..*..#..*...*..#..*..*..#..*...*..#..*..*..#..*...*..#..*..*..#..*...*..#...+-+ | * * # * * |# * * # * * # * * # * * # * * # * * # * * # * * # * * # | | * * # * * |# * * # * * # * * # * * # * * # * * # * * # * * # * * # | 0.9x +-+---*****###--****###--*****###--****###--*****###--****###--*****###--****###--*****###--****###--*****###---+-+ ASSIGNMENT BITFIELD FOURFP EMULATION HUFFMAN LU DECOMPOSITIONEURAL NNUMERIC SOSTRING SORT hmean png: http://imgur.com/FfD27ey Reviewed-by: Alex Bennée Reviewed-by: Richard Henderson Signed-off-by: Emilio G. Cota Message-Id: <1493263764-18657-12-git-send-email-cota@braap.org> Signed-off-by: Richard Henderson --- include/exec/tb-hash.h | 12 ++++++++++++ 1 file changed, 12 insertions(+) diff --git a/include/exec/tb-hash.h b/include/exec/tb-hash.h index 2c27490..b1fe2d0 100644 --- a/include/exec/tb-hash.h +++ b/include/exec/tb-hash.h @@ -22,6 +22,8 @@ #include "exec/tb-hash-xx.h" +#ifdef CONFIG_SOFTMMU + /* Only the bottom TB_JMP_PAGE_BITS of the jump cache hash bits vary for addresses on the same page. The top bits are the same. This allows TLB invalidation to quickly clear a subset of the hash table. */ @@ -45,6 +47,16 @@ static inline unsigned int tb_jmp_cache_hash_func(target_ulong pc) | (tmp & TB_JMP_ADDR_MASK)); } +#else + +/* In user-mode we can get better hashing because we do not have a TLB */ +static inline unsigned int tb_jmp_cache_hash_func(target_ulong pc) +{ + return (pc ^ (pc >> TB_JMP_CACHE_BITS)) & (TB_JMP_CACHE_SIZE - 1); +} + +#endif /* CONFIG_SOFTMMU */ + static inline uint32_t tb_hash_func(tb_page_addr_t phys_pc, target_ulong pc, uint32_t flags) {