3 ms·
I've never constructed an editor -- but I have used one before ;) so I thought I'd make a few suggestions about the architectural considerations off the top of
by todd8 11y ago
I've never constructed an editor -- but I have used one before ;) so I thought I'd make a few suggestions about the architectural considerations off the top of my head. I'm an Emacs user, but I'm very excited about NeoVim. It looks like your project is another really interesting one. I hope it takes off.
I notice that you've choosen Rust as the programming language for the editor, a fine choice. Performance appears to be a key factor in your choice of language. However, realize that performance isn't the reason one should use Rust or C++ for the backend of an editor. Let's go though some simple back of the envelope calculations. A realistic goal for editors is to keep ordinary command and keystroke latency under 100ms, this should appear to users as if operations are performed instantaniously. You've picked a more aggressive goal of a maximum latency of 16ms, so let's go with that.
Today, a slow processor runs perhaps 5,000,000,000 instructions per second (speed of Raspberry Pi 2). By the time the editor is ready for general use, most programmer's development systems will probably run something like 20 times faster or 100 Billion instructions per second. For this rough calculation I'll use the speed of a Raspberry Pi 2. In 16ms that's 8 million instructions.
What this means is that in the backend of the editor we have plenty of time to perform the editing operations no matter what language is used as long as it is a straight code path through the editor. The pedestrian operations of the editor, like reading a keystroke or inserting a letter into the text don't require Rust or C++ or C. They can be done with practically any programming language, even a language that runs a hundred times slower than C++ like Python. It is the iterated operations where performance will be a concern: searching big files, complex regular expression searches, syntax highlighting after each keystroke, autocomplete, refactoring, the GUI and interfacing to the GUI.
I couldn't agree more with your requirement that the editor shouldn't hang or crash or lose work. Further, a modern editor is a big project and won't gain traction without additional contributors. From a performance perspective my gut feeling is that any language that performs no worse than 10 times slower than C is a fine choice. For safety, either managed memory (with GC etc.) or an approach like Rust is essential to allow code to be contributed. The JVM languages, while being attractive in many ways carry the burden of a big infrastructure; Jetbrains has figured it out but even after all these years Eclipse feels so klunky--this make me rule out Java, Clojure and Scala. I think this leaves at least Rust, Go, OCaml, Common Lisp, Dart, and Swift. (I'd probably pick Go hoping to get more contributors.)
What about ropes, a clever and much more modern data structure for holding strings than ancient Emac's gap buffer. Ropes do indead have better asymptotic performace for many of the basic string operations: delete an arbitrary character, insert a substring, etc. What about all of the other operations that you'd like your editor to do? Fast searching, backwards or forwards? Handling UTF-8? Doing regular expression matching. Ropes turn the text being edited into a tree of text segments so high speed searching is much more difficult. An abstraction layer over the data structure to make it appear to be indexed like an ordinary array will make some things run much slower, for example, Boyer-Moore string searches, regular expression searching (done for code highlighting), etc.
Ropes or other persistent data structures for sequences will work because they can present an abstract indexed access interface to the rest of the program, but you will always be dealing with it though this abstraction layer just when you'd rather not. Processors can move several bytes per instruction cycle so the gap buffer can close it's gap while editing a 10MB file in less than a millisecond. This leaves the data in one contiguous block. So for simple things the gap buffer is much faster than rope structures because for most simple activity all of the additions and deletions are at the cursor, where the gap is located, and for complex things there is a 1ms overhead before the operation starts (to close the gap) but then things run basically full processor speed without the requirement to go though the abstraction layers. The places where I see this as likely to be important in modern editors is in the design of incremental backups, persistent text attributes, memory mapped access to underlying files, and coordination with asynchronous plugins working on the buffer. I'll be curious to see how this works out for Xi.
Keystrokes and plugins. Emacs can end up running lisp code, through a pretty slow lisp interpreter, on every keystroke. It's completely imperceptable. So performance isn't a reason to treat keybindings differently than other plugins. The overhead of IPC to a plugin is measured in micro seconds.
While supporting Sublime Text keybindings is fine. The programmers most likely to be sensitive to keybindings will probably want either Vim or Emacs keybindings. A good way to support multiple keybindings will make the editor appeal to a much broader set of users. Plugins seem ideal for this. A key comes in, is processed by a plugin and a few elemental backend operations are invoked by the plugin in response to the key. This seems completely reasonable.
The real issue with plugins is direct access to the edit buffer if the plugins run in a separate process and address space. This is complex especially if the buffer is being accessed asynchronously. How is syntax highlighting done in a plugin for example. Where does the syntax highlighting actually get stored? Does the plugin have to be informed each time the user scrolls the screen or types a key (probably yes). What asynchronous commands does the plugin send back to the editor to update the display. Is there a separate plugin working on autocomplete? Does it also have to parse the source code just like the syntax highlighting plugin? Well those are things to figure out, but the keystroke bindings seem much easier to address in a plugin. Plugins provide a convienient place to address the semantic difference between a modal editing model (used extensively by Vim and to a degree by Emacs editors) and the underlying editor backends capabilities.
- raphlinus 11y agoThanks for your thoughtful comments. I'll try to address some. Using ropes is a tradeoff. A gapped buffer is viable for the reasons you state, but I think ropes come out ahead for what I'm trying to do. It's not so much the cost of filling the gap, as that ropes really facilitate parallel, incremental, and asynchronous computation. For example, I want the "save" operation to write a snapshot of the current buffer to disk, while still being fully editable. The snapshot operation is trivially easy and fast with immutable ropes, but if you tried to hack something like that on top of a gapped buffer, it would increase complexity dramatically. If you look at the implementation of my Unicode line breaking algorithm, you'll see that the indirection cost of the rope abstraction is minimal. In fact, it _flies_ - in my tests, it's about 3x faster than ICU working on a contiguous string. This is because it's able to work on a leaf at a time. The same can be done for search, etc. Yes, it'll require some reimplementation of string basics, but I personally find that kind of thing fun. I'm still working out the plugin story. Quick answers to your questions though. A syntax highlighting plugin sees a window of the source buffer (effectively a cache, with invalidation by RPC). I'm thinking a contiguous buffer for the window, not a rope - it'd be bounded by a few megs. For a huge file, computing the syntax highlight of what's off screen can be slow. In no case does it block typing, worst case there's a lag before the colors resolve. The plugin sends the annotations back as rich-text spans, which are stored in the core. Scrolling is instant and doesn't inform the plugin. The autocomplete plugin will almost certainly be separate from the syntax highlighting one (but presumably an author could create a combo plugin if it had advantages). This doesn't address everything you brought up, but hope it helps illuminate some of my thinking.
- martanne 11y agoAs the main developer of an editor (vis) using a similar segmented data structure (a piece chain, similar to a rope, but storing the text junks in a double linked list, thus asymptotically worse) I can attest that the performance is generally very good. Some work will be required to adapt/write a regexp library around some kind of iterator interface, but in general I found that persistent data structures are very well suited for editors. One problem with the gap buffer is that as soon as you have multiple cursors/selections or in my case structural regular expression support, then you have to move the gap around all the time. Also undo/redo support is simply not as elegant as with a persistent data structure. For syntax highlighting copying the relevant text region into a contiguous memory block is simple and works well. For now I'm trying a completely stateless approach to syntax highlighting i.e. the text coloring is always completely recalculated. This trades highlighting accuracy for simplicity, but in practice the results aren't too bad. Efficient syntax highlighting for huge files is a hard problem.