store/cachekv: newMemIterator and others could use a typed linked list because type assertions are expensive #8810
Assignees
Labels
T: Performance
Performance improvements
Comments
odeke-em
assigned odeke-em, tac0turtle, alessio and robert-zaremba and unassigned odeke-em and tac0turtle
|
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
added a commit
that referenced
this issue
Mar 6, 2021
Reduces CPU burn by using a typed List to avoid the expensive type
assertions from using an interface. This is the only option for now
until Go makes generics generally available.
The change brings time spent on the time assertion cummulatively to:
580ms down from 6.88s
Explanation:
The type assertions were showing up heavily in profiles:
* Before this commit
```shell
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: }
```
and given that the list only uses that type, it is only right to lift the
code from container/list.List, and only modify Element.Value's type.
For emphasis, the code is basically just a retrofit of
container/list/list.go but with a typing, and we'll keep it as is
until perhaps Go1.17 or Go1.18 or when everyone uses Go1.17+ after
generics have landed.
* After this commit
```shell
Total: 45.25s
ROUTINE ======================== github.com/cosmos/cosmos-sdk/store/cachekv.newMemIterator
in /Users/emmanuelodeke/go/src/github.com/cosmos/cosmos-sdk/store/cachekv/memiterator.go
4.84s 6.77s (flat, cum) 14.96% of Total
. . 16: items []*kv.Pair
. . 17: ascending bool
. . 18:}
. . 19:
. . 20:func newMemIterator(start, end []byte, items *kv.List, ascending bool) *memIterator {
. 330ms 21: itemsInDomain := make([]*kv.Pair, 0, items.Len())
. . 22:
. . 23: var entered bool
. . 24:
60ms 160ms 25: for e := items.Front(); e != nil; e = e.Next() {
580ms 580ms 26: item := e.Value
3.68s 4.78s 27: if !dbm.IsKeyInDomain(item.Key, start, end) {
80ms 80ms 28: if entered {
. . 29: break
. . 30: }
. . 31:
. . 32: continue
. . 33: }
. . 34:
440ms 580ms 35: itemsInDomain = append(itemsInDomain, item)
. . 36: entered = true
. . 37: }
. . 38:
. 260ms 39: return &memIterator{
. . 40: start: start,
. . 41: end: end,
. . 42: items: itemsInDomain,
. . 43: ascending: ascending,
. . 44: }
```
Fixes #8810
9 tasks
|
I've mailed a PR for this, which is using a typed list adapted/lifted from container/list |
odeke-em
added a commit
that referenced
this issue
Mar 7, 2021
Reduces CPU burn by using a typed List to avoid the expensive type
assertions from using an interface. This is the only option for now
until Go makes generics generally available.
The change brings time spent on the time assertion cummulatively to:
580ms down from 6.88s
Explanation:
The type assertions were showing up heavily in profiles:
* Before this commit
```shell
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: }
```
and given that the list only uses that type, it is only right to lift the
code from container/list.List, and only modify Element.Value's type.
For emphasis, the code is basically just a retrofit of
container/list/list.go but with a typing, and we'll keep it as is
until perhaps Go1.17 or Go1.18 or when everyone uses Go1.17+ after
generics have landed.
* After this commit
```shell
Total: 45.25s
ROUTINE ======================== github.com/cosmos/cosmos-sdk/store/cachekv.newMemIterator
in /Users/emmanuelodeke/go/src/github.com/cosmos/cosmos-sdk/store/cachekv/memiterator.go
4.84s 6.77s (flat, cum) 14.96% of Total
. . 16: items []*kv.Pair
. . 17: ascending bool
. . 18:}
. . 19:
. . 20:func newMemIterator(start, end []byte, items *kv.List, ascending bool) *memIterator {
. 330ms 21: itemsInDomain := make([]*kv.Pair, 0, items.Len())
. . 22:
. . 23: var entered bool
. . 24:
60ms 160ms 25: for e := items.Front(); e != nil; e = e.Next() {
580ms 580ms 26: item := e.Value
3.68s 4.78s 27: if !dbm.IsKeyInDomain(item.Key, start, end) {
80ms 80ms 28: if entered {
. . 29: break
. . 30: }
. . 31:
. . 32: continue
. . 33: }
. . 34:
440ms 580ms 35: itemsInDomain = append(itemsInDomain, item)
. . 36: entered = true
. . 37: }
. . 38:
. 260ms 39: return &memIterator{
. . 40: start: start,
. . 41: end: end,
. . 42: items: itemsInDomain,
. . 43: ascending: ascending,
. . 44: }
```
Fixes #8810
odeke-em
added a commit
that referenced
this issue
Mar 8, 2021
…#8811) Reduces CPU burn by using a typed List to avoid the expensive type assertions from using an interface. This is the only option for now until Go makes generics generally available. The change brings time spent on the time assertion cummulatively to: 580ms down from 6.88s Explanation: The type assertions were showing up heavily in profiles: * Before this commit ```shell 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: } ``` and given that the list only uses that type, it is only right to lift the code from container/list.List, and only modify Element.Value's type. For emphasis, the code is basically just a retrofit of container/list/list.go but with a typing, and we'll keep it as is until perhaps Go1.17 or Go1.18 or when everyone uses Go1.17+ after generics have landed. * After this commit ```shell Total: 45.25s ROUTINE ======================== github.com/cosmos/cosmos-sdk/store/cachekv.newMemIterator in /Users/emmanuelodeke/go/src/github.com/cosmos/cosmos-sdk/store/cachekv/memiterator.go 4.84s 6.77s (flat, cum) 14.96% of Total . . 16: items []*kv.Pair . . 17: ascending bool . . 18:} . . 19: . . 20:func newMemIterator(start, end []byte, items *kv.List, ascending bool) *memIterator { . 330ms 21: itemsInDomain := make([]*kv.Pair, 0, items.Len()) . . 22: . . 23: var entered bool . . 24: 60ms 160ms 25: for e := items.Front(); e != nil; e = e.Next() { 580ms 580ms 26: item := e.Value 3.68s 4.78s 27: if !dbm.IsKeyInDomain(item.Key, start, end) { 80ms 80ms 28: if entered { . . 29: break . . 30: } . . 31: . . 32: continue . . 33: } . . 34: 440ms 580ms 35: itemsInDomain = append(itemsInDomain, item) . . 36: entered = true . . 37: } . . 38: . 260ms 39: return &memIterator{ . . 40: start: start, . . 41: end: end, . . 42: items: itemsInDomain, . . 43: ascending: ascending, . . 44: } ``` Fixes #8810
mergify bot
pushed a commit
that referenced
this issue
Mar 8, 2021
…#8811) Reduces CPU burn by using a typed List to avoid the expensive type assertions from using an interface. This is the only option for now until Go makes generics generally available. The change brings time spent on the time assertion cummulatively to: 580ms down from 6.88s Explanation: The type assertions were showing up heavily in profiles: * Before this commit ```shell 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: } ``` and given that the list only uses that type, it is only right to lift the code from container/list.List, and only modify Element.Value's type. For emphasis, the code is basically just a retrofit of container/list/list.go but with a typing, and we'll keep it as is until perhaps Go1.17 or Go1.18 or when everyone uses Go1.17+ after generics have landed. * After this commit ```shell Total: 45.25s ROUTINE ======================== github.com/cosmos/cosmos-sdk/store/cachekv.newMemIterator in /Users/emmanuelodeke/go/src/github.com/cosmos/cosmos-sdk/store/cachekv/memiterator.go 4.84s 6.77s (flat, cum) 14.96% of Total . . 16: items []*kv.Pair . . 17: ascending bool . . 18:} . . 19: . . 20:func newMemIterator(start, end []byte, items *kv.List, ascending bool) *memIterator { . 330ms 21: itemsInDomain := make([]*kv.Pair, 0, items.Len()) . . 22: . . 23: var entered bool . . 24: 60ms 160ms 25: for e := items.Front(); e != nil; e = e.Next() { 580ms 580ms 26: item := e.Value 3.68s 4.78s 27: if !dbm.IsKeyInDomain(item.Key, start, end) { 80ms 80ms 28: if entered { . . 29: break . . 30: } . . 31: . . 32: continue . . 33: } . . 34: 440ms 580ms 35: itemsInDomain = append(itemsInDomain, item) . . 36: entered = true . . 37: } . . 38: . 260ms 39: return &memIterator{ . . 40: start: start, . . 41: end: end, . . 42: items: itemsInDomain, . . 43: ascending: ascending, . . 44: } ``` Fixes #8810 (cherry picked from commit c2d5b24)
charleenfei
pushed a commit
to charleenfei/cosmos-sdk
that referenced
this issue
Mar 10, 2021
…cosmos#8811) Reduces CPU burn by using a typed List to avoid the expensive type assertions from using an interface. This is the only option for now until Go makes generics generally available. The change brings time spent on the time assertion cummulatively to: 580ms down from 6.88s Explanation: The type assertions were showing up heavily in profiles: * Before this commit ```shell 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: } ``` and given that the list only uses that type, it is only right to lift the code from container/list.List, and only modify Element.Value's type. For emphasis, the code is basically just a retrofit of container/list/list.go but with a typing, and we'll keep it as is until perhaps Go1.17 or Go1.18 or when everyone uses Go1.17+ after generics have landed. * After this commit ```shell Total: 45.25s ROUTINE ======================== github.com/cosmos/cosmos-sdk/store/cachekv.newMemIterator in /Users/emmanuelodeke/go/src/github.com/cosmos/cosmos-sdk/store/cachekv/memiterator.go 4.84s 6.77s (flat, cum) 14.96% of Total . . 16: items []*kv.Pair . . 17: ascending bool . . 18:} . . 19: . . 20:func newMemIterator(start, end []byte, items *kv.List, ascending bool) *memIterator { . 330ms 21: itemsInDomain := make([]*kv.Pair, 0, items.Len()) . . 22: . . 23: var entered bool . . 24: 60ms 160ms 25: for e := items.Front(); e != nil; e = e.Next() { 580ms 580ms 26: item := e.Value 3.68s 4.78s 27: if !dbm.IsKeyInDomain(item.Key, start, end) { 80ms 80ms 28: if entered { . . 29: break . . 30: } . . 31: . . 32: continue . . 33: } . . 34: 440ms 580ms 35: itemsInDomain = append(itemsInDomain, item) . . 36: entered = true . . 37: } . . 38: . 260ms 39: return &memIterator{ . . 40: start: start, . . 41: end: end, . . 42: items: itemsInDomain, . . 43: ascending: ascending, . . 44: } ``` Fixes cosmos#8810
alessio
pushed a commit
that referenced
this issue
Mar 10, 2021
…#8811) (#8817) Reduces CPU burn by using a typed List to avoid the expensive type assertions from using an interface. This is the only option for now until Go makes generics generally available. The change brings time spent on the time assertion cummulatively to: 580ms down from 6.88s Explanation: The type assertions were showing up heavily in profiles: * Before this commit ```shell 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: } ``` and given that the list only uses that type, it is only right to lift the code from container/list.List, and only modify Element.Value's type. For emphasis, the code is basically just a retrofit of container/list/list.go but with a typing, and we'll keep it as is until perhaps Go1.17 or Go1.18 or when everyone uses Go1.17+ after generics have landed. * After this commit ```shell Total: 45.25s ROUTINE ======================== github.com/cosmos/cosmos-sdk/store/cachekv.newMemIterator in /Users/emmanuelodeke/go/src/github.com/cosmos/cosmos-sdk/store/cachekv/memiterator.go 4.84s 6.77s (flat, cum) 14.96% of Total . . 16: items []*kv.Pair . . 17: ascending bool . . 18:} . . 19: . . 20:func newMemIterator(start, end []byte, items *kv.List, ascending bool) *memIterator { . 330ms 21: itemsInDomain := make([]*kv.Pair, 0, items.Len()) . . 22: . . 23: var entered bool . . 24: 60ms 160ms 25: for e := items.Front(); e != nil; e = e.Next() { 580ms 580ms 26: item := e.Value 3.68s 4.78s 27: if !dbm.IsKeyInDomain(item.Key, start, end) { 80ms 80ms 28: if entered { . . 29: break . . 30: } . . 31: . . 32: continue . . 33: } . . 34: 440ms 580ms 35: itemsInDomain = append(itemsInDomain, item) . . 36: entered = true . . 37: } . . 38: . 260ms 39: return &memIterator{ . . 40: start: start, . . 41: end: end, . . 42: items: itemsInDomain, . . 43: ascending: ascending, . . 44: } ``` Fixes #8810 (cherry picked from commit c2d5b24) Co-authored-by: Emmanuel T Odeke <[email protected]>
mergify bot
added a commit
that referenced
this issue
Mar 10, 2021
* fixed broken links, typos * Update docs/ibc/overview.md Co-authored-by: Amaury <[email protected]> * Update docs/intro/sdk-app-architecture.md Co-authored-by: Marko <[email protected]> * Update docs/building-modules/simulator.md Co-authored-by: Marko <[email protected]> * build(deps): bump JamesIves/github-pages-deploy-action from 4.0.0 to 4.1.0 (#8792) Bumps [JamesIves/github-pages-deploy-action](https://github.com/JamesIves/github-pages-deploy-action) from 4.0.0 to 4.1.0. - [Release notes](https://github.com/JamesIves/github-pages-deploy-action/releases) - [Commits](JamesIves/github-pages-deploy-action@4.0.0...3dbacc7) Signed-off-by: dependabot[bot] <[email protected]> Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com> * fix multisig account pubkeys migration (#8794) closes: #8776 * Update mergify (#8784) * Update mergify Prep for the v0.42 release series. * retire v0.41, the hub can upgrade to v0.42 smoothly * perf change (#8796) Co-authored-by: Alessio Treglia <[email protected]> Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com> * Supply by denom Migrations (#8780) * Add back supply proto * Add migration for supply * Fix lint * Update x/bank/spec/01_state.md * Fix test * Proto gen * Update x/bank/spec/01_state.md * Make proto gen Co-authored-by: Jonathan Gimeno <[email protected]> * fix make protoc error (#8799) * reduce gas costs by 10x for transient store operations (#8790) * reduce gas costs by 10x for transient store operations * fix TestTransientGasConfig for ReadCostFlat * added changelog entry * fix changelog * fix changelog Co-authored-by: Alessio Treglia <[email protected]> * x/gov: fix NormalizeProposalType() return values (#8808) Closes: #8806 * store/cachekv: use typed types/kv.List instead of container/list.List (#8811) Reduces CPU burn by using a typed List to avoid the expensive type assertions from using an interface. This is the only option for now until Go makes generics generally available. The change brings time spent on the time assertion cummulatively to: 580ms down from 6.88s Explanation: The type assertions were showing up heavily in profiles: * Before this commit ```shell 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: } ``` and given that the list only uses that type, it is only right to lift the code from container/list.List, and only modify Element.Value's type. For emphasis, the code is basically just a retrofit of container/list/list.go but with a typing, and we'll keep it as is until perhaps Go1.17 or Go1.18 or when everyone uses Go1.17+ after generics have landed. * After this commit ```shell Total: 45.25s ROUTINE ======================== github.com/cosmos/cosmos-sdk/store/cachekv.newMemIterator in /Users/emmanuelodeke/go/src/github.com/cosmos/cosmos-sdk/store/cachekv/memiterator.go 4.84s 6.77s (flat, cum) 14.96% of Total . . 16: items []*kv.Pair . . 17: ascending bool . . 18:} . . 19: . . 20:func newMemIterator(start, end []byte, items *kv.List, ascending bool) *memIterator { . 330ms 21: itemsInDomain := make([]*kv.Pair, 0, items.Len()) . . 22: . . 23: var entered bool . . 24: 60ms 160ms 25: for e := items.Front(); e != nil; e = e.Next() { 580ms 580ms 26: item := e.Value 3.68s 4.78s 27: if !dbm.IsKeyInDomain(item.Key, start, end) { 80ms 80ms 28: if entered { . . 29: break . . 30: } . . 31: . . 32: continue . . 33: } . . 34: 440ms 580ms 35: itemsInDomain = append(itemsInDomain, item) . . 36: entered = true . . 37: } . . 38: . 260ms 39: return &memIterator{ . . 40: start: start, . . 41: end: end, . . 42: items: itemsInDomain, . . 43: ascending: ascending, . . 44: } ``` Fixes #8810 * Move all migration scripts to v043 (#8814) * Move all migration scripts to v043 * Fix permaling * Fix test * Fix test again Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com> * permalinks Co-authored-by: chrly <[email protected]> Co-authored-by: Amaury <[email protected]> Co-authored-by: Jonathan Gimeno <[email protected]> Co-authored-by: Marko <[email protected]> Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com> Co-authored-by: Akhil Kumar P <[email protected]> Co-authored-by: Alessio Treglia <[email protected]> Co-authored-by: Marko <[email protected]> Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com> Co-authored-by: Albert Chon <[email protected]> Co-authored-by: Emmanuel T Odeke <[email protected]>
mergify bot
pushed a commit
that referenced
this issue
Mar 10, 2021
* fixed broken links, typos * Update docs/ibc/overview.md Co-authored-by: Amaury <[email protected]> * Update docs/intro/sdk-app-architecture.md Co-authored-by: Marko <[email protected]> * Update docs/building-modules/simulator.md Co-authored-by: Marko <[email protected]> * build(deps): bump JamesIves/github-pages-deploy-action from 4.0.0 to 4.1.0 (#8792) Bumps [JamesIves/github-pages-deploy-action](https://github.com/JamesIves/github-pages-deploy-action) from 4.0.0 to 4.1.0. - [Release notes](https://github.com/JamesIves/github-pages-deploy-action/releases) - [Commits](JamesIves/github-pages-deploy-action@4.0.0...3dbacc7) Signed-off-by: dependabot[bot] <[email protected]> Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com> * fix multisig account pubkeys migration (#8794) closes: #8776 * Update mergify (#8784) * Update mergify Prep for the v0.42 release series. * retire v0.41, the hub can upgrade to v0.42 smoothly * perf change (#8796) Co-authored-by: Alessio Treglia <[email protected]> Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com> * Supply by denom Migrations (#8780) * Add back supply proto * Add migration for supply * Fix lint * Update x/bank/spec/01_state.md * Fix test * Proto gen * Update x/bank/spec/01_state.md * Make proto gen Co-authored-by: Jonathan Gimeno <[email protected]> * fix make protoc error (#8799) * reduce gas costs by 10x for transient store operations (#8790) * reduce gas costs by 10x for transient store operations * fix TestTransientGasConfig for ReadCostFlat * added changelog entry * fix changelog * fix changelog Co-authored-by: Alessio Treglia <[email protected]> * x/gov: fix NormalizeProposalType() return values (#8808) Closes: #8806 * store/cachekv: use typed types/kv.List instead of container/list.List (#8811) Reduces CPU burn by using a typed List to avoid the expensive type assertions from using an interface. This is the only option for now until Go makes generics generally available. The change brings time spent on the time assertion cummulatively to: 580ms down from 6.88s Explanation: The type assertions were showing up heavily in profiles: * Before this commit ```shell 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: } ``` and given that the list only uses that type, it is only right to lift the code from container/list.List, and only modify Element.Value's type. For emphasis, the code is basically just a retrofit of container/list/list.go but with a typing, and we'll keep it as is until perhaps Go1.17 or Go1.18 or when everyone uses Go1.17+ after generics have landed. * After this commit ```shell Total: 45.25s ROUTINE ======================== github.com/cosmos/cosmos-sdk/store/cachekv.newMemIterator in /Users/emmanuelodeke/go/src/github.com/cosmos/cosmos-sdk/store/cachekv/memiterator.go 4.84s 6.77s (flat, cum) 14.96% of Total . . 16: items []*kv.Pair . . 17: ascending bool . . 18:} . . 19: . . 20:func newMemIterator(start, end []byte, items *kv.List, ascending bool) *memIterator { . 330ms 21: itemsInDomain := make([]*kv.Pair, 0, items.Len()) . . 22: . . 23: var entered bool . . 24: 60ms 160ms 25: for e := items.Front(); e != nil; e = e.Next() { 580ms 580ms 26: item := e.Value 3.68s 4.78s 27: if !dbm.IsKeyInDomain(item.Key, start, end) { 80ms 80ms 28: if entered { . . 29: break . . 30: } . . 31: . . 32: continue . . 33: } . . 34: 440ms 580ms 35: itemsInDomain = append(itemsInDomain, item) . . 36: entered = true . . 37: } . . 38: . 260ms 39: return &memIterator{ . . 40: start: start, . . 41: end: end, . . 42: items: itemsInDomain, . . 43: ascending: ascending, . . 44: } ``` Fixes #8810 * Move all migration scripts to v043 (#8814) * Move all migration scripts to v043 * Fix permaling * Fix test * Fix test again Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com> * permalinks Co-authored-by: chrly <[email protected]> Co-authored-by: Amaury <[email protected]> Co-authored-by: Jonathan Gimeno <[email protected]> Co-authored-by: Marko <[email protected]> Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com> Co-authored-by: Akhil Kumar P <[email protected]> Co-authored-by: Alessio Treglia <[email protected]> Co-authored-by: Marko <[email protected]> Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com> Co-authored-by: Albert Chon <[email protected]> Co-authored-by: Emmanuel T Odeke <[email protected]> (cherry picked from commit 55fc465)
alessio
pushed a commit
that referenced
this issue
Mar 10, 2021
* fixed broken links, typos * Update docs/ibc/overview.md Co-authored-by: Amaury <[email protected]> * Update docs/intro/sdk-app-architecture.md Co-authored-by: Marko <[email protected]> * Update docs/building-modules/simulator.md Co-authored-by: Marko <[email protected]> * build(deps): bump JamesIves/github-pages-deploy-action from 4.0.0 to 4.1.0 (#8792) Bumps [JamesIves/github-pages-deploy-action](https://github.com/JamesIves/github-pages-deploy-action) from 4.0.0 to 4.1.0. - [Release notes](https://github.com/JamesIves/github-pages-deploy-action/releases) - [Commits](JamesIves/github-pages-deploy-action@4.0.0...3dbacc7) Signed-off-by: dependabot[bot] <[email protected]> Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com> * fix multisig account pubkeys migration (#8794) closes: #8776 * Update mergify (#8784) * Update mergify Prep for the v0.42 release series. * retire v0.41, the hub can upgrade to v0.42 smoothly * perf change (#8796) Co-authored-by: Alessio Treglia <[email protected]> Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com> * Supply by denom Migrations (#8780) * Add back supply proto * Add migration for supply * Fix lint * Update x/bank/spec/01_state.md * Fix test * Proto gen * Update x/bank/spec/01_state.md * Make proto gen Co-authored-by: Jonathan Gimeno <[email protected]> * fix make protoc error (#8799) * reduce gas costs by 10x for transient store operations (#8790) * reduce gas costs by 10x for transient store operations * fix TestTransientGasConfig for ReadCostFlat * added changelog entry * fix changelog * fix changelog Co-authored-by: Alessio Treglia <[email protected]> * x/gov: fix NormalizeProposalType() return values (#8808) Closes: #8806 * store/cachekv: use typed types/kv.List instead of container/list.List (#8811) Reduces CPU burn by using a typed List to avoid the expensive type assertions from using an interface. This is the only option for now until Go makes generics generally available. The change brings time spent on the time assertion cummulatively to: 580ms down from 6.88s Explanation: The type assertions were showing up heavily in profiles: * Before this commit ```shell 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: } ``` and given that the list only uses that type, it is only right to lift the code from container/list.List, and only modify Element.Value's type. For emphasis, the code is basically just a retrofit of container/list/list.go but with a typing, and we'll keep it as is until perhaps Go1.17 or Go1.18 or when everyone uses Go1.17+ after generics have landed. * After this commit ```shell Total: 45.25s ROUTINE ======================== github.com/cosmos/cosmos-sdk/store/cachekv.newMemIterator in /Users/emmanuelodeke/go/src/github.com/cosmos/cosmos-sdk/store/cachekv/memiterator.go 4.84s 6.77s (flat, cum) 14.96% of Total . . 16: items []*kv.Pair . . 17: ascending bool . . 18:} . . 19: . . 20:func newMemIterator(start, end []byte, items *kv.List, ascending bool) *memIterator { . 330ms 21: itemsInDomain := make([]*kv.Pair, 0, items.Len()) . . 22: . . 23: var entered bool . . 24: 60ms 160ms 25: for e := items.Front(); e != nil; e = e.Next() { 580ms 580ms 26: item := e.Value 3.68s 4.78s 27: if !dbm.IsKeyInDomain(item.Key, start, end) { 80ms 80ms 28: if entered { . . 29: break . . 30: } . . 31: . . 32: continue . . 33: } . . 34: 440ms 580ms 35: itemsInDomain = append(itemsInDomain, item) . . 36: entered = true . . 37: } . . 38: . 260ms 39: return &memIterator{ . . 40: start: start, . . 41: end: end, . . 42: items: itemsInDomain, . . 43: ascending: ascending, . . 44: } ``` Fixes #8810 * Move all migration scripts to v043 (#8814) * Move all migration scripts to v043 * Fix permaling * Fix test * Fix test again Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com> * permalinks Co-authored-by: chrly <[email protected]> Co-authored-by: Amaury <[email protected]> Co-authored-by: Jonathan Gimeno <[email protected]> Co-authored-by: Marko <[email protected]> Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com> Co-authored-by: Akhil Kumar P <[email protected]> Co-authored-by: Alessio Treglia <[email protected]> Co-authored-by: Marko <[email protected]> Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com> Co-authored-by: Albert Chon <[email protected]> Co-authored-by: Emmanuel T Odeke <[email protected]> (cherry picked from commit 55fc465) Co-authored-by: Charly <[email protected]>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Summary of Bug
The code in
cosmos-sdk/store/cachekv/memiterator.go
Lines 21 to 27 in a65f838
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!!
Version
At a65f838
For Admin Use
The text was updated successfully, but these errors were encountered: