[grovesNL]

I tried a bitmask/bitset/bitvec but found the performance of searches to be a worse than the ordered map I'm using. Intuitively I expected it to perform slightly better for searches because of the cache efficiency, but I guess the way my ranges were distributed made it spend a lot of time searching within each element of the set. I'd like to revisit it eventually though because I think this direction is promising.

[ashf023]

A few rough ideas for bitsets:

- To find runs of 15+ 1s you can find bytes with the value 255 using SIMD eq

- For windows of width N you could AND the bitmap with itself shifted by N to find spots where there's an opening at index i AND index i+N, then check that those openings are actually contiguous

- You can use count-trailing-zeros (generally very fast on modern CPUs) to quickly find the positions of set bits. For more than 1 searched bit in a word, you can do x = x & (x-1) to unset the last bit and find the next one. This would require you search for 1's and keep the bitmap reversed. You can of course skip any words that are fully 0.

- In general, bitmaps let you use a bunch of bit hacks like in https://graphics.stanford.edu/~seander/bithacks.html

[grovesNL]

Thanks for the ideas! I did try lzcnt/tzcnt with bitshifts to find contiguous intervals across elements, but I found that it tended to be more expensive than searching the map depending on the density. I think it's a really promising approach though, and I've like to figure out a way to make it work better for my test case.

[ashf023]

Gotcha. I wasn't quite sure from your post, are you storing free slots in the map, or booked slots? And do you know, for the cases that aren't fast enough, how much they tend to search through? Like are there just a ton of bookings before the first free slot, or are the slow cases maybe trying to find very wide slots that are just hard to find?

[grovesNL]

I'm storing free slots right now, but either would be ok if a data structure would benefit from the other representation.

The slow cases usually tend to be trying to find wider slots and skipping through many smaller slots. There are often a lot of bookings up to the first wide enough slot too though, so it's a little bit of both.

[ashf023]

Maybe an additional "lower resolution" index on top of the map could help as a heuristic to skip whole regions, then using the map to double check possible matches. I have a rough idea that I think could possibly work:

Maintain the sum of booked time within each coarser time bucket, e.g. 1 hour or something (ideally a power of two though so you can use shifts to find the index for a timestamp), and keep that in a flat array. If you're looking for a slot that's less than 2x the coarser interval here, e.g. a 90-minute one, look for look for two consecutive buckets with a combined sum <= 30 minutes. 2 hours or more is guaranteed to fully overlap a 1 hour bucket, so look for completely empty buckets, etc. These scans can be done with SIMD.

When candidate buckets are found, use the start timestamp of the bucket (i*1hr) to jump into map and start scanning the map there, up to the end of the possible range of buckets. The index can confidently skip too full regions but doesn't guarantee there's a contiguous slot of the right size. I don't have a great sense of how much this would filter out in practice, but maybe there's some tuning of the parameters here that works for your case.

Updates should be relatively cheap since the ranges don't overlap, just +/- the duration of each booking added/removed. But it would have to deal with bookings that overlap multiple buckets. But, the logic is just arithmetic on newly inserted/deleted values which are already in registers at least, rather than scanning parts of the map, e.g. if you wanted to maintain the min/max value in each bucket and support deletes.

[Terr_]

> Maybe an additional "lower resolution" index on top of the map could help as a heuristic to skip whole regions

That sounds a bit like circling back around to a tree-based system (albeit with depth=2) where each parent is somehow summarizing the state of child nodes below it.

[SnowflakeOnIce]

If your ranges end up sparsely distributed, using roaring bitmaps can speed things up a lot.

https://roaringbitmap.org/