[Roguelazer]

This is the same problem as `malloc`, right?

I imagine the answer depends on exactly what queries you need. If you have a bunch of different standard event sizes, then managing multiple different sorted freelists for the next open 1 hour slot, the next open 3 hour slot, etc might work. If you need high concurrency and "next available slot" is allowed to be fuzzy, then managing four distinct "event heaps" and parallelizing across them might work.

[grovesNL]

There are definitely a lot of similarities. I spent some time reviewing allocator designs to see if some ideas might carry over.

One problem I found is that a lot of allocators benefit from being able to track freelists based on some minimum sizes needed for allocations (e.g., https://github.com/sebbbi/OffsetAllocator). This problem is a bit different in that I want to know the first available block even though it might be much bigger than I need. Having multiple lists might still be useful though, but it's not as effective as how they're used in allocators - you'd usually need to search multiple freelists to know the first available instead of one.

[hyperpape]

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]

That'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.