←back to thread

Bit-twiddling optimizations in Zed's Rope

(zed.dev)
120 points misternugget | 5 comments | 18 Nov 24 16:39 UTC | HN request time: 0.215s | source
1. camel-cdr ◴[20 Nov 24 21:29 UTC] No.42198301[source]▶
nth_set_bit_u64: wouldn't that be __builtin_ctzll(_pdep_u64(1<<n, v)) with BMI2?
replies(3): >>42198733 #>>42199867 #>>42200581 #
2. SkiFire13 ◴[20 Nov 24 22:21 UTC] No.42198733[source]▶
That's assuming you're ok with your program not running on some older cpus.
replies(1): >>42200177 #
3. kwillets ◴[21 Nov 24 00:48 UTC] No.42199867[source]▶
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.

4. zamadatix ◴[21 Nov 24 01:41 UTC] No.42200177[source]▶
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.
5. stouset ◴[21 Nov 24 02:46 UTC] No.42200581[source]▶
I believe the equivalent ARM64 instructions are in SVE2 which isn’t yet supported on Apple’s M-series chips as of M4, sadly.