3 ms·

I once build a text editor using a rope[1] data structure where every line was a node. The tree was augmented[2] with information about line numbers, titles in

I once build a text editor using a rope[1] data structure where every line was a node. The tree was augmented[2] with information about line numbers, titles in the document... for very fast navigation. I don't think primitive data structures like a gap buffer are useful anymore. They come from a time where saving on memory was more important than it is now. EDIT: I forgot it was also a self balancing tree! Very cool stuff. [1] https://en.wikipedia.org/wiki/Rope_(data_structure) https://en.wikipedia.org/wiki/Rope_(data_structure) [2] https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree

teddyh 10y ago
> I don't think primitive data structures like a gap buffer are useful anymore. They come from a time where saving on memory was more important than it is now. I beg to differ. I routinely open multi-gigabyte log files and SQL dumps in text format, and would not like to have to resort to “sed” to edit them.
- AlexanderDhoore 10y ago
  I don't disagree. Although a good rope implementation can handle that. Ropes are nice because it doesn't matter where you edit. Gap buffers have to copy around a lot of data if you are editing in different places. Btw the memory overhead is not that much. It's just the memory needed to keep the pointers between the nodes. So I'm talking 10% increase or something.
geocar 10y ago
A dissent: Saving memory isn't strictly orthogonal to editing performance. A paged gap buffer (as described with an array index) remains ideal when you need to make a small number of surgical changes (insertions, deletions, etc) to a very large file, especially given the fact that all modern systems have page mapping hardware, so anything you implement is effectively on top of a paged gap buffer anyway. What we're really searching for is a better program-visible structure. To that end, the biggest difficulties in efficient text editor, is that most text editing is (ahem) textbook, and neglects the fact that fork() copies on write making most real operations asynchronous, and combining writev() and mmap() can be used to produce whatever memory layout you want (a plain old stupid byte array if that's convenient); The kernel will memcpy your page table for you, so there's no sense in also doing it in user-space. And so on. If you consider at which point a write() and a mmap() (or on OSX a mach_vm_remap()) will be faster, just how much faster it will be -- imagine: programming something as simple as a plain byte array but with instant inserts (memmove) across multi-gigabyte buffers. Then consider the cost of a write()+mmap() syscall combination in the worst case (a couple hundred micros?) and you'll never use a complicated (linked list) data structure again.
- maxbrunsfeld 10y ago
  How would a gap buffer handle distributed editing operations like search-and-replace, or multi-cursor typing? The data structure seems optimized for editing in one place at a time.
  - geocar 10y ago
    There aren't a lot of structures that have an amortised cost-per-edit; you're really only ever considering the cost of doing a single insert/deletion operation, and you're really only ever trading that performance against the complexity. A paged gap buffer is actually more like a tree, so instead of a single gap in the middle of a file, you have a gap in the middle of a block, and one block mapped per modified space. Cost of insert/delete is limited to the cost of a memmove within a block (cheap!), and your extent map never grows beyond 2x the number of changes. These upper bounds are incredibly good for edits, and there are only pathological cases that do better. But what about search? Search is faster too! Because virtual memory has your entire file contiguous, a search is as fast as a scan[1], which might embolden you to try indexing your file, which might really impress your users. [1]: https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm
edmccard 10y ago
>I don't think primitive data structures like a gap buffer are useful anymore. Emacs seems to do just fine with gap buffers. And thinking about algorithms with greater complexity as being less primitive can obscure the fact that the complexity isn't always worth the tradeoff; see "Gap Buffers, or, Don't Get Tied Up With Ropes"[1] [1] http://scienceblogs.com/goodmath/2009/02/18/gap-buffers-or-why-bother-with-1/ http://scienceblogs.com/goodmath/2009/02/18/gap-buffers-or-w...

teddyh 10y ago

> I don't think primitive data structures like a gap buffer are useful anymore. They come from a time where saving on memory was more important than it is now. I beg to differ. I routinely open multi-gigabyte log files and SQL dumps in text format, and would not like to have to resort to “sed” to edit them.

AlexanderDhoore 10y ago
I don't disagree. Although a good rope implementation can handle that. Ropes are nice because it doesn't matter where you edit. Gap buffers have to copy around a lot of data if you are editing in different places. Btw the memory overhead is not that much. It's just the memory needed to keep the pointers between the nodes. So I'm talking 10% increase or something.

geocar 10y ago

A dissent: Saving memory isn't strictly orthogonal to editing performance. A paged gap buffer (as described with an array index) remains ideal when you need to make a small number of surgical changes (insertions, deletions, etc) to a very large file, especially given the fact that all modern systems have page mapping hardware, so anything you implement is effectively on top of a paged gap buffer anyway. What we're really searching for is a better program-visible structure. To that end, the biggest difficulties in efficient text editor, is that most text editing is (ahem) textbook, and neglects the fact that fork() copies on write making most real operations asynchronous, and combining writev() and mmap() can be used to produce whatever memory layout you want (a plain old stupid byte array if that's convenient); The kernel will memcpy your page table for you, so there's no sense in also doing it in user-space. And so on. If you consider at which point a write() and a mmap() (or on OSX a mach_vm_remap()) will be faster, just how much faster it will be -- imagine: programming something as simple as a plain byte array but with instant inserts (memmove) across multi-gigabyte buffers. Then consider the cost of a write()+mmap() syscall combination in the worst case (a couple hundred micros?) and you'll never use a complicated (linked list) data structure again.

maxbrunsfeld 10y ago
How would a gap buffer handle distributed editing operations like search-and-replace, or multi-cursor typing? The data structure seems optimized for editing in one place at a time.
- geocar 10y ago
  There aren't a lot of structures that have an amortised cost-per-edit; you're really only ever considering the cost of doing a single insert/deletion operation, and you're really only ever trading that performance against the complexity. A paged gap buffer is actually more like a tree, so instead of a single gap in the middle of a file, you have a gap in the middle of a block, and one block mapped per modified space. Cost of insert/delete is limited to the cost of a memmove within a block (cheap!), and your extent map never grows beyond 2x the number of changes. These upper bounds are incredibly good for edits, and there are only pathological cases that do better. But what about search? Search is faster too! Because virtual memory has your entire file contiguous, a search is as fast as a scan[1], which might embolden you to try indexing your file, which might really impress your users. [1]: https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm

edmccard 10y ago

>I don't think primitive data structures like a gap buffer are useful anymore. Emacs seems to do just fine with gap buffers. And thinking about algorithms with greater complexity as being less primitive can obscure the fact that the complexity isn't always worth the tradeoff; see "Gap Buffers, or, Don't Get Tied Up With Ropes"[1] [1] http://scienceblogs.com/goodmath/2009/02/18/gap-buffers-or-why-bother-with-1/ http://scienceblogs.com/goodmath/2009/02/18/gap-buffers-or-w...