From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:59190) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1awLfI-0003tm-Ve for qemu-devel@nongnu.org; Fri, 29 Apr 2016 23:34:09 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1awLey-0008Ti-EL for qemu-devel@nongnu.org; Fri, 29 Apr 2016 23:33:51 -0400 Received: from out5-smtp.messagingengine.com ([66.111.4.29]:43434) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1awLew-0008Ow-3L for qemu-devel@nongnu.org; Fri, 29 Apr 2016 23:33:36 -0400 Received: from compute2.internal (compute2.nyi.internal [10.202.2.42]) by mailout.nyi.internal (Postfix) with ESMTP id A619A20801 for ; Fri, 29 Apr 2016 23:33:19 -0400 (EDT) From: "Emilio G. Cota" Date: Fri, 29 Apr 2016 23:33:03 -0400 Message-Id: <1461987197-31264-1-git-send-email-cota@braap.org> Subject: [Qemu-devel] [PATCH v4 00/14] tb hash improvements List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: QEMU Developers , MTTCG Devel Cc: =?UTF-8?q?Alex=20Benn=C3=A9e?= , Paolo Bonzini , Peter Crosthwaite , Richard Henderson , Sergey Fedorov 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