Re: [PATCH v10 1/4] hash: pack the hitmask for hash in bulk lookup

[Yoan Picchi <yoan.picchi@arm.com>]

I'll push a v11 tonight. There is a couple of comments I disagree with 
tough:

On 7/4/24 21:31, David Marchand wrote:
> Hello Yoan,
> 
> On Wed, Jul 3, 2024 at 7:13 PM Yoan Picchi <yoan.picchi@arm.com> wrote:
>>
>> Current hitmask includes padding due to Intel's SIMD
>> implementation detail. This patch allows non Intel SIMD
>> implementations to benefit from a dense hitmask.
>> In addition, the new dense hitmask interweave the primary
>> and secondary matches which allow a better cache usage and
>> enable future improvements for the SIMD implementations
>> The default non SIMD path now use this dense mask.
>>
>> Signed-off-by: Yoan Picchi <yoan.picchi@arm.com>
>> Reviewed-by: Ruifeng Wang <ruifeng.wang@arm.com>
>> Reviewed-by: Nathan Brown <nathan.brown@arm.com>
> 
> This patch does too many things at the same time.
> There is code movement and behavior modifications all mixed in.
> 
> As there was still no review from the lib maintainer... I am going a
> bit more in depth this time.
> Please split this patch to make it less hard to understand.
> 
> I can see the need for at least one patch for isolating the change on
> sig_cmp_fn from the exposed API, then one patch for moving the code to
> per arch headers with *no behavior change*, and one patch for
> introducing/switching to "dense hitmask".
> 
> More comments below.
> 
> 
>> ---
>>   .mailmap                                  |   1 +
>>   lib/hash/compare_signatures_arm_pvt.h     |  60 +++++++
>>   lib/hash/compare_signatures_generic_pvt.h |  37 +++++
>>   lib/hash/compare_signatures_x86_pvt.h     |  49 ++++++
>>   lib/hash/hash_sig_cmp_func_pvt.h          |  20 +++
>>   lib/hash/rte_cuckoo_hash.c                | 190 +++++++++++-----------
>>   lib/hash/rte_cuckoo_hash.h                |  10 +-
>>   7 files changed, 267 insertions(+), 100 deletions(-)
>>   create mode 100644 lib/hash/compare_signatures_arm_pvt.h
>>   create mode 100644 lib/hash/compare_signatures_generic_pvt.h
>>   create mode 100644 lib/hash/compare_signatures_x86_pvt.h
>>   create mode 100644 lib/hash/hash_sig_cmp_func_pvt.h
>>
>> diff --git a/.mailmap b/.mailmap
>> index f76037213d..ec525981fe 100644
>> --- a/.mailmap
>> +++ b/.mailmap
>> @@ -1661,6 +1661,7 @@ Yixue Wang <yixue.wang@intel.com>
>>   Yi Yang <yangyi01@inspur.com> <yi.y.yang@intel.com>
>>   Yi Zhang <zhang.yi75@zte.com.cn>
>>   Yoann Desmouceaux <ydesmouc@cisco.com>
>> +Yoan Picchi <yoan.picchi@arm.com>
>>   Yogesh Jangra <yogesh.jangra@intel.com>
>>   Yogev Chaimovich <yogev@cgstowernetworks.com>
>>   Yongjie Gu <yongjiex.gu@intel.com>
>> diff --git a/lib/hash/compare_signatures_arm_pvt.h b/lib/hash/compare_signatures_arm_pvt.h
>> new file mode 100644
>> index 0000000000..e83bae9912
>> --- /dev/null
>> +++ b/lib/hash/compare_signatures_arm_pvt.h
> 
> I guess pvt stands for private.
> No need for such suffix, this header won't be exported in any case.

pvt do stand for private, yes. I had a look at the other lib and what 
they used to state a header as private. Several (rcu, ring and stack) 
use _pvt so it looks like that's might be the standard? If no, then how 
am I supposed to differentiate a public and a private header?

> 
> 
>> @@ -0,0 +1,60 @@
>> +/* SPDX-License-Identifier: BSD-3-Clause
>> + * Copyright(c) 2010-2016 Intel Corporation
>> + * Copyright(c) 2018-2024 Arm Limited
>> + */
>> +
>> +/*
>> + * Arm's version uses a densely packed hitmask buffer:
>> + * Every bit is in use.
>> + */
> 
> Please put a header guard.
> 
> #ifndef <UPPERCASE_HEADER_NAME>_H
> #define <UPPERCASE_HEADER_NAME>_H
> 
>> +
>> +#include <inttypes.h>
>> +#include <rte_common.h>
>> +#include <rte_vect.h>
>> +
>> +#include "rte_cuckoo_hash.h"
>> +#include "hash_sig_cmp_func_pvt.h"
>> +
>> +#define DENSE_HASH_BULK_LOOKUP 1
>> +
>> +static inline void
>> +compare_signatures_dense(uint16_t *hitmask_buffer,
>> +                       const uint16_t *prim_bucket_sigs,
>> +                       const uint16_t *sec_bucket_sigs,
>> +                       uint16_t sig,
>> +                       enum rte_hash_sig_compare_function sig_cmp_fn)
>> +{
>> +
>> +       static_assert(sizeof(*hitmask_buffer) >= 2 * (RTE_HASH_BUCKET_ENTRIES / 8),
>> +               "hitmask_buffer must be wide enough to fit a dense hitmask");
>> +
>> +       /* For match mask every bits indicates the match */
>> +       switch (sig_cmp_fn) {
>> +#if RTE_HASH_BUCKET_ENTRIES <= 8
>> +       case RTE_HASH_COMPARE_NEON: {
>> +               uint16x8_t vmat, vsig, x;
>> +               int16x8_t shift = {0, 1, 2, 3, 4, 5, 6, 7};
>> +               uint16_t low, high;
>> +
>> +               vsig = vld1q_dup_u16((uint16_t const *)&sig);
>> +               /* Compare all signatures in the primary bucket */
>> +               vmat = vceqq_u16(vsig, vld1q_u16((uint16_t const *)prim_bucket_sigs));
>> +               x = vshlq_u16(vandq_u16(vmat, vdupq_n_u16(0x0001)), shift);
>> +               low = (uint16_t)(vaddvq_u16(x));
>> +               /* Compare all signatures in the secondary bucket */
>> +               vmat = vceqq_u16(vsig, vld1q_u16((uint16_t const *)sec_bucket_sigs));
>> +               x = vshlq_u16(vandq_u16(vmat, vdupq_n_u16(0x0001)), shift);
>> +               high = (uint16_t)(vaddvq_u16(x));
>> +               *hitmask_buffer = low | high << RTE_HASH_BUCKET_ENTRIES;
>> +
>> +               }
>> +               break;
>> +#endif
>> +       default:
>> +               for (unsigned int i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
>> +                       *hitmask_buffer |= (sig == prim_bucket_sigs[i]) << i;
>> +                       *hitmask_buffer |=
>> +                               ((sig == sec_bucket_sigs[i]) << i) << RTE_HASH_BUCKET_ENTRIES;
>> +               }
>> +       }
>> +}
> 
> IIRC, this code is copied in all three headers.
> It is a common scalar version, so the ARM code could simply call the
> "generic" implementation rather than copy/paste.

Out of the three files, only two versions are the same: generic and arm. 
Intel's version do have some padding added (given it's sparse).
I prefer to keep a scalar version in the arm implementation because 
that's what match the legacy implementation. We used to be able to 
choose (at runtime) to use the scalar path even if we had neon. In 
practice the choice ends up being made from #defines, but as far as this 
function goes, it is a runtime decision.

[snip]