kernel-shark: Increase the size of the task hash
When loading a data file that contained 100,000s of tasks, using a 256
bucket size hash crippled it. By increasing the hash to 2^16 (65536) it
solves the issue (still small enough not to waste too much memory).
Also switched to the tracecmd_quick_hash() which is basically the same
as the local knuth_hash() function in libkshark.c.
Link: http://lore.kernel.org/linux-trace-devel/20190828140016.3ce1be4f@gandalf.local.home
Link: http://lore.kernel.org/linux-trace-devel/20190920152024.729716704@goodmis.org
Reviewed-by: Yordan Karadzhov (VMware) <y.karadz@gmail.com>
Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
diff --git a/kernel-shark/src/libkshark.c b/kernel-shark/src/libkshark.c
index 4207ae6..a361578 100644
--- a/kernel-shark/src/libkshark.c
+++ b/kernel-shark/src/libkshark.c
@@ -252,19 +252,8 @@
free(kshark_ctx);
}
-static inline uint8_t knuth_hash(uint32_t val)
-{
- /*
- * Small table hashing function adapted from Donald E. Knuth's 32 bit
- * multiplicative hash. See The Art of Computer Programming (TAOCP).
- * Multiplication by the Prime number, closest to the golden ratio of
- * 2^8.
- */
- return UINT8_C(val) * UINT8_C(157);
-}
-
static struct kshark_task_list *
-kshark_find_task(struct kshark_context *kshark_ctx, uint8_t key, int pid)
+kshark_find_task(struct kshark_context *kshark_ctx, uint32_t key, int pid)
{
struct kshark_task_list *list;
@@ -280,9 +269,10 @@
kshark_add_task(struct kshark_context *kshark_ctx, int pid)
{
struct kshark_task_list *list;
- uint8_t key;
+ uint32_t key;
- key = knuth_hash(pid);
+ key = tracecmd_quick_hash(pid, KS_TASK_HASH_SHIFT);
+
list = kshark_find_task(kshark_ctx, key, pid);
if (list)
return list;
diff --git a/kernel-shark/src/libkshark.h b/kernel-shark/src/libkshark.h
index 04e9cbf..3407db1 100644
--- a/kernel-shark/src/libkshark.h
+++ b/kernel-shark/src/libkshark.h
@@ -72,7 +72,8 @@
};
/** Size of the task's hash table. */
-#define KS_TASK_HASH_SIZE 256
+#define KS_TASK_HASH_SHIFT 16
+#define KS_TASK_HASH_SIZE (1 << KS_TASK_HASH_SHIFT)
/** Linked list of tasks. */
struct kshark_task_list {
