4 ms·

I'm kind of confused by this post. It talks about how this is an example of zero-cost abstractions, while actually showing the opposite. The original implement

by jsnell 3y ago

I'm kind of confused by this post. It talks about how this is an example of zero-cost abstractions, while actually showing the opposite. The original implementation was grotesquely inefficient, it's a 172kB file! To fix that, they ended up manually inlining and duplicating 70 lines of code. And the optimized version is still 50x slower than grep --color would be. Why was the original version so slow? Can't be due to the searching, given they were 4 orders of magnitude off from where they should be. It can't be due to this kind of batch oriented programming having more efficient memory access patterns. The data set is so tiny that it's all going to fit in caches. Something in the editor's internal data structures working better when the stages are not interleaved? That would be my first guess. Maybe making changes to the editor data structures invalidated the search state, forced each search step to restart from the start of the buffer, and you ended up with an accidentally quadratic algorithm? There's clearly a real performance problem in their system that was papered over by copy-pasting some code, but that they'll inevitably keep hitting over and over as people write the obvious code, it seems to work fine, but then has bad performance in practice. The right thing to do is to either fix that underlying problem, or to make it as easy to write the well-performing version as the bad one. (E.g. have some kind of scoped "batch context" abstraction, which queues up the edits and then applies them in a batch when leaving the scope.) Anyway, all of this makes the conclusion quite odd. The real moral of the story should be that CPUs are really fast, not that Rust is magical and will change the way one thinks.

