Changes from v3: - added reviewed-by tags from v3. I dropped the review tags from the 'qht' and 'info jit' patches because they have changed quite a bit from v3. - qdist: new module to print intuitive histograms, see 'info jit' below. - qht: + bug fix: remove unnecessary requirement of hashes being !0; the only requirement is that pointers must be !NULL. * qht-test: hash the integers we insert with their own integer values instead of using tb_hash_func5. This gives us better control of the hash values we're testing, and anyway the values we test are all unique, so this doesn't matter. + bug fix: was not setting map->n_items to 0 in qht_reset(). + Do not leave NULL holes after removals. Instead, swap this hole with the last valid item in the chain. Performance-wise this makes no difference when resize is on; however, without resize the gain is measurable. * A consequence of this is a slight change in MRU promotion: the last item in the head bucket is simply swapped with orig[pos], without bringing orig to head->next. * Added bucket corruption checks, enabled with #define QHT_DEBUG. + Do not set QHT_MODE_MRU_INSERT for the TB hash. With long chains it causes quite a performance decrease; with short chains, such as what we have with xxhash + auto-resize, it has no measurable performance impact. + 'info jit' stats: * Report the number of empty buckets * Do not count empty buckets when reporting avg bucket chain length; by doing this we get an idea of how many buckets the average lookup is going through. * Report the avg bucket chain length + a histogram for its distribution. * Report avg bucket chain occupancy (in %) + its distribution's histogram. + qht-test: add a few more test cases + header guard: s/define QHT_H/define QEMU_QHT_H/ + consistently use uint32_t for keeping the result of tb_hash_func() + avoid false leak reports from valgrind after calling call_rcu(map) by placing the 'struct rcu_head' field at the top of struct qht_map. - define QEMU_ALIGNED(X) instead of QEMU_ALIGNED(B) - add copyright + license to include/processor.h - add atomic_test_and_set to include/atomic.h, using __atomic_test_and_set when available. - spinlock: + use newly-added atomic_test_and_set instead of atomic_xchg + remove TATAS for spin_try_lock
Thanks, Emilio