[dpdk-dev] [PATCH v2 1/2] hash: add hash bulk lookup with hash signatures array

[Wang, Yipeng1]

> -----Original Message-----
> From: Medvedkin, Vladimir <vladimir.medvedkin at intel.com>
> Sent: Thursday, March 26, 2020 9:47 AM
> To: dev at dpdk.org
> Cc: Wang, Yipeng1 <yipeng1.wang at intel.com>; Gobriel, Sameh
> <sameh.gobriel at intel.com>; Richardson, Bruce
> <bruce.richardson at intel.com>
> Subject: [PATCH v2 1/2] hash: add hash bulk lookup with hash signatures
> array
> 
> Implement rte_hash_lookup_with_hash_bulk_data() - lookup function with
> precomputed hash signatures.
> 
> Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin at intel.com>
> ---
>  lib/librte_hash/rte_cuckoo_hash.c    | 296 +++++++++++++++++++++++-----
> -------
>  lib/librte_hash/rte_hash.h           |  27 ++++
>  lib/librte_hash/rte_hash_version.map |   1 +
>  3 files changed, 227 insertions(+), 97 deletions(-)
> 
> diff --git a/lib/librte_hash/rte_cuckoo_hash.c
> b/lib/librte_hash/rte_cuckoo_hash.c
> index 6af8ca4..24a0756 100644
> --- a/lib/librte_hash/rte_cuckoo_hash.c
> +++ b/lib/librte_hash/rte_cuckoo_hash.c
> @@ -1711,64 +1711,20 @@ compare_signatures(uint32_t
> *prim_hash_matches, uint32_t *sec_hash_matches,
>  	}
>  }
> 
> -#define PREFETCH_OFFSET 4
>  static inline void
> -__rte_hash_lookup_bulk_l(const struct rte_hash *h, const void **keys,
> -			int32_t num_keys, int32_t *positions,
> -			uint64_t *hit_mask, void *data[])
> +__bulk_lookup_l(const struct rte_hash *h, const void **keys,
> +		const struct rte_hash_bucket **primary_bkt,
> +		const struct rte_hash_bucket **secondary_bkt,
> +		uint16_t *sig, int32_t num_keys, int32_t *positions,
> +		uint64_t *hit_mask, void *data[])
>  {
>  	uint64_t hits = 0;
>  	int32_t i;
>  	int32_t ret;
> -	uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX];
> -	uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX];
> -	uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX];
> -	uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
> -	const struct rte_hash_bucket
> *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
> -	const struct rte_hash_bucket
> *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
>  	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;
> 
> -	/* Prefetch first keys */
> -	for (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++)
> -		rte_prefetch0(keys[i]);
> -
> -	/*
> -	 * Prefetch rest of the keys, calculate primary and
> -	 * secondary bucket and prefetch them
> -	 */
> -	for (i = 0; i < (num_keys - PREFETCH_OFFSET); i++) {
> -		rte_prefetch0(keys[i + PREFETCH_OFFSET]);
> -
> -		prim_hash[i] = rte_hash_hash(h, keys[i]);
> -
> -		sig[i] = get_short_sig(prim_hash[i]);
> -		prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
> -		sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
> -
> -		primary_bkt[i] = &h->buckets[prim_index[i]];
> -		secondary_bkt[i] = &h->buckets[sec_index[i]];
> -
> -		rte_prefetch0(primary_bkt[i]);
> -		rte_prefetch0(secondary_bkt[i]);
> -	}
> -
> -	/* Calculate and prefetch rest of the buckets */
> -	for (; i < num_keys; i++) {
> -		prim_hash[i] = rte_hash_hash(h, keys[i]);
> -
> -		sig[i] = get_short_sig(prim_hash[i]);
> -		prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
> -		sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
> -
> -		primary_bkt[i] = &h->buckets[prim_index[i]];
> -		secondary_bkt[i] = &h->buckets[sec_index[i]];
> -
> -		rte_prefetch0(primary_bkt[i]);
> -		rte_prefetch0(secondary_bkt[i]);
> -	}
> -
>  	__hash_rw_reader_lock(h);
> 
>  	/* Compare signatures and prefetch key slot of first hit */ @@ -
> 1903,63 +1859,20 @@ __rte_hash_lookup_bulk_l(const struct rte_hash *h,
> const void **keys,  }
> 
>  static inline void
> -__rte_hash_lookup_bulk_lf(const struct rte_hash *h, const void **keys,
> -			int32_t num_keys, int32_t *positions,
> -			uint64_t *hit_mask, void *data[])
> +__bulk_lookup_lf(const struct rte_hash *h, const void **keys,
> +		const struct rte_hash_bucket **primary_bkt,
> +		const struct rte_hash_bucket **secondary_bkt,
> +		uint16_t *sig, int32_t num_keys, int32_t *positions,
> +		uint64_t *hit_mask, void *data[])
>  {
>  	uint64_t hits = 0;
>  	int32_t i;
>  	int32_t ret;
> -	uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX];
> -	uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX];
> -	uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX];
> -	uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
> -	const struct rte_hash_bucket
> *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
> -	const struct rte_hash_bucket
> *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
>  	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;
> 
> -	/* Prefetch first keys */
> -	for (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++)
> -		rte_prefetch0(keys[i]);
> -
> -	/*
> -	 * Prefetch rest of the keys, calculate primary and
> -	 * secondary bucket and prefetch them
> -	 */
> -	for (i = 0; i < (num_keys - PREFETCH_OFFSET); i++) {
> -		rte_prefetch0(keys[i + PREFETCH_OFFSET]);
> -
> -		prim_hash[i] = rte_hash_hash(h, keys[i]);
> -
> -		sig[i] = get_short_sig(prim_hash[i]);
> -		prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
> -		sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
> -
> -		primary_bkt[i] = &h->buckets[prim_index[i]];
> -		secondary_bkt[i] = &h->buckets[sec_index[i]];
> -
> -		rte_prefetch0(primary_bkt[i]);
> -		rte_prefetch0(secondary_bkt[i]);
> -	}
> -
> -	/* Calculate and prefetch rest of the buckets */
> -	for (; i < num_keys; i++) {
> -		prim_hash[i] = rte_hash_hash(h, keys[i]);
> -
> -		sig[i] = get_short_sig(prim_hash[i]);
> -		prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
> -		sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
> -
> -		primary_bkt[i] = &h->buckets[prim_index[i]];
> -		secondary_bkt[i] = &h->buckets[sec_index[i]];
> -
> -		rte_prefetch0(primary_bkt[i]);
> -		rte_prefetch0(secondary_bkt[i]);
> -	}
> -
>  	for (i = 0; i < num_keys; i++)
>  		positions[i] = -ENOENT;
> 
> @@ -2124,6 +2037,92 @@ __rte_hash_lookup_bulk_lf(const struct rte_hash
> *h, const void **keys,
>  		*hit_mask = hits;
>  }
> 
> +#define PREFETCH_OFFSET 4
> +static inline void
> +__bulk_lookup_prefetching_loop(const struct rte_hash *h,
> +	const void **keys, int32_t num_keys,
> +	uint16_t *sig,
> +	const struct rte_hash_bucket **primary_bkt,
> +	const struct rte_hash_bucket **secondary_bkt) {
> +	int32_t i;
> +	uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX];
> +	uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX];
> +	uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX];
> +
> +	/* Prefetch first keys */
> +	for (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++)
> +		rte_prefetch0(keys[i]);
> +
> +	/*
> +	 * Prefetch rest of the keys, calculate primary and
> +	 * secondary bucket and prefetch them
> +	 */
> +	for (i = 0; i < (num_keys - PREFETCH_OFFSET); i++) {
> +		rte_prefetch0(keys[i + PREFETCH_OFFSET]);
> +
> +		prim_hash[i] = rte_hash_hash(h, keys[i]);
> +
> +		sig[i] = get_short_sig(prim_hash[i]);
> +		prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
> +		sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
> +
> +		primary_bkt[i] = &h->buckets[prim_index[i]];
> +		secondary_bkt[i] = &h->buckets[sec_index[i]];
> +
> +		rte_prefetch0(primary_bkt[i]);
> +		rte_prefetch0(secondary_bkt[i]);
> +	}
> +
> +	/* Calculate and prefetch rest of the buckets */
> +	for (; i < num_keys; i++) {
> +		prim_hash[i] = rte_hash_hash(h, keys[i]);
> +
> +		sig[i] = get_short_sig(prim_hash[i]);
> +		prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
> +		sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
> +
> +		primary_bkt[i] = &h->buckets[prim_index[i]];
> +		secondary_bkt[i] = &h->buckets[sec_index[i]];
> +
> +		rte_prefetch0(primary_bkt[i]);
> +		rte_prefetch0(secondary_bkt[i]);
> +	}
> +}
> +
> +
[Wang, Yipeng] Here is an unnecessary blank line.
> +static inline void
> +__rte_hash_lookup_bulk_l(const struct rte_hash *h, const void **keys,
> +			int32_t num_keys, int32_t *positions,
> +			uint64_t *hit_mask, void *data[])
> +{
> +	uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
> +	const struct rte_hash_bucket
> *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];

[Wang, Yipeng] 
Thanks for revising the code to be more concise.
It looks so far so good to me.
BTW, would you like to add also the rte_hash_lookup_with_hash_bulk function in this patchset?
Just for the completeness.

Thanks
Yipeng