Re:Text Showdown: Gap Buffers vs. Ropes
by josephg on Tuesday October 10, 2023 @01:17AM
(#37828750)
Re: a real editor, I guess my question is what queries are made to the rope data structure between edits? If those queries are trivial, we might be able to implement them without disturbing the buffer. (So, an order of magnitude extra performance). And if they’re nontrivial they’d dominate the time spent in the rope data structure for a typical text editor. So the benchmarks we’ve been writing aren’t actually testing the right things!
> I wonder if JumpRopeBuf could become something similar. Basically a piece table…
Maybe, but I doubt it would help.
The reason why JumpropeBuf improves performance over Jumprope is because it doesn’t need to traverse into the skip list structure to make adjacent changes in the most common case (when the new edit happened at the same location as the last change). Basically it’s a micro optimization for a common case. And it provides value because it’s so dead simple that it manages to be an order of magnitude faster than the skip list. I think if you added a full piece table in there, the overhead of piece table operations would be similar to the overhead of modifying the skip list itself. So at that point, the benefits from the JumpropeBuf approach would vanish. And I already have a pretty fast data structure for merging changes at arbitrary locations in the skip list & gap buffer at each node.
In short, I think adding a piece table in front would necessitate deoptimizing for the common case (edit at the last location) without adding real value over what the skip list is already doing.
By all means try it though. I’d love to be proven wrong!
> I wonder if JumpRopeBuf could become something similar. Basically a piece table…
Maybe, but I doubt it would help.
The reason why JumpropeBuf improves performance over Jumprope is because it doesn’t need to traverse into the skip list structure to make adjacent changes in the most common case (when the new edit happened at the same location as the last change). Basically it’s a micro optimization for a common case. And it provides value because it’s so dead simple that it manages to be an order of magnitude faster than the skip list. I think if you added a full piece table in there, the overhead of piece table operations would be similar to the overhead of modifying the skip list itself. So at that point, the benefits from the JumpropeBuf approach would vanish. And I already have a pretty fast data structure for merging changes at arbitrary locations in the skip list & gap buffer at each node.
In short, I think adding a piece table in front would necessitate deoptimizing for the common case (edit at the last location) without adding real value over what the skip list is already doing.
By all means try it though. I’d love to be proven wrong!