The idea we had converged on at the end of the convo was basically to have a concurrent tree with sorting enabled for storing the bulk of the mempool, with txs verified independently. However, each validator should also maintain a few "threads" of txs. The idea of a "thread" is that these are all verified to pass CheckTx when ran sequentially. (So the proposer can basically instantly propose its highest value thread) This is unlike the mempool, as the mempool constantly changes ordering.

When initially building a thread, you make it sorted by value. If you detect that you are proposing soon, you check to see if your mempool contains any txs with greater fees than what you have in the thread. Suppose there are n better txs in the mempool than whats in the thread. Then you remove the last n txs from the thread, and put these new ones.

The idea behind multiple threads is to reduce re-computation when you receive another persons block. There is a lot of design work for how to optimally do this thread concept. Please note that this thread design can be done incrementally. Phase 1 may just have a single thread, and a slightly slower update process right before you Reap. Later phases can incorporate more threads, and more improvements for incremental updates, and detection for when you will be proposing soon.

Originally posted by @ValarDragon in #2147 (comment)