4 ms·

CoroBase: Database engine using C++20 coroutines to hide cache misses

49 points by matt_d 6y ago

Const-me 6y ago
Nice idea. If anyone is interested how the hell that works despite CPUs expose no instructions to handle cache misses in explicit way, here’s a quote from the linked article. To access data (e.g., a tree node) in request t1 which may incur a cache miss, the thread issues a prefetch and switches to another request t2, and repeats this process. While the data needed by t1 is being fetched from memory to CPU cache, the worker thread handles t2, which may further cause the thread to issue prefetch and switch to another request. By the time the worker thread switches back to t1, the hope is that the needed data is (already and still) cache-resident. The thread then picks up at where it left for t1, dereferences the pointer to the prefetched data and continues executing t1 until the next possible cache miss upon which a prefetch will be issued. It is important that the switching mechanism and representation of requests are cheap and lightweight enough to achieve a net gain.
- brooksbp 6y ago
  Even if you know which accesses have a high probability of missing in core or chip cache, it is tricky to write portable software that takes advantage of (switches/branches to other work) the time it takes between prefetch and data available in L1. It is not just architecture specific, or microarchitecture specific, it's chip specific.
  - Const-me 6y ago
    Not sure I understand your comment. Many things may go wrong, interference from another hardware thread running on the same core, context switches, cache associativity shenanigans, and more. But still, if you prefetch, switch a co-routine so that other one is spending their 100-500 CPU cycles doing something else, then switch back — I would expect statistically significant performance win, at the cost of code complexity.
