On Tue, Sep 09, 2014 at 11:42:40AM +0000, De Lara Guarch, Pablo wrote: > That 4 is not shifted, so it is actually 4 entries/bucket. Actually, the > maximum number of entries you can use is 16, as bucket will be as big as a > cache line. However, regardless the number of entries, memory size will > remain the same, but using 4 entries/bucket, with 16-byte key, all keys > stored for a bucket will fit in a cache line, so performance looks to be > better in this case (although a non-optimal hash function could lead not to > be able to store all keys, as chances to fill a bucket are higher). Anyway, > for this example, 4 entries/bucket looks a good number to me.
So, a general purpose hash usually has some kind of conflict resolution when a bucket is full rather than just tossing out entries. It could be open addressing, chaining, secondary hashing, etc. If I'm putting security indicators into a bucket and the buckets just toss stuff out without warning that's a security problem. Same thing could be true for firewall tables. Also, if we're assuming a 16-byte key, what happens when I want to do matching against www.badness.com or www.this-is-a-really-long-malware-domain.net ? Did anybody have a performant general purpose hash table for DPDK that doesn't have problems with bigger keys or depth issues in a bucket? Matthew.
