Why a text editor stores its lines in an array, not a linked list

Before a text editor can do anything interesting, it has to answer one very basic question: where do the lines go? To edit a text file, you split it into lines, and after that almost every operation — moving the caret, typing a character, searching, repainting — begins with finding line N.

Crimson Editor solved that in 1999 with a doubly-linked list, and kept it that way for twenty-five years. This year we moved it to an array. This post explains why. It turned out the linked list was slower than the array even at the operation it’s supposed to be best at.

The lines started out in a linked list

Two MFC CLists, to be exact — one holding each line’s text and syntax tokens, the other its on-screen layout.

For editing text, a linked list looks like the natural choice. Editing is ultimately about inserting and deleting in the middle, and a linked list inserts in O(1). But reaching line N — FindIndex(N) — is O(n). It’s the classic trade-off you learn in school.

But as files grew, the problem showed.

Finding line N was worse than O(n)

Here are the results of running FindIndex() on a 900,000-line document:

line	FindIndex
1,000	2.4 µs
100,000	367 µs
450,000	3,220 µs
899,999	6,984 µs

The cost of finding a line wasn’t linear. Reaching a line nine times deeper took nineteen times as long.

In theory the cost is O(n), but the measured numbers climbed far more steeply than that. The reason was cache locality.

Each node sits somewhere different on the heap. Walking the list means visiting scattered memory one node at a time, and each hop tends to miss the CPU cache. So following a single next pointer costs you a round trip to memory.

And in an editor, finding a line happens constantly. Caret movement, editing, searching, highlighting, repainting — all of it goes through this. Near the bottom of a big file, every keypress was spending about 7 ms.

The list lost at middle insertion, too

Usually you accept slower lookups in exchange for fast insertion in the middle — that’s the reason to pick a linked list.

But when you think about it, to insert a line in the middle you first have to find the spot.

on 900,000 lines	linked list	array of pointers
reach the last line	6,879 µs	~0 µs
insert a line in the middle	3,378 µs	187 µs
insert a line at the very front	0.3 µs	265 µs

InsertBefore() itself is O(1), but you have to run FindIndex() first. The lookup ends up dominating, so the array — which memmove()s half the file — comes out 18× faster.

What replaced it, and the new problem

Crimson Editor’s new container, CLineList, is a std::vector<Line*>. It stores pointers, not objects.

There are two reasons to store pointers:

1. On insertion, only 8-byte pointers move, not whole lines.
2. A line object’s address never changes, so existing references don’t break.

Both lookup and insertion got faster. But a new problem appeared.

In the linked list, a POSITION is a pointer to a node, so it’s stable. In the array, it’s an index — and inserting or deleting a line in the middle shifts every index after it.

This is the hardest kind of bug to debug. The program runs fine; it just edits the wrong line.

So in debug builds we tag every POSITION with a version number, and reusing an old index after a structural change fires an assert immediately.

Bulk edits

In an array, deleting one line at a time in a loop means one memmove() after another.

So we added bulk operations like InsertGap(), RemoveRange(), and ReplaceRange(). The structure changes only once, and performance improves dramatically.

It mattered most for something like word wrap, where one line turns into several on-screen rows.

• one row at a time, across 90,000 lines: 2,779 ms
• handed to ReplaceRange() in one call: 168 ms

Looking back

The biggest thing this work taught me is that Big-O alone can’t explain real performance.

In a text editor there’s always the cost of finding the position first, so the O(1)-insertion advantage barely ever showed itself. Cache locality, on the other hand, was the deciding factor.

Harder than swapping the data structure was the POSITION. The moment a stable node pointer became an index, every assumption in the existing code changed — and the compiler offered no help at all.

For a long time, “a linked list for a text editor” was treated as the right answer. On small files it’s still a perfectly good choice. But on big files it became the bottleneck — and the fix was a far more ordinary data structure than you’d expect: an array.