Optimizations in Syntax Highlighting
Join VS Code at Microsoft Ignite or catch the sessions online. A year of VS Code, wrapped. Explore the highlights. On this page Visual Studio Code version 1.9 includes a cool performance improvement that we've been working on and I wanted to tell its story. TL;DR TextMate themes will look more like their authors intended in VS Code 1.9, while being rendered faster and with less memory consumption. Syntax Highlighting Syntax Highlighting usually consists of two phases.
Tokens are assigned to source code, and then they are targeted by a theme, assigned colors, and voilà, your source code is rendered with colors. It is the one feature that turns a text editor into a code editor. Tokenization in VS Code (and in the Monaco Editor ) runs line-by-line, from top to bottom, in a single pass. A tokenizer can store some state at the end of a tokenized line, which will be passed back when tokenizing the next line.
This is a technique used by many tokenization engines, including TextMate grammars, that allows an editor to retokenize only a small subset of the lines when the user makes edits. Most of the time, typing on a line results in only that line being retokenized, as the tokenizer returns the same end state and the editor can assume the following lines are not getting new tokens: More rarely, typing on a line results in a retokenization/repaint of the current line and some of the ones below (until an equal end state is encountered): How we represented tokens in the past The code for the editor in VS Code was written long before VS Code existed.
It was shipped in the form of the Monaco Editor in various Microsoft projects, including Internet Explorer's F12 tools. One requirement we had was to reduce memory usage. In the past, we wrote tokenizers by hand (there is no feasible way to interpret TextMate grammars in the browser even today, but that's another story). For the line below, we would get the following tokens from our hand-written tokenizers: tokens = [ { startIndex: 0 , type: 'keyword.js' }, { startIndex: 8 , type: '' }, { startIndex: 9 , type: 'identifier.js' }, { startIndex: 11 , type: 'delimiter.paren.js' }, { startIndex: 12 , type: 'delimiter.paren.js' }, { startIndex: 13 , type: '' }, { startIndex: 14 , type: 'delimiter.curly.js' } ]; Holding on to that tokens array takes 648 bytes in Chrome and so storing such an object is quite costly in terms of memory (each object instance must reserve space for pointing to its prototype, to its properties list, etc).
Our current machines do have a lot of RAM, but storing 648 bytes for a 15 characters line is unacceptable. So, at the time, we came up with a binary format to store the tokens, a format that was being used up to and including VS Code 1.8 . Given that there would be duplicate token types, we collected them in a separate map (per file), doing something like the following: // 0 1 2 3 4 map = [ '' , 'keyword.js' , 'identifier.js' , 'delimiter.paren.js' , 'delimiter.curly.js' ]; tokens = [ { startIndex: 0 , type: 1 }, { startIndex: 8 , type: 0 }, { startIndex: 9 , type: 2 }, { startIndex: 11 , type: 3 }, { startIndex: 12 , type: 3 }, { startIndex: 13 , type: 0 }, { startIndex: 14 , type: 4 } ]; We'd then encode the startIndex (32 bits) and the type (16 bits) in 48 bits of the 53 mantissa bits a JavaScript number has.
Our tokens array would finally look like this, and the map array would be reused for the entire file: tokens = [ // type startIndex 4294967296 , // 0000000000000001 00000000000000000000000000000000 8 , // 0000000000000000 00000000000000000000000000001000 8589934601 , // 0000000000000010 00000000000000000000000000001001 12884901899 , // 0000000000000011 00000000000000000000000000001011 12884901900 , // 0000000000000011 00000000000000000000000000001100 13 , // 0000000000000000 00000000000000000000000000001101 17179869198 // 0000000000000100 00000000000000000000000000001110 ]; Holding on to this tokens array takes 104 bytes in Chrome.
The elements themselves should take only 56 bytes (7 x 64-bit numbers), and the rest is probably explained by v8 storing other metadata with the array, or probably allocating the backing store in powers of 2. However, the memory savings are obvious and get better with more tokens per line. We were happy with this approach and we've been using this representation ever since. Note: There may be more compact ways of storing the tokens, but having them in a binary-searchable linear format gives us the best trade-off in terms of memory usage and access performance.
Tokens <-> Theme matching We thought it would be a good idea to follow browser best practices, such as leaving the styling up to CSS, so when rendering the above line, we'd decode the binary tokens using the map , and then render it using the token types like this: < span class = "token keyword js" > function </ span > < span class = "token" > </ span > < span class = "token identifier js" > f1 </ span > < span class = "token delimiter paren js" > ( </ span > < span class = "token delimiter paren js" > ) </ span > < span class = "token" > </ span > < span class = "token delimiter curly js" > { </ span > And we'd write our themes in CSS (for example the Visual Studio theme): ... .monaco-editor.vs .token.delimiter { color : #000000 ; } .monaco-editor.vs .token.keyword { color : #0000FF ; } .monaco-editor.vs .token.keyword.flow { color : #AF00DB ; } ...
It turned out quite nicely, we could flip a class name somewhere and immediately get a new theme applied to the editor. TextMate Grammars For the launch of VS Code, we had something like 10 hand-written tokenizers, mostly for web languages, which would definitely not be sufficient for a general-purpose desktop code editor. Enter TextMate grammars , a descriptive form of specifying the tokenization rules, which has been adopted in numerous editors.
There was one problem though, TextMate grammars didn't work quite like our hand-written tokenizers. TextMate grammars, through their use of begin/end states, or while states, can push scopes that can span multiple tokens. Here's the same example under a JavaScript TextMate Grammar (ignoring whitespace for brevity): TextMate Grammars in VS Code 1.8 If we were to make a section through the scopes stack, each token basically gets an array of scope names, and we'd get something like the following back from the tokenizer: tokens = [ { startIndex: 0 , scopes: [ 'source.js' , 'meta.function.js' , 'storage.type.function.js' ] }, { startIndex: 8 , scopes: [ 'source.js' , 'meta.function.js' ] }, { startIndex: 9 , scopes: [ 'source.js' , 'meta.function.js' , 'meta.definition.function.js' , 'entity.name.function.js' ] }, { startIndex: 11 , scopes: [ 'source.js' , 'meta.function.js' , 'meta.parameters.js' , 'punctuation.definition.parameters.js' ] }, { startIndex: 13 , scopes: [ 'source.js' , 'meta.function.js' ] }, { startIndex: 14 , scopes: [ 'source.js' , 'meta.function.js' , 'meta.block.js' , 'punctuation.definition.block.js' ] } ]; All of the token types were strings and our code was not ready to handle string arrays, not to mention the implications on the binary encoding of tokens.
We therefore proceeded to "approximate"* the array of scopes into a single string using the following strategy: Ignore the least specific scope (i.e. source.js ); it was rarely adding any value. Split each remaining scope on "." . De-duplicate unique pieces. Sort the remaining pieces with a stable sort function (not necessarily lexicographic sort). Join the pieces on "." . tokens = [ { startIndex: 0 , type: 'meta.function.js.storage.type' }, { startIndex: 9 , type: 'meta.function.js' }, { startIndex: 9 , type: 'meta.function.js.definition.entity.name' }, { startIndex: 11 , type: 'meta.function.js.definition.parameters.punctuation' }, { startIndex: 13 , type: 'meta.function.js' }, { startIndex: 14 , type: 'meta.function.js.definition.punctuation.block' } ]; *: What we were doing was plain wrong and "approximate" is a very nice w
The rest of this page is on the live site.