7 ms·

Bit-twiddling optimizations in Zed's Rope

168 points by misternugget 2y ago

camel-cdr 2y ago
nth_set_bit_u64: wouldn't that be __builtin_ctzll(_pdep_u64(1<<n, v)) with BMI2?
- SkiFire13 2y ago
  That's assuming you're ok with your program not running on some older cpus.
  - zamadatix 2y ago
    That and that you're not willing to entertain splitting the manual version as #[cfg(not(target_feature = "bmi2"))] fallback implementation. For something already down to ~ 1 ns both of those may well be very reasonable assumptions of course.
    - Validark 2y ago
      AMD machines prior to Zen 3 had a micro-coded implementation of pdep and pext, so they're actually relatively expensive for those earlier Zen machines (as well as Bulldozer). Some people still have Ryzen 3000 series chips. On the Intel side, pdep has been fast since its release with the Haswell in 2013, so pretty much everyone using Intel should be fine in this regard.
- kwillets 2y ago
  That's my guess as well. Bitstring rank/select is a well-known problem, and the BMI and non-BMI (Hacker's Delight) versions are available as a reference.
- stouset 2y ago
  I believe the equivalent ARM64 instructions are in SVE2 which isn’t yet supported on Apple’s M-series chips as of M4, sadly.
rgrmrts 2y ago
I really like all the blog posts and videos the Zed team has put out, thank you if you’re reading this! Unrelated to this specific post I’m such a fan of Zed. It’s the first feature complete text editor in recent memory that I’ve truly enjoyed using (i.e. it stays out of the way, is really fast, feels well engineered). I’m coming to Zed after years of Emacs which I still have love for but no longer feels like a competitive piece of software (it does not take full advantage of how good computers are today, e.g. gpu rendering or multicore). I really hope Zed stays a fast and lightweight text editor instead of becoming some bloated growth-at-all-cost VC ware (not that they’ve exhibited any signs of that happening). I’d also happily pay for Zed without a subscription based thing for access to LLM features (which I do not use).
- seanw444 2y ago
  > it does not take full advantage of how good computers are today, e.g. gpu rendering or multicore Why does Emacs need that though? I hear people say this all the time and I don't get it. Multicore kind of works against the structure that Emacs touts as a feature. And GPU rendering? In many applications, I totally agree with these complaints. But it's a text editor. I tried Zed myself, and it's good. But it doesn't dethrone Emacs (for me personally).
  - PittleyDunkin 2y ago
    > Multicore kind of works against the structure that Emacs touts as a feature. I have consistent issues with emacs locking up when executing network requests. I'm sure there's a specific bug that could be hunted down and addressed, but this sort of thing shouldn't happen much in an editor that's multicore by default. I'm not trying to dismiss emacs' reasoning, of course, but I can understand being disgruntled with it. The actual rendering I've been quite please by, though!
    - rgrmrts 2y ago
      Yeah this is one reason, or Emacs freezing for up to a minute when updating packages. Also when using an LSP I notice latency. I use Emacs GUI (outside of the terminal) and comparing performance for rending to something like Zed or Sublime is definitely noticeable. It’s great that Emacs is so resource efficient but sometimes I wish it used more of my beefy computer(s). Like I said I still love Emacs and it’s okay for it to make a different set of trade-offs. I honestly didn’t think I’d ever switch editors but here we are!
dmitrygr 2y ago
> // Parallel bit count intermediates > let a = v - ((v >> 1) & (u64::MAX / 3)); > let b = (a & (u64::MAX / 5)) + ((a >> 2) & (u64::MAX / 5)); > let c = (b + (b >> 4)) & (u64::MAX / 0x11); > let d = (c + (c >> 8)) & (u64::MAX / 0x101); That "parallel bit count" is almost certainly slower than using two POPCNT instructions on a modern cpu. Should just call __builtin_popcount() and let the compiler do it the most optimal way. Luckily, people do this sort of thing so often that many modern compilers will try (and often succeed) to detect you trying this insanity and convert it to a POPCOUNT (or a pair of POPCOUNTs as the case may be here)
- akoboldfrying 2y ago
  Which compilers support __builtin_popcount()? From memory, it's a gcc extension. If the compiler selects a CPU POPCOUNT instruction for it, are you sure it will work on all machines that you want to run it on? The above code is completely source- and binary-portable and reasonably fast -- certainly faster than naively looping through the bits, and within a small constant factor of a CPU POPCOUNT instruction.
  - woadwarrior01 2y ago
    > Which compilers support __builtin_popcount()? Clang supports __builtin_popcount() too. And MSVC has __popcnt().
  - dmitrygr 2y ago
    Your compiler will know the best way to popcount, that is the point of that builtin. It'll use the best method - sometimes this one. GCC does this, MSVC does this, clang does this, i think even rust has some way to do it (EDIT: it does: count_ones()). On archs which lack POPCNT, it will use this method or another, based on knowing the target. On x86 this approach is OK as is. On arm64, for example, it will be suboptimal due to all the literals needed. On armv6m, this method is bad and table lookups are faster.
    - SkiFire13 2y ago
      Note that by default rustc targets x86-64-v1 when compiling for x86-64, and that lacks the popcount instruction. You need to change the target_cpu to at least x86-64-v2 or enable the popcount target_feature. This means that even if your cpu is relatively new and you intend to run your code on relatively new cpus, rustc will still generate older and slower code for count_ones() using bitshifts and masks. That said, I don't see the point in writing them manually if the compiler can generate them for you.
