3 ms·

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

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

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