17 ms·

Text Editor Data Structures

367 points by starfreakclone 3y ago

mannyv 3y ago
Apple's MPW was Apple's programming environment for a long time. It's been a while, but I believe that it represented everything in a tree of n-character chunks (n = 6?). It was probably the first editor that I used that could open files of pretty much any length.
- eschneider 3y ago
  I do miss the 'select and execute', and 'everything is a shell' model of MPW. Definitely one of my favorite development environments.
  - tomjakubowski 3y ago
    sounds like plan9's acme
  - scelerat 3y ago
    elsewhere on HN today is a short article on BBedit, which has a really nice shell worksheet interface similar to the old MPW. Select the text you want to execute, hit control-return, and the shell output will appear below the selected text.
    - deleted 3y ago
      [deleted]
    - kerkeslager 3y ago
      If I'm not mistaken, I believe this feature originates with Smalltalk (you might think that Smalltalk is a language and the feature in question is an editor feature, but most Smalltalk variants are tightly integrated with an editing environment).
toppy 3y ago
There is also a great documentation on the topic (and CRDT) by /u/raphlinus: https://xi-editor.io/docs.html https://xi-editor.io/docs.html
badsectoracula 3y ago
There are tons of articles about plain text editor data structures, but what about rich text editor data structures? Let's say i want to implement a text editor that can have bold, italic, underline, etc text but also be able to do automatic word breaking, align paragraph text to left/middle/right, insert images and/or other objects, have floating images and/or other objects around which the other (non floating) text/images/objects wrap, etc. What would be the data structures for that? I can only think of trying to replicate something like the HTML DOM but i have a feeling something like Write for Windows 3.1 used a simpler data structure.
- KerrAvon 3y ago
  It's not actually that different or complicated if you're already doing proportional plaintext rendering -- you need to store style attributes for a range of text, and you need to support different heights per line. The real complexity is rendering all of unicode properly, and supporting international fonts, bidi layout, vertical text, etc.
  - starfreakclone 3y ago
    Indeed, you could even use a piece tree just like in the blog but you store additional information in each piece which tell the renderer how to layout the associated text. My understanding is that most rich text editors represent the text as a node-based tree anyway.
    - WorldMaker 3y ago
      Some early rich text editors never used a tree representation for formatting represented the formatting as "control character sequences". This was part of why some people loved WordPerfect so much because you could toggle a view of all the control characters and just delete/copy/paste them like any other text in the same document. It's basically how the classic RTF format [1] works, and things like VT100/ANSI escape codes in terminals. It's kind of like the difference between imperative code and declarative code: "this character sequence means toggle the state of bold" versus "this node of characters is bold". [1] https://docs.fileformat.com/word-processing/rtf/ https://docs.fileformat.com/word-processing/rtf/
phildenhoff 3y ago
Thanks to this article, I learned that the core data structure for VSCode's text is written in TypeScript[0]. I, uh, I knew VS Code was written in TypeScript but I didn't realise _all_ of it was. It's crazy to think that the editor works as well as it does! [0]: https://github.com/microsoft/vscode/tree/main/src/vs/editor/common/model/pieceTreeTextBuffer https://github.com/microsoft/vscode/tree/main/src/vs/editor/...
- deleted 3y ago
  [deleted]
- cmrdporcupine 3y ago
  I used a red-black tree written in JS over 15 years ago at a job where I needed to use lower bound and range operations for nodes in a pivot-table type dashboard for telecoms metrics. I was actually blown away at the time at how it actually performed rather decently, and this is back in the pre-Chrome Firefox & IE6&IE7 days. Now in the world of V8 and JavaScriptCore, I don't think it's crazy at all. So much work has gone into JS runtime optimization. For heavily concurrent and memory intensive workloads, I can imagine problems though.
