From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:59197) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1awLfJ-0003v2-Vm for qemu-devel@nongnu.org; Fri, 29 Apr 2016 23:34:04 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1awLf7-00005F-FN for qemu-devel@nongnu.org; Fri, 29 Apr 2016 23:33:52 -0400 Received: from out5-smtp.messagingengine.com ([66.111.4.29]:33198) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1awLf6-0008TW-6E for qemu-devel@nongnu.org; Fri, 29 Apr 2016 23:33:45 -0400 Received: from compute1.internal (compute1.nyi.internal [10.202.2.41]) by mailout.nyi.internal (Postfix) with ESMTP id 145FA20AAC for ; Fri, 29 Apr 2016 23:33:21 -0400 (EDT) From: "Emilio G. Cota" Date: Fri, 29 Apr 2016 23:33:11 -0400 Message-Id: <1461987197-31264-9-git-send-email-cota@braap.org> In-Reply-To: <1461987197-31264-1-git-send-email-cota@braap.org> References: <1461987197-31264-1-git-send-email-cota@braap.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Subject: [Qemu-devel] [PATCH v4 08/14] tb hash: hash phys_pc, pc, and flags with xxhash List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: QEMU Developers , MTTCG Devel Cc: =?UTF-8?q?Alex=20Benn=C3=A9e?= , Paolo Bonzini , Peter Crosthwaite , Richard Henderson , Sergey Fedorov For some workloads such as arm bootup, tb_phys_hash is performance-critical. The is due to the high frequency of accesses to the hash table, originated by (frequent) TLB flushes that wipe out the cpu-private tb_jmp_cache's. More info: https://lists.nongnu.org/archive/html/qemu-devel/2016-03/msg05098.html To dig further into this I modified an arm image booting debian jessie to immediately shut down after boot. Analysis revealed that quite a bit of time is unnecessarily spent in tb_phys_hash: the cause is poor hashing that results in very uneven loading of chains in the hash table's buckets; the longest observed chain had ~550 elements. The appended addresses this with two changes: 1) Use xxhash as the hash table's hash function. xxhash is a fast, high-quality hashing function. 2) Feed the hashing function with not just tb_phys, but also pc and flags. This improves performance over using just tb_phys for hashing, since that resulted in some hash buckets having many TB's, while others getting very few; with these changes, the longest observed chain on a single hash bucket is brought down from ~550 to ~40. Tests show that the other element checked for in tb_find_physical, cs_base, is always a match when tb_phys+pc+flags are a match, so hashing cs_base is wasteful. It could be that this is an ARM-only thing, though. BTW, after this change the hash table should not be called "tb_hash_phys" anymore; this is addressed later in this series. This change gives consistent bootup time improvements. I tested two host machines: - Intel Xeon E5-2690: 11.6% less time - Intel i7-4790K: 19.2% less time Increasing the number of hash buckets yields further improvements. However, using a larger, fixed number of buckets can degrade performance for other workloads that do not translate as many blocks (600K+ for debian-jessie arm bootup). This is dealt with later in this series. Reviewed-by: Richard Henderson Reviewed-by: Alex Bennée Signed-off-by: Emilio G. Cota --- cpu-exec.c | 4 ++-- include/exec/tb-hash.h | 8 ++++++-- translate-all.c | 11 ++++++----- 3 files changed, 14 insertions(+), 9 deletions(-) diff --git a/cpu-exec.c b/cpu-exec.c index debc65c..395b302 100644 --- a/cpu-exec.c +++ b/cpu-exec.c @@ -224,7 +224,7 @@ static TranslationBlock *tb_find_physical(CPUState *cpu, { CPUArchState *env = (CPUArchState *)cpu->env_ptr; TranslationBlock *tb, **ptb1; - unsigned int h; + uint32_t h; tb_page_addr_t phys_pc, phys_page1; target_ulong virt_page2; @@ -233,7 +233,7 @@ static TranslationBlock *tb_find_physical(CPUState *cpu, /* find translated block using physical mappings */ phys_pc = get_page_addr_code(env, pc); phys_page1 = phys_pc & TARGET_PAGE_MASK; - h = tb_phys_hash_func(phys_pc); + h = tb_hash_func(phys_pc, pc, flags); ptb1 = &tcg_ctx.tb_ctx.tb_phys_hash[h]; for(;;) { tb = *ptb1; diff --git a/include/exec/tb-hash.h b/include/exec/tb-hash.h index 0f4e8a0..4b9635a 100644 --- a/include/exec/tb-hash.h +++ b/include/exec/tb-hash.h @@ -20,6 +20,9 @@ #ifndef EXEC_TB_HASH #define EXEC_TB_HASH +#include "exec/exec-all.h" +#include "exec/tb-hash-xx.h" + /* 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. */ @@ -43,9 +46,10 @@ static inline unsigned int tb_jmp_cache_hash_func(target_ulong pc) | (tmp & TB_JMP_ADDR_MASK)); } -static inline unsigned int tb_phys_hash_func(tb_page_addr_t pc) +static inline +uint32_t tb_hash_func(tb_page_addr_t phys_pc, target_ulong pc, int flags) { - return (pc >> 2) & (CODE_GEN_PHYS_HASH_SIZE - 1); + return tb_hash_func5(phys_pc, pc, flags) & (CODE_GEN_PHYS_HASH_SIZE - 1); } #endif diff --git a/translate-all.c b/translate-all.c index 05c0b50..0463efc 100644 --- a/translate-all.c +++ b/translate-all.c @@ -965,13 +965,14 @@ void tb_phys_invalidate(TranslationBlock *tb, tb_page_addr_t page_addr) { CPUState *cpu; PageDesc *p; - unsigned int h, n1; + unsigned int n1; + uint32_t h; tb_page_addr_t phys_pc; TranslationBlock *tb1, *tb2; /* remove the TB from the hash list */ phys_pc = tb->page_addr[0] + (tb->pc & ~TARGET_PAGE_MASK); - h = tb_phys_hash_func(phys_pc); + h = tb_hash_func(phys_pc, tb->pc, tb->flags); tb_hash_remove(&tcg_ctx.tb_ctx.tb_phys_hash[h], tb); /* remove the TB from the page list */ @@ -1470,11 +1471,11 @@ static inline void tb_alloc_page(TranslationBlock *tb, static void tb_link_page(TranslationBlock *tb, tb_page_addr_t phys_pc, tb_page_addr_t phys_page2) { - unsigned int h; + uint32_t h; TranslationBlock **ptb; - /* add in the physical hash table */ - h = tb_phys_hash_func(phys_pc); + /* add in the hash table */ + h = tb_hash_func(phys_pc, tb->pc, tb->flags); ptb = &tcg_ctx.tb_ctx.tb_phys_hash[h]; tb->phys_hash_next = *ptb; *ptb = tb; -- 2.5.0