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

Use a maple tree inspired data structure for the Calendar #469

Open
tijlleenders opened this issue Oct 20, 2024 · 0 comments
Open

Use a maple tree inspired data structure for the Calendar #469

tijlleenders opened this issue Oct 20, 2024 · 0 comments
Labels

Comments

@tijlleenders
Copy link
Owner

tijlleenders commented Oct 20, 2024

Is your feature request related to a problem? Please describe.
I'm always frustrated when:

  • The Calendar granularity is limited by memory and lookup efficiency. It takes a few seconds on a relatively performant mobile phone to recalculate my Calendar currently, for only two weeks - and using 1h granularity. The reason is that representing each smallest time slot of a Calendar as a separate entry in a Vec is not space or lookup efficient.

Resolving this issue would also allow for #394 while maintaining/improving performance.

Describe the solution you'd like
Make Calendar data storage and finding/counting of Slots more efficient by using ranges.
There have been thoughts about this (using ranges in a B-Tree or adapting interval tree) - but so far I've never encountered an example of an implementation specifically designed for storing non-overlapping ranges and the gaps in between. Maple Tree seems to fit. Linking to that via FFI or more likely rewriting it in Rust (as a separate Rust crate so others can use it too) could be a solution. The ZinZen use case, unlike Linux, is single-user - and can be optimized differently. Also, it needs to store information on the number of claims per null range - and which activity claimed wich range.

Describe alternatives you've considered

  • Not increasing granularity. Not an option.
  • Optimizing current brute-force 'walking' the Calendar with caches / smart logic like suggested in Allow 5 minute duration goals #394

Additional context
lib/maple_tree.c
lib/test_maple_tree.c

@tijlleenders tijlleenders moved this to temp to drag faster in ZinZen scheduler Oct 20, 2024
@tijlleenders tijlleenders changed the title Use a maple tree as the Calendar internal data structure Use a maple tree inspired data structure for the Calendar Oct 20, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
Status: Backlog
Development

No branches or pull requests

1 participant