Text Editor: Data Structures
averylaird.com
averylaird.com
Has some good visualizations as well.
Claim made from theoretical considerations, without any actual reference to real-world editors. The popular Micro[1] text editor uses a simple line array[2], and performs fantastically well on real-world editing tasks.
Meanwhile, ropes are so complicated that even high-quality implementations have extremely subtle bugs[3] that can lead to state or content corruption.
Which data structure is "best" is not just a function of its asymptotic performance. Practical considerations are equally important (arguably more so).
[1] https://github.com/zyedidia/micro
[2] https://github.com/zyedidia/micro/blob/master/internal/buffe...
ropes can be complicated but they don't have to be. ropey is ten thousand lines of code, and only six years old, so it's not surprising that it's buggy. https://github.com/ivanbgd/Rope-Data-Structure-C is 339 lines of code, but it's probably not a real-world rope
probably the most widely used implementation of ropes is the one from the sgi stl, which is in gcc as libstdc++/ext/rope https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USER... and libstdc++/ext/ropeimpl.h https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USER..., which total 1485 lines of code, about halfway in between the two. in a garbage-collected language, like the cedar language where ropes originated, most of that complexity goes away, and production-quality ropes are only a few hundred lines of code. also c++'s verbose syntax isn't doing brevity any favors here
http://www.bitsavers.org/pdf/xerox/parc/cedar/Cedar_7.0/09_C...
(but i didn't think it was surprising)
> Claim made from theoretical considerations, without any actual reference to real-world editors.
I also found this weird, especially when the author then extols the piece table (an approach going back at least to the early 60s) which itself is nothing but an array!
And the author did cite emacs as an example (emacs inherited that approach from TECO).
Note to self: do not comment from bed.
Someone has clearly not heard of Notepad nor used the prolific quantity of text editors for DOS that appeared in the 80s/early 90s, a time when memory bandwidths were in the low MB/s; or even before that, micros with CP/M where memory bandwidths were measured in KB/s (and the whole address space was only 64k). Modern systems have memory bandwidths of dozens of GB/s.
Or perhaps that old saying really applies: worse is better.
IMHO an array is all you need for a regular general-purpose text editor. I hate needless complexity in software, but unfortunately others seem to love it.
And of course, if performance becomes an issue, we can make minor improvements then.
until you try to open up a multi gigabyte log file in notepad, and find that it's consuming all your system resources.
But opening that same file in sublime text works perfectly, scrolls fast and zero lag. Guess which one is my daily driver?
Q: How big is the 90th percentile text file?
64KB? That text file fits in some some level of cache and not RAM. An array is just fine most of the time.
Use a different purpose-built editor for those multi-GB text files.
E.g. Text editor Hex editor Source code editor
consequently the editors we used on those computers did not use this approach
however, a gap buffer is perfectly workable, and preserves most of the array's advantages, such as rapid text search. and so emacs continues to use gap buffers to this day
That works well enough for me: https://asciinema.org/a/314752
This requires loading the entire file into memory, but computers are so fast today that optimizing that away is pointless IMO (as the video shows, a 12MB file with 400k lines can be loaded/edited/saved reasonably).
The tree structure is implemented as a generic container here: https://github.com/alefore/edge/blob/master/src/language/con.... The tree is actually deeply immutable; each modification operation returns a new tree (where most contents are shared with the original tree). The leafs contain std::vectors that hold between 128 and 256 lines (save for a few cases). The actual specialization that holds a sequence of lines is LineSequence::Lines here: https://github.com/alefore/edge/blob/master/src/language/tex...
If I open a huge one it's usually either an accident or because I want to view it, not edit it. It's easy enough to support abnormally large files, but it felt to me like a distraction that adds complexity for the sake of a fringe case I was perfectly happy to just define as out of scope.
Incidentally, the server process for my editor holds every buffer that I've ever opened (over several years) and not explicitly killed in memory, and it's consuming too little for me to bother adding any garbage collection for buffers or similar (it's synced to disk, so on reboot I have the full same set of buffers available). We're talking many hundred buffers. RAM is cheap and plentiful.
Before you say it's unrealistic; sure, it's not a normal use case for code, but I frequently find myself wanting to open a huge JSON file, for example, just to perform a search/replace, or a minor edit, or copy some fragment, or just look at its contents. Pretty-printing first, or doing the change with a specialized tool like jq, is also something I do, but being able to just load the file into a text editor is often more convenient.
In my experience, editors tend to break down on edge cases like these. Editors (e.g. Jetbrains) often turn off syntax highlighting and/or edit capabilities on large files, not to mention put an upper limit on the number of cursors.
I expect very long lines should work just fine, but I'll give it a try when I have a chance.
I represent lines using a virtual class that has a few implementations. IIRC, the line will start as a tree containing 64kb chunks. As edits are applied, these chunks will gradually get replaced with other implementations (of the virtual class) that delegate to the original instances (and the representation is occasionally optimized (which can incur copying) to avoid too much nesting). So simplifying, I think this should just work due to the optimized representation that I use for lines, which doesn't require the characters to be contiguous in memory.
I fully agree with your observation about how things often break in the corner cases. I actually also put a configurable cap on the number of cursors (e.g., a reg exp search stops after 100 matches).
For syntax highlighting I don't currently have a cap, but this is ~fine: it just ~wastes a background thread (all syntax parsing is offloaded to a background thread, not blocking the main thread). But yeah, I should probably make this thread give up after a configurable time out.
Here are genome sequence files that are several hundred MB compressed (the decompressed format is text): https://ftp.ncbi.nlm.nih.gov/genomes/refseq/
Finally here is an almost 2 TB XML file: https://wiki.openstreetmap.org/wiki/Planet.osm
These aren’t the most typical use cases, but it’s nice if an editor can at least handle > 32-bit files (larger than 2 or 4 GB).
mmap() isn't entirely safe under Unix/Linux anyway because there is no Mandatory Locking. And it would still be useful only if you operate on the original text encoding.
You want to at the very least be able to show the user on which line his cursor is, and that already requires reading all the contents from the start up to the cursor. You might as well read the entire file and also show the user the total line count.
What is interesting is the opposite question: how do you enable editing that is bounded only by storage limits?
A piece table is a good solution for this since the original file and the added data is immutable, which lends itself to mmap-ing. Then you can implement the piece table and various indexes (line breaks, etc) in a database (such as SQLite) or similar. Overall this gives you consistent performance at any size or number of edits limited only by storage.
>It was also possible that characters that were still stored in the document file, had been deleted since those characters were first copied into the file. That meant if a user of the program had typed embarassing or incriminating text in a Word document, saved it and then thought better of publishing such thoughts, and erased them, that once saved text still was recorded in a Word file. If you used an operating system utility to dump the raw content of a fast saved Word file, this stuff became visible to the technically minded nosy person.
This fast-save feature is hilarious and reminds me of https://en.wikipedia.org/wiki/ACropalypse. Wondering how many awkward stories out there caused by this ”optimization”.
Not only that, multiple cursors is simple.
"An Efficient Data Structure For A Hex Editor" https://www.chiark.greenend.org.uk/~sgtatham/tweak/btree.htm...
As the article says, it’s quite a complex data structure though.
Then you don’t need to keep it in memory, can have unlimited undo and hand over to complexity to a solution (SQL) than you know with be there the next 20years
you don't even need parent references; you can just assign synthetic sequence identifiers to the pieces and rely on sql lexicographical ordering to put them in order. (sql is not really very good with parent references.) this would be handy when you want to annotate the text with things like line numbers and syntax highlighting information. you wouldn't get undo for free, though
Just sayin’
all of my C homebrew editors have been gap buffer based, and I told myself I'd reimplement if I ever wanted to edit something large enough for that to be a problem — but it never was.
I can see if you need to edit multi-gig log files and things will not fit in memory, but for small files, array is totally fine.
There were other tricks that were done back then to keep the number of single char inserts down to a minimum while typing. Like reading chars into a small buffer during fast typing and then inserting all the keystrokes at once as soon as you had the time.
But when pressing enter, pasting a bigger snippet, or deleting lines the slowdown is less noticeable. When you type a word, the deltas are tiny and it is easy to process for your brain. While the changes in multiple lines happen less often, so waiting a couple of frames doesn’t bother you much.
This is at millions of lines. With small files it is indeed too fast.
the performance cost of a dumb array is being oversold here. it's true that insertion and deletion are slow in arrays, but let's put this in perspective. i'm displaying my editor on a 2-megapixel display, which is 8 megabytes of pixels because they're 32 bits per pixel. drawing a single frame of video involves the same amount of memory traffic as memmove()ing 4 megabytes of text. so until you have a few megabytes, even with a dumb array, ordinary text editing operations will easily support interactive responsivity. even things like refilling paragraphs and indenting or outdenting regions, which might involve hundreds of individual edits, is fine on everyday-sized files. this laptop can do about 20 gigabytes a second to main memory, 10 gigabytes of memmove(), so in 16.7 milliseconds (a 60-hertz frame) it can memmove() 167 megabytes. it isn't until you get into things like search-and-replace jobs on big logfiles that you start to feel the pain
the complexity of ropes is also being oversold here. as i pointed out in a comment in a subthread, you can make ropes quite complex, but https://github.com/ivanbgd/Rope-Data-Structure-C is 339 lines of code. it's probably not a real-world rope, though; it has far too much memory overhead
probably the most widely used implementation of ropes is the one from the sgi stl, which is in gcc as libstdc++/ext/rope https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USER... and libstdc++/ext/ropeimpl.h https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USER..., which total 1485 lines of code, about five times larger. c++'s verbose syntax isn't doing brevity any favors here
in a garbage-collected language, like the cedar language where ropes originated, most of that complexity goes away, and production-quality ropes can be only a few hundred lines of code
http://www.bitsavers.org/pdf/xerox/parc/cedar/Cedar_7.0/09_C...
another somewhat popular rope implementation is librope, in c https://github.com/josephg/librope which is 684 lines of code and looks to be production-quality
there's an unrelated librope-ocaml in debian (and opam); it's 1029 lines of code but nothing in debian depends on it. it looks quite full-featured; the documentation says it 'has all non-deprecated operations of String' http://chris00.github.io/ocaml-rope/doc/rope/Rope/
in ur-scheme i used the simplest, dumbest kind of rope for building up output text (input was parsed into s-expressions character by character): an output text was either a string, a pair (representing the concatenation of its arguments), or nil (representing the empty string). this is very similar to erlang's io lists. the only operations supported were (constant-time) concatenation (implemented as cons) and (linear-time) flattening into a string; this took 27 lines of scheme because the subset of scheme i implemented it in was quite limited. http://canonical.org/~kragen/sw/urscheme/
finseth's book is worth reading https://www.finseth.com/craft/, tatham's notes on b-tree ropes https://www.chiark.greenend.org.uk/~sgtatham/tweak/btree.htm... are worth reading, and raph levien's notes on xi and ropes https://xi-editor.io/docs/rope_science_00.html are worth reading. chris wellons's post about gap buffers https://nullprogram.com/blog/2017/09/07/ is a little bit silly but has animations
Vim feels sluggish compared to NeoVim.
NeoVim feels sluggish compared to Helix.
Of course, if you offer only a portion of NeoVim's features the speed improvement should not be surprising.
Anyway, can you name a few NeoVim features you miss in Helix? I still use NeoVim now and then, so I'd be happy to learn more, even if it's something small.
This is one area where NeoVim afaik comes out on top: Vimscript isn't fast, and NeoVim allows Lua plugins via the embedded LuaJit, and those should be significantly faster.
Five years ago:
time emacs -Q -eval '(kill-emacs)'
But on a "recent" AMD 7700X that'd be 80ms.
That's starting emacs, evaluating elisp code, and exiting Emacs.
Surely if you can start Emacs, execute elisp, code and exit in 80ms it shouldn't lag too much to insert a character.
Now, I know, some modes can be slow. But Emacs in recent version as seen lots of changes enhancing its performances. And hardware have become really very fast.
YMMV but my Emacs is really incredibly responsive.
P.S: I was already using Emacs on a 486 back in the "Eight Megabytes And Constantly Swapping" days. The joke was fun and true. Nowadays Emacs is actually one of the lightest sofware I use.
$ tim 'vim --clean -c quit' 'nvim --clean -c quit' 'emacs -nw -Q -eval "(kill-emacs)"'
(3.45 +- 0.27)e-04 (AlreadySubtracted)Overhead
(7.929 +- 0.052)e-03 vim --clean -c quit
(8.329 +- 0.031)e-03 nvim --clean -c quit
0.05302 +- 0.00023 emacs -nw -Q -eval "(kill-emacs)"
EDIT: BTW, chances are good that the 4X reduction from 320ms to 80ms over 5 years you are seeing is in large part due to ahead-of-time native compilation of elisp (https://www.gnu.org/software/emacs/manual/html_node/elisp/Na... ) and libgccjit/etc. not just CPU/DRAM improvement.
[9front@RIPPER ~]$ time emacs -Q -eval '(kill-emacs)'
real 0m0.193s
user 0m0.136s
sys 0m0.010sI know for a fact that vim is faster than Emacs and I'm pretty sure it uses an array (although I don't know that for a fact).