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

perf: Improve SizeBoundedMap complexity #1805

Open
griffinteller opened this issue Jun 25, 2024 · 0 comments
Open

perf: Improve SizeBoundedMap complexity #1805

griffinteller opened this issue Jun 25, 2024 · 0 comments

Comments

@griffinteller
Copy link
Contributor

Is your feature request related to a problem? Please describe.

The recent ide refactor #1804 uses a SizeBoundedMap to keep track of DiagramIDs and StepSequenceIDs, which maintains a queue internally, deleting the least-recent entries when the size of the map exceeds the max. Currently, this queue is just an array which is shifted, causing most operations to have $O(n)$ complexity. When we start keeping track of larger numbers of these ids, it will be nice to improve this complexity (either with a linked list, or by moving to a different scheme for automatic deletion).

Describe alternatives you've considered

Another (likely better) specifically for step sequences option is to use the doubly-linked list that already exists between step sequences to throw out old sequences:

  • We maintain a reference to the "head" step sequence (whose parent is null)
  • When the number of step sequences exceeds maxLen, delete the head and set the child's parent to null
  • When an internal node is deleted, recursively delete its children.

This has the advantage of maintain more clear invariants about when children/parents actually exist. For DiagramIDs, we would still need the size bounded map, hopefully with better time complexity.

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

No branches or pull requests

1 participant