lite: memStoreProvider should use binary/range search for GetByHeight #1021
Description
Just by reading the code I noticed that the only place that we seem to be mutating is by appending to it then subsequently sorting byHeight at
tendermint/lite/memprovider.go
Lines 54 to 55 in d14ec7d
However, GetByHeight performs a linear search each time
tendermint/lite/memprovider.go
Lines 64 to 70 in d14ec7d
which in the code above always assumes the best case. IMO this doesn't do much to guarantee us speed and cuts out the benefits of sorting each time. Let's make this a binary/range search because no matter how many items are inserted in there, the worst case for the binary/range search will always be O(log(n)) while the current code is linear and to show the impact of this change:
If there are are 1million byHeight entries:
| n=len(m.byHeight) | maxIterations(Linear search) | maxIterations(Binary search) |
|---|---|---|
| 10 | 10 | 4 |
| 100 | 100 | 7 |
| 1000 | 1000 | 10 |
| 10000 | 10000 | 14 |
| 100000 | 100000 | 17 |
| 1000000 | 1000000 | 20 |
and here is the code that we can use to fix this, it is also shorter and magnitudes more efficent
// Since it is already sorted by largest to lowest in StoreCommit
i := sort.Search(len(m.byHeight), func(j int) bool {
return m.byHeight[j].Height() <= h
})and for more information, please read https://en.wikipedia.org/wiki/Binary_search_algorithm