5 ms·

I don't see it mentioned in the text, but essentially the best-known data structure for representing large amounts of random-location-editable text is called th

by wyager 10y ago

I don't see it mentioned in the text, but essentially the best-known data structure for representing large amounts of random-location-editable text is called the Rope. It's based on my favorite data structure, the Finger Tree, which has very impressive asymptotic performance characteristics over a huge range of intuitively (but not actually) expensive operations. It doesn't require you to break the text up into lines and hope for short lines or anything; you can insert, split, cut, paste, delete, whatever, with at worst O(log(n)) for "expensive" operations (like beginning to edit at a random point in the text, or cutting/pasting a huge chunk of text) and O(1) for "cheap" operations (like insertion/deletion of a character after you've started editing). It's based on a finger tree containing densely packed byte or UTF arrays (strictly speaking, this isn't necessary, but gives an appreciable constant time/memory speedup), and tree nodes are tagged with the length of all text underneath them. Here's an implementation specialized to byte arrays (not UTF-8). https://hackage.haskell.org/package/rope https://hackage.haskell.org/package/rope

greglindahl 10y ago
Given the desire for syntax highlighting and other demanding features in modern editors, it would be fun to see a comparison of "piece chains" or "the rope" with a gap buffer, which is the data structure historically used by Emacs. Sure, it's easy to see how different editing itself fares with these various data structures, but what about syntax highlighting?
- codygman 10y ago
  There exists a phenomenal paper comparing ropes, gap buffers, and piece chains I cannot recall. There is a lua editor called Vis that uses piece chains which the paper suggests is best.
  - taeric 10y ago
    I would be very interested in if you could find that paper. Briefly reading on piece chains, I can't see how they would be the preferred way, sadly. (I'm assuming the failing is on me, hence the sadly.) Even gap buffers seem somewhat odd to me. I'm assuming the gap is only created/inserted when text is typed. Not just on moving of the point/cursor. That, or thinking longer, I suppose that the contents of the file can be out of sync while the buffer is not saved. So, probably possible to easily insert and shift a gap periodically into the text, as needed. (I'm envisioning the rotate memory code from Programming Pearls to keep the gap where you want it.) Similarly, the piece chain (which, I should add that googling that was a piece of hilarity), if it is possible to "snapshot" the base of the piece chain every so often to what is on disk, it would just mean inverting some of the change pieces. Which doesn't sound too hard.
    - abecedarius 10y ago
      You don't need to rotate memory, because you don't care about the contents of the gap.
      - taeric 10y ago
        My thinking: You load a file. All text is one giant buffer. You make a gap buffer and need it somewhere in the original buffer. Otherwise... How does this work? You want to move the gap to a new location. Which is the same as originally moving it in. This is effectively rotating part of the buffer.
        greglindahl 10y ago
        https://en.wikipedia.org/wiki/Gap_buffer https://en.wikipedia.org/wiki/Gap_buffer has a good explanation. You allocate extra space and do memmove() to open/move/close the gap.
        taeric 10y ago
        This is exactly what I described. You make a gap buffer and move it into the original text. As typing happens, the size of the buffer is effectively decreased. You move the cursor/point, and need to move what is left of the gap. This is the same as rotating it. To be clear, memcopy to move the buffer without using extra memory is the same as rotating. If you don't believe me. Try it. Move some memory of arbitrary size using constant memory and see what algorithms you find. :)
        greglindahl 10y ago
        I can only repeat what abecedarius said: it's nothing like a rotation because you don't care about the bytes in the gap. It's a pretty tortured way to think about it; after googling I finally figured out what you meant. Sounds like the kind of algorithm I would never, ever ask about in a programming interview!
  - gbrown_ 10y ago
    Data Structures for Text Sequences by Charles Crowley? https://www.cs.unm.edu/~crowley/papers/sds.pdf https://www.cs.unm.edu/~crowley/papers/sds.pdf I recall coming across this when hearing about vis.
    - greglindahl 10y ago
      This paper only discusses editing.
    - codygman 10y ago
      Yes! I believe that was it. If not it's very similar.
