10 ms·

Text showdown: Gap Buffers vs. Ropes

zogrodea 3y ago
This is an interesting article. Not 100% sure about the implementation of JumpRope, but I think it combines a gap buffer together with a rope. Ropey (and I think Crop too?) also support cheap persistence.
- celeritascelery 3y ago
  I should have added a section on that. 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.
  - zogrodea 3y ago
    Thank you for writing the fun article and experiments! :)
scotty79 3y ago
I wonder if these benchmarks include the time spent on updating the tree that stores information where the lines begin. Because if you have a gap at the beginning of the buffer and you make an insert you need to update all of that information.
- celeritascelery 3y ago
  All the containers store the metrics (line endings, unicode codepoints, UTF-16 codepoints, etc) in a tree. The tree stores the value of all it's children summed up. So if if you do an insert at the start you only need to update a single branch. When calculating the line count you have to walk down the tree summing all the children as you go. But this means updating and lookup are both logn instead of having to update N nodes. These benchmarks include that time.
  - ahefner 3y ago
    A neat trick with gap buffers is you can track the line boundaries as indices into the gap buffer itself rather than 'real' indices into the document. In this way the indices of line starts seldom change except when the gap buffer is resized. You can then keep a second gap buffer, this one recording the start of line indices, and keep its gap in sync with cursor movement in the text gap buffer, making insertion cheap and giving a trivial way to map from line numbers to a position in the gap buffer. No trees necessary.
    - celeritascelery 3y ago
      hmm. What happens when you move the gap from the front to the end of the text (or vice versa)? wouldn't that require you to update all the line boundaries? And wouldn't finding the position of the Nth line be O(n).
      - ahefner 3y ago
        Moving the gap from front to end - it takes O(n) time to do that both on the text (gap) buffer and the line-tracking (gap) buffer, so you're only a small constant factor worse. 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.
        celeritascelery 3y ago
        This does seem like a really neat trick I have not heard of before. I am still confused about moving the gap in the line-tracking buffer. It seems to me the only way you could make look-up O(1) is if you updated all the line indexes you passed over when you moved the gap. Because they are pointing to absolute positions (right?). So moving the line-tracking gap would technically be O(n), but you couldn't use memmove, and instead would need to iterate over one and add or subtract the gap size. Am I misunderstanding?
raphlinus 3y ago
Interesting article, and I love to see performance numbers to back up engineering decisions. I'm also glad xi-rope wasn't included, as I'm sure it's performance lags :) 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.
- loeg 3y ago
  Also, the author is quick to dismiss 20-100ms latencies as imperceptible, or nearly so. That is too high.
  - chongli 3y ago
    Yeah. 20ms is more than a full frame at 60hz. This sort of delay is unacceptable in 3D games! And here we’re talking about inserting a character into the data structure used to keep track of edits to a text file! 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. [1] https://danluu.com/input-lag/ https://danluu.com/input-lag/
    - kaba0 3y ago
      Maybe reread the relevant part of the article. It’s not average case at all.
gumby 3y ago
In a modern OS, you can combine the gap and the piece table approaches using the MMU to eliminate most copying in the common cases. 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.
- kammerdiener 3y ago
  Do you have any more info on this?
  - gumby 3y ago
    I thought my comment was pretty comprehensive on the technique. Is there something that was unclear? I can clarify. I’ve used this technique a few times over the decades in non-editor applications with large sorted vectors.
    - PH95VuimJjqBqy 3y ago
      Not only was it clear but it's the approach that popped into my head immediately while reading the article.
    - kammerdiener 3y ago
      Your explanation was just fine. I was simply asking what else you knew about the technique. Perhaps where you first heard of it or some examples where it has been applied/benchmarked.
jll29 3y ago
I'm curious: who invented gap buffers originally? Do we know if it was RMS? What was the first peer-reviewed publication describing or mentioning them? A quick search brings up only references in the 1990s or later...
- gumby 3y ago
  Emacs uses a gap buffer because TECO used one, long before RMS finished high school. 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.
  - cbsmith 3y ago
    Yeah, gap buffers LONG predate RMS.
  - jwstarr 3y ago
    The author of TECO, Dan Murphy, wrote an article about its history for the IEEE Annals of the History of Computing. A PDF copy of the article is available here: https://opost.com/tenex/anhc-31-4-anec.pdf https://opost.com/tenex/anhc-31-4-anec.pdf 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 http://www.finseth.com/craft/#c6.6), although this claim is given no support.
    - gumby 3y ago
      Thanks for that reference — I’d never seen it. I’ll be happy never to write any more TECO in my life, but that doesn’t mean I’m not interested.
