Shardable, O(N/m) Editor Infra

Published Dec 19, 2020

Writing text editors is my hobby. Over the last few years, I've been researching on how to make the editor "fast" -- faster than any other editor out there.

My editor assumes that there is infinite memory. It views memory as a field, much like magnetism -- it exists, it's all around us, and you can't "run out." [Justification: I'm the sole user of a 12 processor 24 thread 4GHz machine with 64GB of RAM -- it would be criminal not to make full use of the machine!]

My editor has one goal: speed. If it can be done faster, I'm all for it.

So, let's get to the guts.

An editor's heart and soul is the line database. In its simplest form, it's an array of pointers to characters, with the characters forming the lines in the document. The usual C convention of nul-termination is followed, allowing lines of arbitrary length.

My editor is constructed on a vector of OneLine objects, each consisting of:

struct OneLine
{
	uint32_t	flags;	// line notations
	const char	*ptr;	// pointer to line content in the memory field
	OneList		*list;	// side list
};

I'll delve into the operation by way of examples that should be familiar pain points to all editor users. [Note: see my subsequent article, [16]Cracking the Editor's Back, for some updates on this facet of the architecture.]

Deleting Lines in O(N)

First off, deleting lines should never be an O(N^2) operation -- if you're doing a g/rexp/d operation, then it's got to be done as a "tag & bag". The g command runs around and tags all the lines that match the expression. It then executes the d command on each line to be deleted.

In a traditional editor's O(N^2) implementation, the g command invokes the d command handler for each line; each d command deletes its line by moving all the other lines up by one. And then the next d command does the same thing, and so on.

In my implementation, the lines are simply marked as "to be deleted" in their flags field, and then a single pass "compresses" the array.

This is the first architectural component -- operations are divided into a logical and physical phase. Here, to logically delete lines, we mark them as "gone". Then, (when the g command is done), we resolve the logical operations into a physically consistent representation.

Inserting Lines in O(N)

The next pain point is inserting lines. For example, you want to split lines based on spaces, so you execute %s/ /\n/g to replace all spaces with newlines. Most editors today will go through each line that matches, construct a working buffer that expands the original line by replacing spaces with newlines, and then insert each new line, one at a time, into the line array.

You guessed it, that's O(N^2).

In my implementation, the replacement lines are simply expanded (by replacing spaces with newlines) and placed into the OneList object that's part of each line:

struct OneList
{
  OneList              *next;
  vector <const char *> lines;   // one or more memory field lines
};

That's the logical phase. When the s command is finished, the resolver comes around and "expands" the array.

This is the second architectural component -- a side list for each line that contains logical expansion. The resolver counts the total delta in the line array -- did it grow (because I'm adding lines, like in this example) or did it shrink (because I'm deleting lines, like in the previous example)? If the resolver computes that the array is to be grown, we grow it, move the existing const char * line pointers into the side list, and then "expand" all side list elements back into the array.

Reversing all Lines in the File in O(N)

The "kryptonite" for the editor is the g/^/.m0 command. This expands to "find all lines" (the g/^/) part, and then, for every line that you've found, move it to after line 0 (the .m0 part). A traditional editor does it in O(N^2) because the first line is moved to after line zero (this isn't interesting, as it's already there). The second line is moved to after line zero (so, the second line is removed, the first line is pushed down one, and the second line replaces where the first line had been). The third line is moved to after line zero... and so on.

