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

Updating chunksInUse in Allocate/Deallocate results in performance degradation with each allocation. #70

Closed
m4drat opened this issue Sep 4, 2022 · 0 comments
Assignees
Labels

Comments

@m4drat
Copy link
Owner

m4drat commented Sep 4, 2022

  1. Completely remove chunksInUse and build it only when we need it (e.g. inside GC::Collect). This structure can be created in O(N), because we need to iterate over all chunks inside current arena starting from the first one. Note that the complexity is really O(N) even considering the fact that we need O(NlogN) to create a map. This works because we are iterating over chunks in a sorted order. Thus it is possible to provide chunksInUse.end() as a hint for insert method
  2. Using binary search find closest deallocated chunk inside chunkTreap. Starting from this chunk iterate in the right direction to find if we have required chunk or not.

Complete #29 before fixing this one

@m4drat m4drat added the Medium label Sep 4, 2022
@m4drat m4drat self-assigned this Sep 4, 2022
@m4drat m4drat added this to the Memory Manager milestone Sep 4, 2022
m4drat added a commit that referenced this issue Oct 25, 2022
@m4drat m4drat closed this as completed in 6861e00 Oct 25, 2022
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

2 participants