Make mempool cache a proper LRU

[ValarDragon]

Currently the mempool cache is just a linked list + a hashmap. Continued access won't change your location in the linked list. This is very easy to ensure that it stays frequency based. (Basically 4 pointer sets on top of what we already have) We should add a function to our linked list to allow moving a node, and then convert the mempools cache into a full LRU. This would mean that suppose I receive a tx now, and then 1000 txs later, I suddenly receive alot of that same original tx. In our implementation, that original tx would get evicted once the list is full, but instead we can have it move the front rather easily.

[bradyjoestar]

Thanks for guidance of ValarDragon. 😄

[melekes]

Let's also benchmark #2407 just to make sure perf. did not go down drastically.

[ValarDragon]

I'd expect it to be unchanged, since the mempool hashmap hashing, plus sha2'ing the tx should dominate by an order of magnitude. But always worth checking!

[melekes]

I can do that tomorrow.

[melekes]

BenchmarkCacheInsertTime
goos: linux
goarch: amd64
pkg: github.com/tendermint/tendermint/mempool
BenchmarkCacheInsertTime-2         10000           5396158 ns/op
PASS
ok      github.com/tendermint/tendermint/mempool        57.260s
vagrant@ubuntu-xenial:~/go/src/github.com/tendermint/tendermint/mempool$ go test -bench=BenchmarkCacheInsertTime
goos: linux
goarch: amd64
pkg: github.com/tendermint/tendermint/mempool
BenchmarkCacheInsertTime-2         10000           5741434 ns/op
PASS
ok      github.com/tendermint/tendermint/mempool        61.051s

👍 given this should occur pretty infrequently

[melekes]

Merged to develop.

[ValarDragon]

Oh wow, that is a surprisingly large difference, thanks for benchmarking it! I'm actually surprised its that high.