store/cachekv: newMemIterator and others could use a typed linked list because type assertions are expensive

[odeke-em]

Summary of Bug

The code in

cosmos-sdk/store/cachekv/memiterator.go

Lines 21 to 27 in a65f838

	func newMemIterator(start, end []byte, items *list.List, ascending bool) *memIterator {
	itemsInDomain := make([]*kv.Pair, 0, items.Len())
	var entered bool
	for e := items.Front(); e != nil; e = e.Next() {
	item := e.Value.(*kv.Pair)

uses container/list.List but on every single iteration has to type assert on the value burns a whole lot of CPU time, moreover we know we'll ONLY EVER use *kv.Pair and this is how it shows up

and if we look closely, 6.88s in a routine that consumes 18.87s cumulatively, just for type assertions!!

Total: 42.18s
ROUTINE ======================== github.com/cosmos/cosmos-sdk/store/cachekv.newMemIterator in /Users/emmanuelodeke/go/src/github.com/cosmos/cosmos-sdk/store/cachekv/memiterator.go
    14.01s     18.87s (flat, cum) 44.74% of Total
         .          .     17:	items      []*kv.Pair
         .          .     18:	ascending  bool
         .          .     19:}
         .          .     20:
         .          .     21:func newMemIterator(start, end []byte, items *list.List, ascending bool) *memIterator {
         .      620ms     22:	itemsInDomain := make([]*kv.Pair, 0, items.Len())
         .          .     23:
         .          .     24:	var entered bool
         .          .     25:
     510ms      870ms     26:	for e := items.Front(); e != nil; e = e.Next() {
     6.85s      6.88s     27:		item := e.Value.(*kv.Pair)
     5.71s      8.19s     28:		if !dbm.IsKeyInDomain(item.Key, start, end) {
     120ms      120ms     29:			if entered {
         .          .     30:				break
         .          .     31:			}
         .          .     32:
         .          .     33:			continue
         .          .     34:		}
         .          .     35:
     820ms      980ms     36:		itemsInDomain = append(itemsInDomain, item)
         .          .     37:		entered = true
         .          .     38:	}
         .          .     39:
         .      1.21s     40:	return &memIterator{
         .          .     41:		start:     start,
         .          .     42:		end:       end,
         .          .     43:		items:     itemsInDomain,
         .          .     44:		ascending: ascending,
         .          .     45:	}

Version

At a65f838

---

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

[odeke-em]

I've tagged other folks in case someone has the bandwidth and time to write the typed kv.Pair list, before I get to it. Thank you!

[odeke-em]

I've mailed a PR for this, which is using a typed list adapted/lifted from container/list