←back to thread

Bit-twiddling optimizations in Zed's Rope

(zed.dev)
168 points misternugget | 1 comments | 18 Nov 24 16:39 UTC | HN request time: 0.351s | source
Show context
eviks ◴[21 Nov 24 04:10 UTC] No.42201015[source]▶
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

replies(1): >>42201548 #
teo_zero ◴[21 Nov 24 06:01 UTC] No.42201548[source]▶
As I understand it, they do exactly what you say. TFA is about optimizing the last chunk's loop.
replies(1): >>42201664 #
eviks ◴[21 Nov 24 06:25 UTC] No.42201664[source]▶
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
replies(2): >>42201856 #>>42209413 #
1. DylanSp ◴[21 Nov 24 22:37 UTC] No.42209413[source]▶
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.