- userbinator 10y ago
  Syntax highlighting is primarily a "read" operation, and for that I suspect a plain buffer is going to have the advantage in speed since all the characters are contiguous and no pointer-chasing is required to read, unlike with the other data structures.
josephg 10y ago
Finger trees are very cool. I have an efficient rope implementation in C based on skip lists here: https://github.com/josephg/librope https://github.com/josephg/librope I'm proud to say that the only bugs AFL found in my implementation were related to my (documented) lack of UTF8 validation. And my skip list implementation beats the performance of the SGI C++ STL rope implementation by about 20x while being several times smaller. (It comfortably performs in the millions of random operations/second on documents up to 1M in size, and it has a smooth logarithmic decline in performance after that). Unfortunately in C its quite awkward to generically control what aggregate information is cached at internal nodes in the tree. You need control over that to be able to efficiently implement lots of the operations you need in a normal text editor. For example converting between line/character positions and offset positions. I can't just hardcode a lot of those translations into the data type because the bookkeeping is expensive and it kills cache coherence. Its a cost you only want to pay when you need it. I'm curious to try porting the skip list code to unsafe rust to see if I can add that abstraction capacity in while maintaining the current performance profile. Data structures are fun!
SamReidHughes 10y ago
In 2010 I tried using a pair of FingerTrees, whose elements were strings, to make an in-browser text editor in JavaScript. It was visibly slow on small buffers, much slower than using a plain pair of Strings. It'd have been fine in C++, and I'm really quite surprised how bad it ended up being. Maybe JS is faster now. Funnily enough, when looking for a job out of college I was asked what data structure I would use for a text editor in a phone screen, and answered, "a pair of finger trees." The next hour was spent trying to explain over the phone what a finger tree was. And then I was asked to pick something as simple as possible, so I answered, "an array." No, not that simple: "A cut buffer. No? How about a linked list... of character arrays of bounded size." I didn't get an onsite.
- gravypod 10y ago
  You're not going to be hit by V8 if you use complicated operations and data structures. Raw strings over a certain size will probably be prioritized by any jit as they are a classic example of what to optimize. You're also going to loose any semblance of a cache if you do something like tree navigation I'm a dynamic runtime.
  - greglindahl 10y ago
    It's worth noting that the only thing that has to be fast in a gap buffer is memmove(), which usually works fine even in interpreters. (In Javascript you'd probably represent this via substring operations.)
raphlinus 10y ago
People interested in this stuff might also want to take a look at the rope in https://github.com/google/xi-editor https://github.com/google/xi-editor. It's not a finger tree, rather it's based on a B-tree, which is simpler but doesn't have quite as good asymptotic guarantees for operations at the beginning and end of the sequence. Also, Rust.
userbinator 10y ago
I've read a lot about different advanced data structures for text editing, but in my experience the reality is that, with memory bandwidths and CPU speeds being what they are today, and the speed at which human inputs occur, one big linear buffer is the simplest way to do it and the performance is not as bad as you'd think --- indeed it seems inefficient to be moving blocks of memory up to the whole size of the file whenever you insert a character, but when you consider that ~30CPS is the fastest input rate you're likely to encounter for individual single-character inserts (keyboard autorepeat), and that a modern CPU can memmove() at >1GB/s, you are unlikely to notice any difference in performance until the file you're editing is several tens of MB; and that is a relatively rare use-case (large files are usually opened not for actual editing, but for browsing and searching --- like logs. In that case, the overhead of constructing a more complex datastructure upon open may actually be slower.) Even PCs in the DOS era with memory bandwidths in the single-digit MB/s range were OK with text editors that use a linear buffer, simply because people didn't really edit nor generate huge text files very often ("huge" being more than several hundred KB.)
- greglindahl 10y ago
  The PC word processor "Final Word", also available on some earlier machines, used a gap buffer for the part of the file that was in memory.
