[RFC 3/3] hash: add support for common small key sizes

[Morten Brørup]

> From: Mattias Rönnblom [mailto:hofors at lysator.liu.se]
> Sent: Friday, 22 August 2025 09.20
> 
> On 2025-08-21 22:35, Stephen Hemminger wrote:
> > Add new compare functions for common small key sizes.
> >
> > Bugzilla ID: 1775
> > Suggested-by: Morten Brørup <mb at smartsharesystems.com>
> > Reported-by: Mattias Rönnblom <mattias.ronnblom at ericsson.com>
> >
> > Signed-off-by: Stephen Hemminger <stephen at networkplumber.org>
> > ---
> >   lib/hash/rte_cuckoo_hash.c | 54 ++++++++++++++++++++++++++++++++++++++
> >   1 file changed, 54 insertions(+)
> >
> > diff --git a/lib/hash/rte_cuckoo_hash.c b/lib/hash/rte_cuckoo_hash.c
> > index 3212695d92..825889c320 100644
> > --- a/lib/hash/rte_cuckoo_hash.c
> > +++ b/lib/hash/rte_cuckoo_hash.c
> > @@ -49,6 +49,11 @@ RTE_LOG_REGISTER_DEFAULT(hash_logtype, INFO);
> >    */
> >   enum cmp_jump_table_case {
> >   	KEY_CUSTOM = 0,
> > +	KEY_2_BYTES,
> > +	KEY_4_BYTES,
> > +	KEY_6_BYTES,
> > +	KEY_8_BYTES,
> > +	KEY_12_BYTES,

While you are at it, consider adding handlers for 3, 5, 10 and 14 bytes too.

> >   	KEY_16_BYTES,
> >   	KEY_32_BYTES,
> >   	KEY_48_BYTES,
> > @@ -86,6 +91,50 @@ rte_hash_k32_cmp_eq(const void *key1, const void *key2,
> size_t key_len)
> >   }
> >   #endif
> >
> > +static inline int
> > +rte_hash_k2_cmp_eq(const void *key1, const void *key2, size_t key_len
> __rte_unused)
> > +{
> > +	const uint16_t *k1 = key1;
> > +	const uint16_t *k2 = key2;
> > +
> 
> What we do now is to require the keys are 16-bit aligned (which wasn't
> the case before).
> 
> You could
> 
> uint16_t k1;
> memcpy(&k1, key1, sizeof(uint16_t));
> instead.
> 
> Would generate the same code, but be safe from any future alignment issues.

Or use the unaligned types, e.g.:
	const unaligned_uint16_t *k1 = key1;
	const unaligned_uint16_t *k2 = key2;

> 
> Anyway, maybe it's safe to assume the keys are aligned, so this is not
> an issue.

Lots of DPDK code ignores alignment issues.

> 
> > +	return k1[0] ^ k2[0];
> > +}
> 
> Haven't you implemented "neq" rather than "eq" here? If the keys are
> equal, the result is 0. Should be != 0.

Not a bug.
These hash compare functions are in fact "neq", not "eq".
Having "_cmp_eq" in the function names is extremely unfortunate and misleading.

> 
> Would it be worth adding a comment like "use XOR to make this
> branch-free"? It may not be obvious to all readers.
> 
> That said, I’m not sure this trick will actually change the generated
> object code - especially if the result of the eq function is still used
> in a conditional afterward. Anyway, keeping it seems like a good
> conservative approach.

I wonder if any compiler is clever enough to use a different memcmp implementation if we inform the compiler at build time that we don't care if key1 is less than or greater key2, only if they differ or not.
If so, the OTHER_BYTES handler shouldn't call memcmp() directly, but a wrapper around it:

rte_hash_k_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused)
{
	return memcmp(key1, key2, key_len) != 0;
}

> 
> > +
> > +static inline int
> > +rte_hash_k4_cmp_eq(const void *key1, const void *key2, size_t key_len
> __rte_unused)
> > +{
> > +	const uint32_t *k1 = key1;
> > +	const uint32_t *k2 = key2;
> > +
> > +	return k1[0] ^ k2[0];
> > +}
> > +
> > +static inline int
> > +rte_hash_k6_cmp_eq(const void *key1, const void *key2, size_t key_len
> __rte_unused)
> > +{
> > +	const uint16_t *k1 = key1;
> > +	const uint16_t *k2 = key2;
> > +
> > +	return (k1[0] ^ k2[0]) | (k1[1] ^ k2[1]) | (k1[2] ^ k2[2]);
> > +}
> > +
> > +static inline int
> > +rte_hash_k8_cmp_eq(const void *key1, const void *key2, size_t key_len
> __rte_unused)
> > +{
> > +	const uint64_t *k1 = key1;
> > +	const uint64_t *k2 = key2;
> > +
> > +	return k1[0] ^ k2[0];

I think this has a truncation bug when converting from uint64_t to int return type.
Also consider if 32 bit architecture need a different implementation. (Don't know, just raising a potential flag.)

> > +}
> > +
> > +static inline int
> > +rte_hash_k12_cmp_eq(const void *key1, const void *key2, size_t key_len
> __rte_unused)
> > +{
> > +	const uint32_t *k1 = key1;
> > +	const uint32_t *k2 = key2;
> > +
> > +	return (k1[0] ^ k2[0]) | (k1[1] ^ k2[1]) | (k1[2] ^ k2[2]);
> > +}
> >
> >   static inline int
> >   rte_hash_k48_cmp_eq(const void *key1, const void *key2, size_t key_len)
> > @@ -228,6 +277,11 @@ void rte_hash_set_cmp_func(struct rte_hash *h,
> rte_hash_cmp_eq_t func)
> >    */
> >   static const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = {
> >   	[KEY_CUSTOM] = NULL,
> > +	[KEY_2_BYTES] = rte_hash_k2_cmp_eq,
> > +	[KEY_4_BYTES] = rte_hash_k4_cmp_eq,
> > +	[KEY_6_BYTES] = rte_hash_k6_cmp_eq,
> > +	[KEY_8_BYTES] = rte_hash_k8_cmp_eq,
> > +	[KEY_12_BYTES] = rte_hash_k12_cmp_eq,
> >   	[KEY_16_BYTES] = rte_hash_k16_cmp_eq,
> >   	[KEY_32_BYTES] = rte_hash_k32_cmp_eq,
> >   	[KEY_48_BYTES] = rte_hash_k48_cmp_eq,