Currently our mempool uses a linked list with a cache implemented as a hashmap (default size 100k).
The operations involved have the following asymptotics:
(assume mempool has N items already in it)

Add Tx - O(1) check in cache, locks on the cache. (Note this has a non-neglible hash involved, so the constant here is important!) Doesn't check if tx is in the main mempool linked list, which means we can add duplicate txs if our mempool size in the config is greater than our cache size.
Update k Txs - O(N), progresses serially. This doesn't parallelize because we iterate through every tx, and run recheck Tx blocking on that response. We also lock on the cache here, so parallelizing this part would still cause the threads to hang at the last step.
Reap k Txs - O(k) locks, unsorted. cache locks and unlocks here.

The cache locking and unlocking is on every operation is a huge barrier to this scaling. We also want our mempool to be sorted, which would mean our Add operation would have to be O(N). (This is a property required of basically all blockchain mempools, to handle periods of high tx volume)

I propose that we switch to the following concurrent AVL tree, that doesn't require locks: http://ddana.cswp.cs.technion.ac.il/wp-content/uploads/sites/19/2015/12/logicalorderingavl.pdf. Looking at table 1, this allows large numbers of threads quite well. Our expected number of txs in the mempool is between 10^3 and 10^5 I'd guess. No locking means we don't have to fear deadlocks in our implementation, and that implementation is significantly simpler. The other suggested implementations there either have locks, or "virtual nodes" which opens up fears of memleaks. (Note this suggestion presumes implementation of an ABCI "priority" function for txs)

This allows us to having the sorting property we want, and get rid of all locks, so we can easily support parallelizability in Add Tx and Update Tx. (No need to even lock between them!!) (Its not fully clear to me if Reap can be parallelized as well, however we don't need parallellizability in reap at all) We also use lots of extra memory in our Clist, so we will get a significantly more memory efficient implementation. (As this gets rid of the cache as well)

Our operations are all now either log(n) or k log (n) for the batch variants. We get the advantage that we can execute them all in parallel safely, this tree is self-balancing, and no constant hash overheads.