Editor perf: markers vs. tracking spans

Rico just put up an interesting post on editor performance, so if you have a few minutes, go check it out.

I thought I'd take a minute and give a bit more detail on one of the topics Rico mentions, which he called regions (but are really called markers; po-TAY-to, po-TAH-to, and all that).

(Old editor) VS markers

There are quite a few clients to the editor that want to track a piece of text in a given buffer through edits made to the buffer. Things like bookmarks, breakpoints, error squiggles, and outlining regions (a.k.a. folds) are all examples that either work through markers or just are conventionally tracked through markers. Markers can have some type of associated UI, like the red highlight of a breakpoint, but they don't have to. Outlining regions, for example, don't require markers to be created on the client side, but it's common for language services to create invisible markers to keep track of their positions.

That's all well and good, and it's a service that is truly required, but there are two seemingly small characteristics of markers that make them a huge performance tax on the old editor.

First and foremost, markers are tracked on every edit. Since there is only one real version of the old editor's buffer contents (i.e. what you see on the screen at any time), markers are always accurate against that version. This means that every time the user types a character, the editor has to go through every single marker and figure out where its new position should be. The simple cases are the ones you may expect - if the change comes before the marker, it pushes the marker towards the end of the file; if the change comes after the marker, the marker doesn't move.  However, there are various behaviors for when changes intersect the marker in some way, and there’s a rather nasty little piece of code in the old editor to manage that.

Added to that, there is an optional callback mechanism on markers, so clients can ask to be notified when the marker "moves", where "moves" means that the absolute offset from the start of the buffer or length have changes. This means that if you type a "u" at the very first position in the buffer, the editor has to walk every single marker to figure out if any clients have requested a callback, and inform them that their marker has moved 1 character towards the end of the buffer. Fortunately, this mechanism isn't used all that much, but it's still something that has to be dealt with.

In the past, clients have done some rather heroic things to mitigate these issues. Things like combining what would be multiple edits into a single edit, so that it would be one pass through the markers instead of many, were common. It was an unfortunate but necessary tradeoff.

As Rico said, we've provided a rather comprehensive shim layer over the old editor, which includes markers. Since the real issue with markers wasn't so much the implementation of markers but the design of markers, there wasn't too much we could do to make it faster. This is one of those areas where the only way to get a performance improvement is to move off markers and move forward to the new editor interfaces. That leads us to...

(New editor) Tracking spans (and text markers)

First off, in the new editor, we've split markers into a few parts.

