Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Substate scanning can be made O(log n) rather than O(n) #853

Open
CjS77 opened this issue Dec 20, 2023 · 0 comments
Open

Substate scanning can be made O(log n) rather than O(n) #853

CjS77 opened this issue Dec 20, 2023 · 0 comments
Labels
C-enhancement C-performance No new functions but ^^^ performance. Should contain benchmarks E-good_first_issue Good for newcomers

Comments

@CjS77
Copy link
Contributor

CjS77 commented Dec 20, 2023

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:

  1. Set last known down version to last_down_version.
  2. Set version += step = INITIAL_STEP = 8
  3. If state is still down, set last_down_version to version. Double step and goto 2.
  4. If state is UP, we're done.
  5. If state is down, update last_down_version <-- version. Set version = pvs_version-1.
  6. Set pvs_version <= version.
  7. Else state must be DoesNotExist. Set version = (version + last_down_version)/2
  8. Goto 4.
@CjS77 CjS77 added E-good_first_issue Good for newcomers C-performance No new functions but ^^^ performance. Should contain benchmarks C-enhancement labels Dec 20, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
C-enhancement C-performance No new functions but ^^^ performance. Should contain benchmarks E-good_first_issue Good for newcomers
Projects
None yet
Development

No branches or pull requests

1 participant