  Hash tables are an essential data-structure for numerous networking
applications (e.g., connection tracking, firewalls, network address
translators). Among these, cuckoo hash tables provide excellent performance by
allowing lookups to be processed with very few memory accesses (2 to 3 per
lookup). Yet, for large tables, cuckoo hash tables remain memory bound and each
memory access impacts performance. In this paper, we propose algorithmic
improvements to cuckoo hash tables allowing to eliminate some unnecessary
memory accesses; these changes are conducted without altering the properties of
the original cuckoo hash table so that all existing theoretical analysis remain
applicable. On a single core, our hash table achieves 37M lookups per second
for positive lookups (i.e., when the key looked up is present in the table),
and 60M lookups per second for negative lookups, a 50% improvement over the
implementation included into the DPDK. On a 18-core, with mostly positive
lookups, our implementation achieves 496M lookups per second, a 45% improvement
over DPDK.
