This is the mail archive of the systemtap@sourceware.org mailing list for the systemtap project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[Bug runtime/19802] bad hash value distribution and horrible performance for large arrays with multiple small-integer indices


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.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]