Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Optimizations in Syntax Highlighting

code.visualstudio.com

Post reply on HN
Print view View original

31–40 of 55 posts

Re: Optimizations in Syntax Highlighting

#31

Post by alexdima »

nhaehnle wrote: post #23
trishume wrote: post #5

Shameless plug: my implementation of Sublime's syntax highlighting engine in Rust has similar optimizations and more. I'm not at my computer to benchmark on the same files but it should be >2x as fast as their "after" numbers just based on lines/second for JS-like files. This evening I'm even trying to port it to a pure Rust regex engine that should eliminate non-Rust code and make it substantially faster. It also im…

Thanks for this. Clearly the original post describes good work, but I can't help feeling the JS community is slacking off when it comes to performance. Just eyeballing the cited numbers, they take 3939ms to handle a 1.18MB input on "a somewhat powerful desktop machine". Assuming that that means a chip running at 2GHz, we're talking about over 6300 cycles per byte! That's quite frankly ridiculous. An improvement by at…

I hate slowness and inefficiency too, that's why I try to make the editor as fast as possible :), but at least in this case, it is not the dynamic nature of JS to blame, but rather the nature of TM grammars. TM grammars consist of rules that have regular expressions, which need to be constantly evaluated; and in order to implement a correct TM grammar interpreter, you must evaluate them.

I've looked in the past for optimization opportunities in the C land (mostly through better caching), which yielded quite nice results [1][2]. I would love if you'd want to take a look too.

At this point, in tokenization, 90% of the time is spent in C, matching regular expressions in oniguruma. More precisely, regular expressions are executed 3,933,859 times to tokenize checker.ts -- the 1.18MB file. That is with some very good caching in node-oniguruma and it just speaks to the inefficiency of the TM grammars regex based design, more than anything else.

It is definitely possible to write faster tokenizers, especially when writing them by hand (even in JS), see for example the Monaco Editor[3] where we use the TypeScript compiler's lexer as a tokenizer.

At least in this case, inefficiencies are not caused by our runtime.

[1] https://github.com/atom/node-oniguruma/pull/40

[2] https://github.com/atom/node-oniguruma/pull/46

[3] https://microsoft.github.io/monaco-editor/

Re: Optimizations in Syntax Highlighting

#32

Post by trishume »

algorithmsRcool wrote: post #9
trishume wrote: post #4

Earlier quoted context omitted.

The reason is that they basically rely on using the Oniguruma regret engine, and reimplementing that in JS would be hella slow.

> using the Oniguruma regret engine I'm surprised I've never seen that typo for regex before. It's wonderful.

lol I typed that on an IOS device correctly but it autocompleted it since "regex" isn't a real word apparently.

Re: Optimizations in Syntax Highlighting

#33

Post by trishume »

jbmorgado wrote: post #30
mrgalaxy wrote: post #2

> there is no feasible way to interpret TextMate grammars in the browser even today That doesn't sound right... but then again I don't know enough about TextMate grammars to argue.

What I don't understand is why do we still use TextMate grammars. Can anyone explain why this is the case? It's not only in VSCode, I remember seeing something about TextMate grammars also in other editors.

Copy-pasted from a comment I made elsewhere:

It's harder than it sounds if you want to support many languages. The Sublime syntaxes repo I use has 34,000 lines of grammars whereas my engine is only 3000 lines of code. If you count all the tmLanguage files for nice languages available online it's probably hundreds of thousands of lines, and that's in a pretty dense format. The whole point of using tmLanguage files is that people don't care about how fast other languages are if there is no highlighting for their language. I could get way better performance by rewriting all those grammars using compiled parsers in Rust (like Xi has as an option https://github.com/google/xi-editor) but it would take an absurd amount of effort.

Re: Optimizations in Syntax Highlighting

#34

Post by trishume »

trishume wrote: post #5

Shameless plug: my implementation of Sublime's syntax highlighting engine in Rust has similar optimizations and more. I'm not at my computer to benchmark on the same files but it should be >2x as fast as their "after" numbers just based on lines/second for JS-like files. This evening I'm even trying to port it to a pure Rust regex engine that should eliminate non-Rust code and make it substantially faster. It also im…

So I ran the sqlite3.c benchmark on my machine (a comparable "somewhat powerful" machine) and it took 6.7s with my engine vs 10.9s with the new VSCode one. Both are doing tokenization+theme matching but the machines and exact grammars are not necessarily the same. I'm using ST3's C grammar but they are using a different one. It could be that I ran it on a faster computer with an easier grammar, or it could be the opposite. It's close enough I'm not willing to claim my engine is substantially faster.

For context Sublime Text 3 takes 2 seconds with the same grammar and same file on the same computer due to using a better custom regex engine written specifically for highlighting.

Given what alexdima mentioned in a different comment about spending most of the time in the regex engine, I'm not sure that my engine would be substantially faster under exactly identical conditions since I'm also bottlenecked by Oniguruma.

However, maybe after I port my engine to https://github.com/google/fancy-regex I'll be substantially faster. And if I do it is likely they could also benefit from a fancy-regex port.

Re: Optimizations in Syntax Highlighting

#35

Post by flamedoge »

whatever_dude wrote: post #22
farnsworth wrote: post #21

Earlier quoted context omitted.

Automatic indentation saves a few keystrokes. A languages service (go to definition, etc) is what turns a text editor into a code editor!

A language service is for people with poor memory. A terminal window is what turns a text editor into a code editor.

I need OOP navigator to use C++/Java/C#

Re: Optimizations in Syntax Highlighting

#36

Post by trishume »

iveqy wrote: post #24

So VSCode is great in many ways, and the article might be interesting. But I would never call it fast. It's still really really slow. Just see this comparision: https://www.youtube.com/watch?v=nDRBxtEUOFE

That's not a perfectly fair comparison. Vim's syntaxes are often super simple and do a much less nice job at highlighting than most tmLanguage syntaxes.

Also all that video tests for is the presence of an optimization where it updates the on-screen colours as soon as that part of the file is done instead of after the entire file is done. It tells nothing about the underlying speed of the highlighting engines. Perhaps an important optimization, but not much information here.

Re: Optimizations in Syntax Highlighting

#37

Post by alexdima »

iveqy wrote: post #24

So VSCode is great in many ways, and the article might be interesting. But I would never call it fast. It's still really really slow. Just see this comparision: https://www.youtube.com/watch?v=nDRBxtEUOFE

When we started the project, we did write tokenizers by hand. I mention that in the blog post. You can write some very fast tokenizers by hand, even in JavaScript. Of course they won't be as fast as hand written tokenizers in C, but you'd be surprised how well the code of a hand written tokenizer in JavaScript can be optimized by a JS engine, at least I was :). IR Hydra 2 is a great tool to visualise v8's IR representation of JS code [1]. It is a shame it is not built into the Chrome Dev Tools.

In the end, we simply could not write tokenizers for all languages by hand. And our users wanted to take their themes with them when switching to VS Code. That's why we added support for TM grammars and TM themes, and in hindsight I still consider it to be a very smart decision.

[1] http://mrale.ph/irhydra/2/

Re: Optimizations in Syntax Highlighting

#38

Post by jbmorgado »

trishume wrote: post #33
jbmorgado wrote: post #30

Earlier quoted context omitted.

What I don't understand is why do we still use TextMate grammars. Can anyone explain why this is the case? It's not only in VSCode, I remember seeing something about TextMate grammars also in other editors.

Copy-pasted from a comment I made elsewhere: It's harder than it sounds if you want to support many languages. The Sublime syntaxes repo I use has 34,000 lines of grammars whereas my engine is only 3000 lines of code. If you count all the tmLanguage files for nice languages available online it's probably hundreds of thousands of lines, and that's in a pretty dense format. The whole point of using tmLanguage files is…

Thank you, that explains a lot, but now a new doubt came from it:

Why don't we use other text editors grammars that are simpler/quicker to parse in JS? I have no idea on the technicalities, but for instance, Vim or Emacs grammars instead?

Re: Optimizations in Syntax Highlighting

#39

Post by HeyImAlex »

trishume wrote: post #5

Shameless plug: my implementation of Sublime's syntax highlighting engine in Rust has similar optimizations and more. I'm not at my computer to benchmark on the same files but it should be >2x as fast as their "after" numbers just based on lines/second for JS-like files. This evening I'm even trying to port it to a pure Rust regex engine that should eliminate non-Rust code and make it substantially faster. It also im…

That moment when someone else already did your hobby project :congrats through tears:

Re: Optimizations in Syntax Highlighting

#40

Post by pygy_ »

Groxx wrote: post #28
alexdima wrote: post #7

Earlier quoted context omitted.

- all the regular expressions in TM grammars are based on oniguruma, a regular expression library written in C. - the only way to interpret the grammars and get anywhere near original fidelity is to use the exact same regular expression library (with its custom syntax constructs) in VSCode, our runtime is node.js and we can use a node native module that exposes the library to JavaScript - in the Monaco Editor, we are…

Is there a reason the oniguruma syntax can't be translated into other regexes? It'd require a fairly feature-rich engine since oniguruma supports practically everything, but is Chrome missing something fundamental that can't be mimicked? E.g. [::alpha::] could be converted to [a-zA-Z] or the UTF equivalent (though I doubt this particular one is a problem).

They have lookbehind lookup that's only coming now in ESNext , and, more importantly, recursion, if I understand properly[0].

Maybe more things, I stopped reading the docs at that point to comment here. They have other features absent from JS that can be more or less polyfilled, like possessive quantifiers and sticky matching (they do it with an escape sequence, though, so it can only be polyfilled using this trick[1] if the escape character applies to the whole regexp rather than part of it).

[0] https://github.com/kkos/oniguruma/blob/1983356862bc3ff795d77...

[1] https://github.com/slevithan/xregexp/issues/152

Post reply on HN