Nishanov Beats Hand-Rolled Code With C++ Coroutines to Cut Memory Stalls

Nishanov使用C++协程超越手写代码以减少内存停顿 利用C++纳秒级协程交错执行批量内存查找可掩盖DRAM延迟，且性能优于手写状态机，因为编译器驱动的降级保留了标准优化通道，从而避免了寄存器溢出。 针对随机内存表查找导致CPU执行停顿60纳秒的内存延迟墙问题，Gor Nishanov展示了一种名为软件超线程的技术，该技术利用硬件预取提示来交错执行独立的搜索操作。虽然手写状态机可以通过交错任务来掩盖这种延迟，但会引入极高的代码复杂度和寄存器压力；相比之下，无栈纳秒级协程允许编译器在对函数体进行降级之前先对其进行优化，从而比原始基准提升了3.5倍的速度。Nishanov详细介绍了如何构建自定义非临时预取awaitable、并发限制节流器以及避免调度器开销的对称传输，同时解释了协程如何在有栈fiber失效的情况下安全处理线程局部存储和线程迁移。 使用Coroutines TS纳秒级协程交错执行独立的内存查找，将大型数据集上的二分搜索延迟从每步26纳秒降低至约7.4纳秒，实现了近3.5倍的加速。 (38:15) 编译器生成的协程状态机击败了手动编写的C语言风格状态机（7.4纳秒对比10纳秒），因为优化器可以在将标准函数降级切分之前对其运行完整的优化通道。 (40:51) 与fiber或操作系统线程不同，C++协程的切换成本低于纳秒级，并使挂起点显式化，从而防止了跨迁移时线程局部存储（TLS）出现的编译器寄存器缓存问题。 (54:01) 通过协程实现的软件超线程将非临时预取指令（PREFETCHNTA）与对称传输相结合，消除了调度器开销并避免逐出已缓存的数据库有效载荷。 (30:04)

Gor Nishanov argues that C++ Coroutines TS can implement software hyper-threading via "nano-coroutines" to hide hardware memory latency in batch database lookups. This design yields a negative-overhead abstraction that outperforms handcrafted C-style state machines. The Memory Wall and Software Hyper-Threading (8:14) In large database queries such as joins, index lookups land at random memory locations across gigabyte-scale datasets, completely bypassing CPU caches. While sequential scans benefit from hardware prefetching, random access forces the processor to stall for approximately 60 nanoseconds per main-memory access. Nishanov notes that when a working set reaches 256 MB on a quad-core test laptop, binary search throughput collapses to 0.21 instructions per cycle, roughly one-twentieth of theoretical peak performance. Because a 60-nanosecond stall is too brief for an operating system thread context switch—which requires roughly half a microsecond—and hardware hyper-threading only provides two threads per core, the execution core sits idle. To bridge this gap without blocking the CPU, developers can interleave multiple concurrent lookups in software. By dispatching explicit hardware prefetch instructions (such as `PREFETCHNTA` to bypass L2 and L3 caches and avoid polluting resident data) and immediately switching to another search stream while the memory line is fetched, the CPU can overlap waiting periods with productive work. This approach cannot accelerate an isolated binary search due to sequential data dependencies, but it dramatically boosts throughput for large batches. Compiler-Driven Optimization Beats Handcrafted State Machines (16:22) Manually implementing software hyper-threading requires converting binary search into an explicit state machine by splitting logic into `init()` and `run()` functions, saving local variables (`first`, `last`, `middle`, `length`, `value`) across suspension points into custom frames, and driving them in a round-robin loop. While a handcrafted state machine interleaving 16 streams dropped normalized lookup latency from 26 nanoseconds down to 10 nanoseconds, Nishanov cautions that the resulting code is fragile, difficult to maintain, and exhibits severe register pressure caused by premature lowering. Rewriting the lookup as a C++ coroutine that `co_await`s a prefetch intrinsic lowered execution time further to roughly 7.4 nanoseconds with 20 interleaved streams—an overall 3.5x speedup over baseline. Nishanov explains this "negative overhead abstraction" by inspecting compiler pipelines in MSVC, Clang, and GCC. When written as a coroutine, the compiler treats the code as a standard function for as long as possible, executing standard optimization passes (inlining, constant propagation, dead-code elimination) before lowering it into a state machine. Handcrafted state machines force explicit branching and frame storage too early, impeding the optimizer and generating suboptimal assembly with heavy register spilling. Nano-Coroutine Architecture and Symmetric Transfer (27:31) Adapting coroutines to sub-nanosecond switching requires deliberate runtime engineering. Nishanov treats each lookup as an asynchronous task awaiting high-latency memory. To prevent overwhelming system queues when executing millions of lookups, a throttler bounds active concurrency using a fork-join model. The prefetch awaitable unconditionally returns `false` from `await_ready()` because x86 prefetch instructions do not report cache status, forcing an immediate suspension that issues the prefetch intrinsic. To eliminate scheduler overhead, the implementation relies on symmetric transfer: returning a `coroutine_handle` directly from `await_suspend` enables direct coroutine-to-coroutine jumps, avoiding an outer centralized queue loop that otherwise added three CPU cycles (roughly 0.75 nanoseconds). Frame allocations are further optimized by overriding `operator new` and `operator delete` on the coroutine promise with a custom recycling allocator, and setting `final_suspend` to `suspend_never` so coroutines self-destroy immediately upon task completion. Standardization, Tooling, and Migration Safety (43:44) Addressing ecosystem integration, Nishanov highlights that C++ coroutines have a sub-nanosecond switching overhead, compared to 10 to 50 nanoseconds for stackful fibers. Unlike fibers, stackless coroutines expose explicit suspension boundaries to the compiler. This prevents architectures like ARM from caching thread-local storage (TLS) register pointers across suspension points, eliminating memory corruption risks during cross-thread migration. Nishanov notes that while coroutines interoperate cleanly with executors and the forthcoming Networking TS, they remain fully decoupled from mandatory runtimes. At the time of the presentation, the Coroutines TS was targeted for C++20, with support existing in Clang and MSVC and active development underway in GCC via a Facebook-sponsored engineer. Standard library types like `std::task` and `std::generator` were slated for standardization committee review. On hardware tuning, Nishanov noted that optimal interleaving depth currently requires empirical calibration because current CPU instruction sets lack mechanisms to report prefetch queue saturation dynamically. Nano-coroutines demonstrate that modern compiler-driven coroutine transformations can outperform human-crafted state machines even in extreme, latency-sensitive domains. However, practical deployment requires careful consideration of recycling allocators and machine-specific interleave tuning until future CPU hardware surfaces dynamic prefetcher queue metrics.

