store/cachekv: newMemIterator should use list.Len() to retrieve the slice size and cut out append activity

[odeke-em]

Summary of Bug

While profiling to fix #8747, while examining many profiles for a bunch, over 53 seconds, noticed this code

cosmos-sdk/store/cachekv/memiterator.go

Lines 21 to 22 in 432b0b2

	func newMemIterator(start, end []byte, items *list.List, ascending bool) *memIterator {
	itemsInDomain := make([]*kv.Pair, 0)

if we look at profiles

ROUTINE ======================== github.com/cosmos/cosmos-sdk/store/cachekv.newMemIterator in /Users/emmanuelodeke/go/src/github.com/cosmos/cosmos-sdk/store/cachekv/memiterator.go
     3.89s      8.09s (flat, cum) 15.02% of Total
         .          .     21:func newMemIterator(start, end []byte, items *list.List, ascending bool) *memIterator {
         .          .     22:	itemsInDomain := make([]*kv.Pair, 0)
         .          .     23:
         .          .     24:	var entered bool
         .          .     25:
     160ms      440ms     26:	for e := items.Front(); e != nil; e = e.Next() {
     1.47s      1.48s     27:		item := e.Value.(*kv.Pair)
     1.93s      2.96s     28:		if !dbm.IsKeyInDomain(item.Key, start, end) {
         .          .     29:			if entered {
         .          .     30:				break
         .          .     31:			}
         .          .     32:
         .          .     33:			continue
         .          .     34:		}
         .          .     35:
     330ms      3.20s     36:		itemsInDomain = append(itemsInDomain, item)
         .          .     37:		entered = true
         .          .     38:	}
         .          .     39:
         .       10ms     40:	return &memIterator{
         .          .     41:		start:     start,
         .          .     42:		end:       end,
         .          .     43:		items:     itemsInDomain,
         .          .     44:		ascending: ascending,
         .          .     45:	}

The culprit to focus on is

     330ms      3.20s     36:		itemsInDomain = append(itemsInDomain, item)

cumulatively it took 3.20 seconds, but really items is a container/list.List which has a property https://golang.org/pkg/container/list/#List.Len which when used shaves down time from 3.20 seconds down to 600ms

ROUTINE ======================== github.com/cosmos/cosmos-sdk/store/cachekv.newMemIterator in /Users/emmanuelodeke/go/src/github.com/cosmos/cosmos-sdk/store/cachekv/memiterator.go
     5.61s      7.91s (flat, cum) 17.74% of Total
         .          .     17:	items      []*kv.Pair
         .          .     18:	ascending  bool
         .          .     19:}
         .          .     20:
         .          .     21:func newMemIterator(start, end []byte, items *list.List, ascending bool) *memIterator {
         .      260ms     22:	itemsInDomain := make([]*kv.Pair, 0, items.Len())
         .          .     23:
         .          .     24:	var entered bool
         .          .     25:
     190ms      410ms     26:	for e := items.Front(); e != nil; e = e.Next() {
     2.28s      2.30s     27:		item := e.Value.(*kv.Pair)
     2.61s      4.06s     28:		if !dbm.IsKeyInDomain(item.Key, start, end) {
      40ms       40ms     29:			if entered {
         .          .     30:				break
         .          .     31:			}
         .          .     32:
         .          .     33:			continue
         .          .     34:		}
         .          .     35:
     490ms      600ms     36:		itemsInDomain = append(itemsInDomain, item)
         .          .     37:		entered = true
         .          .     38:	}
         .          .     39:
         .      240ms     40:	return &memIterator{
         .          .     41:		start:     start,
         .          .     42:		end:       end,
         .          .     43:		items:     itemsInDomain,
         .          .     44:		ascending: ascending,
         .          .     45:	}

Version

Latest at 432b0b2

It is 4:25AM, and I've been on a long performance hunt, but I need to go to bed, but kindly delegating to other folks to take a look, the PR is pretty straightforward to get in.

---

For Admin Use

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