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

[De Lara Guarch, Pablo]

Hi,

> From: yangguangjerry at hotmail.com [mailto:yangguangjerry at hotmail.com]
> Sent: Tuesday, April 07, 2015 10:46 AM
> To: De Lara Guarch, Pablo
> Cc: "dev at dpdk.org"
> Subject: Re:[dpdk-dev] [RFC] Cuckoo hash for DPDK 2.1
> 
> 
> 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 ?

I have looked at that and you are right, we can use the new hash function, 
so I will send a patch to replace the existing jhash function.

Anyway, keep in mind that this is independent of my proposal.
In the future implementation I will continue using the existing hash functions,
and what is going to change is the hash table behaviour and API, not the hash functions themselves.

Thanks,
Pablo
> 
> 
> 
> 
> 
> At 2015-04-04 04:28:06, "De Lara Guarch, Pablo"
> <pablo.de.lara.guarch at 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 at hotmail.com