Re: [dpdk-dev] [PATCH v2] hash table: add an iterator over conflicting entries

["Wang, Yipeng1" <yipeng1.wang@intel.com>]

Thanks for the patch and sorry for the late review.
I believe this will be a good addition to the library and please
keep me cc'ed for V3 as well.

We have the linked list cuckoo hash on the roadmap for 18.11
http://mails.dpdk.org/archives/dev/2018-August/109986.html

I think with Honnappa suggested "uint32_t* next",
we may need a little bit tricks to make it work with the extra linked list.
The performance may not be optimal though comparing to your original approach.
Is this important to your use case?

I think we can work something out to satisfy everybody :)

Thanks
Yipeng

>-----Original Message-----
>From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
>Sent: Tuesday, August 21, 2018 4:43 PM
>To: Michel Machado <michel@digirati.com.br>; Fu, Qiaobin <qiaobinf@bu.edu>; Richardson, Bruce <bruce.richardson@intel.com>;
>De Lara Guarch, Pablo <pablo.de.lara.guarch@intel.com>
>Cc: dev@dpdk.org; Doucette, Cody, Joseph <doucette@bu.edu>; Wang, Yipeng1 <yipeng1.wang@intel.com>; Wiles, Keith
><keith.wiles@intel.com>; Gobriel, Sameh <sameh.gobriel@intel.com>; Tai, Charlie <charlie.tai@intel.com>; Stephen Hemminger
><stephen@networkplumber.org>; nd <nd@arm.com>
>Subject: RE: [dpdk-dev] [PATCH v2] hash table: add an iterator over conflicting entries
>
>
>
>-----Original Message-----
>From: Michel Machado <michel@digirati.com.br>
>Sent: Tuesday, August 21, 2018 7:42 AM
>To: Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>; Fu, Qiaobin <qiaobinf@bu.edu>; Richardson, Bruce
><bruce.richardson@intel.com>; De Lara Guarch, Pablo <pablo.de.lara.guarch@intel.com>
>Cc: dev@dpdk.org; Doucette, Cody, Joseph <doucette@bu.edu>; Wang, Yipeng1 <yipeng1.wang@intel.com>; Wiles, Keith
><keith.wiles@intel.com>; Gobriel, Sameh <sameh.gobriel@intel.com>; Tai, Charlie <charlie.tai@intel.com>; Stephen Hemminger
><stephen@networkplumber.org>; nd <nd@arm.com>
>Subject: Re: [dpdk-dev] [PATCH v2] hash table: add an iterator over conflicting entries
>
>On 08/21/2018 01:10 AM, Honnappa Nagarahalli wrote:
>> On 08/17/2018 03:41 PM, Honnappa Nagarahalli wrote:
>>> Can you elaborate more on using ' struct rte_conflict_iterator_state' as the argument for the API?
>>>
>>> If the API signature is changed to: rte_hash_iterate_conflict_entries (const struct rte_hash *h, void **key, void **data, const
>hash_sig_t sig, struct rte_conflict_iterator_state *state) - it will be inline with the existing APIs. Contents of 'state' must be initialized
>to 0 for the first call. This will also avoid creating 'rte_hash_iterator_conflict_entries_init' API.
>>
>>      Testing `state' every time rte_hash_iterate_conflict_entries() is
>> called to find out if it's the first call of the iterator will
>> possibly add some small, but unnecessary, overhead on
>> rte_hash_iterate_conflict_entries() and constraints on struct
>> rte_conflict_iterator_state. Moreover,
>> rte_hash_iterator_conflict_entries_init() enables one to easily add variations of the init function to initialize the state (e.g. using a
>key instead of a sig) and still use the exactly same iterator.
>>
>> IMO, I think, this over-head will be trivial. Looking at the function 'rte_hash_iterate_conflict_entries' the check for '(__state->vnext
>< RTE_HASH_BUCKET_ENTRIES * 2)' already exists. If the primary/secondary bucket indices are calculated as well in
>'rte_hash_iterate_conflict_entries' API ('rte_hash_iterate' API does such calculations), storing them in the state can be avoided. I am
>wondering if it makes sense to benchmark with these changes and then take a decision?
>
>    We have come up with the init function and struct rte_conflict_iterator_state in v2 to make the new iterator as future proof to a
>change of the underlying algorithm as possible. But going through your feedback, it seems to me that your top concern is to not
>deviate much of the current interface of rte_hash_iterate(). We are fine with pushing v3 using the interface you've suggested to
>avoid the init function and struct rte_conflict_iterator_state:
>
>int32_t
>rte_hash_iterate_conflict_entries__with_hash(const struct rte_hash *h, const void **key, void **data, hash_sig_t sig, uint32_t
>*next);
>
>Yes, this is my primary concern. Above signature will conform to what we have currently. If APIs have to change because of the
>change in underlying algorithm we can do it when it happens (with the better understanding of the situation at that time).
>
>I have to add that I liked your idea of 64B state. But that also means it is not in line with rte_hash_iterate(). We should remember to
>do it in the future if we happen to change the API signature.
>
>[ ]'s
>Michel Machado