This is the mail archive of the
systemtap@sourceware.org
mailing list for the systemtap project.
[Bug runtime/19802] bad hash value distribution and horrible performance for large arrays with multiple small-integer indices
- From: "dsmith at redhat dot com" <sourceware-bugzilla at sourceware dot org>
- To: systemtap at sourceware dot org
- Date: Thu, 10 Mar 2016 21:08:12 +0000
- Subject: [Bug runtime/19802] bad hash value distribution and horrible performance for large arrays with multiple small-integer indices
- Auto-submitted: auto-generated
- References: <bug-19802-6586 at http dot sourceware dot org/bugzilla/>
https://sourceware.org/bugzilla/show_bug.cgi?id=19802
David Smith <dsmith at redhat dot com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |dsmith at redhat dot com
--- Comment #1 from David Smith <dsmith at redhat dot com> ---
(In reply to Ken Raeburn from comment #0)
> I see two particular problems:
>
> First, the hash function in map-gen.c is not a terribly good mixing
> function. If the per-key hashes only vary in a few bits, especially if those
> bit-ranges overlap between keys, the results won't be well distributed. And
> with several keys, it's shifting the earlier results to the left and doing
> XORs, which means the first key doesn't contribute at all to the lower bits
> of the output. (If the hash table size were prime it would be another
> matter, but it's a power of two so we're just masking off the high bits when
> we do the modulus operation.)
>
> Second, hash_64 isn't a good choice for a hash function if you don't have a
> lot of varying input bits, and you need a lot of output bits, and you don't
> follow it with a good mixing function.
I took a bit of a look at this today. We're using the kernel's hash_{64,32}
function. (We do have a copy of it down src/runtime/dyninst/linux_hash.c, but
that just for the use of "stap --dyninst".)
The advantage the kernel has when using hash_{64,32} on multiple values is that
it knows what data is it is mixing, so it can mix the data semi-intelligently.
Here are some examples from the kernel source:
from drivers/net/ethernet/mellanox/mlx4/en_netdev.c:
====
filter_hash_bucket(struct mlx4_en_priv *priv, __be32 src_ip, __be32 dst_ip,
__be16 src_port, __be16 dst_port)
{
unsigned long l;
int bucket_idx;
l = (__force unsigned long)src_port |
((__force unsigned long)dst_port << 2);
l ^= (__force unsigned long)(src_ip ^ dst_ip);
bucket_idx = hash_long(l, MLX4_EN_FILTER_HASH_SHIFT);
====
from fs/mbcache.c:
====
mb_cache_entry_get(struct mb_cache *cache, struct block_device *bdev,
sector_t block)
{
unsigned int bucket;
struct hlist_bl_node *l;
struct mb_cache_entry *ce;
struct hlist_bl_head *block_hash_p;
bucket = hash_long((unsigned long)bdev + (block & 0xffffffff),
cache->c_bucket_bits);
====
In systemtap's case, we don't know if we're going to be mixing small integers
or pointer values, which makes things tricky when it comes to mixing the data
--
You are receiving this mail because:
You are the assignee for the bug.