- hawski 10y ago
  I agree to some point with you. Simpler data structures will not result with abysmal performance nowadays. However I would not use fastest human character input as a benchmark. In advanced editor you may want computer to do some edits/inputs for you. Code pasting, filtering of lines or search/replace should also be considered. That said it is probably easy to move blocks if you know the size of edits. I am developing experimental text editor in C. What I am currently using is array of lines (strings). Entering new line is a memmove in array of pointers. Entering new character is a memmove in array of chars. I concatenated all sources of Linux kernel. Resulting file has 542MB and 19'726'498 lines. Insertion of line is slightly laggy then - probably on the edge of noticeability. I also tested it a bit with a file containing single long line and it was also OK. Based on what profiler shows me rendering takes much more time and that's what I have to optimize.

by wyager 10y ago

greglindahl 10y ago

Given the desire for syntax highlighting and other demanding features in modern editors, it would be fun to see a comparison of "piece chains" or "the rope" with a gap buffer, which is the data structure historically used by Emacs. Sure, it's easy to see how different editing itself fares with these various data structures, but what about syntax highlighting?

codygman 10y ago
There exists a phenomenal paper comparing ropes, gap buffers, and piece chains I cannot recall. There is a lua editor called Vis that uses piece chains which the paper suggests is best.
- taeric 10y ago
  I would be very interested in if you could find that paper. Briefly reading on piece chains, I can't see how they would be the preferred way, sadly. (I'm assuming the failing is on me, hence the sadly.) Even gap buffers seem somewhat odd to me. I'm assuming the gap is only created/inserted when text is typed. Not just on moving of the point/cursor. That, or thinking longer, I suppose that the contents of the file can be out of sync while the buffer is not saved. So, probably possible to easily insert and shift a gap periodically into the text, as needed. (I'm envisioning the rotate memory code from Programming Pearls to keep the gap where you want it.) Similarly, the piece chain (which, I should add that googling that was a piece of hilarity), if it is possible to "snapshot" the base of the piece chain every so often to what is on disk, it would just mean inverting some of the change pieces. Which doesn't sound too hard.
  - abecedarius 10y ago
    You don't need to rotate memory, because you don't care about the contents of the gap.
    - taeric 10y ago
      My thinking: You load a file. All text is one giant buffer. You make a gap buffer and need it somewhere in the original buffer. Otherwise... How does this work? You want to move the gap to a new location. Which is the same as originally moving it in. This is effectively rotating part of the buffer.
      - greglindahl 10y ago
        https://en.wikipedia.org/wiki/Gap_buffer https://en.wikipedia.org/wiki/Gap_buffer has a good explanation. You allocate extra space and do memmove() to open/move/close the gap.
        taeric 10y ago
        This is exactly what I described. You make a gap buffer and move it into the original text. As typing happens, the size of the buffer is effectively decreased. You move the cursor/point, and need to move what is left of the gap. This is the same as rotating it. To be clear, memcopy to move the buffer without using extra memory is the same as rotating. If you don't believe me. Try it. Move some memory of arbitrary size using constant memory and see what algorithms you find. :)
        greglindahl 10y ago
        I can only repeat what abecedarius said: it's nothing like a rotation because you don't care about the bytes in the gap. It's a pretty tortured way to think about it; after googling I finally figured out what you meant. Sounds like the kind of algorithm I would never, ever ask about in a programming interview!
- gbrown_ 10y ago
  Data Structures for Text Sequences by Charles Crowley? https://www.cs.unm.edu/~crowley/papers/sds.pdf https://www.cs.unm.edu/~crowley/papers/sds.pdf I recall coming across this when hearing about vis.
  - greglindahl 10y ago
    This paper only discusses editing.
  - codygman 10y ago
    Yes! I believe that was it. If not it's very similar.
userbinator 10y ago
Syntax highlighting is primarily a "read" operation, and for that I suspect a plain buffer is going to have the advantage in speed since all the characters are contiguous and no pointer-chasing is required to read, unlike with the other data structures.

josephg 10y ago