Most marker visualization, like breakpoints use for the red text background, is accomplished through Text Markers, surfaced as TextMarkerTags, provided via Tagging.  Sorry for the confusing naming :(

Squiggle visualization, used for errors of various types, is accomplished through  SquiggleTags, which really should be called something like ErrorTag or similar, as they don't really have anything to do with squiggles, though they happen to be visualized as such.  I still have my fingers crossed that the name will be different in the future.

And the really important part, which is tracking text as the buffer changes, is exposed through tracking spans (ITrackingSpan).

A tracking span is used for basically the same purpose as an (invisible) marker - you create a span over a piece of text, and you can ask for that span's position after the text has changed. But there is one huge difference in how tracking spans operate: tracking spans are evaluated lazily.

If you create a tracking span and then never ask for its position, it will never do anything. Tracking spans don't participate in buffer changes, so you could create a million tracking spans and not pay any cost if you never actually ask them where the span has moved to.

We can do this because of another point Rico mentioned - Snapshots and Versions.

The new editor's data model (for the text buffer) is very functional (as in functional programming, not a measure of "it works well"). A buffer, at its core, is just a Snapshot/Version plus some methods for creating and applying edits. When an edit is applied, the buffer creates a new Snapshot, which shares almost all its data with the previous Snapshot, and places the change deltas in the Version. In this way, there is a complete history of the contents of the buffer (in the past Snapshots), and a complete history of what edits were made in the buffer (in the past Versions).

So, let's say you create a tracking span on version 2, and the user types a couple of times. You want to know where the span is now, so you ask for the span on version 6 (or you ask for the span against the current Snapshot; either works). The tracking span then walks from version 2 to version 6, seeing which changes would cause the span to move, and gives you back the span's position in the new version.

The worst case behavior of tracking spans, then, is that someone treats them exactly as markers. If you create a large number of tracking spans, and request every single span's position on a new version on every single text change, it will be doing just as much work as the markers (minus the callbacks). This is basically what the marker shims do, in order to fulfill the contract of the old marker APIs.  So, the laziness is only helpful if clients use it to their advantage.

Fidelity modes

Next, there are few different kinds of tracking "fidelity" modes. The most common usage of these spans is to keep tracking them forward as the buffer changes (this is basically the only service the old editor markers provided), and so the most common fidelity mode is forward fidelity. What the means is that, when the tracking span gets tracked to version 6, it remembers the span in version 6 and forgets the span from version 2. This means that the next time you ask for it's position in version 6, it won't require any work (besides the check to see if the version requested is the same as the cached span's version).

The other commonly used fidelity mode is backward fidelity. In this mode, the span never forgets the original span it was created on, so you can always track to any version/snapshot that is after the original version/snapshot, without loss of fidelity (tracking before the version that the span was created on will behave just like a forward fidelity span - it'll work, but it may not be exactly what you want). Unless you really need them, however, these should be avoided; because they always remember the old snapshot and version, they'll keep them in memory as long as they're alive, which means the CLR won't be able to collect them. Snapshots and versions are designed to only point forwards in time, so as soon as the last person stops referencing an old snapshot/version, they can all be collected along the chain until the next snapshot/version that someone is holding on to. If you create a backward fidelity tracking span on the very first snapshot, then no snapshots will ever be collected (same goes for a forward fidelity tracking span that you never track), until that tracking span becomes collectible.

Tracking modes

I should also talk briefly about tracking modes; there aren't any performance considerations associated with which mode you pick, but it's important to understand what each means.

There are four different SpanTrackingModes that can be used to specify the tracking behavior of the span when text is changed at its endpoints. There is also an ITrackingPoint, which is basically the same as a 0-length tracking span, and it has PointTrackingModes, so I'll start there.

First off, tracking modes only apply when text is inserted at the point (in the case of a tracking point) or at either of the endpoints (in the case of a tracking span). If text is inserted before the span/point (and not at the point or immediate start of the span), the point/span always moves towards the end of the buffer. If text is inserted after the span/point, it doesn't move. If text is inserted in the middle of the span, the endpoint of the span moves towards the end of the buffer.

There are two point tracking modes: Positive and Negative. Positive is analogous to "move like the caret/cursor does when you type". If you think of typing as inserting a character at the position of the cursor (or, as it visibly appears, just after the cursor, if you think of the cursor as appearing between characters), then the cursor always moves to the right of the newly inserted text. Positive means "towards the end of the buffer". If the cursor was negative, then, it would appear to not move, but the text would be inserted to the right of the cursor.

The four span tracking modes are just the four possible combinations of point tracking modes for its endpoints.

SpanTrackingMode	Start	End
EdgeExclusive	Positive	Negative	Never grows to include text inserted on the endpoints
EdgeInclusive	Negative	Positive	Always grows to include text inserted on the endpoints
Positive	Positive	Positive	Grows to include text inserted at the end of the span
Negative	Negative	Negative	Grows to include text inserted at the beginning of the span

EdgeExclusive is the most common, and EdgeInclusive the next most (Negative and Positive are fairly rare, as there aren’t too many use cases for them).  EdgeExclusive has the nice property that abutting spans (spans that touch on the endpoints but don’t overlap) will never overlap when tracked in this way (since neither one will ever grow towards the other).  Thus, if you are tracking lots of spans as EdgeExclusive, then their relative order will never change, where order is a combination of start point and length.

Things to remember

In order to ensure your extension performs well, there are a few simple things to remember:

Use forward fidelity spanswhere you can, unless you absolutely need backward fidelity tracking.  If you do need backward fidelity tracking, try and use the tracking span for as short a period as possible (don’t hold references to the tracking span after you are done with it, and it will get collected).

Track only what you need, when you need it.  If you have, say, a sorted list of EdgeExclusive tracking spans that don’t overlap, and you want to find which spans intersect a given span (this is applicable to a tagger or classifier you may write), you can use a binary search and just track the items along the path of the binary search.  Because you are using EdgeExclusive tracking spans, you are guaranteed that the sorting will be stable through text changes, so you don’t actually need to track the “gaps” in the binary search.

Use new APIs, when appropriate.   If you have existing code that uses markers, it’s probably fine to keep around; for example, we’ve never seen a noticeable performance impact from the markers that come from breakpoints, because there aren’t usually that many.  However, if you had something that was creating a very large number of markers, and have found in the past that that was a performance issue, it may be a good idea to move off the old marker API.

Comments appreciated.  Thanks!