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.
hansvm|1 year ago
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.