jonstewart 3y ago
First, I agree with your overall point, that this post illustrates the opposite of what it claims. However, the discrepancy can be due to cache misses (and likely is, in part). One thing people get wrong about caches is looking at some smallish data set and thinking, “oh that fits in cache.” However, cache is divided into small 64-byte chunks (“lines”). And there are typically three levels of cache, each using lines. Hardware may detect sequential access and start pulling in next lines for you in advance, but it depends a lot on access patterns. With the original loop, the access patterns are such that there’s no guarantee the next bit of data will be in memory. It’s proceeding sequentially, perhaps, but through several different areas of memory. I’d love to instrument the code to compare dcache miss rates, and L1 vs L2 vs L3, though not enough to deal with building zed myself. My guess is that the before version has a worse hit rate than the after version. What’s more, there’s also the instruction cache. The original version pulls a lot of code into that loop. My guess is that the icache hit rate is also worse in the original. That’s deadly — the CPU does nothing. And it might stall enough that the OS context switches (after all, the times reported in the blog post are probably wall clock time; reducing idle enough so that the OS doesn’t context switch goes a long ways towards explaining a 250X speed up). Finally, with the batched loops, there’s not that much code in each one and they’re classic for-loops. The compiler can apply unrolling; even if it doesn’t, the CPU reorder buffer/dispatcher basically will. My bet is that the after version has a significantly higher instructions per cycle (IPC) score, ie better instruction-level parallelism. I’m agnostic about your conclusion, that the main data structures in place in zed doom it to similar performance problems. Not sure? It may have reasonable data structures. But as you point out with the grep comparison, the competition when it comes to these operations are tools and techniques that have been honed to an unreasonable degree over decades, to the point where their codebases and CPU architectures have co-evolved. It’s a steep hill to climb.
- jsnell 3y ago
  It really can't be just cache effects. You might not be appreciating just how slow that original program was, or how little data this is. To illustrate, I wrote a Python program[0] that does the search using the naive algorithm, implemented using pure interpreted Python rather than calling out to any optimized builtin or native code libraries, with each character being a separate object, and with each character being stored in a separate 128 element array just to waste more cache. So really absurdly inefficient. It executes the benchmark search on the sample file in 2ms on a Ryzen 2700. Sure, cache effects would have contributed a bit to the difference between the original and optimized version, but the contribution just has to be minor. [0] https://www.snellman.net/tmp/39417829.py https://www.snellman.net/tmp/39417829.py
  - jonstewart 3y ago
    As context, I’ve implemented a specialized grep engine in C++, with decent performance (not the best, but better than classic PCRE). So, not saying you’re wrong, simply that, I have some background/intuition about searching, too. Why is the original Rust code slow, though? You say it’s bad code — what’s bad? Why are the data structures bad? I haven’t looked further into zed than this blog post so curious whether you have more insight. With your Python script, it’s a straightforward state machine and just counts the number of matches. Now, Python is slow. But this should be fairly simple, small pcode all the same and doesn’t compare to all that the original code is doing (ie manipulating the offsets and making selections). Do you insight into what their selection code is doing? Is that drawing at the same time? Or somehow has complicated nonlinear access times? I’m just learning Rust and don’t yet have good intuition for its pitfalls. I find it curious that they didn’t present any info from a profiler. I suspect it’s not their search code that’s slow, but, again, not clear about Rust or surrounding code/context of zed and its data structures. Appreciate your comments.
    - jsnell 3y ago
      First, just to be clear, I didn't call their code or data structures bad. The only context where I used that word was "make it as easy to write the well-performing version as the bad one", which was talking about the performance, not the code. I know nothing about their code or data structures beyond what was in this blog post. I'm just working from the numbers, which don't add up. In the interleaved version they're spending about 430 microseconds for each of the editor operations. In the batch version they're spending <2 microseconds. As per the blog post, the order of operations is the same. (The bit about removing overlapping search results is irrelevant, their search term can't self-overlap, so doing that portion in batch doesn't seem relevant.) So, given the order of operations is the same, how much cache pressure is there between two calls to the editor data structures in the? The file is tiny and the results are dense. There's a span element on average evey 74 bytes. There's basically no pressure. And still the interleaved version is taking 430 microseconds longer. Given the minimal cache pressure between the calls, it is just impossible for that to be due to cache misses. It'd basically require that having accessed a couple of cachelines worth of (easily prefetchable) data would have the side effect of turning thousands of memory accesses from L1 hits to L3 misses in the next function call. Seems pretty implausible. Why do you think that this is a more likely explanation than second order effects from the interleaving? (It doesn't need to be my initial guess of edits resetting the search state, there's plenty of other similar issues where a leaky abstraction causes minor changes in the order of operations to have outsized performance impact. For example, maybe they don't commit edits immediately, but only on the next read operation.)
KTibow 3y ago
It's worth noting that this isn't a find command, it's a find and select command
asQuirreL 3y ago
There's no great mystery here, if you look at the internal function that's being called, it contains a TODO explaining that the code is unnecessarily quadratic and needs to be fixed: https://github.com/zed-industries/zed/blob/12b12ba17a380e321d47704d487b5d4cdca7877a/crates/editor/src/editor.rs#L6389 https://github.com/zed-industries/zed/blob/12b12ba17a380e321... So if selecting all matches requires calling this function for each match then I guess it's accidentally cubic? I also spotted two linear scans before this code (min by key and max by key). It seems like a combination of the implementation being inefficient even for what it was for (and that this was known), then it was used for something else in a naive way, and the use of a bad abstraction in the code base came at a performance cost. I don't think this is a case of Rust either demonstrating or failing to demonstrate zero-cost abstractions (at a language level). A language with zero-cost abstractions doesn't promise that any abstraction you write in it is magically going to be free, it just promises that when it makes a choice and abstracts that away from you, it is free (like with dynamic dispatch, or heap allocation, or destructors, or reference counting, etc).

by jsnell 3y ago

jonstewart 3y ago

First, I agree with your overall point, that this post illustrates the opposite of what it claims. However, the discrepancy can be due to cache misses (and likely is, in part). One thing people get wrong about caches is looking at some smallish data set and thinking, “oh that fits in cache.” However, cache is divided into small 64-byte chunks (“lines”). And there are typically three levels of cache, each using lines. Hardware may detect sequential access and start pulling in next lines for you in advance, but it depends a lot on access patterns. With the original loop, the access patterns are such that there’s no guarantee the next bit of data will be in memory. It’s proceeding sequentially, perhaps, but through several different areas of memory. I’d love to instrument the code to compare dcache miss rates, and L1 vs L2 vs L3, though not enough to deal with building zed myself. My guess is that the before version has a worse hit rate than the after version. What’s more, there’s also the instruction cache. The original version pulls a lot of code into that loop. My guess is that the icache hit rate is also worse in the original. That’s deadly — the CPU does nothing. And it might stall enough that the OS context switches (after all, the times reported in the blog post are probably wall clock time; reducing idle enough so that the OS doesn’t context switch goes a long ways towards explaining a 250X speed up). Finally, with the batched loops, there’s not that much code in each one and they’re classic for-loops. The compiler can apply unrolling; even if it doesn’t, the CPU reorder buffer/dispatcher basically will. My bet is that the after version has a significantly higher instructions per cycle (IPC) score, ie better instruction-level parallelism. I’m agnostic about your conclusion, that the main data structures in place in zed doom it to similar performance problems. Not sure? It may have reasonable data structures. But as you point out with the grep comparison, the competition when it comes to these operations are tools and techniques that have been honed to an unreasonable degree over decades, to the point where their codebases and CPU architectures have co-evolved. It’s a steep hill to climb.

jsnell 3y ago
It really can't be just cache effects. You might not be appreciating just how slow that original program was, or how little data this is. To illustrate, I wrote a Python program[0] that does the search using the naive algorithm, implemented using pure interpreted Python rather than calling out to any optimized builtin or native code libraries, with each character being a separate object, and with each character being stored in a separate 128 element array just to waste more cache. So really absurdly inefficient. It executes the benchmark search on the sample file in 2ms on a Ryzen 2700. Sure, cache effects would have contributed a bit to the difference between the original and optimized version, but the contribution just has to be minor. [0] https://www.snellman.net/tmp/39417829.py https://www.snellman.net/tmp/39417829.py
- jonstewart 3y ago
  As context, I’ve implemented a specialized grep engine in C++, with decent performance (not the best, but better than classic PCRE). So, not saying you’re wrong, simply that, I have some background/intuition about searching, too. Why is the original Rust code slow, though? You say it’s bad code — what’s bad? Why are the data structures bad? I haven’t looked further into zed than this blog post so curious whether you have more insight. With your Python script, it’s a straightforward state machine and just counts the number of matches. Now, Python is slow. But this should be fairly simple, small pcode all the same and doesn’t compare to all that the original code is doing (ie manipulating the offsets and making selections). Do you insight into what their selection code is doing? Is that drawing at the same time? Or somehow has complicated nonlinear access times? I’m just learning Rust and don’t yet have good intuition for its pitfalls. I find it curious that they didn’t present any info from a profiler. I suspect it’s not their search code that’s slow, but, again, not clear about Rust or surrounding code/context of zed and its data structures. Appreciate your comments.
  - jsnell 3y ago
    First, just to be clear, I didn't call their code or data structures bad. The only context where I used that word was "make it as easy to write the well-performing version as the bad one", which was talking about the performance, not the code. I know nothing about their code or data structures beyond what was in this blog post. I'm just working from the numbers, which don't add up. In the interleaved version they're spending about 430 microseconds for each of the editor operations. In the batch version they're spending <2 microseconds. As per the blog post, the order of operations is the same. (The bit about removing overlapping search results is irrelevant, their search term can't self-overlap, so doing that portion in batch doesn't seem relevant.) So, given the order of operations is the same, how much cache pressure is there between two calls to the editor data structures in the? The file is tiny and the results are dense. There's a span element on average evey 74 bytes. There's basically no pressure. And still the interleaved version is taking 430 microseconds longer. Given the minimal cache pressure between the calls, it is just impossible for that to be due to cache misses. It'd basically require that having accessed a couple of cachelines worth of (easily prefetchable) data would have the side effect of turning thousands of memory accesses from L1 hits to L3 misses in the next function call. Seems pretty implausible. Why do you think that this is a more likely explanation than second order effects from the interleaving? (It doesn't need to be my initial guess of edits resetting the search state, there's plenty of other similar issues where a leaky abstraction causes minor changes in the order of operations to have outsized performance impact. For example, maybe they don't commit edits immediately, but only on the next read operation.)

KTibow 3y ago

It's worth noting that this isn't a find command, it's a find and select command

asQuirreL 3y ago

There's no great mystery here, if you look at the internal function that's being called, it contains a TODO explaining that the code is unnecessarily quadratic and needs to be fixed: https://github.com/zed-industries/zed/blob/12b12ba17a380e321d47704d487b5d4cdca7877a/crates/editor/src/editor.rs#L6389 https://github.com/zed-industries/zed/blob/12b12ba17a380e321... So if selecting all matches requires calling this function for each match then I guess it's accidentally cubic? I also spotted two linear scans before this code (min by key and max by key). It seems like a combination of the implementation being inefficient even for what it was for (and that this was known), then it was used for something else in a naive way, and the use of a bad abstraction in the code base came at a performance cost. I don't think this is a case of Rust either demonstrating or failing to demonstrate zero-cost abstractions (at a language level). A language with zero-cost abstractions doesn't promise that any abstraction you write in it is magically going to be free, it just promises that when it makes a choice and abstracts that away from you, it is free (like with dynamic dispatch, or heap allocation, or destructors, or reference counting, etc).