diff options
| author | Mike Dodd <mdodd@google.com> | 2010-11-11 10:34:36 -0800 |
|---|---|---|
| committer | Mike Dodd <mdodd@google.com> | 2010-11-11 10:58:41 -0800 |
| commit | 8a572b129c9755959b4421970947aeda4119c3b7 (patch) | |
| tree | b7ae64a56f421b982a01450bfc2ce568640c62df | |
| parent | 20192a82b8a01a01949c720bf8f5f34a4ef9a31c (diff) | |
| download | oprofile-8a572b129c9755959b4421970947aeda4119c3b7.tar.gz | |
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
| -rw-r--r-- | .gitignore | 2 | ||||
| -rw-r--r-- | libdb/odb.h | 2 |
2 files changed, 3 insertions, 1 deletions
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; } |