Reading through your other responses, I'm gathering your requirements are something like a throughput of 300 clock cycles per query, working with thousands of items in the data structure. Details are necessary for specific recommendations, but here are a few observations which might be applicable here or elsewhere.
- If you're only querying one of these things frequently, just do something better than a linear scan and ensure the backing memory is contiguous. It'll fit in the L1 cache and be fast enough.
- If you're querying hundreds of thousands of these (e.g., checking different pieces of equipment?), don't do that. Go up one level of abstraction so that you don't have to do hundreds of thousands of queries. Going to the equipment example, some of that equipment will be equivalent for a given query (maybe all of it, maybe each piece is truly unique for a given application, but for any incoming query there exists a category describing which subset of the equipment you care about). The simplest thing that could possibly work is if you have a low enough category count that you can just have an ordered multiset of available intervals for each category, with some auxilliary data for the bookkeeping on mutations. Any time you're looking at hundreds of thousands of disjiont things in a loop though, that's suggestive of the wrong level of abstraction (from a performance perspective). Even throwing it into in-memory sqlite with a multi-column index is probably better.
- It's almost always worth looking at your desired performance for each possible action on a data structure. E.g., I'm imagining "insert 1" is an atomic thing you don't want to feel laggy to the user, same with "delete 1", and same with "query all." If that's a good enough approximation of your requirements then it buys you a boatload of flexibility since you can move work from query time (which, if you have to do a linear scan of subsets of 100k biggish things is going to be pushing uncumfortably close to the limits of random-access main memory loads no matter which data structure you choose) to mutation time. You can linearly scan the entire L1 cache a thousand times in 10ms, which is a lot of budget to compact a data structure, duplicate its indices hierarchially, or otherwise manipulate the data to make queries faster.
- You can make that idea more flexible with some sort of "deferred maintenance" approach. E.g., if you're inserting `n` things, you can almost certainly afford to defer maintenance till after they're all inserted, hopefully saving some work if a few of those were in the same structure. E.g., if the only maintenance you're doing is compaction for cache reasons, you can maintain a counter of how many inserts have happened (or how slow recent queries were), and the next insert once the scale is tipped will be the one to actually do that maintenance -- allowing a simple strategy of blindly rebuilding these things every time to actually scale to reasonable volumes of bulk inserts within a 10ms window (to keep users from noticing lag).
- You gain a lot of power by your intervals being disjoint. You gain more if they're never adjacent (i.e., a booked block is always an endpoint in the data structure or bounded by unbooked blocks, and vice versa). Representing contiguous blocks of bookings as a single unit referencing the actual blocks (that unit could be some sort of balanced tree if you want, easy to split in half on deletions, just hold a pointer to it and its endpoints though and basically never peek into the details till you decide to actually render that contiguous block as being comprised of its parts).
All great points, thank you! I'll need to think about this some more.
For context, queries are trying to find the next available equipment for tens of thousands of tasks, so hundreds of thousands of queries isn't too bad relative the to the amount of tasks. Equipment candidates are matched based on their capabilities (some equipment might support A or B, while others support B or C) and tasks might require certain combinations. This might complicate the multiset slightly but it seems like a good idea.
The ordered map I'm currently using handles adjacent available intervals by automatically coalescing them together, so I'm definitely taking advantage of that.
Yeah, so with capabilities, the naive idea of "categories" might or might not make sense. It depends how much duplication you get (how many pieces of equipment have large counts of capabilities). Most real-world scenarios I've seen only have 2-10 capabilities per piece of equipment though, which makes the simplest, dumbest solution work in the real world (anything fancier pushes closer to the database literature, and there are good solutions, but you hopefully don't have to care).
tens of thousands of tasks
Am I misinterpreting, or are you saying that you have tens of thousands of queries and a much lower equipment count? That enables all kinds of solutions. Even on a single machine, multi-thread it. For deletions and insertions, use something like bounded-wait hazard pointers [0] with a bias toward cheap reads. If you have concurrent tasks, horizontal scaling is the name of the game. 10 microseconds is an easy baseline for intra-datacenter networking, easily allowing 10 millisecond reads and mutations even with a distributed solution.
Related, simply caching results might get you the performance you want on a single core if you only have hundreds of pieces of equipment you're searching each time. For each capability, just record the last time you mutated it. You can re-use any query result whose associated results don't have potential mutations. Especially if writes are much less frequent than reads, and especially if you have a bias toward not handing out equipment with all possible capabilities when something cheaper would suffice, most of the time you never have to hit the raw data structure, allowing a single core to handle a much higher query load even with worse data structures.
Multi-threading would be really nice, although it's not clear to me how to parallelize this in a way where the synchronization cost wouldn't regress performance. Tasks are prioritized, so each booking happens in sequence (i.e., each task needs to know where the higher priority tasks ended up being placed). There are cases where it's possible to determine whether they might be fully isolated (e.g., if one booking couldn't possibly affect another) to run those in parallel, but sometimes determining that might be non-trivial too.
I have been experimenting with a few caching approaches, but the caches tend to be invalidated so often that they didn't seem to help much yet. Some of the coarser-grained caches mentioned in some of the other comments could be interesting though, as a way to quickly skip over entire regions when the remaining availability intervals are too short for typical queries.
This is one of those places where the details matter a ton. E.g. low contention hazard pointers are nearly free (under 10 clock cycles per read), and if writes are less common than reads (seems likely? you present 10-100 reads for available equipment before somebody chooses 1 or 0 of the available options) you'll barely notice the overhead. Synchronization only gets expensive when you have contention.
Examining the problem of allocating equipment, how often do you actually have contended writes on the same piece of equipment? If it's very often, presumably the top few matches are nearly interchangeable (or, even if they aren't, milliseconds separate who wins the non-interchangeable equipment, and from a user's perspective if you're not running a stock exchange they don't know if they didn't win because the equipment wasn't available or because you have a few milliseconds of fuzz behind the scenes). Can you tweak the business requirements and uniformly choose from the top k matches when displaying results to readers to artificially reduce contention?
Adding onto one of the previous ideas, even if tasks are prioritized, if outside parties don't communicate those priorities there isn't much practical difference over the span of a few milliseconds between low and high priority tasks. Sure, if a high priority task has been waiting longer than a few milliseconds you can prioritize it over low priority tasks, but you have a few milliseconds of slop available to quickly execute a "maybe wrong" solution and increase system throughput.
caching doesn't work
That happens. It's almost always possible to construct malicious workloads against any caching strategy. If your real workload isn't very cachable, that's annoying, but it's fine.
Did you happen to measure the relative performance of a cache hit vs a cache miss? Your perf budget is fairly tight, and I'd be curious to know if the lack of improvement is because the caches aren't optimized or because the misses reduce the gains.
Comments
Reading through your other responses, I'm gathering your requirements are something like a throughput of 300 clock cycles per query, working with thousands of items in the data structure. Details are necessary for specific recommendations, but here are a few observations which might be applicable here or elsewhere.
- If you're only querying one of these things frequently, just do something better than a linear scan and ensure the backing memory is contiguous. It'll fit in the L1 cache and be fast enough.
- If you're querying hundreds of thousands of these (e.g., checking different pieces of equipment?), don't do that. Go up one level of abstraction so that you don't have to do hundreds of thousands of queries. Going to the equipment example, some of that equipment will be equivalent for a given query (maybe all of it, maybe each piece is truly unique for a given application, but for any incoming query there exists a category describing which subset of the equipment you care about). The simplest thing that could possibly work is if you have a low enough category count that you can just have an ordered multiset of available intervals for each category, with some auxilliary data for the bookkeeping on mutations. Any time you're looking at hundreds of thousands of disjiont things in a loop though, that's suggestive of the wrong level of abstraction (from a performance perspective). Even throwing it into in-memory sqlite with a multi-column index is probably better.
- It's almost always worth looking at your desired performance for each possible action on a data structure. E.g., I'm imagining "insert 1" is an atomic thing you don't want to feel laggy to the user, same with "delete 1", and same with "query all." If that's a good enough approximation of your requirements then it buys you a boatload of flexibility since you can move work from query time (which, if you have to do a linear scan of subsets of 100k biggish things is going to be pushing uncumfortably close to the limits of random-access main memory loads no matter which data structure you choose) to mutation time. You can linearly scan the entire L1 cache a thousand times in 10ms, which is a lot of budget to compact a data structure, duplicate its indices hierarchially, or otherwise manipulate the data to make queries faster.
- You can make that idea more flexible with some sort of "deferred maintenance" approach. E.g., if you're inserting `n` things, you can almost certainly afford to defer maintenance till after they're all inserted, hopefully saving some work if a few of those were in the same structure. E.g., if the only maintenance you're doing is compaction for cache reasons, you can maintain a counter of how many inserts have happened (or how slow recent queries were), and the next insert once the scale is tipped will be the one to actually do that maintenance -- allowing a simple strategy of blindly rebuilding these things every time to actually scale to reasonable volumes of bulk inserts within a 10ms window (to keep users from noticing lag).
- You gain a lot of power by your intervals being disjoint. You gain more if they're never adjacent (i.e., a booked block is always an endpoint in the data structure or bounded by unbooked blocks, and vice versa). Representing contiguous blocks of bookings as a single unit referencing the actual blocks (that unit could be some sort of balanced tree if you want, easy to split in half on deletions, just hold a pointer to it and its endpoints though and basically never peek into the details till you decide to actually render that contiguous block as being comprised of its parts).
All great points, thank you! I'll need to think about this some more.
For context, queries are trying to find the next available equipment for tens of thousands of tasks, so hundreds of thousands of queries isn't too bad relative the to the amount of tasks. Equipment candidates are matched based on their capabilities (some equipment might support A or B, while others support B or C) and tasks might require certain combinations. This might complicate the multiset slightly but it seems like a good idea.
The ordered map I'm currently using handles adjacent available intervals by automatically coalescing them together, so I'm definitely taking advantage of that.
Yeah, so with capabilities, the naive idea of "categories" might or might not make sense. It depends how much duplication you get (how many pieces of equipment have large counts of capabilities). Most real-world scenarios I've seen only have 2-10 capabilities per piece of equipment though, which makes the simplest, dumbest solution work in the real world (anything fancier pushes closer to the database literature, and there are good solutions, but you hopefully don't have to care).
Am I misinterpreting, or are you saying that you have tens of thousands of queries and a much lower equipment count? That enables all kinds of solutions. Even on a single machine, multi-thread it. For deletions and insertions, use something like bounded-wait hazard pointers [0] with a bias toward cheap reads. If you have concurrent tasks, horizontal scaling is the name of the game. 10 microseconds is an easy baseline for intra-datacenter networking, easily allowing 10 millisecond reads and mutations even with a distributed solution.
Related, simply caching results might get you the performance you want on a single core if you only have hundreds of pieces of equipment you're searching each time. For each capability, just record the last time you mutated it. You can re-use any query result whose associated results don't have potential mutations. Especially if writes are much less frequent than reads, and especially if you have a bias toward not handing out equipment with all possible capabilities when something cheaper would suffice, most of the time you never have to hit the raw data structure, allowing a single core to handle a much higher query load even with worse data structures.
[0] a decent walkthrough: https://pvk.ca/Blog/2020/07/07/flatter-wait-free-hazard-poin...
Multi-threading would be really nice, although it's not clear to me how to parallelize this in a way where the synchronization cost wouldn't regress performance. Tasks are prioritized, so each booking happens in sequence (i.e., each task needs to know where the higher priority tasks ended up being placed). There are cases where it's possible to determine whether they might be fully isolated (e.g., if one booking couldn't possibly affect another) to run those in parallel, but sometimes determining that might be non-trivial too.
I have been experimenting with a few caching approaches, but the caches tend to be invalidated so often that they didn't seem to help much yet. Some of the coarser-grained caches mentioned in some of the other comments could be interesting though, as a way to quickly skip over entire regions when the remaining availability intervals are too short for typical queries.
This is one of those places where the details matter a ton. E.g. low contention hazard pointers are nearly free (under 10 clock cycles per read), and if writes are less common than reads (seems likely? you present 10-100 reads for available equipment before somebody chooses 1 or 0 of the available options) you'll barely notice the overhead. Synchronization only gets expensive when you have contention.
Examining the problem of allocating equipment, how often do you actually have contended writes on the same piece of equipment? If it's very often, presumably the top few matches are nearly interchangeable (or, even if they aren't, milliseconds separate who wins the non-interchangeable equipment, and from a user's perspective if you're not running a stock exchange they don't know if they didn't win because the equipment wasn't available or because you have a few milliseconds of fuzz behind the scenes). Can you tweak the business requirements and uniformly choose from the top k matches when displaying results to readers to artificially reduce contention?
Adding onto one of the previous ideas, even if tasks are prioritized, if outside parties don't communicate those priorities there isn't much practical difference over the span of a few milliseconds between low and high priority tasks. Sure, if a high priority task has been waiting longer than a few milliseconds you can prioritize it over low priority tasks, but you have a few milliseconds of slop available to quickly execute a "maybe wrong" solution and increase system throughput.
That happens. It's almost always possible to construct malicious workloads against any caching strategy. If your real workload isn't very cachable, that's annoying, but it's fine.
Did you happen to measure the relative performance of a cache hit vs a cache miss? Your perf budget is fairly tight, and I'd be curious to know if the lack of improvement is because the caches aren't optimized or because the misses reduce the gains.