From 8a572b129c9755959b4421970947aeda4119c3b7 Mon Sep 17 00:00:00 2001 From: Mike Dodd Date: Thu, 11 Nov 2010 10:34:36 -0800 Subject: oprofile fix for hashing backtraces. Oprofile's hash function uses a 64-bit value for the key where the high 32-bit are the 'from' address in a backtrace, and the low 32-bits are the current PC. However, the hash function was: uint32_t temp = (value >> 32) ^ value; return ((temp << 0) ^ (temp >> 8)) & data->hash_mask; If 'from' and 'to' are the same (recursive function), this hashes to 0, and you end up with lots of collisions, turning the theoretically O(1) operation into O(n). To fix it, I just drop the high 32-bits from the hash: uint32_t temp = value & 0xffffffff; return ((temp << 0) ^ (temp >> 8)) & data->hash_mask; In testing, this drastically reduces the oprofile overhead for some tracing. Change-Id: I8ae65a8a73771c89b576c895f135efd7b730eaf5 --- .gitignore | 2 ++ libdb/odb.h | 2 +- 2 files changed, 3 insertions(+), 1 deletion(-) create mode 100644 .gitignore diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..86b18f5 --- /dev/null +++ b/.gitignore @@ -0,0 +1,2 @@ +.cproject +.project diff --git a/libdb/odb.h b/libdb/odb.h index 9ad1da2..1e777da 100644 --- a/libdb/odb.h +++ b/libdb/odb.h @@ -228,7 +228,7 @@ odb_do_hash(odb_data_t const * data, odb_key_t value) * files avoiding to rebuilding them at profiling re-start so * on changing do_hash() change the file format! */ - uint32_t temp = (value >> 32) ^ value; + uint32_t temp = value & 0xffffffff; return ((temp << 0) ^ (temp >> 8)) & data->hash_mask; } -- cgit v1.2.3