ramon156 2y ago
Isnt the tab example wrong? Id assume it to be aa -> -> bb -> -> bb It only takes up two spaces, after all
sapiogram 2y ago
Is there a way to adjust text contrast in light mode in Zed yet? The editor is unfortunately unusable for me, because of how washed out the colors are.
- mattbaker 2y ago
  There are themes now and a UI to install them, I also didn’t like the washed out colors.
  - onyno 2y ago
    Moved to zed a while ago. I’m using a light theme - Xcode low key now (With some settings to turn off the bold fonts).
  - sapiogram 2y ago
    Have you found a light theme you're happy with? Which one?
Am4TIfIsER0ppos 2y ago
> opacity: 0; > filter: blur(1px); Wonderful styling!
dzaima 2y ago
SIMD can work quite well here too - with 128-bit SIMD (available on both baseline x86-64 and aarch64) this can be just ≤8 loop iterations checking for the newline character (each iteration counting the number of newline characters encountered, and a lzcnt on the last iteration), and similar for characters (assuming valid UTF-8, it's a single comparison to test if a byte starts a new char).
eviks 2y ago
Why not store just a small u8 count of newlines in a chunk instead of their u128 positions and then only loop through the last chunk for precision? You don't need information about the position of newlines in all the chunks located before the one your offset lands on
- teo_zero 2y ago
  As I understand it, they do exactly what you say. TFA is about optimizing the last chunk's loop.
  - eviks 2y ago
    Maybe I got confused, but how do they then count the newlines in all the previous chunks? That information is still needed to calculate the line for a specific position in the last chunk
    - teo_zero 2y ago
      It's not you who's confused, it's that this part of the process is not described. We only have some hints, here: > If you called rope.offset_to_point(7234), the Rope would traverse its SumTree to find the Chunk that contains offset 7234 and then, on that Chunk, it would call offset_to_point again. And here: > while the Rope can get us to the right Chunk in O(log(n)) I would guess that each node of the SumTree includes the number of newlines of all the chunks before it.
    - DylanSp 2y ago
      It's outlined in their previous post on the Rope/SumTree data structure they use, which this article links to: https://zed.dev/blog/zed-decoded-rope-sumtree https://zed.dev/blog/zed-decoded-rope-sumtree.
benreesman 2y ago
I really want to admire the Zed folks even though they are a new faction in the editor wars where I’m an emacs guy: they take mostly all the things I care about seriously. The are serious about local vs. remote vs. shared. They are serious about hardware acceleration because they care about users who type fast and edit big files. They care about real computer science on how to push the current hardware to serve the user, rather than treating the hardware as a crutch to give the user a slightly worse experience at a fraction of the development cost. They care about code highlighting the snippets on their blog like very similar to the default Zed theme. These are cool, serious people. If they give me emacs key bindings with full paredit-everywhere, I might switch my daily driver. And this is about using modern SIMD-style stuff, branch less stuff, Lemire stuff in a modern and relevant context. Other commenters have pointed out that you can do the mask or popcount better with intrinsically, and yeah, but they probably know that, and B. They got the massive win, the remaining factor of K on the pop count is coming. Long Zed.
m1keil 2y ago
This is all really cool, but I just want soft wrap to be fixed
veltas 2y ago
> Turns out CPUs are pretty good with zeros and ones. I've been saying this a lot recently, that CPU's are powerful 1-bit vector machines!
eliasson 2y ago
Does anyone know of any good presentations about the Zed architecture and internals around? I know that they have some recordings from their coding session, but I am looking for something more overall.

168 points by misternugget 2y ago

camel-cdr 2y ago

nth_set_bit_u64: wouldn't that be __builtin_ctzll(_pdep_u64(1<<n, v)) with BMI2?

SkiFire13 2y ago
That's assuming you're ok with your program not running on some older cpus.
- zamadatix 2y ago
  That and that you're not willing to entertain splitting the manual version as #[cfg(not(target_feature = "bmi2"))] fallback implementation. For something already down to ~ 1 ns both of those may well be very reasonable assumptions of course.
  - Validark 2y ago
    AMD machines prior to Zen 3 had a micro-coded implementation of pdep and pext, so they're actually relatively expensive for those earlier Zen machines (as well as Bulldozer). Some people still have Ryzen 3000 series chips. On the Intel side, pdep has been fast since its release with the Haswell in 2013, so pretty much everyone using Intel should be fine in this regard.
kwillets 2y ago
That's my guess as well. Bitstring rank/select is a well-known problem, and the BMI and non-BMI (Hacker's Delight) versions are available as a reference.
stouset 2y ago
I believe the equivalent ARM64 instructions are in SVE2 which isn’t yet supported on Apple’s M-series chips as of M4, sadly.

