Substate scanning can be made O(log n) rather than O(n) #853
Labels
C-enhancement
C-performance
No new functions but ^^^ performance. Should contain benchmarks
E-good_first_issue
Good for newcomers
Currently,
get_latest_substate_from_committee
does a linear search for the latest version of a substate. This is O(n).You won't notice for version < 20 or so, but once a contract is used for a while, and versions reach 100+ and/or are very busy (with lots of updates between caches), this will become a noticeable performance drag.
Since substate versions are all down, then one up, then all non-existent, a binary search can make this an O(log_2 n) search by:
last_down_version
.version += step = INITIAL_STEP = 8
last_down_version
to version. Doublestep
and goto 2.last_down_version
<--version
. Set version = pvs_version-1.pvs_version <= version
.version = (version + last_down_version)/2
The text was updated successfully, but these errors were encountered: