[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH v3 07/11] tb hash: hash phys_pc, pc, and flags w
From: |
Alex Bennée |
Subject: |
Re: [Qemu-devel] [PATCH v3 07/11] tb hash: hash phys_pc, pc, and flags with xxhash |
Date: |
Fri, 22 Apr 2016 13:58:05 +0100 |
User-agent: |
mu4e 0.9.17; emacs 25.0.92.6 |
Emilio G. Cota <address@hidden> 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 <address@hidden>
> Signed-off-by: Emilio G. Cota <address@hidden>
Reviewed-by: Alex Bennée <address@hidden>
> ---
> 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
- [Qemu-devel] [UPDATED v3 05/11] qemu-thread: add simple test-and-set spinlock, (continued)
- [Qemu-devel] [PATCH v3 03/11] seqlock: rename write_lock/unlock to write_begin/end, Emilio G. Cota, 2016/04/19
- [Qemu-devel] [PATCH v3 10/11] tb hash: track translated blocks with qht, Emilio G. Cota, 2016/04/19
- [Qemu-devel] [PATCH v3 07/11] tb hash: hash phys_pc, pc, and flags with xxhash, Emilio G. Cota, 2016/04/19
- Re: [Qemu-devel] [PATCH v3 07/11] tb hash: hash phys_pc, pc, and flags with xxhash,
Alex Bennée <=
- [Qemu-devel] [PATCH v3 09/11] qht: add test program, Emilio G. Cota, 2016/04/19
- [Qemu-devel] [PATCH v3 08/11] qht: QEMU's fast, resizable and scalable Hash Table, Emilio G. Cota, 2016/04/19
- [Qemu-devel] [PATCH v3 06/11] exec: add tb_hash_func5, derived from xxhash, Emilio G. Cota, 2016/04/19
- [Qemu-devel] [PATCH v3 11/11] translate-all: add tb hash bucket info to 'info jit' dump, Emilio G. Cota, 2016/04/19