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

Optimize DenseSet::Grow #3870

Open
romange opened this issue Oct 5, 2024 · 0 comments · May be fixed by #3894
Open

Optimize DenseSet::Grow #3870

romange opened this issue Oct 5, 2024 · 0 comments · May be fixed by #3894
Assignees
Labels
enhancement New feature or request important higher priority than the usual ongoing development tasks

Comments

@romange
Copy link
Collaborator

romange commented Oct 5, 2024

DenseSet::Grow suffers from slow memory latency and it has a good potential for optimization.

introduce resharding algorithm that moves items to new buckets after the resize, but it does it in chunks of kBatchSize.

Similar to #3863

  1. Must add benchmarking code to string_set_test to evaluate the performance
  2. The benchmarking code must only evaluate Grow - which is not simple thing to do. For that it must add, say 2^15 items without mesuring and then use additional Add to trigger Grow event (when we cross 2^k we grow). The additional Add must be under measurement. See BM_AddMany for example, how we control timing with PauseTiming/ResumeTiming.
  3. Once the benchmark exists you can run it with ./string_set_test --bench --benchmark_filter=.*BM_Grow - should be done in opt mode.
  4. Now it is possible to improve the implementation of grow - introduce a state machine that takes a batch of buckets and iteratively reshards all the elements in them (GrowBatch). Grow should iterate over all old buckets and call GrowBatch.

I would expect ~50% CPU reduction for large sets

@romange romange added enhancement New feature or request important higher priority than the usual ongoing development tasks labels Oct 5, 2024
@BorysTheDev BorysTheDev linked a pull request Oct 9, 2024 that will close this issue
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request important higher priority than the usual ongoing development tasks
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants