I'm reopening this because I think it's worth some long-term consideration. We're not going to get many opportunities to improve block connection by ~12%, so I think this is worth continuing to look at. Now that bitcoin is on c++17, I wonder if there aren't some good ways to slim down @martinus's implementation, since it contains a number of provisions to deal with <c++17 platforms. At the very least we could work on fuzz testing this to our satisfaction.

I've rerun some benchmarks on an idle workstation and have confirmed that I continue to see ~13% speedups along with reduction in memory use, which is especially pronounced when using a large dbcache.

Issues to consider

• From the README: "For a really bad hash the performance will not only degrade like in std::unordered_map, the map will simply fail with an std::overflow_error. In practice, when using the standard robin_hood::hash, I have never seen this happening."
  • Insert fails with std::overflow_error again martinus/robin-hood-hashing#117
  • Possible that we can amend this behavior, or at least convince ourselves this is appropriately unlikely given our use of siphash?

Benchmarks

dbcache=10000

commands index

jamesob/2019-08-robinhood vs. $mergebase (absolute)

jamesob/2019-08-robinhood vs. $mergebase (relative)

dbcache=300

commands index

2019-08-robinhood vs. master (absolute)

2019-08-robinhood vs. master (relative)

Cool. I plan on benchmarking this too (at least IBD speed) via the validation::connect_block USDT tracepoint.

It's unfortunately really hard to fix martinus/robin-hood-hashing#117 without losing at least some of the performance benefit. Also I don't really have the time to do it properly... So I'm personally quite a bit weary about using my robin_hood map for such a critical place. I mean I've been using it in for a long time in many countless installations and personally have never seen that problem, but other users of the map have definitely seen it. And it definitely is possible for an malicious actor to construct sequence of values that will cause the map to always fail. That's not possible for unordered_map, this would only degrades the performance.

I think it would be good to try the same benchmarks also with #16801 and also with tsl::sparse_map.

• faster & less memory for sync: bulk pool allocator for node based containers #16801 introduces a relatively simple bulk pool allocator for std::unordered_map. I think most of the performance improvement from robin_hood comes due to the more efficient allocation, and that pool allocator would bring the same allocation behavior to std::unordered_map. The code can be updated with C++17 features which would make it less of a hack. Such a pool allocator could also be beneficial in other places in the code too, wherever node based containers are used.

• Have a look at memory efficient hashmap implementation: tsl::sparse_map seems to be excellent, header only, and in my benchmarks while slower than robin_hood it is faster than std::unordered_map and more memory efficient than both. I think being able to keep more elements in memory should be a better trade off because it needs less flushes. https://github.com/Tessil/sparse-map

I have now rebased my branch https://github.com/martinus/bitcoin/tree/2019-08-bulkpoolallocator and done some rudimentary benchmarks: create the CCoinsMap, and 5 times insert 1 million entries and then clear it. I measured average time per insertion in ns/op and maximum resident set size in kbyte.

I tried std::unordered_map and std::map with and without the bulk_pool, and also tried a very simple hash:

struct Xor {
    size_t operator()(const COutPoint& id) const noexcept {
        return static_cast<size_t>(id.hash.GetUint64(0) ^ id.hash.GetUint64(1) ^ id.hash.GetUint64(2) ^ id.hash.GetUint64(3));
    }
};

I tried a few different hash implementations that I thought would be interesting, https://github.com/greg7mdp/parallel-hashmap, my https://github.com/martinus/robin-hood-hashing and https://github.com/Tessil/sparse-map.

Well, I actually didn't expect robin_hood map to be so good :)

Interestingly though, at least in that benchmark, std::unordered_map with the bulk_pool and the simple hash performs really well, even faster than robin_hood::unordered_node_map. I didn't expect tsl::sparse_map and phmap::node_hash_map to be so slow. Maybe they fare better in a real world benchmark with lots of lookups.

So I think it would be worthwhile to properly benchmark the bulk_pool way and a faster hash. Not sure if such a strong hash like siphash is actually needed here.

Once again, @martinus has convinced me that the relative performance benefits of swapping out the entire map implementation aren't worth the risks inherent in robin_hood's more uncertain failure modes. Luckily, bitcoinperf benchmarks (#16801 (comment)) indicate that work on the allocator may (as Martin suspected) yield most of the benefits of the change here with much less risk.

I'm closing this PR (again) and I think we should focus effort on vetting the allocator in Martin's branch.