3 ms·

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 wrot

by 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.)
kibibu 3y ago
To me, the order of magnitude suggests that the select function used in the first version did UI updates for each occurence, which the new version deferred and did only once.

by jsnell 3y ago

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.)

kibibu 3y ago

To me, the order of magnitude suggests that the select function used in the first version did UI updates for each occurence, which the new version deferred and did only once.