Bit-twiddling optimizations in Zed's Rope
1–10 of 51 posts
Re: Bit-twiddling optimizations in Zed's Rope
#2I 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).
Re: Bit-twiddling optimizations in Zed's Rope
#3 > // 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);
Re: Bit-twiddling optimizations in Zed's Rope
#4> // 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 optim…
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.
Re: Bit-twiddling optimizations in Zed's Rope
#5nth_set_bit_u64: wouldn't that be __builtin_ctzll(_pdep_u64(1<<n, v)) with BMI2?
Re: Bit-twiddling optimizations in Zed's Rope
#6> // 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 optim…
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.
> Which compilers support __builtin_popcount()?
Clang supports __builtin_popcount() too. And MSVC has __popcnt().
Re: Bit-twiddling optimizations in Zed's Rope
#7I 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 compe…
> 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).
Re: Bit-twiddling optimizations in Zed's Rope
#8> // 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 optim…
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.
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.
Re: Bit-twiddling optimizations in Zed's Rope
#9> // 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 optim…
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.
Most vaguely recent compilers will convert naively looping through bits into a native POPCOUNT instruction. The parallel bit count algorithm was not reliably detected until more recently and therefore would sometimes produce unoptimized code, though current versions of gcc/clang/msvc can all detect it now.
Also, pretty much every compiler for a very long time has supported __builtin_popcount or equivalent.
Re: Bit-twiddling optimizations in Zed's Rope
#10I 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 compe…
> 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 d…
> 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!