Optimize chain selection in ChainDB

[edsko]

The chain selection code in the chain DB follows the specification very closely, but of course the specification is not concerned with performance, only efficiency. Chain selection works by finding a set of candidates starting at a particular point; if a new block comes in, and that block fits onto our current chain, the set of candidates is computed from current tip of the chain. However, if that block does not find onto our chain, we construct a prefix path backwards from that block to the tip of the immutable DB, find all candidates starting at the new block, and then construct the set of candidates by prepending that prefix path to those candidates.

imm DB tip I-------|-------------------------- our chain
                   |
                   --------------B new header

imm DB tip I=======X-------------------------- our chain
                   |
                   |   rollback
                   ===============B----------
                                  |
                                  *-------------------
                                  |
                                  *--------------                   

We then construct a set of "candidate suffixes", by computing an intersection of that chain with our current chain, and then using that to compute a rollback (in terms of a number of blocks) and a set of new headers. However, of course, the rollback will in fact be the same for all of those candidates, and there was no need to recompute the intersection point at all, because we knew that as soon as we computed the prefix back from the new header to our current chain.

This means that the implementation is correct, but is doing unnecessary work, which will become important once chains are more frequent. Therefore marking this as high priority, but only for shelley.

[edsko]

Dropping priority to medium, since we could release without this: the amount of extra work is not huge. It would however be good to do. Certainly not required for a testnet.

[edsko]

Note: if we trigger chain selection for a block already on the current chain, this optimization should imply that the path we find is the empty path.

[mrBliss]

Line in question: https://github.com/input-output-hk/ouroboros-network/blob/281b2bb08e4fbdb43817fb55fb55b1ceca2b518b/ouroboros-consensus/src/Ouroboros/Consensus/Storage/ChainDB/Impl/ChainSel.hs#L416