`fatxpool`: re-use tags from older views in `Pool::prune` function

[michalkucharczyk]

It seems that while handling forks there is a bottleneck in the Pool::prune function. Here is the log excerpt showing this situation:

processing event: NewBestBlock { hash: BLOCK335, tree_route: Some(TreeRoute { route: [HashAndNumber { number: 334, hash: BLOCK334 }, HashAndNumber { number: 333, hash: BLOCK333 }, HashAndNumber { number: 332, hash: BLOCK332 }, HashAndNumber { number: 333, hash: BLOCK333f01 }, HashAndNumber { number: 334, hash: BLOCK334f01 }], pivot: 2 }) }    
build_new_view: for: HashAndNumber { number: 335, hash: BLOCK335 } from: Some(HashAndNumber { number: 334, hash: BLOCK334 }) tree_route: TreeRoute { route: [HashAndNumber { number: 334, hash: BLOCK334 }, HashAndNumber { number: 333, hash: BLOCK333 }, HashAndNumber { number: 332, hash: BLOCK332 }, HashAndNumber { number: 333, hash: BLOCK333f01 }, HashAndNumber { number: 334, hash: BLOCK334f01 }, HashAndNumber { number: 335, hash: BLOCK335 }], pivot: 2 }    
register listeners: at HashAndNumber { number: 335, hash: BLOCK335 } took 11.103871ms    
update_view_with_fork tree_route: HashAndNumber { number: 335, hash: BLOCK335 } TreeRoute { route: [HashAndNumber { number: 334, hash: BLOCK334 }, HashAndNumber { number: 333, hash: BLOCK333 }, HashAndNumber { number: 332, hash: BLOCK332 }, HashAndNumber { number: 333, hash: BLOCK333f01 }, HashAndNumber { number: 334, hash: BLOCK334f01 }, HashAndNumber { number: 335, hash: BLOCK335 }], pivot: 2 }    
Starting pruning of block HashAndNumber { number: 333, hash: BLOCK333f01 } (extrinsics: 5263)    
Starting pruning of block HashAndNumber { number: 334, hash: BLOCK334f01 } (extrinsics: 5263)    
Starting pruning of block HashAndNumber { number: 335, hash: BLOCK335 } (extrinsics: 5263)    
prune: validated_counter:2, took:577.748µs    
Pruning at HashAndNumber { number: 335, hash: BLOCK335 }. Resubmitting transactions: 5261, reverification took: 14.775952ms    
prune: validated_counter:5263, took:2.642222163s    
Pruning at HashAndNumber { number: 334, hash: BLOCK334f01 }. Resubmitting transactions: 0, reverification took: 3.372911ms    
prune: validated_counter:5263, took:2.777313693s    
Pruning at HashAndNumber { number: 333, hash: BLOCK333f01 }. Resubmitting transactions: 0, reverification took: 3.61487ms    
update_view_with_fork: at HashAndNumber { number: 335, hash: BLOCK335 } took 2.817505998s    
update_view_with_mempool: HashAndNumber { number: 335, hash: BLOCK335 } xts:(37044, 0) v:1    
fatp::extrinsics_included_since_finalized BLOCK335 from BLOCK330 count: 26314 took:14.741272ms    
update_view_with_mempool: at BLOCK335 submitted 0/37044    
update_view_with_mempool: at HashAndNumber { number: 335, hash: BLOCK335 } took 36.381255ms    
maintain: txs:(37044, 0) views:[2;[(335, 10739, 0), (334, 16000, 0)]] event:NewBestBlock { hash: BLOCK335, tree_route: Some(TreeRoute { route: [HashAndNumber { number: 334, hash: BLOCK334 }, HashAndNumber { number: 333, hash: BLOCK333 }, HashAndNumber { number: 332, hash: BLOCK332 }, HashAndNumber { number: 333, hash: BLOCK333f01 }, HashAndNumber { number: 334, hash: BLOCK334f01 }], pivot: 2 }) }  took:2.933302247s

Note those lines:

prune: validated_counter:5263, took:2.642222163s    
prune: validated_counter:5263, took:2.777313693s    

The prune function removes the transactions providing the same tags as transactions included in the newly imported blocks from the pool. It also promotes future transactions basing on those tags.

Many transactions recently included in blocks BLOCK333f01, BLOCK334f01 are not present in the newly built view. As a result, we need the validate them with the runtime. This is the cost we see.

These transactions are absent because the new view for BLOCK335 was cloned from the tip of parallel fork BLOCK334, where they were likely already included and pruned.

We could re-use tags for those transactions from the past inactive_views. The provide tags should not be significantly changed for transactions with block progression.

The implementation would require to inject known tags into the prune function (probably a new function shall be created and new execution path shall be introduced for the fork-aware pool, or optional parameters with tags map shall be added to the related methods). Known tags need to be collected at the higher level - at the fork-aware pool where pruning is started.