josephg 3y ago
Author of jumprope here. Great post! It’s cool seeing so many other good rope libraries ready to use. 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.
- IshKebab 3y ago
  > Text is really small Tell that to my 10GB JSON files.
  - kaba0 3y ago
    Arguably, different algorithm could be used for that and for “normally” occurring files.
  - pphysch 3y ago
    You're opening those in a text editor?
subarctic 3y ago
I really like this article's structure for showing benchmarks. each benchmark has its own heading and a paragraph explaining the reason for it and analyzing the results. 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.
nayuki 3y ago
A fantastic article that goes into a lot of depth and rigor until I got to the very end: > 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.
- kaba0 3y ago
  > centrifugal force is fictitious It is not. It exists if you change your point of reference.
- userbinator 3y ago
  1KB is 1024 bytes per JEDEC. 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.
  - nayuki 3y ago
    Good luck fitting a 16 "GB" RAM dump on a 16 GB flash drive when you hibernate the computer. 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.
    - userbinator 3y ago
      Good luck fitting a 16 "GB" RAM dump on a 16 GB flash drive when you hibernate the computer. 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.
jiggawatts 3y ago
Notably, most modern text editors such as Visual Studio Code use neither of those. They use "piece tables", which have a number of advantages. For example they allow efficient incremental saves and the list of edit changes can be trivially wound back or replayed for undo/redo. https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation https://code.visualstudio.com/blogs/2018/03/23/text-buffer-r... https://en.wikipedia.org/wiki/Piece_table https://en.wikipedia.org/wiki/Piece_table
- throwaway17_17 3y ago
  Do you know of any assessment of performance characteristics for said ‘piece tables’? The thrust of TFA is essentially a performance comparison, so I can’t help but wonder why this implementation wasn’t addressed if it is present in one of the most widely used code editors. Also, VS Code is not known for its responsiveness for text editing, is this due to the ‘piece table’, or more likely, due to architectural decisions in the application more generally? 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.
  - rudedogg 3y ago
    https://www.cs.unm.edu/~crowley/papers/sds/sds.html https://www.cs.unm.edu/~crowley/papers/sds/sds.html
- zogrodea 3y ago
  I implemented a Piece Tree like VS Code's not long ago and found the insert/delete performance fine, but performance for text retrieval (line retrieval, substring) queries wwas embarrassingly bad. Like, 10x slower than the other ropes I compared it with. 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.pdf 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 Say you want to get a substring from (root - 1) to (root + 1), one character before the tree's root up to one character after the root. How many tree nodes do you need to visit? We can understand by reminding ourselves that "the whole string can be reconstructed through an in order traversal", letting us know the order we need to visit nodes in. c / \ v v / \ / \ o cc o (where c = a node whose string we copy and v = a node we visit on our way to a node we need to copy). That is two separate O(log n) queries we make from the root of the tree for our substring operation. What are ropes like in contrast? v / \ v o / \ / \ c co o You do still need basically two O(log n) queries, but not from the tree's root. You find the inner metadata node where the start of the substring and the end of the substring (and all strings in between) can be reached and make an in-order traversal from there, which is less traversal time. This, combined with the lower fragmentation that ropes enable (or rather that high fragmentation the Piece Tables have), makes them faster than Piece Trees in my experience. (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-part-ii-breaking-down-the-editor/ 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.)
userbinator 3y ago
The simplest approach is to just use a large string or array of lines. However these each suffer from poor performance as either the size or line length of text increases. 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.
- hoseja 3y ago
  And yet, search-and-replace on big files takes seconds.
  - kaba0 3y ago
    I can grep through half my file system in seconds. What do you measure?
- PH95VuimJjqBqy 3y ago
  I don't know this authoritatively, but I believe vim uses a simple array internally. And it works well.
sfink 3y ago
When you resize a large gap buffer, it seems like you could mremap the pages after the gap and avoid almost all copying. The usual alignment problems don't apply since you can adjust the position and size of the gap slightly as needed to accommodate.