Gor Nishanov 阐述了如何利用 C++ Coroutines TS（无栈协程）实现“软件超线程”，通过将内存预取转化为纳秒级任务切换，有效隐藏数据库批量检索中的缓存缺失停顿，并证实编译器自动优化的协程状态机在吞吐性能上优于手写代码。 内存墙与软件超线程机制 (8:14) 在现代计算体系中，内存检索延迟与 CPU 缓存容量存在严重的物理失配。Nishanov 指出，当二分查找的工作集超出 8 MB 的 L3 缓存并扩展至 256 MB 主存时，每次缓存缺失需要约 60 纳秒的检索延迟，使理论上每周期可执行 4 条指令的处理器核心实际 IPC 骤降至 0.21。单次查找的链式依赖无法通过硬件消除，但在数据库连接等批量执行数万至数百万次查找的场景下，核心可以通过“软件超线程”在等待内存加载期间交替执行其他任务。 由于操作系统线程上下文切换耗时达半微秒以上，光靠两路硬件超线程也会在两次内存停顿间迅速卡死，因此必须在微秒以下的极小粒度调度。通过调用处理器提供的硬件预取指令（如避免污染各级缓存的 `PREFETCHNTA` 指令），程序能够在需要读取数据前向 CPU 发出预取信号，并在等待数据从内存送抵核心的 60 纳秒窗口期内，将执行流切换至其他检索流，从而用有用的比较计算完全填满总线等待周期。 手写状态机缺陷与协程转化 (16:22) 为了在同一执行线程内交替驱动多个查找流，开发人员通常需要手动提取函数的局部变量（如 `first`、`last`、`middle`、`length` 等），将其打包到持久化的帧结构中，并拆分为负责触发预取的 `init()` 和负责读取比较的 `run()` 函数。基准测试显示，在交织驱动 16 个并发帧时，手写状态机相比朴素二分查找（每次查找约 26 纳秒）获得了 2.5 倍的速度提升，将单步耗时降至 10 纳秒。然而，手工维护此类代码极其繁琐，且复杂的显式分支导致寄存器严重溢出，限制了更复杂算法的拓展。 将该模式改写为 C++ 纳秒级协程（Nano-coroutines）仅需极小的语法改动。由于协程切换开销低于 1 纳秒，这种将内存访问视作高延迟 I/O 的模式与异步网络任务高度相似。开发人员只需把内存解引用替换为针对地址的 `co_await prefetch(address)`，并将函数返回类型替换为专用的协程根任务，即可交由编译器自动管理执行帧与挂起状态。 对称传输与节流调度器架构 (27:31) 为了构建高效的协程执行管线，系统引入了类似 Fork-Join 模型的节流器（Throttler）组件。该组件设置并发上限，仅向 CPU 内存队列分发刚好能够饱和预取流水线的任务数量，并在任务完成时回收执行帧，防止针对百万级查询一次性分配过多协程。此外，自定义任务 Promise 类型通过重写 `operator new` 与 `operator delete` 构建回收分配器，规避通用堆分配耗时；其 `final_suspend` 返回 `suspend_never`，使任务在通知节流器完成后能自毁回收。 在等待体（Awaitable）的调度设计中，`prefetch` 类型在构造时保存目标地址引用，其 `await_ready()` 恒定返回 `false` 以强制挂起，因为 x86 预取指令无法即时反馈数据是否在缓存中。为消除中央调度循环带来的 3 个 CPU 周期（约 0.75 纳秒）开销，该方案采用了 Coroutines TS 的对称传输（Symmetric Transfer）机制：`await_suspend` 直接返回待唤醒的下一个 `coroutine_handle`，通过尾调用实现协程之间的直接跳转，彻底去除了外层轮询代码。 负开销抽象与编译器优化优势 (38:15) 基准测试最终呈现了“负开销抽象”的结果：朴素实现每次查找耗时 26 纳秒，16 路并发的手写状态机降至 10 纳秒，而驱动 20 路并发的协程实现则降至约 7.4 纳秒，相较基线实现了 3.5 倍的整体加速，且超越了人工调优的手写状态机。Nishanov 强调，这证明了优秀的语法抽象不仅不会带来性能损失，反而能够产生优于手写汇编或 C 风格状态机的机器码。 汇编分析揭示了协程胜出的根本原因：在 MSVC、Clang 和 GCC 的编译管线中，协程在早期优化阶段仍被视为常规函数，编译器能够先行执行内联、常量折叠、公共子表达式消除及死代码消除；直至逻辑充分简化后，前端才将其降级为状态机切片。相反，人类开发者过早地在源码层拆解了状态机控制流，导致编译器无法有效推导跨状态的变量生存期，引发严重的寄存器换入换出与内存重载。正因编译器生成的协程代码单步指令消耗更少，系统才能够并发交织更多检索流（20 路对比 16 路）以占满总线等待空隙。 无栈协程的线程迁移安全性 (54:01) 针对协程与系统执行模型的关系，Nishanov 阐明协程本身不强行依赖 Executors 或 Networking TS 等基础设施，但能与之良好协同。对于在多线程间迁移任务时普遍遭遇的问题，有栈协程（Fibers）在跨线程调度时极易导致线程局部存储（TLS）损坏：例如在 ARM 架构下，编译器常会将 TLS 页面基址缓存到非易失性寄存器中，隐藏的 Fiber 切换恢复后将读取到陈旧地址，引发内存混乱。 相反，C++ 无栈协程的每个挂起与恢复点（`co_await`）在源码与 AST 级别均对编译器明确可见。由于挂起边界被严格建模，编译器绝不会跨越挂起屏障缓存 TLS 寄存器，从而确保了带魔术静态变量（Magic Statics）、线程缓存分配器或 `std::error_code` 的任务在跨线程迁移时的安全性。 该方案的核心局限在于无法加速单次独立的二分查找，仅适用于利用独立批处理流填补内存流水线的吞吐场景；由于当前 CPU 指令集无法直接探测预取器饱和度或缓存命中状态，最优并发批次仍需依靠静态手工调优或启动自检校准。

[27:31] Gor Nishanov: Frequently I advise when people say, 'Hey, you know, how can I do this with coroutines?' I will say, first think of the best way of solving this problem. Just imagine, imagine the syntax and then you can make it work. [46:03] Gor Nishanov: if you are going for nanoseconds, you better use some good recycling allocator.

