Comment by jakear | Hacker News Reader

Comment by jakear | Hacker News Reader

Heh... reminds me of my first proper MS internship, when I too was responsible for speeding up some code, this time in the VS Code Go extension. This code was responsible for tokenization, so it affected pretty much every operation and ran on every edit. Important shit.

Day 1: do some basic hoisting. O(n^3) => O(n^2). Tokenization times for a 10k line file go from ~15s to 500ms. Sweet.

Days 2-30 [1]: ideate, develop, bug fix, iterate on, etc, a novel (to me) data-structure to speed up the program even more. O(n^2) => O(n x log(n)) (expected). Great! Runtime on 10k line file went from 500ms to maybe 300ms. Oooops.

But hey, all the people working in 500k line files must really love the couple seconds my month of toiling (more importantly, my month of not doing other, more impactful things) saved them.

Learned a lot from that experience, and writing this out now I can see how that impacted engineering decisions I make to this day. I suppose thats the real point of an internship, so time well spent, in a way.

[1] It probably wasn't actually a month, but certainly a significant chunk of the internship.

> But hey, all the people working in 500k line files must really love the couple seconds my month of toiling (more importantly, my month of not doing other, more impactful things) saved them.

This stuff matters. These couple seconds per operation may very well be a difference between being able to open a 100k+ LOC file in the same editor you're doing your other work in, vs. giving up in frustration and looking for something else that can handle large files. Large files happen surprisingly often (in particular: log files, data dumps, machine-generated code). A "month of toiling" like this may immediately enable new use cases.

This is true, but my approach was still not a great one. It turns out the data structure was only accessed in a very specific way, which I could have exploited to dramatically simplify the implementation. If I had researched the problem more before diving into my original idea, I could have achieved the same end goal with much less work.

Lessons upon lessons :)

I have adhd. Every "couple seconds" of waiting is a chance for me to lose focus and "wait what was I doing?" 15 minutes later. This stuff definitely matters.

One of the most important things you can do in perf analysis is to know when to stop looking for incremental improvement.

If this subject in particular interests you, we did a lot of work in the C# lexer/parser so that once the file is lexed, it only re-lexes the tokens which changed on every edit. It also does fun stuff like the syntax colourizer only runs on code that's actually on the screen. Getting every operation that depends on the lex/parse of code in the editor down to running in much less than 30ms so that it would not slow down keystrokes was a huge amount of work.

Does the C# parser implement incremental parsing by just using a recursive descent parser with caching, or does it do parsing with nonterminals as lookahead?

It does a full lex and parse. Then if there is an edit, it determines based on the edit which tokens need to be re-lexed; maybe we went from "[10,20]" to "[10.20]" and so now the [ and ] tokens are fine but everything in the middle is changed.

So we go from a data structure representing "original text plus edit" to a data structure representing "original lex plus changes". Now we have the information we need to do the same to the parse tree, which has also been stored. Given the set of tokens in the program which changed, and knowledge of where the textual boundaries are of every parse node, we can restrict the re-parse to the affected syntax tree spine. In the example given, we know that we've still got, say, an array index list but the contents of the list need to be re-parsed, so we re-start the parser on the left bracket.

The algorithm that does this is called "the blender", and reading that code makes my brain feel like it is in a blender. The code was written by Neal Gafter and based on his PhD thesis in incremental parser theory.

The source code is available on github; do a search for "roslyn" and you'll find it.

Wow that still sounds really long for simply tokenizing a file? I worked on parsers a while ago and for reference I benchmarked e.g. the Python parser at 300.000 loc / second (for tokenization and building an AST) on my machine (a i7 laptop). Also tokenization complexity should not increase quadratically with the length of the file?

You probably know what you’re doing, just curious why these numbers seem to be off so much to what I would expect. What approach did you use for tokenization if I may ask?

I don't recall the exact numbers to be honest. I know the original was in many seconds, and in the end it was sub 1.

As mentioned in another comment:

The go extension is a thin wrapper around standard go tooling, we weren’t tokenizing ourselves just converting between their tokens and ones we could process; a large part of that was converting from byte offsets to UTC-8 character offsets.

The quadratic behavior was a bug caused by reconverting segments over and over again instead of converting deltas between previously converted subsegments.

I just want to thank you personally for speeding up the VS Code Go extension because I use it every day! Thank you!

I'm curious: why can't you do tokenization in linear time? And why not use incremental tokenization for an editor?

I think you’re right, the end result was actually linear.

And the go extension is a thin wrapper around standard go tooling, we weren’t tokenizing ourselves just converting between their tokens and ones we could process; a large part of that was converting from byte offsets to UTC-8 character offsets.

Reply on news.ycombinator.com