←back to thread

Bit-twiddling optimizations in Zed's Rope

(zed.dev)
120 points misternugget | 3 comments | 18 Nov 24 16:39 UTC | HN request time: 0s | 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 #
1. 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 #
2. 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(1): >>42201856 #
3. teo_zero ◴[21 Nov 24 07:05 UTC] No.42201856[source]▶
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.