[0:00] - So, my name is Gor Nishanov. [0:03] I am a developer in Visual C++ team, [0:06] and one of the thing I work on [0:08] is design and standardization of C++ coroutines. [0:12] Most efficient, most scalable, most open coroutines [0:16] of any programing language in existence. [0:19] And, how many people attended any of the coroutine talks? [0:25] We have about, okay, let's do it the other way around. [0:28] So, we had probably, I think, every CppCon [0:32] there is one or two coroutine talks. [0:34] Who haven't been to any of them? [0:38] Oops, okay. [0:42] This will not be an introduction to coroutine. [0:44] I put a few slides to give a context, [0:46] but this still assumes that you are roughly aware [0:50] how a C++ coroutines work, but don't worry, [0:55] we'll have a few slides to get you up to speed. [0:58] So coroutines is a very, very old abstraction. [1:02] It is a bare function. [1:04] It was invented 60 years ago by Melvin Conway, [1:09] and Knuth gave it a more convenient definition as [1:15] actually, he did the opposite. [1:16] He said that the subroutine is a special case [1:20] of a more general construction, which is a coroutine. [1:24] And if we look at it, coroutines are just like functions [1:29] but better, because they get two more operations. [1:32] Just like normal functions which get call and return, [1:36] coroutines get two more: suspend and resume. [1:39] And in C++ we are roughly getting this, [1:43] or at least in terms of the coroutine TS [1:45] which is currently going through [1:47] the sub-duct-iz-ation process. [1:49] So coroutine is a function which has an await [1:54] or halt expression, or a special form [1:56] of a coreturn statement. [2:00] And one of the common patterns people use [2:03] with coroutines are generators. [2:06] You can think of them as a lazily-produced sequence. [2:11] So in this case I have a hello generator, [2:15] which yields character one at a time. [2:19] And generator, from the perspective [2:20] of the consumer, is just an iterable. [2:23] It has begin and end, you can pass it to arrange base four, [2:29] you can pass it to a standard algorithm, [2:32] and what happens is that when coroutine [2:34] gets to a suspend point, in this case it's yield [2:37] which pushes the value out of the coroutine, [2:40] it gets suspended keeping all of its state intact, [2:43] and then when the main in this case will [2:46] pull the next value we will jump back in [2:49] right where the yield was and keep going. [2:54] Another common pattern with coroutines [2:57] are asynchronous tasks. [2:59] In this case we have some activity which as a [3:02] an iteration, an expression which is not ready yet. [3:06] It could be some lengthy operation like for example [3:09] TCP connection, establishing TCP connection, [3:11] or maybe reading from a socket. [3:14] And instead of blocking the thread, we will suspend [3:18] the coroutine while waiting for the result [3:20] of that operation to become available. [3:24] And once available, coroutine will be resumed [3:26] from the point where it was suspended and will keep going. [3:35] Many languages, about 11 by last count, [3:40] have acquired coroutines of roughly the same same shape [3:45] over the last four years. [3:47] 10 or 11 counting the ones which are [3:50] still in the design phases, and those which already [3:53] shipped the standard with that language. [3:55] It's DART, JavaScript, C#, F#, Python, [4:02] I think now Rust is in process of getting them. [4:05] Swift is getting in the progress, so anyway. [4:07] A lot of languages are getting those facilities. [4:10] What makes C++ coroutines unique is the design principles [4:14] that we established that wanted to guide [4:16] the design of our coroutines. [4:19] So we wanted coroutines to be scalable. [4:21] Not like hey, we will solve 10k problem. [4:24] If you look it up there was this problem, I think, [4:26] it mostly union circulated, it's how many... [4:32] Can you handle 10,000 connections on the same box [4:36] without creating too many threads? [4:38] No, we are talking billions of coroutines. [4:41] So the overhead of every individual coroutine [4:43] is tiny, it's just a few bytes. [4:45] So if you want to you can scale to billions. [4:48] So far I have not seen a very good example [4:52] of an application which uses million coroutines, but... [4:56] We can hope. [4:58] Now coroutines need to be efficient. [5:00] So the overhead of suspend and resume [5:03] is equivalent or roughly on the same order as function call. [5:10] And that actually gives a hint, or at least small hint, [5:15] to you what this talk will be about. [5:17] Because now that coroutines are playing off from the fact [5:21] that the switch between coroutines is less than 1 nanosecond [5:25] And we can do very funny things if that is the case. [5:30] We didn't want to do any funny business [5:33] with stack switching, changing TLS that [5:36] for example fibers do, that put any limit [5:39] on what you can do inside of the coroutine. [5:42] Moreover, coroutines themselves can be passed through [5:45] a C boundary, a boundary as avoid start. [5:49] And then from your third-party library, from an OS call [5:53] in the callback, you can reconstitute the coroutine back [5:56] and resume it, and that allows very nice [5:58] interactions with legacy C code. [6:02] Finally, unlike most of the other languages [6:04] which have coroutines, we did not tie [6:07] coroutines to any particular runtime. [6:09] Because requirements for the runtimes say in a kernel mode [6:13] or in embedded systems could be very different [6:17] from requirements needed for, say, [6:20] UI applications or some others. [6:23] So we made coroutine open-ended. [6:26] You can define the meaning to them, which is provide [6:30] efficient chopping of a function into a nice state machine. [6:34] And finally, we added efficient cancellation to coroutine. [6:38] So any coroutine can be canceled at any suspend point [6:42] without relying on exceptions. [6:44] And that is mostly to increase applicability of coroutines. [6:48] There are environments, like Google for example, [6:51] that does not use exceptions, or at least [6:55] in a large part of your code base, [6:57] and you can use coroutines there. [7:00] Same with kernel, like in Windows, kernel exceptions [7:04] are generally banned or unusable [7:06] because runtime does not support them. [7:08] Anyway, so this is what distinguishes coroutines in C++ [7:14] from coroutines in any other language. [7:16] And couple of years ago, we went through detailed talk [7:19] where I explained what compiler does with coroutines. [7:24] How compiler synthesizes the coroutines, [7:26] and we saw what major compiler is doing [7:30] to turn all of those wonderful coroutines on the left [7:33] into a tiny, single constant on the right. [7:37] So here you can see that we created [7:39] a bunch of generator coroutines. [7:41] That we composed them together, we passed them on to [7:46] a standard accumulate, and in the end we get a single number [7:50] Wonderful. [7:51] So coroutines are very efficient and optimizable in C++. [7:55] Last year we looked at interactions [7:57] between the network in TS and coroutines. [8:00] So we can take this wonderful server, [8:02] which is a little bit hard to read, and [8:05] this is the same server but written as a coroutine, [8:09] which is the same efficiency but easier on your eyes. [8:14] So nano-coroutines. [8:18] This is an application of coroutines [8:20] in the field of databases. [8:21] And I have not actually discovered that. [8:24] All the created goals to research that presented [8:29] and discovered that in VLDB conferences [8:32] and written those papers. [8:34] So why database people, why people [8:38] that go to VLDB Conference, which is [8:41] Very Large Database Conference, care about coroutines? [8:47] Especially nano-coroutines, [8:49] coroutines that can switch in nanoseconds. [8:52] Well, the trouble is very large database. [8:58] A lot, right? [9:00] And this is a tiny, tiny CPU, actually, well, yes. [9:03] It's a four core CPU on my laptop on which [9:07] I was running on the benchmark. [9:08] Look at those tiny, tiny numbers. [9:12] L1 cache, 32 kilobytes. [9:15] L2 cache, 256. [9:18] L3 cache, 8 megabytes. [9:21] And then memory. [9:25] And it takes 60 nanoseconds to bring a value [9:29] from the memory to the... [9:35] To the CPU. [9:36] And because it is a very large database [9:39] their index is, they're gigabytes, their own memory. [9:44] And they are hid at random spots. [9:47] So whatever you do, whatever wonderful (mumbles) [9:52] you are trying to achieve, when you start taking [9:54] those indexes, you're hitting memory [9:56] in absolutely random spots and nothing can help you. [10:02] So let's see what happens, and I will use [10:04] the simplest algorithm we can have for index searching. [10:09] A binary search, because it fits the screen. [10:13] Databases use more complicated b-trees and hashing [10:17] and combination of those but this will be good enough for us [10:21] So it is a version of the binary search [10:24] mostly stolen from a lower bound with one extra check [10:29] which allows us to bail out earlier [10:32] than the standard algorithm. [10:35] So let's run it on a small array. [10:40] Wonderful, if it fits L1 we're getting roughly [10:44] four nanosecond lookup over log two. [10:47] In this case I have this little metric [10:51] which allows us to evaluate how good the algorithm performs [10:54] by simply dividing how long did it take [10:57] to look do this search, divided by the log [11:01] of the size of the array. [11:03] Which is roughly how many hits into the memory it will do. [11:08] So wonderful, array comfortably fits L1. [11:12] We are barely having any misses, four nanoseconds per lookup [11:17] Okay, let's grow bigger. [11:19] Okay, 4.7 nanoseconds, reasonable. [11:24] Well, half of the L1 cache misses, but L2 if you see [11:28] is just 3.5 nanoseconds latency, so still not bad. [11:33] Again, even when the array fits L3, still wonderful. [11:39] Now this is where we're getting with databases. [11:44] With databases the actual index is gigabytes. [11:49] So even with this tiny array of 256 megabytes, [11:54] suddenly we are having 0.21 instructions per cycle. [12:00] This CPU can do four instructions per cycle. [12:03] Here we're doing it the opposite. [12:05] It's like one fifth of the CPU speed. [12:09] And what can you do about it? [12:15] Like, people have those wonderful data structures [12:18] trying to do cache optimizations, but what if your [12:20] memory access pattern is horribly random? [12:25] Well, if you want to do only one lookup, [12:29] nothing can help you, nothing can help you. [12:32] But luckily in databases, there is this wonderful [12:36] join operation which does a lot of lookups. [12:40] For example, here we have three tables [12:43] containing some customer orders, customer names, [12:45] and what food customers are eating. [12:49] And now we are doing the join operation. [12:52] So probably database would go through one table in a nice, [12:56] linear fashion that will have wonderful cache performance. [13:00] It will go one-by-one, they will prefetch a big table [13:04] of big pages so it will nicely go through all of them. [13:08] But then when it has to use the foreign key [13:10] to hit other table, oops, it's random. [13:14] It's random. [13:15] The core will be very, very sad. [13:19] It will do just a little bit of work, [13:22] and then 60 nanoseconds of nothing. [13:26] Now, 60 nanoseconds is small enough so that it is [13:30] not worth to switching to a different thread, [13:33] because switch to a different thread is what... [13:38] half a microsecond or more, so it's much bigger. [13:42] So core is being wasted. [13:45] Of course, there is hyper-threading, but normally on CPUs [13:49] how many hyper threads are? [13:52] Two, two, right? [13:54] Two, okay, okay. [13:55] So core will be slightly more happy, because what it will do [13:58] it will run until it hits the memory stall, [14:02] then it will start running the next thread [14:06] but if it hits the stall again, we are stuck. [14:10] So what can we do to make it better? [14:14] Luckily, CPU hardware vendors provided us [14:20] with prefetch instructions. [14:22] And this is an intrinsic with a bunch of hints [14:27] which allows us to tell to a CPU, [14:29] "Hey CPU, we are interested in that memory allocation." [14:34] And we can give it a bunch of hints, for example. [14:37] If I say hint is zero, it means I actually want that value [14:42] to be fetched from memory, and then go into L3, L2, L1, [14:47] because I want it to be all throughout. [14:50] And NTA, the last option. [14:53] It's actually the least disturbing flavor of prefetch. [14:56] It's where I have important data in my caches [15:01] and I don't want to evict it. [15:02] Instead, I want to prefetch the value from [15:06] that memory allocation as close to CPU as I want as possible [15:11] without trying to disturb other levels of caching. [15:15] So this is what we will be trying to do. [15:19] We will try to do instruction stream interleaving. [15:23] Because our joint operation needs to do multiple lookups [15:28] we will try to do something like that. [15:32] We will start the first search, and then at the point [15:35] where our binary search used to just read the value [15:39] from memory, we will issue a prefetch instruction [15:42] and then switch to a different... [15:46] Different search that, one you still need to do [15:48] because the joint operation requires multiple lookups. [15:51] And then let it run until we hit a memory [15:57] read from error in the application. [15:58] We will issue a prefetch, switch to the next one. [16:01] And then when we have enough of those [16:03] hopefully by the time when we did the last one [16:07] the first one we prefetched is already in memory, sorry. [16:11] It's already near the CPU so we can [16:14] switch to the original one. [16:15] So essentially what we'll be doing, we'll be doing [16:18] hyper-threading in software. [16:22] Okay, it's actually not that hard, it's just [16:26] you have to be very, very meticulous [16:28] about how you're going to do it. [16:30] So this red line shows roughly how we're going [16:34] to split that function and try [16:36] to turn it into a state machine. [16:38] So here we have this start middle that is trying [16:42] to read from memory, and we'll just partition it, [16:46] well, since we need to make it to a state machine, [16:49] we first need to extract all of the state [16:52] we need that currently inside of that function. [16:55] So do we need first? [16:58] Yeah, we need it because it is used both in [17:02] before the red line and after red line. [17:05] Same with last, middle, length, half, value, [17:13] the value that we are keep comparing, [17:17] okay, and we need a state. [17:19] And we need a state so that we know which part [17:21] of the algorithm we are before the read or afterwards. [17:25] And we'll run the state machine with just two function. [17:29] Initial one which executes the first time we enter function [17:33] and until we hit that read or prefetch instruction. [17:37] And then the one that will run the rest of the loop, [17:40] but again we will split it up so that we [17:42] we stop just before trying to reach from the middle, [17:47] if your prefetch instruction, and then get out. [17:54] Very straightforward. [17:57] This is the initial entry. [17:58] We copied all of the values that were before the while loop, [18:03] then, well, if the range is empty we will bail out [18:08] and we will mark the state as not found. [18:11] Otherwise, we will do all of the stuff which happens [18:14] before the read, namely half divided by, sorry. [18:19] We divided the length stored in half, computed the middle. [18:23] Say that we need to keep going, and we issue [18:26] the prefetch instruction I showed earlier, great. [18:31] Now run will do the rest of what happens once we're read. [18:38] So now the value we think that value had been prefetched. [18:43] So now it is safe to say start middle. [18:46] So we go the middle key, we compare it, [18:49] is it on this side, is it on that side? [18:51] We did the earlier bail out, and one difference here [18:55] is that before in our binary search the return value [19:00] was indicating whether we found a value or not. [19:03] Here I'm using the return value of run [19:07] to simply indicate do we need to run it more or we're done. [19:11] And the state that will be store and found or not found [19:15] will be the thing that will be telling us [19:19] whether we found a value or not. [19:22] And then we'll go prefetch the value again. [19:30] No, yeah, I think we covered all of it, [19:31] and we will mark the state as not found. [19:35] It's tedious, but doable, right? [19:41] Okay, I see one hand, good, good. [19:45] Sorry, oh, one head nodding. [19:47] So and we want to run it roughly like this. [19:50] We will create a bunch of those state machines [19:52] and we will say run init on this one so it'll [19:56] initialize this frame, hit the prefetch, [20:00] then do the same for the second frame, and keep going. [20:04] Now we initiated and prefetches. [20:09] We go back and call run. [20:11] We hope that by the time we get back to the first one [20:14] prefetch has already completed. [20:16] So we will run it again until we hit the prefetch, [20:20] go to the next one and say this one either found a value [20:24] or reached the end of the algorithm. [20:26] So we're done. [20:28] So we consume the result in whatever fashion [20:31] the database wants, and replace that frame [20:34] by running init now for search number N + 1. [20:39] And we will keep going. [20:41] I will bore you with roughly showing [20:45] the code, how it looks like. [20:48] Something like that. [20:51] We create vector frames, we go through the list [20:55] of all of the lookups we need to do, [20:58] and then if the state in a particular frame [21:01] is not equal keep running, we will initialize it. [21:05] Otherwise we will call run until [21:08] it's either found or not found. [21:11] In either of those cases we'll initialize [21:13] it again and so forth, so on. [21:17] And in the very end we need to deal with strugglers. [21:21] What it means is that we run through entire list [21:26] of lookups we need to do, but we still have frames [21:29] that have searchers that haven't completed yet. [21:34] So there will be a tiny loop at the end [21:36] that we'll take care of those. [21:39] Okay, let's see how we did. [21:42] So with naive search we were getting 26 nanoseconds [21:48] per lookup over the log of an array size. [21:53] Now we're getting something. [21:56] We just made it two times, 2.5 times faster. [22:02] And that is with interleaving with 16 streams. [22:04] Essentially I ran it with different amount of frames [22:09] until I find the number of frames which is sufficient for us [22:13] to do enough work between the prefetches [22:18] so by the time we go to the first one it's already there. [22:23] But it's nice, but that's a lot of code. [22:29] Moreover, we need a very, [22:30] very simple algorithm, binary search. [22:34] Now imagine we want to apply that technique [22:36] to more complicated algorithm. [22:39] That is not manageable. [22:42] Can we do it better? [22:45] Yes we can, and we can do it with coroutines! [22:48] So at the very beginning we talked about [22:52] two common patterns people use with coroutines. [22:55] One was generators, lazily-produced sequences, [22:58] and other are sync tasks that await [23:01] for some asynchronous I/O completions. [23:06] So which of those two kind of problems [23:10] this problem reminds me of? [23:13] Who thinks it's generators? [23:16] Two, who thinks it's async tasks, a lot. [23:20] And you are right, and you are right. [23:23] Moreover, that coroutine-based TCP server [23:27] we looked at last year is actually shown us [23:31] almost exactly the kind of patterns we are going [23:36] to use to deal with this problem. [23:39] Because the top part, which is a session where we [23:44] awaiting for TCP read, and then once read completed [23:50] we do a write, and then read again, write again. [23:53] It has the property that this coroutine doesn't go anywhere [23:57] while we're awaiting for the result. [24:00] And that is roughly what binary search is doing. [24:03] Because binary search you can think about it [24:05] a read from memory, oh, that's an I/O. [24:09] That is an I/O that takes a lot of time, 60 nanoseconds. [24:13] Without a coroutine so fast, you know, [24:15] one nanosecond or less switching, we can do a lot. [24:21] One change before I switch to a coroutine [24:23] I will change the way how we deal with the result. [24:27] So here we return the result as a boolean, [24:31] I want to return result in a form of a function object. [24:35] And if you notice, Alex Tiponov long time ago [24:40] discovered that this go behind are the best kind. [24:44] If you have a function object, compiler can actually [24:47] align it inside of the algorithm [24:49] and it will be very, very, very efficient. [24:51] That's why we're doing it this way. [24:54] And you know where I'm going to with this, [24:58] because this is it. [25:02] This is how long it would take us to convert [25:05] the algorithm from a plain one into a coroutine. [25:12] Essentially we have some kind of coroutine type, [25:15] we changed void into a coroutine type, and then [25:18] we replaced the plain read into a waiting on [25:22] a prefetch operation that will suspend that coroutine [25:28] while value is being prefetched, and then hopefully resume [25:32] it at the right time when the value is already in memory. [25:37] And yes, we need to replace return with coreturns. [25:40] There was a battle two years ago, and the coreturns have won [25:44] So we need to write coreturns on coroutines. [25:48] Okay, so that took care of the algorithm. [25:51] Now we need to write an orchestrator. [25:54] Let's get back to our TCP-based server. [25:59] So the bottom part actually has the pattern we want, [26:03] because unlike the session which gets suspended [26:07] while waiting for the result of the read or write, [26:11] we don't want a server to be suspended [26:14] while waiting for a particular session to work. [26:18] We actually would like to spawn as many sessions [26:22] as we want, and we want them to live [26:26] independently from the server itself. [26:29] And in this case, because having detached activity [26:34] right running wild, like detached thread in horrible, [26:37] never, never, never do it, here we are actually [26:40] associating the coroutine with an I/O context. [26:43] So in network in TS I/O context is the thing [26:47] which tracks all of the activity [26:49] which is currently in flight. [26:50] So in this case, we are spawning and we'll make [26:53] the coroutine independent of a server, [26:55] but still there is a way to join them [26:58] in the end, or cancel at the shutdown. [27:01] And that brings me to roughly this shape of an orchestrator. [27:07] So here in sort of I/O context we will have a throttler. [27:10] Because we're potentially doing a million lookups. [27:14] We don't really want to launch a million coroutines. [27:19] So the throttler will just have enough coroutines [27:24] to keep the prefetcher by client busy. [27:27] So and this multi-lookup gets the concurrency parameter [27:31] will given it to a throttler, and then throttler [27:34] will spawn enough coroutines to keep it busy [27:38] and in the end we will do the join. [27:40] So another name for this pattern is fork-join. [27:44] You probably have seen it NCBB and others, [27:48] because what we're trying to do is to spawn [27:51] a whole bunch of stuff, and then in the end [27:54] we want to wait until all of it is done. [27:57] So this is how we imagine the [28:00] simplest possible way to solve this problem. [28:03] Does it look simple to you? [28:06] Yeah, yeah because it's very close to what we're doing [28:09] first with the TCP server, and second the algorithm itself [28:13] is almost the same as a naive version. [28:16] So now let's see how much will it take us [28:18] to actually make it work. [28:21] And that is actually a quite a good approach. [28:24] Frequently I advise when people say, [28:26] "Hey, you know, how can I do this with coroutines?" [28:29] I will say, first think of the best way [28:32] of solving this problem. [28:33] Just imagine, imagine the syntax [28:35] and then you can make it work. [28:36] That's roughly what we were doing here. [28:38] We thought of a way how would we write it in a DL way, [28:43] and then figure out a way to make it with coroutines. [28:48] So the first part, we need to make prefetch an awaitable. [28:57] A quick reminder for those who haven't [29:00] seen the other coroutine talks, [29:03] awaitable is a thing with three functions. [29:08] Await ready, await suspend, and await resume. [29:11] So compiler expanded into something like that. [29:15] First it asks, hey you, awaitable expression, are you ready? [29:21] And if it's ready, then it proceeds straight to the end [29:25] into await resume, which unpacks the result. [29:29] And the result of an entire await expression [29:31] is whatever await resume have returned. [29:37] Now if it's not ready then compiler calls await suspend [29:42] and give it as a parameter, a handle to a coroutine [29:45] it manufactured, and the handler for await suspend [29:51] can then do something with it so that it can resume [29:54] or destroy the coroutine later when it knows the result [29:58] is available or if it knows it will have to cancel [30:01] and get rid of all of this stuff. [30:04] So let's do the awaitable for prefetch. [30:08] So we're going to try to implement this [30:12] prefetch awaitable to templatized on T. [30:16] So first we need to remember to grab [30:20] a reference to the value. [30:22] Right, so whatever is best in a constructure [30:25] we will just store a reference. [30:27] References are cheap, right? [30:29] It's just an address, we're not reading anything. [30:32] Now at the very end when our await is satisfied, [30:37] we will just return that reference to whomever [30:40] and hopefully he will actually use it for good name [30:44] to the reference and get the value that we were looking for. [30:49] Now in this case, if you look at the prefetch instruction [30:53] it doesn't tell us whether the value is already in the cache [30:56] Moreover, probably that will not be a very good instruction [30:59] because it will take a while for hardware to figure out [31:03] whether it's in the cache or not. [31:04] We want to be very fast, we want to cycle [31:06] a lot of coroutines, so we'll just say nope, [31:10] prefetch is never ready. [31:11] We assume that it is always in memory. [31:14] So we need to go on a suspend path. [31:17] And in a suspend path it's quite simple, actually. [31:20] We will call that intrinsic that I showed earlier, [31:25] give it an address of a memory location [31:28] that we want to prefetch. [31:30] And in this case I gave it a hint because [31:33] I didn't want to pollute any other caches. [31:35] I want to just we hit at random spots, [31:38] every time will be different. [31:40] Give us straight to the CPU. [31:43] And now I want to put this coroutine, [31:46] you see, there is coroutine handle that was passed [31:49] to everybody at this point, and they will put it [31:51] into some queue that will put it [31:53] at the very end of the queue. [31:56] Now. [31:59] Couple of years ago when we're talking [32:00] about different coroutine flavors, we talked [32:03] about symmetric and asymmetric coroutines. [32:06] So asymmetric coroutines, they support [32:10] only suspend and resume operation. [32:12] So in order for, well, when you suspend [32:16] you return back to the caller, and the resume [32:19] is a different operation that will resume you. [32:21] So there this unequal variation between the guy [32:24] who called you and the coroutine that suspended. [32:30] There is also a symmetrical coroutine variety [32:33] which allows direct coroutine-to-coroutine transfer. [32:38] More like thread to thread context switch. [32:42] And even though functionally those kind of coroutines [32:47] are accumulating, because we can convert easily [32:49] one into another, there is a cost of conversion [32:54] asymmetric coroutine into a symmetric one. [32:57] And I actually observe that cost right here, [33:01] because we're talking nanoseconds. [33:04] This was my first implementation where I simply [33:08] added a coroutine handle to this queue [33:10] and then I returned control back to the scheduler [33:14] which runs the loop, which de-queues now the coroutine [33:17] from the front and resumes it. [33:20] Well, that's about three cycles, and three cycles [33:23] is about 0.75 nanoseconds on that machine. [33:26] And we want to pack as many coroutines as we want, [33:30] and I wanted to eliminate that. [33:32] Luckily we have a provision in Coroutines TS [33:36] which allows symmetric coroutine-to-coroutine transfer. [33:40] So what we want to do here is this. [33:44] That way we essentially eliminated the scheduler. [33:46] Scheduler became just a very, very simple, dumb queue. [33:50] We're saying, put ourselves at the very end of the queue. [33:56] Get the coroutine at the front of the queue, [34:01] and that is the coroutine I want to [34:03] symmetrically transfer control to. [34:06] So this becomes simple jump from [34:08] this point to a different coroutine. [34:12] Okay, so. [34:16] Queue is boring, anybody can write it. [34:22] Yeah, and at the very end is just tri-pop and a run [34:26] that will keep trying popping the coroutines [34:28] until there is no coroutines anymore. [34:32] And resume on the coroutine handle is the thing you use [34:35] to resume the coroutine which is suspended. [34:40] Any question on the queue? [34:43] No, no, that's... [34:46] Okay. [34:48] Let's see. [34:49] What else is left to implement? [34:52] Okay, now we need to implement a throttler. [34:56] Let's look at the binary search again. [34:59] I lied. [35:00] I said it's a task void, and task void is [35:03] something which currently goes through [35:05] some (mumbles) processes, the zero overhead future. [35:08] We talked about it two years ago [35:12] in the coroutine under the cover of stock. [35:15] Well, this is not it. [35:16] I am going to hack it a little bit. [35:19] So it will be a root task. [35:21] Because I want root task to be aware of the throttler. [35:26] And it's a yucky part, I will show how to fix it later, [35:28] but I need this, so my apologies in advance. [35:32] So what throttler needs to know is, well, [35:35] what are the concurrency factor? [35:37] How many coroutines it want to keep concurrently. [35:42] And in the spawn it will check. [35:46] If it populated the queue with enough coroutines [35:51] it will start writing them down. [35:53] So essentially here what we're doing we'll [35:57] popping the first coroutine from the queue and resume it. [36:02] And then it will start jumping around [36:05] from coroutine-to-coroutine because we say the await, right? [36:08] Await will prefetch is actually doing all of the scheduling [36:12] and will keep running until one [36:15] of the coroutines run to completion. [36:18] And that will create a room in a cube. [36:21] That's why if the limit is zero, [36:23] I will start running the first coroutine [36:26] and then go around everything else. [36:29] Otherwise I will associate this coroutine [36:32] with this throttler so that it knows to tell me [36:36] when it's done so that I can bump up the limit. [36:40] Push it into the queue, and decrement the limit. [36:44] And on task done it is the callback that essentially [36:48] the coroutine will call at the end [36:50] that will increment the limit. [36:53] And the rest are boring functions. [36:59] I needed to do a few tweaks to the zero overhead future. [37:03] And this actually shows those tweaks. [37:05] First I needed to add set owner which will [37:09] disassociate the coroutine from this array type [37:16] which is going to destroy the coroutine and is destructor, [37:20] and transfer the ownership to the throttler, [37:23] because now this will be the guy who running the coroutines [37:26] and will be destroying them in the end. [37:30] And I will remember the throttler in the promise type. [37:34] And I change my final suspend from suspend always [37:37] to suspend never, which means the coroutine [37:41] will self-destroy itself in the end and will let know [37:45] the owner that the task is done, so it reached completion. [37:50] Finally because I am creating a million of coroutines, [37:53] million potentially coroutines, [37:55] I will use a recycling allocator. [37:58] So if you overwrite an operator, new and delete. [38:01] On the coroutine premise, you can supply your own allocator. [38:05] And that helps a little bit. [38:08] You know, extra few nanoseconds, and again [38:10] every nanosecond counts when we're [38:12] doing this kind of operation. [38:15] So let's see what happened. [38:17] So we have... [38:21] 26 nanoseconds for a naive version. [38:24] We have 10 nanoseconds for [38:29] a handcrafted version with 16 streams. [38:33] And do you think it will be better or worse with coroutines? [38:37] (audience laughing) [38:39] Yes, yes, it's actually better. [38:45] So we're getting to, well, almost 3.5 time [38:49] faster performance, and we have 20 streams to get it there. [38:55] (audience applauding) [38:58] Oh, thank you, so you all have to [39:00] leave early, we're almost at the end. [39:02] So negative overhead abstraction again? [39:07] So Alex Tiponov when he was in one of his interviews [39:12] when he was asked how to design good abstractions, [39:16] he explained that it's not like you invent abstractions [39:20] from just your brain, from thin air. [39:22] No, you start from a concrete problem, [39:25] and then you look at the most efficient way [39:28] to solve that problem you know today. [39:32] Okay, at that point you can try to invent abstraction [39:36] and now recode that problem using this new abstraction. [39:40] And see how much overhead have you introduced. [39:43] If not, wonderful, you have a good abstraction. [39:46] Try applying to some other pattern. [39:49] And so far, so on. [39:53] What happened with coroutines, and this is [39:55] not the first time, is that when we take [39:58] the best possible pattern we do today, [40:01] say with handcrafted state machine and then recode them [40:05] with coroutines, for some unknown reason it becomes faster. [40:09] So it is not just abstraction penalty, [40:12] it's a negative overhead abstraction. [40:15] And I try to understand why it happen. [40:18] So I was looking at disassembly, [40:20] because pattern of access for both handcrafted state machine [40:24] and the coroutine-based state machine, it is identical. [40:29] I am running them on the same array, [40:32] with the same set of values to lookup. [40:35] One of them was faster, and I think it happens [40:39] because of when coroutine transformation takes place. [40:44] So both Microsoft compiler, Clang, and a JCC implementation [40:51] which is currently in progress discovered that [40:54] the most profitable way to do a coroutine [40:56] is to actually let the coroutine be observed [41:00] by a compiler as a normal function for as long as it can. [41:04] So that optimizer can simplify the body, [41:07] can do the constant propagation, can do the [41:10] common expression elimination. [41:11] Like, do all of the awesome stuff compilers do inline things [41:15] Discover after aligning that some other stuff disappears. [41:19] And once you finish simplifying the body [41:21] of the function then you do the transformation [41:24] of the coroutine into a state machine. [41:27] So you chop it up into small pieces [41:29] and then you optimize the individual pieces. [41:31] So what happened here, we humans, we did the transformation [41:37] of a function into a state machine to early. [41:42] We did it at this very high level [41:44] before compiler had any chance of doing optimizations. [41:48] And once a function was chopped up into pieces [41:51] it becomes a state machine, compilers are not [41:53] very good at optimizing state machines. [41:56] So that is my guess why it actually faster. [42:00] If you look at disassembly you will see that the [42:05] the handcrafted state machine puts too much [42:07] register pressure on a compiler. [42:10] It is too complicated code, it starts spilling [42:13] and reloading values into the memory and into the registers. [42:18] Whereas coroutines after it's chopped up [42:20] it becomes very, very simple. [42:22] It does almost the same thing that you would have done [42:25] if you were trying to write this in Assembly. [42:28] So that's nano-coroutines for you. [42:30] We're taking advantage of the fact that the switching [42:34] from one coroutine to another is taking less than [42:40] a nanosecond, and in some cases zero [42:42] in case a coroutine is inlined. [42:45] Unlike, for example, fibers or stackful coroutines [42:48] which takes from 10 to 50 nanoseconds [42:50] to switch depending on the OS architecture, [42:53] CPU kind, and how many registers they have to [42:57] save and restore when they do the context switch. [43:01] And naturally you cannot do that with threads, [43:03] because they are we're talking... [43:07] You know, close to a microsecond switch. [43:10] So this approach allows you to... [43:18] To deal with memory latency in those cases [43:21] where nothing can help you. [43:24] No more packing of your data [43:27] in a cache where data structures can help. [43:30] Nothing, you hit the memory at random spots. [43:32] Well, if you have more than one lookup, [43:35] you can try to split your code into several streams [43:39] and then use coroutines to interweave them. [43:44] So coroutines current status, proposal is going through [43:48] the C++ Standardization Committee. [43:50] Maybe it will be in C++ 20. [43:53] We have implementations in Clang and Visual Studio. [43:58] GCC implementation is in progress. [44:03] Nathan, yes, in progress, I see he is nodding there. [44:07] No, he's leaving the room. [44:09] Oh no, he's coming here, excellent! [44:11] So I think we have confirmation [44:13] that CGG implementation is in progress. [44:16] And last year we had a talk where we talked [44:19] about naked coroutines, and that was one of [44:22] the complaints that coroutines are just a compiler feature. [44:27] You always have to come up with [44:29] your own types to play with them. [44:32] No longer naked, we have the task type [44:36] going through standardization. [44:37] We have the generator type that is supposed to come [44:41] in San Diego, which is just in a few months. [44:44] And a bunch of wonderful, wonderful, wonderful [44:48] algorithms that work on awaitable types [44:51] that will helped to... [44:56] And this is just a reminder. [44:57] I'm told to put the slide. [45:01] There are other useful talk, and we are [45:04] at the end of Wednesday, so I will put it back again. [45:08] So questions? [45:11] (audience applauding) [45:18] - [Man] Yes, so go, I just, correct started [45:21] an implementation, as Facebook's hired [45:22] a GCC engineer to work on this. [45:24] Started a week and a half ago, so (laughing) [45:28] But we have a design document that I've been working [45:30] with Gor on and the like, so it's not from a standing start. [45:34] If you go to the GCC wiki page, there's now a new [45:37] project page where you can see what's happening, [45:40] but it'll be a while before there is a result. [45:43] - Uh, wonderful, do I need to repeat the question? [45:48] Oh, excellent. [45:49] Well, it's awesome! [45:51] So I was not lying, GCC implementation is in progress, [45:55] even though it's only a week and a half, it's still awesome. [45:59] It's still in progress! [46:00] (audience laughing) [46:03] - [Man] So what's the performance [46:05] of the coroutine implementation like without the allocator, [46:10] and to what extent does that allocator rely on [46:12] the fact that all of those stack frames [46:15] are expected to be exactly the same size. [46:17] If you were in a place where you couldn't [46:21] rely on that, would the speedup be similar? [46:28] - I think it was about 10 nanoseconds. [46:31] I was surprised by how well malloc actually behaved. [46:35] I didn't use tcalloc, I just used [46:37] very dumb 30 second allocator. [46:40] But even without it, malloc was doing an amazing job. [46:43] But I wouldn't recommend, because if you are [46:46] going for nanoseconds, you better use [46:49] some good recycling allocator. [46:54] - [Man] Alright, thanks. [46:58] - [Man] For those of us who want to write applications [47:00] that other people are going to run on a variety of machines [47:03] that may have more cores or less cores [47:07] or more cache or less cache. [47:09] What facilities are there going to be [47:10] to make the throttlers more well-behaved [47:15] without hand tuning them? [47:21] - With the current instruction sets as they exist today, [47:25] right, that will not give you visibility of say [47:28] how busy a prefetcher is, you have to tune it by hand. [47:33] But I've been talking to some, I think, Intel engineers [47:38] what kind of are the facilities we could have. [47:41] For example, there could be, and again, this is spit balling [47:44] It's not real, no, nothing has happened [47:48] but potentially could have and instructions can tell you, [47:50] hey, prefetcher is that busy, and thus you know [47:55] you need to feed more to it. [47:57] And if it's completely busy, well, you don't [48:00] have to spawn any more, it will not help you at all. [48:04] So this kind of a help. [48:05] Another one somebody suggested was to have [48:08] a prefetch instruction that will give you a hint [48:10] whether the value is already somewhere close, [48:14] but that is likely to be a more [48:16] expensive instruction than a plain prefetch. [48:18] Because it would have to go and check in a bunch of places. [48:22] - [Man] I would be even be happy to let the [48:26] the throttler or whatever initialize itself [48:28] and run some kind of test once at the start of my program [48:32] and then use that data if that's, you know, [48:34] another way that this library could go. [48:38] - Absolutely. [48:57] - [Man] Hi, I'm interested if my own data structures [48:59] and algorithms are cache-friendly. [49:01] Can you comment on the profiling toolkit [49:03] you used to show your latency? [49:06] - I used perf-stat. [49:09] It's Linux tool, perf-stat, to show me [49:12] the Intel counters, the CPU counters. [49:15] - [Man] Perf-stat, what was it called? [49:16] - Perf space, yes, perf. [49:19] - Perf-stat, okay. [49:20] - Perf, P-E-R-F, perf-tool. [49:23] It has a bunch of very useful primitives, [49:25] and if you want to look in more detail, I think Chandler [49:29] had been given couple of talks last CppCon. [49:33] Going nowhere faster, and the previous one before that [49:37] he showed how to use perf-tool to get the information [49:42] about caches, about stalls, front-end stalls, backend stalls [49:48] perf-stat is a wonderful thing. [49:50] It also work as a profiler. [49:52] You can say perf record and then perf report, [49:55] and you will see wonderful text-based UI. [49:58] Which is pretty decent. [50:02] And on Windows you would use something like VTunes, [50:04] but you have to, is it VTunes, right, Intel? [50:07] But you have to pay. [50:09] On Linux is cheap, it's nothing. [50:13] - [Man] So this looks super awesome, but what if you [50:16] put a break point inside of a coroutine [50:18] and look up a call stack and then debugger? [50:20] Like is it a nightmare? [50:24] - If you put a break point into a coroutine [50:28] you will see roughly in, let me get to that. [50:34] Okay, hold on. [50:38] Okay, anyway, it's too far to (laughing) [50:41] to get to the code I want to show, [50:42] but what it will show you, you will have a... [50:45] Your binary search out or function, right, [50:51] and then that function call resume [50:54] and that resume you will be in a coroutine. [50:59] So you'll have just two functions on the stack. [51:00] You will see a function, the multi-lookup, [51:06] and the next one will be a coroutine [51:09] at that point where it is currently executed. [51:12] - [Man] So there's not much of, like, [51:14] sort of impenetrable functions deep [51:17] in some standard library in the call stack? [51:20] - No, no, every time you look you will see [51:22] a normal thread, and you will see the currently executing [51:26] coroutine and what function invoked it. [51:30] In this example it will be just the multi-lookup [51:35] and then a coroutine where it's suspended. [51:37] And if you want to see where other coroutines are, [51:40] then you need to go and look at the queue [51:43] which has coroutine handles and in Microsoft debugger [51:47] we will actually tell you what function it points [51:50] at what suspend point it points. [51:52] But we have plans, both in MSVC and hopefully [51:57] have extensions for other debuggers [51:59] that will show you as if it's a call stack. [52:02] So we'll show you a here's a coroutine suspended here [52:05] and here's all of the locals it has at the moment. [52:09] Right now you cannot examine coroutine handle [52:13] in this fashion unless it's a currently executed coroutine. [52:17] - [Man] Gotcha, thank you. [52:19] - [Man] I'd like to know if there is anything to think about [52:23] in terms of what the prefetch intrinsic does [52:28] with regard to C++ memory model. [52:31] Is there anything funky there [52:33] with acquire-release semantics? [52:36] Is it possible not to see the results of some [52:40] memory operations done by some other thread and-- [52:45] - Well, prefetch is just a hint, right? [52:49] So the actual operation we are doing is the reference. [52:54] That is where we will start worrying about the semantic. [52:58] It's we'll start trying to get that value [53:00] from a cache or from memory. [53:02] Prefetch is just a hint to a CPU hey, try to get me a value. [53:07] The real work will be done when, sorry, [53:08] not real work, but at least the one [53:11] that have all of that semantic associated [53:13] it is the actual the reference of the value. [53:16] - [Man] So the memory access itself should be [53:18] the subject of the same limitations as applies [53:21] to any other program outside of coroutine case? [53:25] Like putting memory barriers and so on. [53:28] - Actually, I think I start, I think I replied [53:31] incorrectly to your question. [53:35] In the sense that yes, we need to make sure [53:37] that the prefetch is not moved [53:41] around the actual read operation. [53:45] I'm not sure if it's hardware catching it [53:47] or it is an intrinsic which is marked somehow [53:53] in the backend which prevents reordering. [53:58] - [Man] And just another question, it sounds like [54:01] execution TS is something that you don't really need [54:05] to integrate with or care about, because you are [54:08] completely outside of whatever threading model, [54:11] execution model's going to be in C++. [54:15] 'Cause it seems to be like completely unrelated [54:17] with anything threading, right? [54:19] - Yes, yeah so, coroutines love executors. [54:24] Coroutines love network NGS. [54:26] Coroutines interact with other things, but by itself [54:31] they do not require those facilities. [54:34] But if you want to inter-operate with them they can. [54:38] And there is a paper in the, if you know where to find [54:43] the standardization mailings, there is a paper [54:46] of coroutine impact on library facilities. [54:50] You Bing this name you will see how it's supposed [54:55] to interact with executors, with networking and other things [55:00] - [Man] Hello, so in my day job we use, like, [55:04] bunch of fiber managers to run on different threads [55:08] and basically serve connections with clients. [55:13] And there is kinda of pain to use mute access and statics [55:17] because they can grab logs that were inside. [55:22] They basically block all the fibers on the same thread. [55:26] Is this going to be the same with coroutines [55:29] or you're going because like for fibers [55:32] we use special fiber matrices. [55:35] - Okay, so one of the fundamental problems [55:38] why you don't want to migrate fibers from one thread [55:42] to another is related how thread [55:45] local storage code is generated. [55:48] So compiler is unaware of at what point of your function [55:55] you can have the fiber switch that will also switch the TLS. [55:59] So if you go to (mumbles) and compile some arm code [56:04] that uses TLS you will observe it, it will cache in some [56:09] non-vault vault or registers the pages of TLSs. [56:12] And thus you will be either reading garbage [56:15] or corrupting the memory if the switch occurs. [56:19] Coroutine control flight, the stack class coroutine [56:23] like this, suspension point is called out. [56:27] It is observable by the compiler. [56:29] So no TLS caching is performed. [56:32] Now, if you are actively trying to defeat [56:35] or write a bug, you can, but you can never [56:39] get into a situation where you are using the facility [56:42] like magic statics, or maybe thread caching allocator. [56:46] Or error_value, which is under covers, [56:51] uses the magic statics. [56:53] You will not end up in the case where you will [56:56] trash the memory or read garbage with these coroutines. [57:01] So they are safe to migrate as long as [57:03] you're not actively writing bugs. [57:05] - [Man] I see, one followup question. [57:07] What about your, like, primitives of STL? [57:12] Are they going to be like variants which support coroutines? [57:16] - Okay, so we have, at the moment we don't have [57:20] any asynchronous I/O in the standard, [57:23] but there is a network in TS which is in flight, [57:26] which might land in 20 or might land slightly later. [57:30] So that network NTS will be interacting [57:34] nicely with coroutines, and if you look at CppCon talk [57:38] called Naked Coroutines Live from last CppCon, [57:42] there will be a demonstration how you can hook up [57:45] network in asynchronous I/O and coroutines. [57:48] - [Man] I would, just that I'm speaking [57:49] about, like, I/O streams for example. [57:52] - Well, I/O streams are not asynchronous yet. [57:55] When they will be we can start talking about coroutines. [58:02] - [Man] As I understand the time when we [58:06] await the result from prefetch depends on [58:10] size of (speaking foreign language). [58:14] So if it's enough featured to between the prefetch [58:21] and when CPU call, move data to L1 cache it's... [58:31] Or isn't, will log best of worst. [58:35] You compare two organization, but in one case was [58:43] 16 streams and the other case 20 threads. [58:49] Are you compare the working this, all that it's [58:51] on same amount of streams? [58:56] - Okay, so what happens is that the handcrafted [59:00] state machine were doing more work. [59:04] So there are four, I only can launch... [59:12] It does more, it consumes more cycles [59:15] in that little squiggly area here, sorry. [59:22] Okay. [59:24] So this squiggly where we actually do useful work [59:28] between the stalls, it was doing more work. [59:33] There are four, I needed less of them [59:37] to consume this empty space between the squigglies. [59:44] Whereas with compiler-generated state machines [59:50] that I did from coroutines, it was actually using [59:52] less instruction to do the same amount of work. [59:55] So I was able to feed more [59:57] coroutines to do more concurrency. [60:01] But I determined that empirically. [60:04] I just random with different concurrency numbers [60:10] and saw which one gave the best performance. [60:13] - [Man] Okay, thank you. [60:16] - So I wasn't trying on purpose to make [60:18] the handcrafted state machine worse. [60:21] It was actually the fasting timing [60:23] I got was with 16 of them. [60:28] - [Man] Hi, I wanted to ask about the binary search. [60:32] I'll try to make it quick. [60:34] So in order to know what else you would need, [60:36] wouldn't you need to do some redundant work [60:39] and bring in some stuff you might, so, [60:42] to know which thing you're going to need next, [60:44] you need to resolve the current check. [60:46] So you need to sort of do work that you [60:50] never would actually need, right? [60:54] So as in prefetch stuff that you wouldn't really require. [61:00] If you would just do it, right, like this, linearly. [61:04] - Well this is exactly the sad situation, [61:06] because if you knew in advance that you need [61:10] that, that, that, that, and that one, [61:13] you can prefetch whole bunch of them. [61:15] But you can't, you first have to prefetch a value [61:18] before you know where to go. [61:21] That is what make this problem very sad problem [61:25] unless you do prefetching combined [61:27] with instruction stream interleaving. [61:29] - [Man] My point is that you're pulling more data [61:32] into the memory, evacuating more stuff out of the memory [61:37] than this thing, right, in some sense? [61:40] - In my testing I have been using the prefetch NTE, [61:44] which is trying to move the value directly [61:48] into L1 cache without touching L2 and L3. [61:51] So supposedly say if your database, [61:53] you have some real data you want to do work with [61:56] and index is just a way to get to the data. [62:00] So in this case I'm trying to be very frugal [62:02] and not evict stuff from big caches which have data, [62:07] and use prefetch NTE to avoid that. [62:10] - [Man] Can you put the slide back [62:11] with all the presentations? [62:13] - Say again, which one? [62:14] - [Man] The slide with all the presentation times. [62:16] You had a slide that says all the other talks. [62:21] The second to last. [62:22] - This one? [62:23] - [Man] Uh, nope, the last. [62:26] - The last one. - At the end. (laughs) [62:31] - Hold on, I think I know the faster way to get there. [62:38] This one? [62:44] - [Man] I wonder if to clarify that the question from before [62:47] You weren't optimizing a single search to be faster, [62:52] you were optimizing many searches [62:54] to happen in a less amount of time. [62:55] So it's, it wasn't the single search that he was prefetching [62:59] he was just interleaving many other searches. [63:02] - Oh, yeah, thank you, thank you for clarification. [63:04] Yeah, if you have to do only one search, nothing. [63:08] Nothing can help you. [63:11] And that is why database people are interested, [63:13] because they actually do multiple lookups. [63:17] - [Man] Would it be also possible to optimize [63:20] single search if you stop prefetching sooner, [63:24] because, well, every time you access memory [63:26] you are actually pulling a little bit [63:28] more data into cache, right? [63:30] So like let's say when you are making less steps [63:32] and bettering your search, and when you're observing like [63:35] last, I don't know, four values or something like that. [63:37] So you probably don't need to do it in separate steps. [63:41] - Can you speak slightly close to the microphone? [63:43] For some reason I'm not getting it here. [63:46] - [Man] Oh, sure. [63:47] My question was when you prefetch something from memory, [63:51] so you were, you know, CPU's not pulling single byte, right, [63:54] so it's pulling couple more bytes after that, then, to cache [63:58] So probably you could stop prefetching [64:01] for the last couple iterations of the binary search. [64:05] And by doing that, so probably you would spit up [64:08] little bit individual search. [64:11] - Possibly. [64:12] I will put up the code on the GitHub, [64:14] and have fun parting on it. [64:15] See if you can make it faster! [64:20] Okay, thank you very much. [64:22] (audience applauding)