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

["Mattias Rönnblom" <hofors@lysator.liu.se>]

On 2025-08-22 11:50, Morten Brørup wrote:
>> From: Mattias Rönnblom [mailto:hofors@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@smartsharesystems.com>
>>> Reported-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
>>>
>>> Signed-off-by: Stephen Hemminger <stephen@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;
> 

Could you explain why that is safe? Doesn't
__attribute__((__aligned__(1)))
just say specify the object doesn't have any alignment requirements, 
without asking the compiler to deal with it?

>>
>> 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.

Well, the function body doesn't do what the function name tells it. :)

> 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.

All what is needed is a constant-size length. (Only tested with the most 
recent GCC and clang.)

At least GCC will emit a cmp instruction though (so not branch free), if 
that matters.

> 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;
> }
> 

Should work. (Remove __rte_unused.)

>>
>>> +
>>> +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,
>