From bf3afd5f419a2054bf03d963bdd223fbb27b72d2 Mon Sep 17 00:00:00 2001 From: "Emilio G. Cota" Date: Wed, 8 Jun 2016 14:55:26 -0400 Subject: qdist: add module to represent frequency distributions of data MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Sometimes it is useful to have a quick histogram to represent a certain distribution -- for example, when investigating a performance regression in a hash table due to inadequate hashing. The appended allows us to easily represent a distribution using Unicode characters. Further, the data structure keeping track of the distribution is so simple that obtaining its values for off-line processing is trivial. Example, taking the last 10 commits to QEMU: Characters in commit title Count ----------------------------------- 39 1 48 1 53 1 54 2 57 1 61 1 67 1 78 1 80 1 qdist_init(&dist); qdist_inc(&dist, 39); [...] qdist_inc(&dist, 80); char *str = qdist_pr(&dist, 9, QDIST_PR_LABELS); // -> [39.0,43.6)▂▂ █▂ ▂ ▄[75.4,80.0] g_free(str); char *str = qdist_pr(&dist, 4, QDIST_PR_LABELS); // -> [39.0,49.2)▁█▁▁[69.8,80.0] g_free(str); Reviewed-by: Richard Henderson Signed-off-by: Emilio G. Cota Message-Id: <1465412133-3029-9-git-send-email-cota@braap.org> Signed-off-by: Richard Henderson --- util/Makefile.objs | 1 + 1 file changed, 1 insertion(+) (limited to 'util/Makefile.objs') diff --git a/util/Makefile.objs b/util/Makefile.objs index a8a777ec40..702435e839 100644 --- a/util/Makefile.objs +++ b/util/Makefile.objs @@ -32,3 +32,4 @@ util-obj-y += buffer.o util-obj-y += timed-average.o util-obj-y += base64.o util-obj-y += log.o +util-obj-y += qdist.o -- cgit v1.2.1 From 2e11264aafe476c7a53accde4a23cfc2395a02fd Mon Sep 17 00:00:00 2001 From: "Emilio G. Cota" Date: Wed, 8 Jun 2016 14:55:28 -0400 Subject: qht: QEMU's fast, resizable and scalable Hash Table This is a fast, scalable chained hash table with optional auto-resizing, allowing reads that are concurrent with reads, and reads/writes that are concurrent with writes to separate buckets. A hash table with these features will be necessary for the scalability of the ongoing MTTCG work; before those changes arrive we can already benefit from the single-threaded speedup that qht also provides. Signed-off-by: Emilio G. Cota Message-Id: <1465412133-3029-11-git-send-email-cota@braap.org> Signed-off-by: Richard Henderson --- util/Makefile.objs | 1 + 1 file changed, 1 insertion(+) (limited to 'util/Makefile.objs') diff --git a/util/Makefile.objs b/util/Makefile.objs index 702435e839..45f8794864 100644 --- a/util/Makefile.objs +++ b/util/Makefile.objs @@ -33,3 +33,4 @@ util-obj-y += timed-average.o util-obj-y += base64.o util-obj-y += log.o util-obj-y += qdist.o +util-obj-y += qht.o -- cgit v1.2.1