nsajko 3y ago
This seems revisionist/ignorant. The article attributes a "piece tree" data structure to VS Code developers, however the must-read 1998 paper by Charles Crowley, Data Structures for Text Sequences, already mentions search trees as being used to enhance the naive piece table in some text editors. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.1265&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48...
- starfreakclone 3y ago
  Thank you for the pointer! I was actually not aware of this paper at all, which is why it was not included here (not sure how I missed it). I'll be sure to push a revision to the blog which mentions this paper.
  - thaliaarchi 3y ago
    You may also want to take a look at “Deletion: The curse of the red-black tree” (Germane and Might 2014), which presents functional deletion for red-black trees. https://matt.might.net/papers/germane2014deletion.pdf https://matt.might.net/papers/germane2014deletion.pdf
  - zogrodea 3y ago
    I might have a useful suggestion. I've implemented a Piece Tree (VS Code style) and a Rope in a functional language (found the Rope much faster at everything but I made a few adjustments to the structure so it's not a straightforward Rope). The major failing point of the Piece Tree from my benchmarks is the substring/querying time. An idea I want to try out to speed up my Piece Tree implementation is to distinguish between Concat (metadata) and Leaf (string) nodes, just as a Rope does, storing metadata in the internal nodes and Pieces at the leaves. The reason (I hope) that will improve substring times is because, in a Piece Tree, the original string can be reconstructed through an in-order traversal of the tree's internal nodes. So, if you specify a substring range that starts from one character before the root node and ends one character after the root node, you end up traversing to the rightmost node in the left subtree and the leftmost node in the right subtree (two O(log n) operations). I'm hopeful the tree depth that would need to be traversed if the nodes were at the Leaves (like in a Rope) would be shorter (especially since adjacent pieces won't be O(log n) distance away) and want to try it out myself, but my intuition might be wrong. You can have a go trying that out yourself if the idea interests you.
tonetheman 3y ago
Why is starfreakclone green? The username I mean.
bjoli 3y ago
I would probably reach for an RRB tree which would, apart from being very very neat, give me free undo/redo.
teddyh 3y ago
I would instead suggest The Craft of Text Editing <https://www.finseth.com/craft/ https://www.finseth.com/craft/>
krackers 3y ago
You might also like reading https://news.ycombinator.com/item?id=16385440 https://news.ycombinator.com/item?id=16385440 (A Brief Glance at How Various Text Editors Manage Their Textual Data) and the comments therein.
vbezhenar 3y ago
Can someone point me to structures/algorithms to use for text editor which could support files of unlimited lengths (including lines of unlimited length) without loading those fully in the buffer? I miss that editor so much, that I'm considering to write one some day, but I have no idea how to do so. I can invent things myself, but I guess those things were invented already back in the days computers were different.
- celeritascelery 3y ago
  That is essentially what VLF[1] does in Emacs. It reads in discrete chunks of the file at a time and doesn’t load the next one till you try to display it. Doesn’t require any fancy data structures, just some extra book keeping and mechanics. [1] https://github.com/m00natic/vlfi https://github.com/m00natic/vlfi
- modernerd 3y ago
  You might be interested in ewig and immer by Juan Pedro Bolivar Puente: https://github.com/arximboldi/ewig https://github.com/arximboldi/ewig https://github.com/arximboldi/immer https://github.com/arximboldi/immer See the author instantly opening a ~1GB text file with async loading, paging through, copying/pasting, and undoing/redoing in their prototype “ewig” text editor about 27 minutes into their talk here: https://m.youtube.com/watch?v=sPhpelUfu8Q https://m.youtube.com/watch?v=sPhpelUfu8Q It’s backed by a “vector of vectors” data structure called a relaxed radix balanced tree: https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf That original paper has seen lots of attention and attempts at performance improvements, such as: https://hypirion.com/musings/thesis https://hypirion.com/musings/thesis https://github.com/hyPiRion/c-rrb https://github.com/hyPiRion/c-rrb
egonschiele 3y ago
I've been wondering if there's a good algorithm to handle highlights in a piece of text. If I highlight some text, lets say the part between the => <= here: "Idioteque" is a song => by the English rock band Radiohead <=, released on their fourth album, Kid A (2000). If I want to then edit this text, is there an efficient algorithm for figuring out the start and end index of the highlight for the edited text?
- kerkeslager 3y ago
  There's way too little detail given in this question for you to get a useful answer. How is the text stored? How are you highlighting if you don't have the indices?
hgs3 3y ago
> Create debugging utilities for data structures very early on. Yes, this isn't encouraged enough. I often serialize my data structures as either JSON or Graphviz DOT files for visualization. It helps save an immense amount of time. You can also use the generated files for regression testing, i.e. diff the actual output with the serialized output and if they're different, then a bug was introduced.
celeritascelery 3y ago
> if the underlying buffer needs to reallocate after some edits the entire process slows to a crawl as you need to allocate a larger buffer and copy each byte into the new buffer and destroy the old one. It can turn an O(n) operation into O(n^2) randomly. This would still only be a O(n) operation. The constant value might be higher, but the complexity is the same. I don’t buy the argument that gap buffers “are bad for multiple cursors”. I get the argument on a theoretical level, but real hardware is not theoretical. There are several operations that are theoretical faster with a hashmap or b-tree than a vector, like insert and delete. But in reality the vector is usually faster in the real world except for very large inputs[1]. Gap buffers are basically vectors. Another point with multiple cursors and gap buffers is that Chris Wellons animations show the gap moving back to the first cursor every time it needed to add a new character. But in reality you would just walk the cursors in reverse order each time, saving a trip. I have actually written and benchmarked a very naive and unoptimized gap buffer, and the results showed that it was faster than highly optimized rope implementations on all real world benchmarks[2], including multiple cursors. That being said, a gap buffer is still probably not the best data structure for a text editor because it has worse “worse case” performance than something like a rope or piece-tree. Even though it is faster overall, it’s the tail latency's that really matter for interactive programs. Overall I enjoyed reading the post, I find the topics fascinating and this was well presented. [1] http://www.goodmath.org/blog/2009/02/18/gap-buffers-or-dont-get-tied-up-with-ropes/ http://www.goodmath.org/blog/2009/02/18/gap-buffers-or-dont-... [2] https://github.com/CeleritasCelery/rune/issues/17#issuecomment-1446690404 https://github.com/CeleritasCelery/rune/issues/17#issuecomme...
- nsajko 3y ago
  These data structures are not mutually exclusive, see the paper by Crowley linked elsewhere in the discussion. You could use, e.g., a piece table with a gap buffer for descriptors, or a piece table with a tree for descriptors.
Onavo 3y ago
Another potential approach is to use a traditional rope as-is, and generate a series of reverse operational transforms everytime there is an edit. Run a "compacting operation" every n edits to keep the stack of ops from growing out of hand.
kerkeslager 3y ago
I feel like the rope was too quickly discarded here. The author stopped exploring ropes because they don't fit criteria 2--efficient undo/redo. There are a few problems with claiming that ropes aren't efficient for this usage: 1. The claim that the rope is inefficient for undo/redo is based on a singular example of a small edit on short strings. This isn't where ropes shine, admittedly, but they don't need to shine there, because when dealing with such small pieces of data, pretty much anything you do will be faster than the user can see. If using larger strings, the space allocated for nodes becomes background noise as the strings themselves dominate the size. 2. The chosen solution, the piece table, is more memory-efficient than the rope at first glance, but that's a surface-level efficiency. The eventually-chosen solution, a piece tree, is far less memory efficient. Sure, at first glance it is more memory-efficient, but this is at the expense of tree traversals, which in the VSCode article, are addressed with cache, which... uses more memory. In the author's implementation there's even more memory used because there's a requirement he didn't include in his list: he wants it all to be immutable. Nevermind that ropes were immutable from the start... 3. If you have a document which uses a lot (read, thousands) of very small edits, then the size of small strings might start to matter. So if you're going to optimize for this, optimize it. There are some fairly small optimizations that make the inefficiency concerns completely irrelevant. One is pointer packing: in a 64-bit system, pointers are 64 bits, but in practice, the vast majority of systems use 48 or fewer of those bits: as it turns out, there aren't many systems with more than 2^48 bytes = 256 terabytes of RAM. This means the leading 16 bits are 0s. Trivially, this means you can store strings of 7 8-bit characters in the pointer itself, using the first 8 bits to signal if it's a string or pointer (if they're all 0s, it's a pointer) and the length of the string. All the strings in the inefficiency example can fit in a 64 bit integer: "Hello", " ", and "world" are all fewer than 7 bytes, which means you're passing around 64-bit integers, by value, with no allocations necessary. In fact, this means you can either append the " " to "Hello" like "Hello ", or prepend it to "world" like " world", and still stay under 7 bytes in either case. Remember, this is now 64 bit integers being passed around by value: this is far faster than piece trees. 4. The author treats undo/redo as a stack, but all the cool editors treat it as a tree. If you make a change, then undo it, then make another change, then undo the second change, is your first change lost? In vim/emacs, the answer is no: you can go back into a tree and find it to reapply. This means that all text is not only immutable but immortal: it has to be kept for the duration of the editing session. This enables a few more optimizations: we no longer need reference counts or garbage collection since we aren't reclaiming the memory, and now we can point into existing strings since they'll never change. Consider the following string: "The quick brown box jumps over the lazy dog." You may have noticed a typo: "box" should be "fox". This change requires 0 buffer allocations: we have a pointer to "The quick brown box jumps over the lazy dog." for the original string, a pointer to the same spot for "The quick brown " (with a length), a second pointer to "ox jumps over the lazy dog.", and a packed pointer (integer) for the string "f". This is pretty key because if you're not freeing any of this memory, you need to make sure you don't allocate more than necessary! NOTE: I'm not saying that the rope is the better structure here. There may be more requirements which weren't captured in the article which mean that piece buffers really are the right answer. All I'm saying is that the article doesn't really explore ropes deeply enough to write them off so quickly.

Apple's MPW was Apple's programming environment for a long time. It's been a while, but I believe that it represented everything in a tree of n-character chunks (n = 6?). It was probably the first editor that I used that could open files of pretty much any length.

eschneider 3y ago
I do miss the 'select and execute', and 'everything is a shell' model of MPW. Definitely one of my favorite development environments.
- tomjakubowski 3y ago
  sounds like plan9's acme
- scelerat 3y ago
  elsewhere on HN today is a short article on BBedit, which has a really nice shell worksheet interface similar to the old MPW. Select the text you want to execute, hit control-return, and the shell output will appear below the selected text.
  - deleted 3y ago
    [deleted]
  - kerkeslager 3y ago
    If I'm not mistaken, I believe this feature originates with Smalltalk (you might think that Smalltalk is a language and the feature in question is an editor feature, but most Smalltalk variants are tightly integrated with an editing environment).

toppy 3y ago

There is also a great documentation on the topic (and CRDT) by /u/raphlinus: https://xi-editor.io/docs.html https://xi-editor.io/docs.html

badsectoracula 3y ago

There are tons of articles about plain text editor data structures, but what about rich text editor data structures? Let's say i want to implement a text editor that can have bold, italic, underline, etc text but also be able to do automatic word breaking, align paragraph text to left/middle/right, insert images and/or other objects, have floating images and/or other objects around which the other (non floating) text/images/objects wrap, etc. What would be the data structures for that? I can only think of trying to replicate something like the HTML DOM but i have a feeling something like Write for Windows 3.1 used a simpler data structure.

KerrAvon 3y ago
It's not actually that different or complicated if you're already doing proportional plaintext rendering -- you need to store style attributes for a range of text, and you need to support different heights per line. The real complexity is rendering all of unicode properly, and supporting international fonts, bidi layout, vertical text, etc.
- starfreakclone 3y ago
  Indeed, you could even use a piece tree just like in the blog but you store additional information in each piece which tell the renderer how to layout the associated text. My understanding is that most rich text editors represent the text as a node-based tree anyway.
  - WorldMaker 3y ago
    Some early rich text editors never used a tree representation for formatting represented the formatting as "control character sequences". This was part of why some people loved WordPerfect so much because you could toggle a view of all the control characters and just delete/copy/paste them like any other text in the same document. It's basically how the classic RTF format [1] works, and things like VT100/ANSI escape codes in terminals. It's kind of like the difference between imperative code and declarative code: "this character sequence means toggle the state of bold" versus "this node of characters is bold". [1] https://docs.fileformat.com/word-processing/rtf/ https://docs.fileformat.com/word-processing/rtf/

phildenhoff 3y ago

Thanks to this article, I learned that the core data structure for VSCode's text is written in TypeScript[0]. I, uh, I knew VS Code was written in TypeScript but I didn't realise _all_ of it was. It's crazy to think that the editor works as well as it does! [0]: https://github.com/microsoft/vscode/tree/main/src/vs/editor/common/model/pieceTreeTextBuffer https://github.com/microsoft/vscode/tree/main/src/vs/editor/...

deleted 3y ago
[deleted]
cmrdporcupine 3y ago
I used a red-black tree written in JS over 15 years ago at a job where I needed to use lower bound and range operations for nodes in a pivot-table type dashboard for telecoms metrics. I was actually blown away at the time at how it actually performed rather decently, and this is back in the pre-Chrome Firefox & IE6&IE7 days. Now in the world of V8 and JavaScriptCore, I don't think it's crazy at all. So much work has gone into JS runtime optimization. For heavily concurrent and memory intensive workloads, I can imagine problems though.

nsajko 3y ago

This seems revisionist/ignorant. The article attributes a "piece tree" data structure to VS Code developers, however the must-read 1998 paper by Charles Crowley, Data Structures for Text Sequences, already mentions search trees as being used to enhance the naive piece table in some text editors. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.1265&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48...

starfreakclone 3y ago
Thank you for the pointer! I was actually not aware of this paper at all, which is why it was not included here (not sure how I missed it). I'll be sure to push a revision to the blog which mentions this paper.
- thaliaarchi 3y ago
  You may also want to take a look at “Deletion: The curse of the red-black tree” (Germane and Might 2014), which presents functional deletion for red-black trees. https://matt.might.net/papers/germane2014deletion.pdf https://matt.might.net/papers/germane2014deletion.pdf
- zogrodea 3y ago
  I might have a useful suggestion. I've implemented a Piece Tree (VS Code style) and a Rope in a functional language (found the Rope much faster at everything but I made a few adjustments to the structure so it's not a straightforward Rope). The major failing point of the Piece Tree from my benchmarks is the substring/querying time. An idea I want to try out to speed up my Piece Tree implementation is to distinguish between Concat (metadata) and Leaf (string) nodes, just as a Rope does, storing metadata in the internal nodes and Pieces at the leaves. The reason (I hope) that will improve substring times is because, in a Piece Tree, the original string can be reconstructed through an in-order traversal of the tree's internal nodes. So, if you specify a substring range that starts from one character before the root node and ends one character after the root node, you end up traversing to the rightmost node in the left subtree and the leftmost node in the right subtree (two O(log n) operations). I'm hopeful the tree depth that would need to be traversed if the nodes were at the Leaves (like in a Rope) would be shorter (especially since adjacent pieces won't be O(log n) distance away) and want to try it out myself, but my intuition might be wrong. You can have a go trying that out yourself if the idea interests you.

tonetheman 3y ago

Why is starfreakclone green? The username I mean.

bjoli 3y ago

I would probably reach for an RRB tree which would, apart from being very very neat, give me free undo/redo.

teddyh 3y ago

I would instead suggest The Craft of Text Editing <https://www.finseth.com/craft/ https://www.finseth.com/craft/>

krackers 3y ago

You might also like reading https://news.ycombinator.com/item?id=16385440 https://news.ycombinator.com/item?id=16385440 (A Brief Glance at How Various Text Editors Manage Their Textual Data) and the comments therein.

vbezhenar 3y ago

Can someone point me to structures/algorithms to use for text editor which could support files of unlimited lengths (including lines of unlimited length) without loading those fully in the buffer? I miss that editor so much, that I'm considering to write one some day, but I have no idea how to do so. I can invent things myself, but I guess those things were invented already back in the days computers were different.

celeritascelery 3y ago
That is essentially what VLF[1] does in Emacs. It reads in discrete chunks of the file at a time and doesn’t load the next one till you try to display it. Doesn’t require any fancy data structures, just some extra book keeping and mechanics. [1] https://github.com/m00natic/vlfi https://github.com/m00natic/vlfi
modernerd 3y ago
You might be interested in ewig and immer by Juan Pedro Bolivar Puente: https://github.com/arximboldi/ewig https://github.com/arximboldi/ewig https://github.com/arximboldi/immer https://github.com/arximboldi/immer See the author instantly opening a ~1GB text file with async loading, paging through, copying/pasting, and undoing/redoing in their prototype “ewig” text editor about 27 minutes into their talk here: https://m.youtube.com/watch?v=sPhpelUfu8Q https://m.youtube.com/watch?v=sPhpelUfu8Q It’s backed by a “vector of vectors” data structure called a relaxed radix balanced tree: https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf That original paper has seen lots of attention and attempts at performance improvements, such as: https://hypirion.com/musings/thesis https://hypirion.com/musings/thesis https://github.com/hyPiRion/c-rrb https://github.com/hyPiRion/c-rrb

egonschiele 3y ago

I've been wondering if there's a good algorithm to handle highlights in a piece of text. If I highlight some text, lets say the part between the => <= here: "Idioteque" is a song => by the English rock band Radiohead <=, released on their fourth album, Kid A (2000). If I want to then edit this text, is there an efficient algorithm for figuring out the start and end index of the highlight for the edited text?

kerkeslager 3y ago
There's way too little detail given in this question for you to get a useful answer. How is the text stored? How are you highlighting if you don't have the indices?

hgs3 3y ago

> Create debugging utilities for data structures very early on. Yes, this isn't encouraged enough. I often serialize my data structures as either JSON or Graphviz DOT files for visualization. It helps save an immense amount of time. You can also use the generated files for regression testing, i.e. diff the actual output with the serialized output and if they're different, then a bug was introduced.

celeritascelery 3y ago

> if the underlying buffer needs to reallocate after some edits the entire process slows to a crawl as you need to allocate a larger buffer and copy each byte into the new buffer and destroy the old one. It can turn an O(n) operation into O(n^2) randomly. This would still only be a O(n) operation. The constant value might be higher, but the complexity is the same. I don’t buy the argument that gap buffers “are bad for multiple cursors”. I get the argument on a theoretical level, but real hardware is not theoretical. There are several operations that are theoretical faster with a hashmap or b-tree than a vector, like insert and delete. But in reality the vector is usually faster in the real world except for very large inputs[1]. Gap buffers are basically vectors. Another point with multiple cursors and gap buffers is that Chris Wellons animations show the gap moving back to the first cursor every time it needed to add a new character. But in reality you would just walk the cursors in reverse order each time, saving a trip. I have actually written and benchmarked a very naive and unoptimized gap buffer, and the results showed that it was faster than highly optimized rope implementations on all real world benchmarks[2], including multiple cursors. That being said, a gap buffer is still probably not the best data structure for a text editor because it has worse “worse case” performance than something like a rope or piece-tree. Even though it is faster overall, it’s the tail latency's that really matter for interactive programs. Overall I enjoyed reading the post, I find the topics fascinating and this was well presented. [1] http://www.goodmath.org/blog/2009/02/18/gap-buffers-or-dont-get-tied-up-with-ropes/ http://www.goodmath.org/blog/2009/02/18/gap-buffers-or-dont-... [2] https://github.com/CeleritasCelery/rune/issues/17#issuecomment-1446690404 https://github.com/CeleritasCelery/rune/issues/17#issuecomme...

nsajko 3y ago
These data structures are not mutually exclusive, see the paper by Crowley linked elsewhere in the discussion. You could use, e.g., a piece table with a gap buffer for descriptors, or a piece table with a tree for descriptors.

Onavo 3y ago

Another potential approach is to use a traditional rope as-is, and generate a series of reverse operational transforms everytime there is an edit. Run a "compacting operation" every n edits to keep the stack of ops from growing out of hand.

kerkeslager 3y ago

I feel like the rope was too quickly discarded here. The author stopped exploring ropes because they don't fit criteria 2--efficient undo/redo. There are a few problems with claiming that ropes aren't efficient for this usage: 1. The claim that the rope is inefficient for undo/redo is based on a singular example of a small edit on short strings. This isn't where ropes shine, admittedly, but they don't need to shine there, because when dealing with such small pieces of data, pretty much anything you do will be faster than the user can see. If using larger strings, the space allocated for nodes becomes background noise as the strings themselves dominate the size. 2. The chosen solution, the piece table, is more memory-efficient than the rope at first glance, but that's a surface-level efficiency. The eventually-chosen solution, a piece tree, is far less memory efficient. Sure, at first glance it is more memory-efficient, but this is at the expense of tree traversals, which in the VSCode article, are addressed with cache, which... uses more memory. In the author's implementation there's even more memory used because there's a requirement he didn't include in his list: he wants it all to be immutable. Nevermind that ropes were immutable from the start... 3. If you have a document which uses a lot (read, thousands) of very small edits, then the size of small strings might start to matter. So if you're going to optimize for this, optimize it. There are some fairly small optimizations that make the inefficiency concerns completely irrelevant. One is pointer packing: in a 64-bit system, pointers are 64 bits, but in practice, the vast majority of systems use 48 or fewer of those bits: as it turns out, there aren't many systems with more than 2^48 bytes = 256 terabytes of RAM. This means the leading 16 bits are 0s. Trivially, this means you can store strings of 7 8-bit characters in the pointer itself, using the first 8 bits to signal if it's a string or pointer (if they're all 0s, it's a pointer) and the length of the string. All the strings in the inefficiency example can fit in a 64 bit integer: "Hello", " ", and "world" are all fewer than 7 bytes, which means you're passing around 64-bit integers, by value, with no allocations necessary. In fact, this means you can either append the " " to "Hello" like "Hello ", or prepend it to "world" like " world", and still stay under 7 bytes in either case. Remember, this is now 64 bit integers being passed around by value: this is far faster than piece trees. 4. The author treats undo/redo as a stack, but all the cool editors treat it as a tree. If you make a change, then undo it, then make another change, then undo the second change, is your first change lost? In vim/emacs, the answer is no: you can go back into a tree and find it to reapply. This means that all text is not only immutable but immortal: it has to be kept for the duration of the editing session. This enables a few more optimizations: we no longer need reference counts or garbage collection since we aren't reclaiming the memory, and now we can point into existing strings since they'll never change. Consider the following string: "The quick brown box jumps over the lazy dog." You may have noticed a typo: "box" should be "fox". This change requires 0 buffer allocations: we have a pointer to "The quick brown box jumps over the lazy dog." for the original string, a pointer to the same spot for "The quick brown " (with a length), a second pointer to "ox jumps over the lazy dog.", and a packed pointer (integer) for the string "f". This is pretty key because if you're not freeing any of this memory, you need to make sure you don't allocate more than necessary! NOTE: I'm not saying that the rope is the better structure here. There may be more requirements which weren't captured in the article which mean that piece buffers really are the right answer. All I'm saying is that the article doesn't really explore ropes deeply enough to write them off so quickly.