But in the case of flow-tracking, many more memory accesses would be needed to organise a heap or timer wheel, so that's where the main win is, compared to an incremental improvement on bucketized cuckoo / horton.
From their GitHub repo[1] it looks like the timer feature isn't built-in by default: BLOOM is just Cuckoo++, while LAZY_BLOOM is Cuckoo++ with timers.
[1] https://github.com/technicolor-research/cuckoopp#benckmarkin...
What's shown in the paper that bucketized cukoo + bloom compares well to he other hash tables they looked at (DPDK is probably a bit of a red-herring since it supports, and is optimized for, concurrent operations - but that's by the by). And here, a comparison with a fast robin-hood-ish hash like swiss or bytell would be interesting.
But also in the same benchmarks, cuckoo++ with timers is being compared directly against benchmark runs where no timer management is performed at all. The results show that it to be comparable. So presumably, when compared against traditional timer management like heaps/wheels it would be significantly ahead. But the explicit comparison hasn't been done anywhere as far as I know.
That's more what I was getting at in previous comments. Of course, you can look at it the other way around and you can rip out the timer stuff and compare bucketized cuckoo + bloom as just a hash table in its own right too.
The other comparison might also be interesting, can you do similar timer stuff with a robin-hood hash? You'd probably have to give up the SIMD, or come up with a new scheme to make SIMD usable, since that's what bucketized cuckoo enables you to do easily and that robin hood doesn't.
Edit: thanks for the correction btw!
In their "Conclusion" section, they write:
"We thus propose Cuckoo++ which adds a bloom filter in the primary bucket, allowing to prune unnecessary accesses to the secondary bucket without requiring expensive computation. Cuckoo++ hash tables have a uniformly good performance when compared to both pessimistic and optimistic implementation, and an improved performance over DPDK and Horton tables for all cases.
We also describe a variant of Cuckoo++ that integrate support for entry expiration directly in the hash table, avoiding the need for external management of timers and the associated overheads. This relies on a new memory layout more compact than DPDK’s original one, and on the use of 16-bit timestamp."
That seems to imply that the timer/expiration feature is an optional added bonus, rather than a core feature of Cuckoo++.