Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bit-twiddling optimizations in Zed's Rope

zed.dev

Post reply on HN
Print view View original

21–30 of 51 posts

Re: Bit-twiddling optimizations in Zed's Rope

#21

Post by Findecanor »

dmitrygr wrote: post #8
akoboldfrying wrote: post #4

Earlier quoted context omitted.

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 subopti…

I once wrote that algorithm, divided into single lines, intending each line to be a single 64-bit ARM instruction. The compiler did idiom detection, transforming it to "builtin popcnt" and (because 64-bit ARMv8.0 lacks a POPCNT instruction) back to the same algorithm. Only that the emitted code was one instruction larger than my code.

64-bit ARM's actually has a very peculiar encoding of immediates to arithmetic instructions. It supports only recurring bit patterns such as used by this algorithm. For example "add x2, x3, #3333333333333333" is encoded as one four-byte instruction.

Re: Bit-twiddling optimizations in Zed's Rope

#22

Post by canucker2016 »

donio wrote: post #20
vinkelhake wrote: post #17

Earlier quoted context omitted.

> But it's a text editor. Long time emacs user here (+20 years, yikes). I've used it on all kinds of computers during this time. Even a relatively modest computer from 2024 is an absolute beast compared to something from the year 2000. With that said, there are text editing operations that can cause it to grind to a complete halt, especially working with large files (or very long lines). And it shouldn't , you know?…

> (or very long lines) Long line handling has greatly improved in emacs-29. Multi-megabyte lines are not a problem anymore.

from Emacs 29.1 NEWS file, https://raw.githubusercontent.com/emacs-mirror/emacs/refs/he...

    ** Emacs is now capable of editing files with very long lines.
    The display of long lines has been optimized, and Emacs should no
    longer choke when a buffer on display contains long lines.  The
    variable 'long-line-threshold' controls whether and when these display
    optimizations are in effect.

    A companion variable 'large-hscroll-threshold' controls when another
    set of display optimizations are in effect, which are aimed
    specifically at speeding up display of long lines that are truncated
    on display.

Re: Bit-twiddling optimizations in Zed's Rope

#24

Post by stassats »

Findecanor wrote: post #21
dmitrygr wrote: post #8

Earlier quoted context omitted.

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 subopti…

I once wrote that algorithm, divided into single lines, intending each line to be a single 64-bit ARM instruction. The compiler did idiom detection, transforming it to "builtin popcnt" and (because 64-bit ARMv8.0 lacks a POPCNT instruction) back to the same algorithm. Only that the emitted code was one instruction larger than my code. 64-bit ARM's actually has a very peculiar encoding of immediates to arithmetic inst…

> because 64-bit ARMv8.0 lacks a POPCNT instruction

It does have this: https://developer.arm.com/documentation/ddi0596/2021-09/SIMD...

And GCC happily uses it https://godbolt.org/z/dTW46f9Kf

Re: Bit-twiddling optimizations in Zed's Rope

#28

Post by PittleyDunkin »

seanw444 wrote: post #15
rgrmrts wrote: post #14

Earlier quoted context omitted.

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…

That's fair I guess. In the case of IO that can be an issue. When I hear multicore, I assume we're talking about parallelism, not concurrency. As for LSP, other than the Nim langserver, I've been quite satisfied with Eglot's performance. I'm curious what your setup is like. To be fair, I'm running a highly customized Doom Emacs config, so it's possible I inherited some non-vanilla optimizations I'm not aware of.

> When I hear multicore, I assume we're talking about parallelism, not concurrency.

Parallelism trivially enables concurrency. The lack of parallelism magnifies the issues emacs has with concurrency.

Re: Bit-twiddling optimizations in Zed's Rope

#29

Post by zamadatix »

SkiFire13 wrote: post #13
camel-cdr wrote: post #5

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

That's assuming you're ok with your program not running on some older cpus.

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.

Re: Bit-twiddling optimizations in Zed's Rope

#30

Post by vlovich123 »

SkiFire13 wrote: post #12
dmitrygr wrote: post #8

Earlier quoted context omitted.

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 subopti…

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…

It's not unreasonable to think that Rust will change the minimum version and you should always override the target cpu anyway for C++-like toolchains when building production binaries (`-Ctarget-cpu` for rust, `march=` for clang/gcc).
Post reply on HN