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

verify_state_blocks() with a max is O(n) #1475

Closed
rkeene opened this issue Dec 18, 2018 · 3 comments
Closed

verify_state_blocks() with a max is O(n) #1475

rkeene opened this issue Dec 18, 2018 · 3 comments
Assignees
Labels
Milestone

Comments

@rkeene
Copy link
Contributor

rkeene commented Dec 18, 2018

verify_state_blocks() with a max parameter (added in #1450) is O(n)

with 1000000 items in the state_blocks deque it takes much more time to do the swap than with 10000 items, given the same "max" parameter

@rkeene rkeene added the bug label Dec 18, 2018
@rkeene rkeene added this to the V18.0 milestone Dec 18, 2018
@rkeene
Copy link
Contributor Author

rkeene commented Dec 18, 2018

@cryptocode
Copy link
Contributor

Here are my notes:

auto position = std::distance(state_blocks.begin(), state_blocks.end () - keep_size); => 2048
so swap_ranges gets to iterate the whole shebang minus max_count
that said, resize is taking even more time in my measurements depending on deque size

SergiySW added a commit to SergiySW/raiblocks that referenced this issue Jan 8, 2019
For max_count = 256 || 2048 items.push_back (state_blocks.front ()) becoming more effective around (state_blocks.size () > 4 * max_count)
Following nanocurrency#1475
@SergiySW
Copy link
Contributor

Closing with #1571

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

3 participants