From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49797) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ataex-0001mh-Ri for qemu-devel@nongnu.org; Fri, 22 Apr 2016 08:58:16 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ataet-0004G7-Mp for qemu-devel@nongnu.org; Fri, 22 Apr 2016 08:58:11 -0400 Received: from mail-wm0-x22d.google.com ([2a00:1450:400c:c09::22d]:36654) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ataet-0004G0-Cd for qemu-devel@nongnu.org; Fri, 22 Apr 2016 08:58:07 -0400 Received: by mail-wm0-x22d.google.com with SMTP id v188so20064903wme.1 for ; Fri, 22 Apr 2016 05:58:07 -0700 (PDT) References: <1461107270-19234-1-git-send-email-cota@braap.org> <1461107270-19234-8-git-send-email-cota@braap.org> From: Alex =?utf-8?Q?Benn=C3=A9e?= In-reply-to: <1461107270-19234-8-git-send-email-cota@braap.org> Date: Fri, 22 Apr 2016 13:58:05 +0100 Message-ID: <87lh45u7fm.fsf@linaro.org> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Subject: Re: [Qemu-devel] [PATCH v3 07/11] tb hash: hash phys_pc, pc, and flags with xxhash List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: "Emilio G. Cota" Cc: QEMU Developers , MTTCG Devel , Paolo Bonzini , Peter Crosthwaite , Richard Henderson , Peter Maydell , Sergey Fedorov Emilio G. Cota writes: > 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 > Signed-off-by: Emilio G. Cota Reviewed-by: Alex Bennée > --- > cpu-exec.c | 2 +- > include/exec/tb-hash.h | 8 ++++++-- > translate-all.c | 6 +++--- > 3 files changed, 10 insertions(+), 6 deletions(-) > > diff --git a/cpu-exec.c b/cpu-exec.c > index debc65c..a889cf1 100644 > --- a/cpu-exec.c > +++ b/cpu-exec.c > @@ -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 1a8f68b..eca2f16 100644 > --- a/translate-all.c > +++ b/translate-all.c > @@ -972,7 +972,7 @@ void tb_phys_invalidate(TranslationBlock *tb, tb_page_addr_t page_addr) > > /* 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 */ > @@ -1474,8 +1474,8 @@ static void tb_link_page(TranslationBlock *tb, tb_page_addr_t phys_pc, > unsigned int 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; -- Alex Bennée