[PATCH v5 4/4] hash: add SVE support for bulk key lookup
Yoan Picchi
yoan.picchi at foss.arm.com
Tue Mar 5 16:36:13 CET 2024
On 3/4/24 13:35, Konstantin Ananyev wrote:
>
>
>>>> - Implemented SVE code for comparing signatures in bulk lookup.
>>>> - Added Defines in code for SVE code support.
>>>> - Optimise NEON code
>>>> - New SVE code is ~5% slower than optimized NEON for N2 processor.
>>>>
>>>> Signed-off-by: Yoan Picchi <yoan.picchi at arm.com>
>>>> Signed-off-by: Harjot Singh <harjot.singh at arm.com>
>>>> Reviewed-by: Nathan Brown <nathan.brown at arm.com>
>>>> Reviewed-by: Ruifeng Wang <ruifeng.wang at arm.com>
>>>> ---
>>>> lib/hash/rte_cuckoo_hash.c | 196 ++++++++++++++++++++++++++++---------
>>>> lib/hash/rte_cuckoo_hash.h | 1 +
>>>> 2 files changed, 151 insertions(+), 46 deletions(-)
>>>>
>>>> diff --git a/lib/hash/rte_cuckoo_hash.c b/lib/hash/rte_cuckoo_hash.c
>>>> index a07dd3a28d..231d6d6ded 100644
>>>> --- a/lib/hash/rte_cuckoo_hash.c
>>>> +++ b/lib/hash/rte_cuckoo_hash.c
>>>> @@ -442,8 +442,11 @@ rte_hash_create(const struct rte_hash_parameters *params)
>>>> h->sig_cmp_fn = RTE_HASH_COMPARE_SSE;
>>>> else
>>>> #elif defined(RTE_ARCH_ARM64)
>>>> - if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_NEON))
>>>> + if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_NEON)) {
>>>> h->sig_cmp_fn = RTE_HASH_COMPARE_NEON;
>>>> + if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_SVE))
>>>> + h->sig_cmp_fn = RTE_HASH_COMPARE_SVE;
>>>> + }
>>>> else
>>>> #endif
>>>> h->sig_cmp_fn = RTE_HASH_COMPARE_SCALAR;
>>>> @@ -1860,37 +1863,103 @@ rte_hash_free_key_with_position(const struct rte_hash *h,
>>>> #if defined(__ARM_NEON)
>>>>
>>>> static inline void
>>>> -compare_signatures_dense(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches,
>>>> - const struct rte_hash_bucket *prim_bkt,
>>>> - const struct rte_hash_bucket *sec_bkt,
>>>> +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)
>>>> {
>>>> unsigned int i;
>>>>
>>>> + static_assert(sizeof(*hitmask_buffer) >= 2*(RTE_HASH_BUCKET_ENTRIES/8),
>>>> + "The hitmask must be exactly wide enough to accept the whole hitmask if it is dense");
>>>> +
>>>> /* For match mask every bits indicates the match */
>>>> switch (sig_cmp_fn) {
>>>
>>> Can I ask to move arch specific comparison code into some arch-specific headers or so?
>>> It is getting really hard to read and understand the generic code with all these ifdefs and arch specific instructions...
>>>
>
> Hi, apologies for long delay in response.
>
>
>> I can easily enough move the compare_signatures into an arm/x86
>> directory, and have a default version in the code.
>
> Yes, that's what I thought about.
>
>> The problem would be for bulk lookup. The function is already duplicated
>> 2 times (the l and lf version). If I remove the #ifdefs, I'll need to
>> duplicate them again into 4 nearly identical versions (dense and
>> sparse). The only third options I see would be some preprocessor macro
>> to patch the function, but that looks even dirtier to me.
>
> Not sure I understood you here: from looking at the code I don't see any
> arch specific ifdefs in bulk_lookup() routines.
> What I am missing here?
>
Most if not all of those #if are architecture specific. For instance:
#if defined(__ARM_NEON)
#if defined(RTE_HAS_SVE_ACLE)
The main reason there's some #if in bulk lookup is to handle whether the
function run with dense hitmask or a sparse hitmask.
x86 only support the sparse hitmask version (1 bit data, 1 bit padding)
but arm support the dense hitmask (every bit count). The later ends up
being faster.
Splitting bulk_lookup into its sparse and dense variant would be a lot
of code duplication that I'd prefer to avoid.
What I might be able to do would be move compare_signatures into some
arch specific version. The function are different enough that it
wouldn't be too much of a code duplication. I'd argue though that the
#ifded for NEON and SSE were already there and I only added the SVE variant.
>
>> I think duplicating the code would be bad, but I can do it if you want.
>> Unless you have a better solution?
>>
>>>> +#if RTE_HASH_BUCKET_ENTRIES <= 8
>>>> case RTE_HASH_COMPARE_NEON: {
>>>> - uint16x8_t vmat, x;
>>>> + uint16x8_t vmat, hit1, hit2;
>>>> const uint16x8_t mask = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};
>>>> const uint16x8_t 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_bkt->sig_current));
>>>> - x = vandq_u16(vmat, mask);
>>>> - *prim_hash_matches = (uint32_t)(vaddvq_u16(x));
>>>> + vmat = vceqq_u16(vsig, vld1q_u16(prim_bucket_sigs));
>>>> + hit1 = vandq_u16(vmat, mask);
>>>> +
>>>> /* Compare all signatures in the secondary bucket */
>>>> - vmat = vceqq_u16(vsig, vld1q_u16((uint16_t const *)sec_bkt->sig_current));
>>>> - x = vandq_u16(vmat, mask);
>>>> - *sec_hash_matches = (uint32_t)(vaddvq_u16(x));
>>>> + vmat = vceqq_u16(vsig, vld1q_u16(sec_bucket_sigs));
>>>> + hit2 = vandq_u16(vmat, mask);
>>>> +
>>>> + hit2 = vshlq_n_u16(hit2, RTE_HASH_BUCKET_ENTRIES);
>>>> + hit2 = vorrq_u16(hit1, hit2);
>>>> + *hitmask_buffer = vaddvq_u16(hit2);
>>>> + }
>>>> + break;
>>>> +#endif
>>>> +#if defined(RTE_HAS_SVE_ACLE)
>>>> + case RTE_HASH_COMPARE_SVE: {
>>>> + svuint16_t vsign, shift, sv_matches;
>>>> + svbool_t pred, match, bucket_wide_pred;
>>>> + int i = 0;
>>>> + uint64_t vl = svcnth();
>>>> +
>>>> + vsign = svdup_u16(sig);
>>>> + shift = svindex_u16(0, 1);
>>>> +
>>>> + if (vl >= 2 * RTE_HASH_BUCKET_ENTRIES && RTE_HASH_BUCKET_ENTRIES <= 8) {
>>>> + svuint16_t primary_array_vect, secondary_array_vect;
>>>> + bucket_wide_pred = svwhilelt_b16(0, RTE_HASH_BUCKET_ENTRIES);
>>>> + primary_array_vect = svld1_u16(bucket_wide_pred, prim_bucket_sigs);
>>>> + secondary_array_vect = svld1_u16(bucket_wide_pred, sec_bucket_sigs);
>>>> +
>>>> + /* We merged the two vectors so we can do both comparison at once */
>>>> + primary_array_vect = svsplice_u16(bucket_wide_pred,
>>>> + primary_array_vect,
>>>> + secondary_array_vect);
>>>> + pred = svwhilelt_b16(0, 2*RTE_HASH_BUCKET_ENTRIES);
>>>> +
>>>> + /* Compare all signatures in the buckets */
>>>> + match = svcmpeq_u16(pred, vsign, primary_array_vect);
>>>> + if (svptest_any(svptrue_b16(), match)) {
>>>> + sv_matches = svdup_u16(1);
>>>> + sv_matches = svlsl_u16_z(match, sv_matches, shift);
>>>> + *hitmask_buffer = svorv_u16(svptrue_b16(), sv_matches);
>>>> + }
>>>> + } else {
>>>> + do {
>>>> + pred = svwhilelt_b16(i, RTE_HASH_BUCKET_ENTRIES);
>>>> + uint16_t lower_half = 0;
>>>> + uint16_t upper_half = 0;
>>>> + /* Compare all signatures in the primary bucket */
>>>> + match = svcmpeq_u16(pred, vsign, svld1_u16(pred,
>>>> + &prim_bucket_sigs[i]));
>>>> + if (svptest_any(svptrue_b16(), match)) {
>>>> + sv_matches = svdup_u16(1);
>>>> + sv_matches = svlsl_u16_z(match, sv_matches, shift);
>>>> + lower_half = svorv_u16(svptrue_b16(), sv_matches);
>>>> + }
>>>> + /* Compare all signatures in the secondary bucket */
>>>> + match = svcmpeq_u16(pred, vsign, svld1_u16(pred,
>>>> + &sec_bucket_sigs[i]));
>>>> + if (svptest_any(svptrue_b16(), match)) {
>>>> + sv_matches = svdup_u16(1);
>>>> + sv_matches = svlsl_u16_z(match, sv_matches, shift);
>>>> + upper_half = svorv_u16(svptrue_b16(), sv_matches)
>>>> + << RTE_HASH_BUCKET_ENTRIES;
>>>> + }
>>>> + hitmask_buffer[i/8] = upper_half | lower_half;
>>>> + i += vl;
>>>> + } while (i < RTE_HASH_BUCKET_ENTRIES);
>>>> + }
>>>> }
>>>> break;
>>>> +#endif
>>>> default:
>>>> for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
>>>> - *prim_hash_matches |=
>>>> - ((sig == prim_bkt->sig_current[i]) << i);
>>>> - *sec_hash_matches |=
>>>> - ((sig == sec_bkt->sig_current[i]) << i);
>>>> + *hitmask_buffer |=
>>>> + ((sig == prim_bucket_sigs[i]) << i);
>>>> + *hitmask_buffer |=
>>>> + ((sig == sec_bucket_sigs[i]) << i) << RTE_HASH_BUCKET_ENTRIES;
>>>> }
>>>> }
>>>> }
>>>> @@ -1908,7 +1977,7 @@ compare_signatures_sparse(uint32_t *prim_hash_matches, uint32_t *sec_hash_matche
>>>>
>>>> /* For match mask the first bit of every two bits indicates the match */
>>>> switch (sig_cmp_fn) {
>>>> -#if defined(__SSE2__)
>>>> +#if defined(__SSE2__) && RTE_HASH_BUCKET_ENTRIES <= 8
>>>> case RTE_HASH_COMPARE_SSE:
>>>> /* Compare all signatures in the bucket */
>>>> *prim_hash_matches = _mm_movemask_epi8(_mm_cmpeq_epi16(
>>>> @@ -1948,14 +2017,18 @@ __bulk_lookup_l(const struct rte_hash *h, const void **keys,
>>>> uint64_t hits = 0;
>>>> int32_t i;
>>>> int32_t ret;
>>>> - uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
>>>> - uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
>>>> struct rte_hash_bucket *cur_bkt, *next_bkt;
>>>>
>>>> #if defined(__ARM_NEON)
>>>> const int hitmask_padding = 0;
>>>> + uint16_t hitmask_buffer[RTE_HASH_LOOKUP_BULK_MAX] = {0};
>>>> +
>>>> + static_assert(sizeof(*hitmask_buffer)*8/2 == RTE_HASH_BUCKET_ENTRIES,
>>>> + "The hitmask must be exactly wide enough to accept the whole hitmask when it is dense");
>>>> #else
>>>> const int hitmask_padding = 1;
>>>> + uint32_t prim_hitmask_buffer[RTE_HASH_LOOKUP_BULK_MAX] = {0};
>>>> + uint32_t sec_hitmask_buffer[RTE_HASH_LOOKUP_BULK_MAX] = {0};
>>>> #endif
>>>>
>>>> __hash_rw_reader_lock(h);
>>>> @@ -1963,18 +2036,24 @@ __bulk_lookup_l(const struct rte_hash *h, const void **keys,
>>>> /* Compare signatures and prefetch key slot of first hit */
>>>> for (i = 0; i < num_keys; i++) {
>>>> #if defined(__ARM_NEON)
>>>> - compare_signatures_dense(&prim_hitmask[i], &sec_hitmask[i],
>>>> - primary_bkt[i], secondary_bkt[i],
>>>> + uint16_t *hitmask = &hitmask_buffer[i];
>>>> + compare_signatures_dense(hitmask,
>>>> + primary_bkt[i]->sig_current,
>>>> + secondary_bkt[i]->sig_current,
>>>> sig[i], h->sig_cmp_fn);
>>>> + const unsigned int prim_hitmask = *(uint8_t *)(hitmask);
>>>> + const unsigned int sec_hitmask = *((uint8_t *)(hitmask)+1);
>>>> #else
>>>> - compare_signatures_sparse(&prim_hitmask[i], &sec_hitmask[i],
>>>> + compare_signatures_sparse(&prim_hitmask_buffer[i], &sec_hitmask_buffer[i],
>>>> primary_bkt[i], secondary_bkt[i],
>>>> sig[i], h->sig_cmp_fn);
>>>> + const unsigned int prim_hitmask = prim_hitmask_buffer[i];
>>>> + const unsigned int sec_hitmask = sec_hitmask_buffer[i];
>>>> #endif
>>>>
>>>> - if (prim_hitmask[i]) {
>>>> + if (prim_hitmask) {
>>>> uint32_t first_hit =
>>>> - rte_ctz32(prim_hitmask[i])
>>>> + rte_ctz32(prim_hitmask)
>>>> >> hitmask_padding;
>>>> uint32_t key_idx =
>>>> primary_bkt[i]->key_idx[first_hit];
>>>> @@ -1986,9 +2065,9 @@ __bulk_lookup_l(const struct rte_hash *h, const void **keys,
>>>> continue;
>>>> }
>>>>
>>>> - if (sec_hitmask[i]) {
>>>> + if (sec_hitmask) {
>>>> uint32_t first_hit =
>>>> - rte_ctz32(sec_hitmask[i])
>>>> + rte_ctz32(sec_hitmask)
>>>> >> hitmask_padding;
>>>> uint32_t key_idx =
>>>> secondary_bkt[i]->key_idx[first_hit];
>>>> @@ -2003,9 +2082,17 @@ __bulk_lookup_l(const struct rte_hash *h, const void **keys,
>>>> /* Compare keys, first hits in primary first */
>>>> for (i = 0; i < num_keys; i++) {
>>>> positions[i] = -ENOENT;
>>>> - while (prim_hitmask[i]) {
>>>> +#if defined(__ARM_NEON)
>>>> + uint16_t *hitmask = &hitmask_buffer[i];
>>>> + unsigned int prim_hitmask = *(uint8_t *)(hitmask);
>>>> + unsigned int sec_hitmask = *((uint8_t *)(hitmask)+1);
>>>> +#else
>>>> + unsigned int prim_hitmask = prim_hitmask_buffer[i];
>>>> + unsigned int sec_hitmask = sec_hitmask_buffer[i];
>>>> +#endif
>>>> + while (prim_hitmask) {
>>>> uint32_t hit_index =
>>>> - rte_ctz32(prim_hitmask[i])
>>>> + rte_ctz32(prim_hitmask)
>>>> >> hitmask_padding;
>>>> uint32_t key_idx =
>>>> primary_bkt[i]->key_idx[hit_index];
>>>> @@ -2028,12 +2115,12 @@ __bulk_lookup_l(const struct rte_hash *h, const void **keys,
>>>> positions[i] = key_idx - 1;
>>>> goto next_key;
>>>> }
>>>> - prim_hitmask[i] &= ~(1 << (hit_index << hitmask_padding));
>>>> + prim_hitmask &= ~(1 << (hit_index << hitmask_padding));
>>>> }
>>>>
>>>> - while (sec_hitmask[i]) {
>>>> + while (sec_hitmask) {
>>>> uint32_t hit_index =
>>>> - rte_ctz32(sec_hitmask[i])
>>>> + rte_ctz32(sec_hitmask)
>>>> >> hitmask_padding;
>>>> uint32_t key_idx =
>>>> secondary_bkt[i]->key_idx[hit_index];
>>>> @@ -2057,7 +2144,7 @@ __bulk_lookup_l(const struct rte_hash *h, const void **keys,
>>>> positions[i] = key_idx - 1;
>>>> goto next_key;
>>>> }
>>>> - sec_hitmask[i] &= ~(1 << (hit_index << hitmask_padding));
>>>> + sec_hitmask &= ~(1 << (hit_index << hitmask_padding));
>>>> }
>>>> next_key:
>>>> continue;
>>>> @@ -2107,15 +2194,18 @@ __bulk_lookup_lf(const struct rte_hash *h, const void **keys,
>>>> uint64_t hits = 0;
>>>> int32_t i;
>>>> int32_t ret;
>>>> - uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
>>>> - uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
>>>> struct rte_hash_bucket *cur_bkt, *next_bkt;
>>>> uint32_t cnt_b, cnt_a;
>>>>
>>>> #if defined(__ARM_NEON)
>>>> const int hitmask_padding = 0;
>>>> + uint16_t hitmask_buffer[RTE_HASH_LOOKUP_BULK_MAX] = {0};
>>>> + static_assert(sizeof(*hitmask_buffer)*8/2 == RTE_HASH_BUCKET_ENTRIES,
>>>> + "The hitmask must be exactly wide enough to accept the whole hitmask chen it is dense");
>>>> #else
>>>> const int hitmask_padding = 1;
>>>> + uint32_t prim_hitmask_buffer[RTE_HASH_LOOKUP_BULK_MAX] = {0};
>>>> + uint32_t sec_hitmask_buffer[RTE_HASH_LOOKUP_BULK_MAX] = {0};
>>>> #endif
>>>>
>>>> for (i = 0; i < num_keys; i++)
>>>> @@ -2132,18 +2222,24 @@ __bulk_lookup_lf(const struct rte_hash *h, const void **keys,
>>>> /* Compare signatures and prefetch key slot of first hit */
>>>> for (i = 0; i < num_keys; i++) {
>>>> #if defined(__ARM_NEON)
>>>> - compare_signatures_dense(&prim_hitmask[i], &sec_hitmask[i],
>>>> - primary_bkt[i], secondary_bkt[i],
>>>> + uint16_t *hitmask = &hitmask_buffer[i];
>>>> + compare_signatures_dense(hitmask,
>>>> + primary_bkt[i]->sig_current,
>>>> + secondary_bkt[i]->sig_current,
>>>> sig[i], h->sig_cmp_fn);
>>>> + const unsigned int prim_hitmask = *(uint8_t *)(hitmask);
>>>> + const unsigned int sec_hitmask = *((uint8_t *)(hitmask)+1);
>>>> #else
>>>> - compare_signatures_sparse(&prim_hitmask[i], &sec_hitmask[i],
>>>> + compare_signatures_sparse(&prim_hitmask_buffer[i], &sec_hitmask_buffer[i],
>>>> primary_bkt[i], secondary_bkt[i],
>>>> sig[i], h->sig_cmp_fn);
>>>> + const unsigned int prim_hitmask = prim_hitmask_buffer[i];
>>>> + const unsigned int sec_hitmask = sec_hitmask_buffer[i];
>>>> #endif
>>>>
>>>> - if (prim_hitmask[i]) {
>>>> + if (prim_hitmask) {
>>>> uint32_t first_hit =
>>>> - rte_ctz32(prim_hitmask[i])
>>>> + rte_ctz32(prim_hitmask)
>>>> >> hitmask_padding;
>>>> uint32_t key_idx =
>>>> primary_bkt[i]->key_idx[first_hit];
>>>> @@ -2155,9 +2251,9 @@ __bulk_lookup_lf(const struct rte_hash *h, const void **keys,
>>>> continue;
>>>> }
>>>>
>>>> - if (sec_hitmask[i]) {
>>>> + if (sec_hitmask) {
>>>> uint32_t first_hit =
>>>> - rte_ctz32(sec_hitmask[i])
>>>> + rte_ctz32(sec_hitmask)
>>>> >> hitmask_padding;
>>>> uint32_t key_idx =
>>>> secondary_bkt[i]->key_idx[first_hit];
>>>> @@ -2171,9 +2267,17 @@ __bulk_lookup_lf(const struct rte_hash *h, const void **keys,
>>>>
>>>> /* Compare keys, first hits in primary first */
>>>> for (i = 0; i < num_keys; i++) {
>>>> - while (prim_hitmask[i]) {
>>>> +#if defined(__ARM_NEON)
>>>> + uint16_t *hitmask = &hitmask_buffer[i];
>>>> + unsigned int prim_hitmask = *(uint8_t *)(hitmask);
>>>> + unsigned int sec_hitmask = *((uint8_t *)(hitmask)+1);
>>>> +#else
>>>> + unsigned int prim_hitmask = prim_hitmask_buffer[i];
>>>> + unsigned int sec_hitmask = sec_hitmask_buffer[i];
>>>> +#endif
>>>> + while (prim_hitmask) {
>>>> uint32_t hit_index =
>>>> - rte_ctz32(prim_hitmask[i])
>>>> + rte_ctz32(prim_hitmask)
>>>> >> hitmask_padding;
>>>> uint32_t key_idx =
>>>> rte_atomic_load_explicit(
>>>> @@ -2200,12 +2304,12 @@ __bulk_lookup_lf(const struct rte_hash *h, const void **keys,
>>>> positions[i] = key_idx - 1;
>>>> goto next_key;
>>>> }
>>>> - prim_hitmask[i] &= ~(1 << (hit_index << hitmask_padding));
>>>> + prim_hitmask &= ~(1 << (hit_index << hitmask_padding));
>>>> }
>>>>
>>>> - while (sec_hitmask[i]) {
>>>> + while (sec_hitmask) {
>>>> uint32_t hit_index =
>>>> - rte_ctz32(sec_hitmask[i])
>>>> + rte_ctz32(sec_hitmask)
>>>> >> hitmask_padding;
>>>> uint32_t key_idx =
>>>> rte_atomic_load_explicit(
>>>> @@ -2233,7 +2337,7 @@ __bulk_lookup_lf(const struct rte_hash *h, const void **keys,
>>>> positions[i] = key_idx - 1;
>>>> goto next_key;
>>>> }
>>>> - sec_hitmask[i] &= ~(1 << (hit_index << hitmask_padding));
>>>> + sec_hitmask &= ~(1 << (hit_index << hitmask_padding));
>>>> }
>>>> next_key:
>>>> continue;
>>>> diff --git a/lib/hash/rte_cuckoo_hash.h b/lib/hash/rte_cuckoo_hash.h
>>>> index 8ea793c66e..ed18e1f41e 100644
>>>> --- a/lib/hash/rte_cuckoo_hash.h
>>>> +++ b/lib/hash/rte_cuckoo_hash.h
>>>> @@ -137,6 +137,7 @@ enum rte_hash_sig_compare_function {
>>>> RTE_HASH_COMPARE_SCALAR = 0,
>>>> RTE_HASH_COMPARE_SSE,
>>>> RTE_HASH_COMPARE_NEON,
>>>> + RTE_HASH_COMPARE_SVE,
>>>> RTE_HASH_COMPARE_NUM
>>>> };
>>>>
>>>> --
>>>> 2.34.1
>>>
>
More information about the dev
mailing list