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