This is an interesting article. Not 100% sure about the implementation of JumpRope, but I think it combines a gap buffer together with a rope. Ropey (and I think Crop too?) also support cheap persistence.

celeritascelery 3y ago
I should have added a section on that. 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.
- zogrodea 3y ago
  Thank you for writing the fun article and experiments! :)

scotty79 3y ago

I wonder if these benchmarks include the time spent on updating the tree that stores information where the lines begin. Because if you have a gap at the beginning of the buffer and you make an insert you need to update all of that information.

celeritascelery 3y ago
All the containers store the metrics (line endings, unicode codepoints, UTF-16 codepoints, etc) in a tree. The tree stores the value of all it's children summed up. So if if you do an insert at the start you only need to update a single branch. When calculating the line count you have to walk down the tree summing all the children as you go. But this means updating and lookup are both logn instead of having to update N nodes. These benchmarks include that time.
- ahefner 3y ago
  A neat trick with gap buffers is you can track the line boundaries as indices into the gap buffer itself rather than 'real' indices into the document. In this way the indices of line starts seldom change except when the gap buffer is resized. You can then keep a second gap buffer, this one recording the start of line indices, and keep its gap in sync with cursor movement in the text gap buffer, making insertion cheap and giving a trivial way to map from line numbers to a position in the gap buffer. No trees necessary.
  - celeritascelery 3y ago
    hmm. What happens when you move the gap from the front to the end of the text (or vice versa)? wouldn't that require you to update all the line boundaries? And wouldn't finding the position of the Nth line be O(n).
    - ahefner 3y ago
      Moving the gap from front to end - it takes O(n) time to do that both on the text (gap) buffer and the line-tracking (gap) buffer, so you're only a small constant factor worse. 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.
      - celeritascelery 3y ago
        This does seem like a really neat trick I have not heard of before. I am still confused about moving the gap in the line-tracking buffer. It seems to me the only way you could make look-up O(1) is if you updated all the line indexes you passed over when you moved the gap. Because they are pointing to absolute positions (right?). So moving the line-tracking gap would technically be O(n), but you couldn't use memmove, and instead would need to iterate over one and add or subtract the gap size. Am I misunderstanding?

raphlinus 3y ago

Interesting article, and I love to see performance numbers to back up engineering decisions. I'm also glad xi-rope wasn't included, as I'm sure it's performance lags :) 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.

loeg 3y ago
Also, the author is quick to dismiss 20-100ms latencies as imperceptible, or nearly so. That is too high.
- chongli 3y ago
  Yeah. 20ms is more than a full frame at 60hz. This sort of delay is unacceptable in 3D games! And here we’re talking about inserting a character into the data structure used to keep track of edits to a text file! 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. [1] https://danluu.com/input-lag/ https://danluu.com/input-lag/
  - kaba0 3y ago
    Maybe reread the relevant part of the article. It’s not average case at all.

gumby 3y ago

In a modern OS, you can combine the gap and the piece table approaches using the MMU to eliminate most copying in the common cases. 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.

kammerdiener 3y ago
Do you have any more info on this?
- gumby 3y ago
  I thought my comment was pretty comprehensive on the technique. Is there something that was unclear? I can clarify. I’ve used this technique a few times over the decades in non-editor applications with large sorted vectors.
  - PH95VuimJjqBqy 3y ago
    Not only was it clear but it's the approach that popped into my head immediately while reading the article.
  - kammerdiener 3y ago
    Your explanation was just fine. I was simply asking what else you knew about the technique. Perhaps where you first heard of it or some examples where it has been applied/benchmarked.

jll29 3y ago

I'm curious: who invented gap buffers originally? Do we know if it was RMS? What was the first peer-reviewed publication describing or mentioning them? A quick search brings up only references in the 1990s or later...

gumby 3y ago
Emacs uses a gap buffer because TECO used one, long before RMS finished high school. 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.
- cbsmith 3y ago
  Yeah, gap buffers LONG predate RMS.