Finger trees are very cool. I have an efficient rope implementation in C based on skip lists here: https://github.com/josephg/librope https://github.com/josephg/librope I'm proud to say that the only bugs AFL found in my implementation were related to my (documented) lack of UTF8 validation. And my skip list implementation beats the performance of the SGI C++ STL rope implementation by about 20x while being several times smaller. (It comfortably performs in the millions of random operations/second on documents up to 1M in size, and it has a smooth logarithmic decline in performance after that). Unfortunately in C its quite awkward to generically control what aggregate information is cached at internal nodes in the tree. You need control over that to be able to efficiently implement lots of the operations you need in a normal text editor. For example converting between line/character positions and offset positions. I can't just hardcode a lot of those translations into the data type because the bookkeeping is expensive and it kills cache coherence. Its a cost you only want to pay when you need it. I'm curious to try porting the skip list code to unsafe rust to see if I can add that abstraction capacity in while maintaining the current performance profile. Data structures are fun!

SamReidHughes 10y ago

In 2010 I tried using a pair of FingerTrees, whose elements were strings, to make an in-browser text editor in JavaScript. It was visibly slow on small buffers, much slower than using a plain pair of Strings. It'd have been fine in C++, and I'm really quite surprised how bad it ended up being. Maybe JS is faster now. Funnily enough, when looking for a job out of college I was asked what data structure I would use for a text editor in a phone screen, and answered, "a pair of finger trees." The next hour was spent trying to explain over the phone what a finger tree was. And then I was asked to pick something as simple as possible, so I answered, "an array." No, not that simple: "A cut buffer. No? How about a linked list... of character arrays of bounded size." I didn't get an onsite.

gravypod 10y ago
You're not going to be hit by V8 if you use complicated operations and data structures. Raw strings over a certain size will probably be prioritized by any jit as they are a classic example of what to optimize. You're also going to loose any semblance of a cache if you do something like tree navigation I'm a dynamic runtime.
- greglindahl 10y ago
  It's worth noting that the only thing that has to be fast in a gap buffer is memmove(), which usually works fine even in interpreters. (In Javascript you'd probably represent this via substring operations.)

raphlinus 10y ago

People interested in this stuff might also want to take a look at the rope in https://github.com/google/xi-editor https://github.com/google/xi-editor. It's not a finger tree, rather it's based on a B-tree, which is simpler but doesn't have quite as good asymptotic guarantees for operations at the beginning and end of the sequence. Also, Rust.

userbinator 10y ago

I've read a lot about different advanced data structures for text editing, but in my experience the reality is that, with memory bandwidths and CPU speeds being what they are today, and the speed at which human inputs occur, one big linear buffer is the simplest way to do it and the performance is not as bad as you'd think --- indeed it seems inefficient to be moving blocks of memory up to the whole size of the file whenever you insert a character, but when you consider that ~30CPS is the fastest input rate you're likely to encounter for individual single-character inserts (keyboard autorepeat), and that a modern CPU can memmove() at >1GB/s, you are unlikely to notice any difference in performance until the file you're editing is several tens of MB; and that is a relatively rare use-case (large files are usually opened not for actual editing, but for browsing and searching --- like logs. In that case, the overhead of constructing a more complex datastructure upon open may actually be slower.) Even PCs in the DOS era with memory bandwidths in the single-digit MB/s range were OK with text editors that use a linear buffer, simply because people didn't really edit nor generate huge text files very often ("huge" being more than several hundred KB.)

greglindahl 10y ago
The PC word processor "Final Word", also available on some earlier machines, used a gap buffer for the part of the file that was in memory.
hawski 10y ago
I agree to some point with you. Simpler data structures will not result with abysmal performance nowadays. However I would not use fastest human character input as a benchmark. In advanced editor you may want computer to do some edits/inputs for you. Code pasting, filtering of lines or search/replace should also be considered. That said it is probably easy to move blocks if you know the size of edits. I am developing experimental text editor in C. What I am currently using is array of lines (strings). Entering new line is a memmove in array of pointers. Entering new character is a memmove in array of chars. I concatenated all sources of Linux kernel. Resulting file has 542MB and 19'726'498 lines. Insertion of line is slightly laggy then - probably on the edge of noticeability. I also tested it a bit with a file containing single long line and it was also OK. Based on what profiler shows me rendering takes much more time and that's what I have to optimize.