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