- jwstarr 3y ago
  The author of TECO, Dan Murphy, wrote an article about its history for the IEEE Annals of the History of Computing. A PDF copy of the article is available here: https://opost.com/tenex/anhc-31-4-anec.pdf https://opost.com/tenex/anhc-31-4-anec.pdf 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 http://www.finseth.com/craft/#c6.6), although this claim is given no support.
  - gumby 3y ago
    Thanks for that reference — I’d never seen it. I’ll be happy never to write any more TECO in my life, but that doesn’t mean I’m not interested.

josephg 3y ago

Author of jumprope here. Great post! It’s cool seeing so many other good rope libraries ready to use. 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.

IshKebab 3y ago
> Text is really small Tell that to my 10GB JSON files.
- kaba0 3y ago
  Arguably, different algorithm could be used for that and for “normally” occurring files.
- pphysch 3y ago
  You're opening those in a text editor?

subarctic 3y ago

I really like this article's structure for showing benchmarks. each benchmark has its own heading and a paragraph explaining the reason for it and analyzing the results. 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.

nayuki 3y ago

A fantastic article that goes into a lot of depth and rigor until I got to the very end: > 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.

kaba0 3y ago
> centrifugal force is fictitious It is not. It exists if you change your point of reference.
userbinator 3y ago
1KB is 1024 bytes per JEDEC. 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.
- nayuki 3y ago
  Good luck fitting a 16 "GB" RAM dump on a 16 GB flash drive when you hibernate the computer. 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.
  - userbinator 3y ago
    Good luck fitting a 16 "GB" RAM dump on a 16 GB flash drive when you hibernate the computer. 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.

jiggawatts 3y ago

Notably, most modern text editors such as Visual Studio Code use neither of those. They use "piece tables", which have a number of advantages. For example they allow efficient incremental saves and the list of edit changes can be trivially wound back or replayed for undo/redo. https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation https://code.visualstudio.com/blogs/2018/03/23/text-buffer-r... https://en.wikipedia.org/wiki/Piece_table https://en.wikipedia.org/wiki/Piece_table

throwaway17_17 3y ago
Do you know of any assessment of performance characteristics for said ‘piece tables’? The thrust of TFA is essentially a performance comparison, so I can’t help but wonder why this implementation wasn’t addressed if it is present in one of the most widely used code editors. Also, VS Code is not known for its responsiveness for text editing, is this due to the ‘piece table’, or more likely, due to architectural decisions in the application more generally? 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.
- rudedogg 3y ago
  https://www.cs.unm.edu/~crowley/papers/sds/sds.html https://www.cs.unm.edu/~crowley/papers/sds/sds.html
zogrodea 3y ago
I implemented a Piece Tree like VS Code's not long ago and found the insert/delete performance fine, but performance for text retrieval (line retrieval, substring) queries wwas embarrassingly bad. Like, 10x slower than the other ropes I compared it with. 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.pdf 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 Say you want to get a substring from (root - 1) to (root + 1), one character before the tree's root up to one character after the root. How many tree nodes do you need to visit? We can understand by reminding ourselves that "the whole string can be reconstructed through an in order traversal", letting us know the order we need to visit nodes in. c / \ v v / \ / \ o cc o (where c = a node whose string we copy and v = a node we visit on our way to a node we need to copy). That is two separate O(log n) queries we make from the root of the tree for our substring operation. What are ropes like in contrast? v / \ v o / \ / \ c co o You do still need basically two O(log n) queries, but not from the tree's root. You find the inner metadata node where the start of the substring and the end of the substring (and all strings in between) can be reached and make an in-order traversal from there, which is less traversal time. This, combined with the lower fragmentation that ropes enable (or rather that high fragmentation the Piece Tables have), makes them faster than Piece Trees in my experience. (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-part-ii-breaking-down-the-editor/ 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.)

userbinator 3y ago

The simplest approach is to just use a large string or array of lines. However these each suffer from poor performance as either the size or line length of text increases. 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.

hoseja 3y ago
And yet, search-and-replace on big files takes seconds.
- kaba0 3y ago
  I can grep through half my file system in seconds. What do you measure?
PH95VuimJjqBqy 3y ago
I don't know this authoritatively, but I believe vim uses a simple array internally. And it works well.

sfink 3y ago

When you resize a large gap buffer, it seems like you could mremap the pages after the gap and avoid almost all copying. The usual alignment problems don't apply since you can adjust the position and size of the gap slightly as needed to accommodate.