[v3,11/11] translate-all: add tb hash bucket info to 'info jit' dump

Suggested-by: Richard Henderson <rth@twiddle.net>
Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 translate-all.c | 5 +++++
 1 file changed, 5 insertions(+)

On 04/19/2016 04:07 PM, Emilio G. Cota wrote:
> Suggested-by: Richard Henderson<rth@twiddle.net>
> Signed-off-by: Emilio G. Cota<cota@braap.org>
> ---
>   translate-all.c | 5 +++++
>   1 file changed, 5 insertions(+)

Reviewed-by: Richard Henderson <rth@twiddle.net>


r~

Emilio G. Cota <cota@braap.org> writes:

> Suggested-by: Richard Henderson <rth@twiddle.net>
> Signed-off-by: Emilio G. Cota <cota@braap.org>

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>


> ---
>  translate-all.c | 5 +++++
>  1 file changed, 5 insertions(+)
>
> diff --git a/translate-all.c b/translate-all.c
> index 617a572..769bffc 100644
> --- a/translate-all.c
> +++ b/translate-all.c
> @@ -1664,6 +1664,8 @@ void dump_exec_info(FILE *f, fprintf_function cpu_fprintf)
>  {
>      int i, target_code_size, max_target_code_size;
>      int direct_jmp_count, direct_jmp2_count, cross_page;
> +    double ht_avg_len;
> +    size_t ht_heads;
>      TranslationBlock *tb;
>
>      target_code_size = 0;
> @@ -1715,6 +1717,9 @@ void dump_exec_info(FILE *f, fprintf_function cpu_fprintf)
>                  direct_jmp2_count,
>                  tcg_ctx.tb_ctx.nb_tbs ? (direct_jmp2_count * 100) /
>                          tcg_ctx.tb_ctx.nb_tbs : 0);
> +    ht_avg_len = qht_avg_bucket_chain_length(&tcg_ctx.tb_ctx.htable, &ht_heads);
> +    cpu_fprintf(f, "TB hash avg chain   %0.5f buckets\n", ht_avg_len);
> +    cpu_fprintf(f, "TB hash size        %zu head buckets\n", ht_heads);
>      cpu_fprintf(f, "\nStatistics:\n");
>      cpu_fprintf(f, "TB flush count      %d\n", tcg_ctx.tb_ctx.tb_flush_count);
>      cpu_fprintf(f, "TB invalidate count %d\n",


--
Alex Bennée

On 04/19/2016 04:07 PM, Emilio G. Cota wrote:
> +    ht_avg_len = qht_avg_bucket_chain_length(&tcg_ctx.tb_ctx.htable, &ht_heads);
> +    cpu_fprintf(f, "TB hash avg chain   %0.5f buckets\n", ht_avg_len);
> +    cpu_fprintf(f, "TB hash size        %zu head buckets\n", ht_heads);


I think the accounting is questionable here.

Consider the following data:

TB count             230467/671088
TB invalidate count  25915
TB hash avg chain    1.03073 buckets
TB hash size         131072 head buckets

This means that we've got 230467 - 25915 = 204552 active TB's, installed into a
hash table with 131072 heads.  For a perfectly uniform distribution of TBs,
that would be an average chain length of 204552 / 131072 = 1.56.

In order to get the average down to 1.03, there need to be a substantial number
of heads with zero entries.

I think perhaps it might be more enlightening to separately account for empty
and non-empty heads.  E.g.

TB hash buckets used  xxxx/131072
TB hash avg chain     yyyy

where xxxx is the number of non-empty heads, and yyyy = |TBs| / xxxx.

I also wonder if it wouldn't be better to size the hash table as appropriate
for the maximum number of allowable TBs.


r~

On Fri, Apr 22, 2016 at 10:41:25 -0700, Richard Henderson wrote:
> On 04/19/2016 04:07 PM, Emilio G. Cota wrote:
> > +    ht_avg_len = qht_avg_bucket_chain_length(&tcg_ctx.tb_ctx.htable, &ht_heads);
> > +    cpu_fprintf(f, "TB hash avg chain   %0.5f buckets\n", ht_avg_len);
> > +    cpu_fprintf(f, "TB hash size        %zu head buckets\n", ht_heads);
> 
> I think the accounting is questionable here.
> 
> Consider the following data:
> 
> TB count             230467/671088
> TB invalidate count  25915
> TB hash avg chain    1.03073 buckets
> TB hash size         131072 head buckets
> 
> This means that we've got 230467 - 25915 = 204552 active TB's, installed into a
> hash table with 131072 heads.  For a perfectly uniform distribution of TBs,
> that would be an average chain length of 204552 / 131072 = 1.56.
>
> In order to get the average down to 1.03, there need to be a substantial number
> of heads with zero entries.

Remember that each head can host up to QHT_BUCKET_ENTRIES, so that
1) the bucket fits in a cache line
2) resizing the cache is fast since the full hashes are also stored
   in the bucket
3) full comparisons (i.e. calls to the user-provided cmp() function) are only
   due to full hash collisions, not due to the hash table being
   undersized.
QHT_BUCKET_ENTRIES is 4 entries on 64-bit hosts, and 6 entries on 32-bit.

For your example hash table, assuming we're on 64-bit and a uniform
distribution, occupancy would be
  204552 / 131072 / 4 = 0.39

The confusion comes from the fact that qht_avg_bucket_chain_length()
returns the number of head buckets, not head entries:
/*
 * Returns the number of buckets that an average lookup will traverse.
 * The return value is always >= 1. With a good hashing function, this
 * value should be close to 1.
 * Note that each bucket tracks up to QHT_BUCKET_ENTRIES items.
 */
double qht_avg_bucket_chain_length(struct qht *ht, size_t *n_head_buckets)

The rationale is that all entries on the same bucket can be found in O(1):
even if a bucket is empty, a lookup will do QHT_BUCKET_ENTRIES
comparisons, since a removal simply sets bucket[entry] to NULL, without
touching other entries (on that bucket or any other chained bucket).
This is done to limit churn on removals (the corresponding bucket chain
would have to be traversed). However, although given the relatively
low amount of removals that we have, this might be worth exploring.

> I also wonder if it wouldn't be better to size the hash table as appropriate
> for the maximum number of allowable TBs.

This would hurt performance for workloads that have very low amounts of TB's
and that go to the hash table often, such as booting a minimal ARM linux image.

		Emilio