- lainga 6y ago
  I wonder if such explicit cache manipulation instructions will ever make their way into an x86_64 extension.
  - Const-me 6y ago
    I know 2 related instructions, prefetch used by the OP, and clflush to flush a line. AFAIK there’s no way to query cache state for an address. With these recent spectre/meltdown/etc, I wouldn’t expect to see an instruction to query cache state for an address, at least in a foreseeable future. An easy implementation probably gonna be a side channel attack vector.
    - PoignardAzur 6y ago
      Afaik the clflush instruction isn't really meant for optimization. It evinces data from all cache levels (so even from L3), which means it's only useful for data you know you won't ever need again. I think the CPU is good enough at flushing that data that additional hints won't improve performance much.
  - PoignardAzur 6y ago
    The instruction this is based on is prefetch; which is essentially the only relevant instruction when doing manual cache optimization on x86/x64. It's not a panacea though; naive usage of prefetch will actually decrease performance [0], because the hardware already does a lot of prefetching on its own and you're messing with that. From what little research I've done, prefetch mostly improves performance when accessing data in a hot loop, in a non-linear pattern (eg nextAddress isn't just prevAdress + constantValue), 3-4 loop iterations ahead of the execution. Eg doThings(myArrayOfPointers[i]); __builtin_prefetch(myArrayOfPointers[i + 4]); (though the above code might be undefined behavior if i + 4 is bigger than the array size, I'm not sure) [0]: https://lwn.net/Articles/444336/ https://lwn.net/Articles/444336/
riyadparvez 6y ago
> CoroBase is a research database engine that models transactions as C++20 stackless coroutine to hide CPU cache misses. Can someone please explain that this means? I am really curious to know.
- scott_s 6y ago
  Their research paper explains the work: https://arxiv.org/pdf/2010.15981.pdf https://arxiv.org/pdf/2010.15981.pdf
- deleted 6y ago
  [deleted]
- stingraycharles 6y ago
  The gist is that C++ coroutines’ context switches are cheaper than cache misses. Hence, if you can write coroutines that fill the caches more intelligently than that the hardware prefetcher can do (because you know more about what your application is trying to achieve), you can outperform the hardware prefetcher. You write a whole lot of coroutines that fill caches, suspend them while they do it, and once they are resumed, you can assume that the caches are now filled with your data and have just achieved better efficiency. Hope this was a clear enough explanation, and someone correct me if I’m wrong.
  - qppo 6y ago
    Not an expert here but I think there's a non trivial detail to your gist, which is that (user space) context switches can be faster than cache misses, and you can design a scheduler that knows enough about its coroutines to switch to a new context with a low probability of a cache miss.
jandrewrogers 6y ago
Pervasive end-to-end hiding of memory cache misses using coroutines is a standard architectural feature of some database engines. It follows naturally from I/O latency hiding; systems designed like the paper suggests are well over a decade old in industry. However, the devil is in the details of the scheduler design when it comes to making the performance benefits robust in real systems. The scheduler design is non-trivial because it is an inference engine that feeds back into the thing it is making inferences about, and there are temporal locality optimizations well-worth doing aside from hiding cache misses. A naive scheduler, like round-robin, can inadvertently cause the thing it prefetched to be evicted under real workloads. There are many examples of how a cache miss hiding design can suddenly turn into a cache miss creating design when the workload patterns shift modestly. At the same time, the scheduling logic, which is theoretically hard, needs to be simple enough that the cost is worth it. And you also need to manage tail latencies in real designs; robust and highly optimal schedulers in terms of aggregate throughput have a tendency to have high worst-case scheduling latencies. The tradeoff space is very complex and interacts with real design constraints in subtle ways. Even if you address all of that in the scheduler design, the efficacy of these optimizations are sensitive to the physical architecture of the CPU cache, which varies widely. The scheduling algorithms are implicitly making assumptions about the design and specification of the target silicon. tl;dr: This is a mature database technique with real benefits but robust real-world implementations are expensive to design. The code is simple, the cost is in being forced to think through the implications and edge cases so that your execution schedule doesn't get stuck in a pathological equilibrium.
- Const-me 6y ago
  They are different caches. The database engines you’re talking about do that for pages not found in RAM, which need to be read from disk. This article is about accessing data that’s already present in system memory. The caches they are talking about are on-chip ones, i.e. L1D and L2 caches inside CPU cores, and L3 cache shared across cores but still located on the same CPU die. Some rare CPUs like in my old laptop with Core i3-6157U even have L4 on-chip cache made of DRAM.
  - jandrewrogers 6y ago
PoignardAzur 6y ago
Huh. From the description, it sounds like CoroBase is essentially doing hyperthreading, except at the software level? Interesting. From the paper's results, it also looks a lot more effective than most brute force prefetch optimizations usually are.
- jandrewrogers 6y ago
  What the paper describes is roughly a software implementation of the Cray MTA[1] supercomputing architecture -- each CPU had 128 threads per core. The ill-fated Cray XMT was the inspiration for applying this technique to databases on arbitrary CPU architectures many years ago. I once emulated the exotic XMT threading behavior and memory model in software on x86 using coroutines, which had the advantage of not requiring me to shell into the supercomputer to test my code -- developer convenience. It turned out that the XMT idiomatic C++, which is strange looking and normally runs poorly on ordinary CPUs, ran faster on this emulator on x86 than the actual XMT CPU. While the XMT CPUs had unusual architectural features that could not be emulated in software (e.g. the XMT CPU knows precisely which threads are stalled on a per clock cycle basis), x86 silicon was so much more advanced at the time that naively scheduling around stalls by inference had higher performance even after the occasional cache miss. Furthermore, this way of designing code greatly improved performance on x86-based supercomputers compared to more conventional multithreading. It changed the way we designed the software At the time, there were a few people straddling the supercomputing and database worlds, which was how the "software XMT architecture" discovery bled over into database engine design. It is more difficult to do robustly in software but it worked really well and you can't beat the cost. [1] https://en.wikipedia.org/wiki/Cray_MTA https://en.wikipedia.org/wiki/Cray_MTA
seertaak 6y ago
Of relevance: Gor Nishanov, "C++ Coroutines: a negative overhead abstraction" https://www.youtube.com/watch?v=_fu0gx-xseY https://www.youtube.com/watch?v=_fu0gx-xseY
ncmncm 6y ago
Use of instructions that compilers have great difficulty (usefully) generating, for various reasons, is a common theme lately. In this case, prefetch, which to be useful often requires a context switch. Another, lately, is popcount. One that only appears in very recent Intel (and AMD?) is an instruction to sleep until a particular cache line gets invalidated, as a way to both save on power and latency, as waking up can be faster than escaping the poorly-branch-predicted spin loop. There are various appalling tricks to keep your branch predictor from killing your loop escape latency.

49 points by matt_d 6y ago

Nice idea. If anyone is interested how the hell that works despite CPUs expose no instructions to handle cache misses in explicit way, here’s a quote from the linked article. To access data (e.g., a tree node) in request t1 which may incur a cache miss, the thread issues a prefetch and switches to another request t2, and repeats this process. While the data needed by t1 is being fetched from memory to CPU cache, the worker thread handles t2, which may further cause the thread to issue prefetch and switch to another request. By the time the worker thread switches back to t1, the hope is that the needed data is (already and still) cache-resident. The thread then picks up at where it left for t1, dereferences the pointer to the prefetched data and continues executing t1 until the next possible cache miss upon which a prefetch will be issued. It is important that the switching mechanism and representation of requests are cheap and lightweight enough to achieve a net gain.

brooksbp 6y ago
Even if you know which accesses have a high probability of missing in core or chip cache, it is tricky to write portable software that takes advantage of (switches/branches to other work) the time it takes between prefetch and data available in L1. It is not just architecture specific, or microarchitecture specific, it's chip specific.
- Const-me 6y ago
  Not sure I understand your comment. Many things may go wrong, interference from another hardware thread running on the same core, context switches, cache associativity shenanigans, and more. But still, if you prefetch, switch a co-routine so that other one is spending their 100-500 CPU cycles doing something else, then switch back — I would expect statistically significant performance win, at the cost of code complexity.
lainga 6y ago
I wonder if such explicit cache manipulation instructions will ever make their way into an x86_64 extension.
- Const-me 6y ago
  I know 2 related instructions, prefetch used by the OP, and clflush to flush a line. AFAIK there’s no way to query cache state for an address. With these recent spectre/meltdown/etc, I wouldn’t expect to see an instruction to query cache state for an address, at least in a foreseeable future. An easy implementation probably gonna be a side channel attack vector.
  - PoignardAzur 6y ago
    Afaik the clflush instruction isn't really meant for optimization. It evinces data from all cache levels (so even from L3), which means it's only useful for data you know you won't ever need again. I think the CPU is good enough at flushing that data that additional hints won't improve performance much.
- PoignardAzur 6y ago
  The instruction this is based on is prefetch; which is essentially the only relevant instruction when doing manual cache optimization on x86/x64. It's not a panacea though; naive usage of prefetch will actually decrease performance [0], because the hardware already does a lot of prefetching on its own and you're messing with that. From what little research I've done, prefetch mostly improves performance when accessing data in a hot loop, in a non-linear pattern (eg nextAddress isn't just prevAdress + constantValue), 3-4 loop iterations ahead of the execution. Eg doThings(myArrayOfPointers[i]); __builtin_prefetch(myArrayOfPointers[i + 4]); (though the above code might be undefined behavior if i + 4 is bigger than the array size, I'm not sure) [0]: https://lwn.net/Articles/444336/ https://lwn.net/Articles/444336/

riyadparvez 6y ago

> CoroBase is a research database engine that models transactions as C++20 stackless coroutine to hide CPU cache misses. Can someone please explain that this means? I am really curious to know.

scott_s 6y ago
Their research paper explains the work: https://arxiv.org/pdf/2010.15981.pdf https://arxiv.org/pdf/2010.15981.pdf
deleted 6y ago
[deleted]
stingraycharles 6y ago
The gist is that C++ coroutines’ context switches are cheaper than cache misses. Hence, if you can write coroutines that fill the caches more intelligently than that the hardware prefetcher can do (because you know more about what your application is trying to achieve), you can outperform the hardware prefetcher. You write a whole lot of coroutines that fill caches, suspend them while they do it, and once they are resumed, you can assume that the caches are now filled with your data and have just achieved better efficiency. Hope this was a clear enough explanation, and someone correct me if I’m wrong.
- qppo 6y ago
  Not an expert here but I think there's a non trivial detail to your gist, which is that (user space) context switches can be faster than cache misses, and you can design a scheduler that knows enough about its coroutines to switch to a new context with a low probability of a cache miss.

jandrewrogers 6y ago

Pervasive end-to-end hiding of memory cache misses using coroutines is a standard architectural feature of some database engines. It follows naturally from I/O latency hiding; systems designed like the paper suggests are well over a decade old in industry. However, the devil is in the details of the scheduler design when it comes to making the performance benefits robust in real systems. The scheduler design is non-trivial because it is an inference engine that feeds back into the thing it is making inferences about, and there are temporal locality optimizations well-worth doing aside from hiding cache misses. A naive scheduler, like round-robin, can inadvertently cause the thing it prefetched to be evicted under real workloads. There are many examples of how a cache miss hiding design can suddenly turn into a cache miss creating design when the workload patterns shift modestly. At the same time, the scheduling logic, which is theoretically hard, needs to be simple enough that the cost is worth it. And you also need to manage tail latencies in real designs; robust and highly optimal schedulers in terms of aggregate throughput have a tendency to have high worst-case scheduling latencies. The tradeoff space is very complex and interacts with real design constraints in subtle ways. Even if you address all of that in the scheduler design, the efficacy of these optimizations are sensitive to the physical architecture of the CPU cache, which varies widely. The scheduling algorithms are implicitly making assumptions about the design and specification of the target silicon. tl;dr: This is a mature database technique with real benefits but robust real-world implementations are expensive to design. The code is simple, the cost is in being forced to think through the implications and edge cases so that your execution schedule doesn't get stuck in a pathological equilibrium.

Const-me 6y ago
They are different caches. The database engines you’re talking about do that for pages not found in RAM, which need to be read from disk. This article is about accessing data that’s already present in system memory. The caches they are talking about are on-chip ones, i.e. L1D and L2 caches inside CPU cores, and L3 cache shared across cores but still located on the same CPU die. Some rare CPUs like in my old laptop with Core i3-6157U even have L4 on-chip cache made of DRAM.
- jandrewrogers 6y ago

PoignardAzur 6y ago

Huh. From the description, it sounds like CoroBase is essentially doing hyperthreading, except at the software level? Interesting. From the paper's results, it also looks a lot more effective than most brute force prefetch optimizations usually are.

jandrewrogers 6y ago
What the paper describes is roughly a software implementation of the Cray MTA[1] supercomputing architecture -- each CPU had 128 threads per core. The ill-fated Cray XMT was the inspiration for applying this technique to databases on arbitrary CPU architectures many years ago. I once emulated the exotic XMT threading behavior and memory model in software on x86 using coroutines, which had the advantage of not requiring me to shell into the supercomputer to test my code -- developer convenience. It turned out that the XMT idiomatic C++, which is strange looking and normally runs poorly on ordinary CPUs, ran faster on this emulator on x86 than the actual XMT CPU. While the XMT CPUs had unusual architectural features that could not be emulated in software (e.g. the XMT CPU knows precisely which threads are stalled on a per clock cycle basis), x86 silicon was so much more advanced at the time that naively scheduling around stalls by inference had higher performance even after the occasional cache miss. Furthermore, this way of designing code greatly improved performance on x86-based supercomputers compared to more conventional multithreading. It changed the way we designed the software At the time, there were a few people straddling the supercomputing and database worlds, which was how the "software XMT architecture" discovery bled over into database engine design. It is more difficult to do robustly in software but it worked really well and you can't beat the cost. [1] https://en.wikipedia.org/wiki/Cray_MTA https://en.wikipedia.org/wiki/Cray_MTA

seertaak 6y ago

Of relevance: Gor Nishanov, "C++ Coroutines: a negative overhead abstraction" https://www.youtube.com/watch?v=_fu0gx-xseY https://www.youtube.com/watch?v=_fu0gx-xseY

ncmncm 6y ago

Use of instructions that compilers have great difficulty (usefully) generating, for various reasons, is a common theme lately. In this case, prefetch, which to be useful often requires a context switch. Another, lately, is popcount. One that only appears in very recent Intel (and AMD?) is an instruction to sleep until a particular cache line gets invalidated, as a way to both save on power and latency, as waking up can be faster than escaping the poorly-branch-predicted spin loop. There are various appalling tricks to keep your branch predictor from killing your loop escape latency.