Re: [Qemu-devel] [PATCH v3 11/11] translate-all: add tb hash bucket info to 'info jit' dump

[Emilio G. Cota]

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