[dpdk-dev] [PATCH v2 7/7] hash: use partial-key hashing

[Wang, Yipeng1]

>-----Original Message-----
>From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli at arm.com]
>Sent: Wednesday, September 26, 2018 9:24 PM
>To: Wang, Yipeng1 <yipeng1.wang at intel.com>; Richardson, Bruce <bruce.richardson at intel.com>
>Cc: dev at dpdk.org; michel at digirati.com.br
>Subject: RE: [PATCH v2 7/7] hash: use partial-key hashing
>
>
>> +static inline void
>> +get_buckets_index(const struct rte_hash *h, const hash_sig_t hash,
>> +uint32_t *prim_bkt, uint32_t *sec_bkt, uint16_t *sig) {
>> +/*
>> + * We use higher 16 bits of hash as the signature value stored in table.
>> + * We use the lower bits for the primary bucket
>> + * location. Then we XOR primary bucket location and the signature
>> + * to get the secondary bucket location. This is same as
>> + * proposed in Bin Fan, et al's paper
>> + * "MemC3: Compact and Concurrent MemCache with Dumber
>> Caching and
>> + * Smarter Hashing". The benefit to use
>> + * XOR is that one could derive the alternative bucket location
>> + * by only using the current bucket location and the signature.
>> + */
>> +*sig = hash >> 16;
>> +
>> +*prim_bkt = hash & h->bucket_bitmask;
>> +*sec_bkt =  (*prim_bkt ^ *sig) & h->bucket_bitmask; }
>> +
>IMO, this function can be split into 2 - one for primary bucket index and another for secondary bucket index. The secondary bucket
>index calculation function can be used in functions ' rte_hash_cuckoo_move_insert_mw' and ' rte_hash_cuckoo_make_space_mw'.
>
[Wang, Yipeng] I agree that breaking them down and use function call instead of explicit code will be easier for future extension,
i.e. changing the algorithm, etc. 
I split the function into 3 in V4. Please check out.

>> -/** Signature of key that is stored internally. */
>> +/**
>> + * A hash value that is used to generate signature stored in table and
>> +the
>> + * location the signature is stored.
>> + */
>This is an external file. This documentation goes into the API guide. IMO, we should change the comment to help the user. How about
>changing this to 'hash value of the key'?
>
[Wang, Yipeng] Improved in V4. Please check! Thanks!