[dpdk-dev] [RFC] Cuckoo hash for DPDK 2.1
De Lara Guarch, Pablo
pablo.de.lara.guarch at intel.com
Fri Apr 3 22:28:06 CEST 2015
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
More information about the dev
mailing list