I do that in O(N) in my editor. In the logical phase, I delete the line from the array and insert it into the side list after line zero. I do this for all lines. Since the insertion is a list operation, it takes no time at all (my next pointer points to the list's next pointer, and the list now points to me -- linear nanoseconds). What this ends up looking like after the logical operations have finished is that all the lines in the array are marked as deleted, and line 1 has a ginormous list hanging off of it. The physical resolver now comes in, computes the new size of the array (same -- no change), and expands the list into consecutive lines.

Who cares?

So, who cares? CPUs are plenty fast, and if your editor can't handle deleting lines fast enough, then you should run it through grep or something first.

Yuck.

I spend most of my life in an editor. If I need to look at a log file to see why something is misbehaving, I don't want to first think about how big that log file might be, and what operations I might want to perform on it. I just need to be able to do stuff. The three use-cases I described above are tremendously useful when analyzing log files and data dumps. Obviously, deleting extraneous information is the first step (or, deleting that information into a buffer and bringing it into another document; same problem). Splitting lines apart is another high runner for me -- mainly to break lines apart into chunks I can operate on. And reversing lines in the file? I use that all the time -- but not for "reversing" lines in the file, but rather for organizing similar events. For example, g/good/.m0 to take all the events that I consider to be "good" and put them somewhere, and then later, g/bad/.m$ to take all the "bad" events and put them somewhere else. When you have a fast editor that can do "all that" you start to get creative.

And now ... O(N/ncpu)

Believe it or not, we can get better than O(N) performance -- with a multicore CPU!

The architecture described above, that is, dividing things into a logical and physical operations phase, readily lends itself to multicore applications.

First of all, the g/rexp/ command can be sharded over all cores in the system. Each core is assigned a range in the line database, and deals with tagging the flags field. These are all independent operations.

Now comes the pièce de résistance: multicore execution. I'll put this on its own line, because it's key:

All logical operations are threadsafe!

Let's consider an expansion substitution (our friend, the %s/ /\n/g command to replace spaces with newlines). We can shard this over all the CPUs in the box because it operates completely in the logical domain associated with each line! There is no interference with anything that other lines are doing!

[Yes, certain operations must be sequenced like the line reversal operation, and thus can't be sharded].

Conclusion

In conclusion, I hope I've inspired you to think about how to improve your favourite editor so that it's O(N/cpu) fast.

Frequently Asked Questions

Why do you use a const char *? Because it's the fastest thing out there. I use the C++ std::string internally for operations because they provide a nice interface, but the line database is stored in the memory field as a pointer to char. Furthermore, consider the operation of expanding a line that contains newline characters (as a result of the %s/ /\n/ operation) -- the resulting line is copied into the memory field, and the \n characters are replaced with nuls. The line array pointers now point into the individual lines thus created.
How can you load files fast? My editor mmap()s the file, and then shards CPUs over it in two phases -- the first phase counts the number of line terminators (be they \n for POSIX, \r for DOS, or 0x1e for QNX 2). When all the threads have completed, I grow the base array (once) and then do the second phase shard to populate the line pointers.
What is the memory field concept? The editor never releases memory associated with lines. This simplifies life so much that it's not even funny. I don't need reference counts, and I know that the pointer to the line is always valid. In fact, this is a requirement -- if you want infinite undo/redo (mine has that) then you really can't get rid of the line database! In this regards, then, I consider memory "like a field, like magnetism" -- it's always there, and you don't run out.
Why don't you go help an open source project with their editor? Have you seen the source for typical open source editors? My complete editor is 12k lines and does everything I need. For comparison, VIM is 300+k lines of code. I tried looking at the function that reads a file into the line database -- it's 2,400 lines of code, written in a "stream of consciousness" model that's littered with #ifdefs. Mine is 240 lines of code and is actually spread over three functions (main-line, and the two shard worker threaders). And then there's the politics. Life is too short.
How would I implement a dictionary? Using the memory field concept, I implement a dictionary (for spelling and identifier highlighting) using a trie. See my Optimizing Scrabble article for some details. I currently have three dictionaries: Trie<28,OneSpelling> for spelling, Trie<64,OneAnnotation> for C/C++/keywords highlighting instances, and Trie<64,vector<OneTag>*> for the tags. Hmmm... I should write another article :-)
Can I get the source? Sure, I'm happy to share the source. But beware, it's not exactly like vi (long story short: my buddy wrote a vi-like editor 30+ years ago that I got used to; unfortunately, it wasn't quite like vi, but ... that's what mine mimics), and the source base is entangled with libraries that I use (for things like command line option processing, etc.). So, it'll be a bit of work for you, but it should give you a good start. Email me. And no, it's not contaminated by GPL :-)
Is everything shardable? Most things are. Even things that you might not believe are shardable. Read my Sharding the Unshardable article for ideas on sharding hashes and syntax highlighting.