3 ms·
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
by 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 agoHow 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 agoThere 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