rgrmrts 2y ago

I really like all the blog posts and videos the Zed team has put out, thank you if you’re reading this! Unrelated to this specific post I’m such a fan of Zed. It’s the first feature complete text editor in recent memory that I’ve truly enjoyed using (i.e. it stays out of the way, is really fast, feels well engineered). I’m coming to Zed after years of Emacs which I still have love for but no longer feels like a competitive piece of software (it does not take full advantage of how good computers are today, e.g. gpu rendering or multicore). I really hope Zed stays a fast and lightweight text editor instead of becoming some bloated growth-at-all-cost VC ware (not that they’ve exhibited any signs of that happening). I’d also happily pay for Zed without a subscription based thing for access to LLM features (which I do not use).

seanw444 2y ago
> it does not take full advantage of how good computers are today, e.g. gpu rendering or multicore Why does Emacs need that though? I hear people say this all the time and I don't get it. Multicore kind of works against the structure that Emacs touts as a feature. And GPU rendering? In many applications, I totally agree with these complaints. But it's a text editor. I tried Zed myself, and it's good. But it doesn't dethrone Emacs (for me personally).
- PittleyDunkin 2y ago
  > Multicore kind of works against the structure that Emacs touts as a feature. I have consistent issues with emacs locking up when executing network requests. I'm sure there's a specific bug that could be hunted down and addressed, but this sort of thing shouldn't happen much in an editor that's multicore by default. I'm not trying to dismiss emacs' reasoning, of course, but I can understand being disgruntled with it. The actual rendering I've been quite please by, though!
  - rgrmrts 2y ago
    Yeah this is one reason, or Emacs freezing for up to a minute when updating packages. Also when using an LSP I notice latency. I use Emacs GUI (outside of the terminal) and comparing performance for rending to something like Zed or Sublime is definitely noticeable. It’s great that Emacs is so resource efficient but sometimes I wish it used more of my beefy computer(s). Like I said I still love Emacs and it’s okay for it to make a different set of trade-offs. I honestly didn’t think I’d ever switch editors but here we are!

dmitrygr 2y ago

> // Parallel bit count intermediates > let a = v - ((v >> 1) & (u64::MAX / 3)); > let b = (a & (u64::MAX / 5)) + ((a >> 2) & (u64::MAX / 5)); > let c = (b + (b >> 4)) & (u64::MAX / 0x11); > let d = (c + (c >> 8)) & (u64::MAX / 0x101); That "parallel bit count" is almost certainly slower than using two POPCNT instructions on a modern cpu. Should just call __builtin_popcount() and let the compiler do it the most optimal way. Luckily, people do this sort of thing so often that many modern compilers will try (and often succeed) to detect you trying this insanity and convert it to a POPCOUNT (or a pair of POPCOUNTs as the case may be here)

akoboldfrying 2y ago
Which compilers support __builtin_popcount()? From memory, it's a gcc extension. If the compiler selects a CPU POPCOUNT instruction for it, are you sure it will work on all machines that you want to run it on? The above code is completely source- and binary-portable and reasonably fast -- certainly faster than naively looping through the bits, and within a small constant factor of a CPU POPCOUNT instruction.
- woadwarrior01 2y ago
  > Which compilers support __builtin_popcount()? Clang supports __builtin_popcount() too. And MSVC has __popcnt().
