As we are not dependent on the ordering, a hash map could improve performance here. As suggested by @sipa.
Consists of a first commit which makes the type easier to change - and should be easy to merge - and a second commit that actually changes the type. This needs benchmarking and extensive testing.
This makes it possible to switch to a more efficient map type
without changing all occurences manually.
As we are not dependent on the ordering, a hash map could
improve performance here. As suggested by @sipa.
We may need to check whether we don’t depend on iterators CCoinsViewCache iterators remaining stable under modifications.
It doesn’t seem that we depend on that. The only place where we pass around the iterators is in FetchCoins/GetCoins/HaveCoins, but there we at most return a reference to a CCoins, not the iterator itself (and the doc http://www.boost.org/doc/libs/1_55_0/doc/html/boost/unordered_map.html mentions that pointers and references to elements are never invalidated).
Outside of CCoinsViewCache (like in txdb) we only ever use constant CCoinsViewMaps.
I’ve compared heap usage over time of a -reindex with and without the patch (using the heap profiler in gperftools):
Not much difference in the overall trend or behavior; but a point of interest is that the memory usage with unordered map has fewer (and lower magnitude) sudden peaks.
I verified that the peak on x=33 for the ordered map is for a major part caused by memory allocation in CCoinsViewCache::BatchWrite / CCoinsViewCache::GetCoins.
As we avoid these kinds of peaks with unordered_map - implying that there is less overhead - in my opinion it’s worth to merge this.
There’s a mild exploitable performance weakness here: transaction signing can be grinded to make the constructed utxo entries end up in the same bucket, causing O(n) behaviour in that set.
I think it’s low risk, but it can be easily avoided by using a more complex function uint256 -> 64bit hash that takes a secret parameter into account (which can be generated at random at startup).
I don’t think the small win achieved here measures up against the extra brittleness involved in making the hashing non-deterministic between runs. In my experience this introduces problems (or at least extra work) while debugging and testing. std::map has a better worst-case performance, so it is a better fit.
I’m going to pull the first commit to make it easier to experiment with alternative data structures here, but not the second.