3 ms·
What if you structure the "lists" so that each "freelist" contains all slots >= 2^n units of time? Then you only ever need to search the list that's the next si
by hyperpape 2y ago
What if you structure the "lists" so that each "freelist" contains all slots >= 2^n units of time? Then you only ever need to search the list that's the next size down from your target slot?
This will be bad for write performance, but solves the problem of needing to do multiple searches to find the next available slot, and you mentioned that you might not mind sacrificing write performance.
- grovesNL 2y agoThat's definitely possible and could be a reasonable tradeoff. I'd be slightly worried about the extent that it sacrifices write performance, but it might not be too bad if if the number of levels are kept small.