Re: [dpdk-dev] [RFC] Cuckoo hash for DPDK 2.1

["yangguangjerry@hotmail.com" <yangguangjerry@hotmail.com>]

hi Pablo,
    rte_hash uses Jenkins hash (http://burtleburtle.net/bob/hash/ ) in older dpdk veriosn,which is originated lookup2.c in 1996.Bob Jenkins updates his hash function named lookup3.c in 2006. The hash function is more faster than lookup2.c. 
   why not continue to adopt the new hash function lookup3.c ?






At 2015-04-04 04:28:06, "De Lara Guarch, Pablo" <pablo.de.lara.guarch@intel.com> wrote:
>Hi all,
>
>This RFC is to describe a proposed replacement for the existing rte_hash implementation,
>using the cuckoo hash scheme (see http://www.cs.cmu.edu/~dongz/papers/cuckooswitch.pdf),
>which should provide better performance, in terms of lookup time, as well as a higher load factor.
>
>This new implementation also shall offer several improvements compared to the existing one, such as:
>
>-        Data return: existing implementation returns an index to the bucket where the key is stored,
>
>whereas the new implementation shall return 8-byte integers or pointers to external data.
>
>
>
>-        Increased key length: key length shall be increased more than the existing 64 bytes,
>
>without having a big penalty on performance
>
>
>
>-        Increased burst size: current implementation only allows 16 lookups at the same time,
>
>whereas the new implementation shall allow more than that (probably 64)
>
>
>
>-        Opening addressing: current implementation does not allow new keys to be added
>
>if its target bucket is full, whereas with Cuckoo hash, it offers an alternative location to store the key.
>
>I am currently working on the implementation, considering several options:
>
>
>-        Using a single table to store all the signatures, regardless they have used their primary or secondary hash function.
>
>
>
>-        Using two tables to store the signatures, one for primary hashes and another for the secondary hashes.
>
>
>I need to do some testing on both implementations to know which one is more suitable for DPDK.
>
>Any comments/ideas welcome.
>
>Thanks
>Pablo
>



yangguangjerry@hotmail.com