3 ms·

It would be interesting to see this benchmarked against absl::flat_hash_map[1] and folly::f14:F14FastMap[2]. [1] https://abseil.io/about/design/swisstables htt

It would be interesting to see this benchmarked against absl::flat_hash_map[1] and folly::f14:F14FastMap[2]. [1] https://abseil.io/about/design/swisstables https://abseil.io/about/design/swisstables [2] https://github.com/facebook/folly/blob/master/folly/container/F14.md https://github.com/facebook/folly/blob/master/folly/containe...

scaramanga 6y ago
The point of cuckoo++ is to handle timers and expiry efficiently so neither of those hash tables is comparable. It would have to be "swisstables + heap" or "+ timer wheel" or some other timer management algorithm.
- alexhutcheson 6y ago
  Interesting, thanks for pointing that out - it wasn't obvious to me from skimming the paper. 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++.
  - scaramanga 6y ago
    Sure, I read it more the other way around, the bloom filter thing is part of an ongoing thrust (like horton) to reduce the number of memory accesses for bucketized cuckoo (2 on failure, 1.5 on success) down closer to 1. 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.
  - scaramanga 6y ago
    So yeah, you're right, comparison would be possible if you subtract all the timer stuff. But as I recall of the offered implementation there wasn't actually an easy way to do that...
    - alexhutcheson 6y ago
      Their graphs include "Cuckoo++" and "Cuckoo++ w/ timers". 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#benckmarking https://github.com/technicolor-research/cuckoopp#benckmarkin...
      - scaramanga 6y ago
        You can see that when TIMER macro is undefined in that benchmark code then no timer management is performed at all. 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!

scaramanga 6y ago

The point of cuckoo++ is to handle timers and expiry efficiently so neither of those hash tables is comparable. It would have to be "swisstables + heap" or "+ timer wheel" or some other timer management algorithm.

alexhutcheson 6y ago
Interesting, thanks for pointing that out - it wasn't obvious to me from skimming the paper. 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++.
- scaramanga 6y ago
  Sure, I read it more the other way around, the bloom filter thing is part of an ongoing thrust (like horton) to reduce the number of memory accesses for bucketized cuckoo (2 on failure, 1.5 on success) down closer to 1. 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.
- scaramanga 6y ago
  So yeah, you're right, comparison would be possible if you subtract all the timer stuff. But as I recall of the offered implementation there wasn't actually an easy way to do that...
  - alexhutcheson 6y ago
    Their graphs include "Cuckoo++" and "Cuckoo++ w/ timers". 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#benckmarking https://github.com/technicolor-research/cuckoopp#benckmarkin...
    - scaramanga 6y ago
      You can see that when TIMER macro is undefined in that benchmark code then no timer management is performed at all. 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!