Text showdown: Gap Buffers vs. Ropes
coredumped.dev
coredumped.dev
That said, it's not measuring what I would measure. The jumprope benchmarks are reported as the total time to complete a number of tasks. To me, the massive strength of the rope data structure is its O(log n) worst case performance when performing a simple operation such as inserting or deleting a character. That translates into user-perceivable latency. If you have a sequence of a thousand edits, and your rope accomplishes each in 200µs, while your gap buffer has a mean of 100µs but variance extending to 10ms, then I'd much prefer the former, even though this benchmark would indicate the latter is 2x faster.
It’s also ignorant of the heavily pipelined nature of input and output on modern computers. If you add up all of the latency from the time you press a key on the keyboard to the time a character appears on the screen — even if you subtract all the time spent inside your text editor — it adds up to many ms of delay. Now the author thinks it’s okay to add another 20-100ms to that just for the basic data structure holding the text? No thank you!
Edit: I have to add this link to a classic post by Dan Luu [1]. The Apple IIe leads the pack with 30ms latency from keystroke down to character on the screen. 20ms for a data structure (in the key-to-screen critical path) on a 2023 computer, even if it only occurs 1% of the time, is totally unacceptable.
NB. Elite running on Emacs https://www.salkosuo.net/2015/10/22/elite-for-emacs.html
We are talking about the worst case when the buffer needs to be resized. This is not for every character. Just once in a while while editing very large texts.
Not that it makes it acceptable. But also not as bad as what you're making it sound.
Also I expect if that was a real problem you could probably implement a system where you have more than one gap. Does that exist?
That is a really cool idea! I actually tried implementing that. However I gave up because the code became quite a bit more complex, but it would totally be possible! That being said, multiple gaps would only help the "move gap" latency, they wouldn't help with the resizing latency. The later is both less predictable and much higher then moving the gap. Also when you need to coalesce the text for searching you would loose all your gaps.
It means an insertion anywhere just involves M character moves where M is the number of ring buffers.
The data layout won't quite be as nice as a gap buffer (2 chunks), instead you get 2*M chunks. But if you make your ring buffers like 10MB it's probably fine.
Could'nt you avoid resizing by massively over allocating in the first place? A decent OS, hint Linux, would only map pages to the allocated memory pages once they are touched.
On the other hand, does speed really matter for small files?
Handling uncommon scenarios gracefully is important.
VSCode is slightly laggy for me just editing a 10k line text file, so my standards are sadly not that high, even though I find typing latency really annoying.
For example, dragging an item around a screen with your finger, 100ms is definitely noticeable. Typing seems to be less although I had a coworker claim he could. So it’s hard to say if we don’t notice it vs we’ve just become accustomed to interacting with text with 100ms of latency (or something about the task of typing is more latency insensitive).
I would be interested in seeing the the same data driven analysis for human factors as HCI is even less intuitive than computer algorithm performance.
Searching is not a particularly latency sensitive task as your next match is probably significantly within 1 gib where you’re paying 250ms at worst. But yeah, if regex searching is the task to optimize around, ropes in Rust won’t work well due to the lack of incremental search at this time.
Again, I’m not saying you won’t notice it, but I know I’m a very fast typer and when I was working on Oculus AirLink we had a prototype virtual desktop thing and I know I personally didn’t really notice any lag despite our internal metrics saying ~100ms of latency (we’d artificially inject extra latency for studies). It may be people differences, but keep in mind that how you measure is also important and almost no one measures true key stroke to display latency nor do they run human factors studies to accurately characterize if there really is anyone who does notice it (even at Oculus - most studies are very poor quality often with limited sample size, skewed population, and very poor reproduction/analysis because the time allotted for these projects is just enough to try to get guidance on next steps)
While I have you, how close is the Rust incremental search support? It sounded like regex-automata might make it possible but hard to easily get a sense of high level progress from a GitHub issue.
> While I have you, how close is the Rust incremental search support? It sounded like regex-automata might make it possible but hard to easily get a sense of high level progress from a GitHub issue.
I'm not working on it. The current status is that other people are working on trying to write it themselves on top of regex-automata in a way that works for their specific use case. That was my high level strategy: release a separately versioned library with the regex internals[1] exposed so that others can experiment and build on top of it.
The regex-automata crate exposes the low level DFA (and lazy DFA) transition function. So you can pretty much do some kind of stream searching out of the box today (certainly at least what Go provides): https://docs.rs/regex-automata/latest/regex_automata/#build-...
Bottom line here is that if you're looking to implement stream searching in Rust, then you should be able to go out and build something to do it today with regex-automata. But you aren't going to get a streamlined experience. (And whether you ever will or not remains unclear to me.)
The regexp.Regexp.FindReaderIndex and .FindReaderSubmatchIndex methods tell you the position of the match.
Thanks for the correction!
Unless you don't mind implementing a couple dozen lines yourself. The regex_automata crate allows you to directly access the DFA, so with iteration through the rope and a bit of state tracking you can already do this, just not as convenient (yet) as a single method call.
https://github.com/rust-lang/regex/issues/425#issuecomment-1...
https://github.com/helix-editor/helix/pull/211#issuecomment-...
for typing characters into a text box this is not imperceptible. it should happen in a single frame.
It’s interesting seeing how poorly jumprope does on memory efficiency. I could definitely change the code to more aggressively join small text nodes together to bring the memory overhead more in line with the other algorithms. I’m just not sure how much anyone cares. Text is really small - a raspberry pi or phone has gigabytes of memory these days. If a 1mb text document takes up 5mb of ram - well, does that matter? I suppose if you’re opening a 1gb log file I do appreciate that some of the other approaches tested here have no overhead until you start making edits.
From a performance standpoint there’s one more trick jumprope has not mentioned here, though it could easily be applied to the other algorithms. And that is, in regular text editing sessions (and in replaying CRDT editing traces) we can buffer the most recent editing run before committing it to the data structure. So, if you start typing some contiguous characters, they get stored separately and only when you move the cursor or start deleting do we flush that change down. This improves performance of replaying editing traces by nearly 10x. But I’m not sure how applicable it is to the “regular” case of text editing. It is, however, super useful for replaying edits in a collaborative editor. It’s fast enough that my crdt doesn’t even bother storing the most recent document on disk - we just replay the entire editing history when a document is opened. Even for large documents, files can usually still be opened in about 1ms (including replaying the entire editing trace). This case doesn’t show up in all benchmarks because you have to opt in to it using the JumpropeBuf wrapper instead of Jumprope.
I did some testing with JumpRopeBuf, but ultimately did not include it because I was comparing things from an "interactive editor" perspective where edits are applied immediately instead of a collaborative/CRDT use case where edits are async. But it did perform very well as you said! I feel like JumpRopeBuf feels similar to a piece table, where edits are stored separately and then joined for reading.
Mind you, at the speeds all these systems operate at, all of the rope libraries you benchmarked should be plenty fast enough not to be a bottleneck in interactive editing anyway. Maybe the nearby posters are right; and the biggest optimization issues remaining are those that only come up when handling 10gb+ documents.
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.
> 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!
Tell that to my 10GB JSON files.
You’re on your own with that one. Sounds like a job for SQLite, not a rope library.
Though note that in many cases long lines are also important to consider - many editors struggle hard and become near unusable if the line on screen is e.g. 1MB long (which again isn't as uncommon as you'd think).
Text files are sometimes not that small. It's not that unusual to have a multigigabyte text log, sometimes larger than system RAM on the machine.
Every time this point comes up in the design of text editors, I feel compelled to mention that memory bandwidth is dozens of GB/s on modern hardware; even when it was only a few MB/s a few decades ago, text editors that used a single contiguous buffer (not even a gap) were very common and no one complained about their speed. Indeed, the benchmarks in this article confirm that.
As another popular article that's often submitted here says: computers are fast --- very fast for human timescales, and in particular manipulating text of humanly-encountered sizes. More performance is lost in unnecessary abstraction and belief that "clever" optimisations (like theoretically-optimal but considerably more complex data structures) work, when they actually turn out the opposite.
There's a lot of dogma around advanced text editor structures and what is "optimal", and IMHO a lot of that is totally unneeded accidental complexity created by those more interested in theoretical daydreaming than real-world solutions. Thus, I think even a gap buffer is "overkill", and a single "gapless" buffer is really sufficient. Don't overthink things.
Basically: if you need to make a gap, split the page it’s on into two (so your region copy is always less than one page long). You can start the copy into the middle of second page or not (I don’t actually think that’s an optimization in practice but have never measured it).
If you get a lot of fragmentation you can have a background process that does coalescence away from the active insertion point.
I’ve used this technique a few times over the decades in non-editor applications with large sorted vectors.
I was a bit surprised, though, with how it ends right after the search benchmark. This seems like the perfect setup to talk about search/replace (aka find/replace), which seems like the best use case for non-local edits that I can think of, and therefore would be a great opportunity to show how the algorithms compare in something the ropes should be better at.
https://code.visualstudio.com/blogs/2018/03/23/text-buffer-r...
I’m not really up-to-date on any text editing implementation details, so if this is basic/common knowledge feel free to just tell me to Google it.
I think this comes down to two things:
1. Fragmentation. When a rope splits a string into two by inserting into it, it is able to rejoin the pieces to form a new string, which "greatly reduces space consumption and traversal times" (quote from the first paper on ropes: https://www.cs.tufts.edu/comp/150FP/archive/hans-boehm/ropes... ).
2. Proximity of nodes. In a Piece Tree, all of the inner nodes contain {start, length} piece data. You can construct the whole string represented by the Piece Tree through an in-order traversal. In contrast, the Rope only stores data at the leaves of the tree.
Imagine you are at the root of a Piece Tree that looks like this (where o = a node containing a piece).
o
/ \
o o
/ \ / \
o oo o
c
/ \
v v
/ \ / \
o cc o
What are ropes like in contrast?
v
/ \
v o
/ \ / \
c co o
(A Piece Table/Piece Tree is able to avoid creating new nodes if you insert consecutively, one character after another without backtracking to edit a previous part, since you could just extend the length of the piece. Real life benchmarking data tells me that's not a big advantage though: the text retrieval time is still embarrassingly bad.)
It's good to see Jetbrains avoid the Piece Table and its variants for Fleet (where they mention using a rope).
https://blog.jetbrains.com/fleet/2022/02/fleet-below-deck-pa...
(Note that the rope diagram I posted copies two strings and the Piece Tree copies three, which might be considered unfair. I didn't want to extend the rope diagram to make it copy three strings, but I would say this is actually an accurate depiction of reality considering the fragmentation the Piece Table/Tree has, meaning more nodes to visit.)
A quick search brings up only references in the 1990s or later...
Emacs was initially just a bunch of macros (in Eugene Ciccarelli's TECO init file IIRC) that provided an easier interface to TECO once a realtime display mode (^R mode of course!) had been added.
Yes, in TECO, control R was a keyword in the language. If you don't know TECO it looks like line noise. For controlling an editor, that's not necessarily insane.
Alas, it does not discuss the gap buffer.
The book The Craft of Text Editing claims the gap buffer technique was first used by TECO (http://www.finseth.com/craft/#c6.6), although this claim is given no support.
These benchmarks include that time.
Find the position of the Nth line is O(1) because N is either before the gap, in which case you just look up the Nth entry in the line-tracking buffer to get the position in the text buffer (which can be similarly mapped back to a position not including the gap in constant time if that's what you need), or N after the gap and you adjust the arithmetic to include the size of the gap.
It doesn't directly matter where the gap is in the line-tracking buffer except ideally it's positioned consistent with the user's cursor so that if they insert a bunch of new lines, they're inserted into the line-tracking gap.
The position of the line-tracking gap doesn't effect the values stored on either side of it gap, so you can still use memmove there.
ptr = pos if pos<=gapstart else pos + gapsizebasically every leaf holds some metrics (say bytes and line endings) for some chunk of text. By just looking at the leaf we don't know which chunk it points to. But since the leafs are all in order, we can calculate their byte position and line ending by adding them up. If we add all the leaf we should get the total number of bytes and lines in the text. In order to avoid O(n) cost of summing every leaf, we store them in a tree, where each parent holds the sums of it's children. So when we want to find the byte position[2] of a particular line ending we can just walk down the tree and see if the line ending we are searching for is greater then the left child or not. If it is, we add the left child's sum to our running total and go to the right. Otherwise we go to the left. By the time we get to the leaf, we have summed all the chunks before it in O(logn) time.
Insertion/deletion are similar, except when we update the leaf, we also go and update each parent on the way back up.
[1] https://www.baeldung.com/cs/fenwick-tree
[2] https://github.com/CeleritasCelery/rune/blob/be243ea2bd385ec...
JumpRope combines a gap buffer with a skip list. Crop combines a gap buffer with a rope. ropey is a "traditional" rope that doesn't use a gap buffer under the hood.
> GB here means 2^30, as it should when talking about base-2 memory. The only people who think it should be 10^9 are hard drive salesmen and the type of people who like to correct all their friends by saying “It’s centripetal, not centrifugal force!”. Also “gibibyte” sounds like Pokémon invented by a first grader.
This attitude ruined it for me. You're a technologist. You should care about vocabulary and precision. You are on the wrong side of history for both of these things - a gigabyte is 10^9 bytes as per SI, and centrifugal force is fictitious.
I challenge you: If a 1 GHz processor can process 1 byte on every cycle, how long does it take to process a 1 GB file? Hopefully you'll see the error in your ways.
Fragmenting the definition of the giga- prefix based on context leads us down some dark paths that we already traversed with the pound-mass vs. pound-force, pound Avoirdupois vs. pound Troy, fluid ounce vs. weight ounce, US gallon and UK gallon, liquid bushel vs. dry bushel, different varieties of tons, statute mile vs. nautical mile, and the list goes on.
If you go to a computer parts store and ask for a 17.179869184GB DDR4 DIMM, you'll probably be laughed at and get some very strange looks.
Your contrived example is absurd; you just have to ask for 16 GiB of RAM, as per the proper definitions.
As for JEDEC, standards bodies are made of people and people are fallible.
Filesystem overhead notwithstanding, it's worth noting that NAND flash usually had true capacities too, with some additional hidden extra for error correction/wear-leveling. I have a 16MB SLC one that truly has 16,777,216 usable bytes (32M 512-byte sectors), and a slightly newer 2GB one with 2147483648 bytes.
Let's not forget the original IBM PC "10MB" hard drive held a little more than 10MB: 10653696 bytes, a bit more than the 10485760 one would expect.
No one seriously talks about "GiB", and the only ones I hear using it are pedantic assholes. It just sounds absurd and stupid.
As for JEDEC, standards bodies are made of people and people are fallible.
I can say the same goes for SI and their "iB" nonsense.
The Ki-, Mi-, Gi-, etc. prefixes aren't in SI. They're defined in IEC 60027 specifically to avoid conflicting with SI.
If you walked in an asked for 16 "gibibytes" of RAM they would just look at you funny. Or think you were non-native speaker.
I work in the hardware software boundary, and I have never once heard someone use the term kibibyte, mebibyte, or gibibyte in real life. Occasionally I will see KiB, MiB, and GiB in an academic paper, but that's about it. When I am talking with people and they say kilobyte, they always mean 1024. Trying to pretend otherwise would just cause unneeded confusion. That's what it meant went the term was coined, that what it meant when IEC tried to change the definition 25 years ago, and (unless you are selling hard drives) that's what it means to most people today.
I agree that it is unfortunate that they reused the terms from SI prefixes, since they are not SI prefixes. And if I had a time machine I would tell them to use different prefixes. But they didn't and those are the terms the world has adopted. It's also unfortunate that hard drive manufactures played fast and loose with the definition to pretend like their drives were bigger then they really were. Words are democracy, and they mean what people say they mean, not what the IEC says they should mean.
> As for JEDEC, standards bodies are made of people and people are fallible.
Exactly, so why is the IEC redefinition somehow more valid?
P.S. Don't forget how "1.44 MB" floppy disks are neither MB nor MiB; their definition is MB = 1024000 bytes. This free-for-all benefits no one. Hard drive manufacturers were right, RAM was wrong.
It sucks, but we lost that fight. GiB is a thing that people use.
It is not. It exists if you change your point of reference.