33 ms·

> There’s nothing stopping you from using it in an interactive environment. What else does a text editor do that would make JumpropeBuf not appropriate in an in

> There’s nothing stopping you from using it in an interactive environment. What else does a text editor do that would make JumpropeBuf not appropriate in an interactive editor? I wouldn't say it's "not appropriate" just that it is not applicable. JumpropeBuf is really design (as I see it) for handling large numbers edits to the same location. Which is exactly what we have in the tracing benchmarks. But in an "realworld" "interactive" environment usually after every edit there are follow up operation like rendering to the screen, sending change set to language servers or linters, running syntax highlighting etc. So you want those edits to applied immediately, not buffered. I understand this is probably different in the CRDT case where you could have swarms of edits coming from other clients. In that case I can see buffering being useful. And as you pointed out, all of these data structures are more then fast enough at the scale of the tracing benchmarks. That being said, it's interesting that piece tables are kind of a similar idea, expect they never actually apply the edits. They just keep them buffered and parse the buffer when they need to get the current state of the text. I wonder if JumpRopeBuf could become something similar. Basically a piece table the occasionally merges the edits to avoid fragmentation.

josephg 3y ago
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!

josephg 3y ago

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!