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

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

[yangguangjerry]

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

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

[De Lara Guarch, Pablo]

Hi,

> From: yangguangjerry@hotmail.com [mailto:yangguangjerry@hotmail.com]
> Sent: Tuesday, April 07, 2015 10:46 AM
> To: De Lara Guarch, Pablo
> Cc: "dev@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@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

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

[De Lara Guarch, Pablo]

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