[dpdk-dev] [PATCH v4 0/7] Cuckoo hash - part 3 of Cuckoo hash
Bruce Richardson
bruce.richardson at intel.com
Fri Jul 10 22:52:49 CEST 2015
On Fri, Jul 10, 2015 at 06:24:17PM +0100, Pablo de Lara wrote:
> This patchset is to replace the existing hash library with
> a more efficient and functional approach, using the Cuckoo hash
> method to deal with collisions. This method is based on using
> two different hash functions to have two possible locations
> in the hash table where an entry can be.
> So, if a bucket is full, a new entry can push one of the items
> in that bucket to its alternative location, making space for itself.
>
> Advantages
> ~~~~~
> - Offers the option to store more entries when the target bucket is full
> (unlike the previous implementation)
> - Memory efficient: for storing those entries, it is not necessary to
> request new memory, as the entries will be stored in the same table
> - Constant worst lookup time: in worst case scenario, it always takes
> the same time to look up an entry, as there are only two possible locations
> where an entry can be.
> - Storing data: user can store data in the hash table, unlike the
> previous implementation, but he can still use the old API
>
> This implementation tipically offers over 90% utilization.
> Notice that API has been extended, but old API remains.
> Check documentation included to know more about this new implementation
> (including how entries are distributed as table utilization increases).
>
> Changes in v4:
> - Unit tests enhancements are not part of this patchset anymore.
> - rte_hash structure has been made internal in another patch,
> so it is not part of this patchset anymore.
> - Add function to iterate through the hash table, as rte_hash
> structure has been made private.
> - Added extra_flag parameter in rte_hash_parameter to be able
> to add new parameters in the future without breaking the ABI
> - Remove proposed lookup_bulk_with_hash function, as it is
> not of much use with the existing hash functions
> (there are no vector hash functions).
> - User can store 8-byte integer or pointer as data, instead
> of variable size data, as discussed in the mailing list.
>
Hi Pablo,
I'm getting some compile errors with this code, perhaps you could recheck e.g
32-bit and with clang.
On the plus side, I like the docs included with this set.
Regards,
/Bruce
More information about the dev
mailing list