Quorum intersection checker might benefit from caching subproblems

[graydon]

There are quite a lot of subproblems so it's not entirely clear that dynamic programming would be a win (or a win in all cases) but it's worth investigating.

[hidenori-shinohara]

I tried caching results of

• contractToMaximalQuorum
• isAQuorum
• containsQuorumSlice
• containsQuorumSliceForNode

(You can see the implementation of each by clicking it. Apologies for the not-so-good-looking implementations. I figured that I'd start with something quick that may not look very pretty just to see how much faster it will be.)

I compared the speed by running time (src/stellar-core test -a 'quorum intersection scaling test') 5 times and calculating the median and average of those 5 runs.

Results

• Both containsQuorumSliceForNode and containsQuorumSlice ended up at least 10x slower.
• Both isAQuorum and contractToMaximalQuorum ended up being roughly 5% faster.

Observations

• In most test cases, the function was only able to reuse cached results 30-70% of the time because not so many problems showed up many times.
• It was surprising to see that containsQuorumSliceForNode and containsQuorumSlice ended up being 10x slower. The only explanation that I could come up with was that turning a BitSet into a key & looking it up may not be that much cheaper than just checking if there exists a quorum slice contained in the BitSet especially if most quorum slices are indeed in the given node set.
• I'd imagine that there's a better implementation to cache subproblems, but from this, I couldn't really figure out a way to make the checker that much faster.