- dmitrygr 2y ago
  Your compiler will know the best way to popcount, that is the point of that builtin. It'll use the best method - sometimes this one. GCC does this, MSVC does this, clang does this, i think even rust has some way to do it (EDIT: it does: count_ones()). On archs which lack POPCNT, it will use this method or another, based on knowing the target. On x86 this approach is OK as is. On arm64, for example, it will be suboptimal due to all the literals needed. On armv6m, this method is bad and table lookups are faster.
  - SkiFire13 2y ago
    Note that by default rustc targets x86-64-v1 when compiling for x86-64, and that lacks the popcount instruction. You need to change the target_cpu to at least x86-64-v2 or enable the popcount target_feature. This means that even if your cpu is relatively new and you intend to run your code on relatively new cpus, rustc will still generate older and slower code for count_ones() using bitshifts and masks. That said, I don't see the point in writing them manually if the compiler can generate them for you.

ramon156 2y ago

Isnt the tab example wrong? Id assume it to be aa -> -> bb -> -> bb It only takes up two spaces, after all

sapiogram 2y ago

Is there a way to adjust text contrast in light mode in Zed yet? The editor is unfortunately unusable for me, because of how washed out the colors are.

mattbaker 2y ago
There are themes now and a UI to install them, I also didn’t like the washed out colors.
- onyno 2y ago
  Moved to zed a while ago. I’m using a light theme - Xcode low key now (With some settings to turn off the bold fonts).
- sapiogram 2y ago
  Have you found a light theme you're happy with? Which one?

Am4TIfIsER0ppos 2y ago

> opacity: 0; > filter: blur(1px); Wonderful styling!

dzaima 2y ago

SIMD can work quite well here too - with 128-bit SIMD (available on both baseline x86-64 and aarch64) this can be just ≤8 loop iterations checking for the newline character (each iteration counting the number of newline characters encountered, and a lzcnt on the last iteration), and similar for characters (assuming valid UTF-8, it's a single comparison to test if a byte starts a new char).

eviks 2y ago

Why not store just a small u8 count of newlines in a chunk instead of their u128 positions and then only loop through the last chunk for precision? You don't need information about the position of newlines in all the chunks located before the one your offset lands on

teo_zero 2y ago
As I understand it, they do exactly what you say. TFA is about optimizing the last chunk's loop.
- eviks 2y ago
  Maybe I got confused, but how do they then count the newlines in all the previous chunks? That information is still needed to calculate the line for a specific position in the last chunk
  - teo_zero 2y ago
    It's not you who's confused, it's that this part of the process is not described. We only have some hints, here: > If you called rope.offset_to_point(7234), the Rope would traverse its SumTree to find the Chunk that contains offset 7234 and then, on that Chunk, it would call offset_to_point again. And here: > while the Rope can get us to the right Chunk in O(log(n)) I would guess that each node of the SumTree includes the number of newlines of all the chunks before it.
  - DylanSp 2y ago
    It's outlined in their previous post on the Rope/SumTree data structure they use, which this article links to: https://zed.dev/blog/zed-decoded-rope-sumtree https://zed.dev/blog/zed-decoded-rope-sumtree.

benreesman 2y ago

I really want to admire the Zed folks even though they are a new faction in the editor wars where I’m an emacs guy: they take mostly all the things I care about seriously. The are serious about local vs. remote vs. shared. They are serious about hardware acceleration because they care about users who type fast and edit big files. They care about real computer science on how to push the current hardware to serve the user, rather than treating the hardware as a crutch to give the user a slightly worse experience at a fraction of the development cost. They care about code highlighting the snippets on their blog like very similar to the default Zed theme. These are cool, serious people. If they give me emacs key bindings with full paredit-everywhere, I might switch my daily driver. And this is about using modern SIMD-style stuff, branch less stuff, Lemire stuff in a modern and relevant context. Other commenters have pointed out that you can do the mask or popcount better with intrinsically, and yeah, but they probably know that, and B. They got the massive win, the remaining factor of K on the pop count is coming. Long Zed.

m1keil 2y ago

This is all really cool, but I just want soft wrap to be fixed

veltas 2y ago

> Turns out CPUs are pretty good with zeros and ones. I've been saying this a lot recently, that CPU's are powerful 1-bit vector machines!

eliasson 2y ago

Does anyone know of any good presentations about the Zed architecture and internals around? I know that they have some recordings from their coding session, but I am looking for something more overall.