Stream: t-compiler/rust-analyzer

Topic: Syntax highlighting is quadratic


Lukas Wirth (May 31 2021 at 21:22, on Zulip):

So after commenting a few things out here and there it seems that the culprit is the doc highlight injection

Lukas Wirth (May 31 2021 at 21:22, on Zulip):

numstructs milliseconds

1000 827
2000 1890
3000 3165
4000 4755
5000 6555
6000 8574
7000 10677
8000 13144

This is what I get when I just comment the injection out

Lukas Wirth (May 31 2021 at 21:23, on Zulip):

Which is already a lot faster than with it uncommented

Lukas Wirth (May 31 2021 at 21:33, on Zulip):

With just calling doc_attributes in the injection code and returning afterwards I get

1000 1556
2000 3737
3000 6653
4000 10340
5000 14573
6000 19411

Adding the attributes.docs_with_rangemap call to that gives:

1000 2343
2000 6425
3000 12279
4000 19838
5000 29203
6000 40330

Note that the only comments in the test fixture are single line doc comments on the generated fields
:grimacing:

Lukas Wirth (May 31 2021 at 22:00, on Zulip):

Adding the attributes.source_map call in gives:

1000 2323
2000 5880
3000 11172
4000 18011
5000 26117
6000 35742
Lukas Wirth (May 31 2021 at 22:06, on Zulip):

I fail to see where all ofthis is getting quadratic in regards to the fields though :confused:
Maybe this isn't the quadratic cause but just something that gets caught up in it?

Laurențiu (Jun 01 2021 at 09:37, on Zulip):

Lukas Wirth said:

numstructs milliseconds

1000 827
2000 1890
3000 3165
4000 4755
5000 6555
6000 8574
7000 10677
8000 13144

This is what I get when I just comment the injection out

But that's already quadratic, so maybe it's not the highlight injection.

pachi (Jun 01 2021 at 09:40, on Zulip):

That's linear, 2ms for each new struct (1000 new structs -> 2000 more ms).

Lukas Wirth (Jun 01 2021 at 09:43, on Zulip):

Laurențiu said:

Lukas Wirth said:

numstructs milliseconds

1000 827
2000 1890
3000 3165
4000 4755
5000 6555
6000 8574
7000 10677
8000 13144

This is what I get when I just comment the injection out

But that's already quadratic, so maybe it's not the highlight injection.

Ye that was what I meant with my last message. It just wasnt too obvious to me at first, but I feel like the "quadratic-ness" got worse with the injection stuff?

Dawer (Jun 01 2021 at 09:44, on Zulip):

Can field resolution cause this? https://github.com/rust-analyzer/rust-analyzer/pull/9031#issuecomment-851409380

Lukas Wirth (Jun 01 2021 at 09:45, on Zulip):

Noh the generated fixture is only struct definitions so those arent revelant(I also checked just in case and commented the parts out)

Lukas Wirth (Jun 01 2021 at 09:45, on Zulip):

Those are still quadratic though with their lookup, its just not the main problem here

bjorn3 (Jun 01 2021 at 09:47, on Zulip):

image.png

This is the plot. It is slightly slower than linear. Maybe O(n log n)?

Mario Carneiro (Jun 02 2021 at 00:04, on Zulip):

Actually if you plot x, y/x it's pretty linear, it just that the quadratic factor is fairly small compared to the linear component. Best fit is about 0.73 n + 0.00011 n^2

Lukas Wirth (Jun 07 2021 at 15:06, on Zulip):

Oh I forgot about this :sweat_smile: I'm still not entirely sure whats going on here but I think the sema.to_def call is quadratic for fields?

Lukas Wirth (Jun 07 2021 at 15:07, on Zulip):

Iirc when looking for definitions we search for the container, which is the struct for fields and then search linearly in the container for the index or something which would be certainly quadratic. This is just a guess though I haven't looked much into how we map ast things to definitions yet

Jonas Schievink [he/him] (Jun 07 2021 at 15:34, on Zulip):

record_field_to_def seems to go through DynMap like other items

Jonas Schievink [he/him] (Jun 07 2021 at 15:39, on Zulip):

hmm, and the HasChildSource code in adt.rs looks linear in the size of the struct from what I can tell

Jonas Schievink [he/him] (Jun 07 2021 at 15:40, on Zulip):

and since this is cached we should only compute it once per struct, and then do O(1) lookups in the map

Lukas Wirth (Jun 07 2021 at 16:49, on Zulip):

Hmm ye that doesn't seem to be it then...

Jonas Schievink [he/him] (Jun 07 2021 at 23:28, on Zulip):

I'm pretty sure that highlighting within macros is quadratic though: TokenMap lookups are linear in the size of the input (I think), and highlighting does it once per input token

Lukas Wirth (Jun 15 2021 at 20:23, on Zulip):

Im looking into this again right now and the fields_attrs_query should only run once per struct right? Afterwards it should be cached if im not mistaken right? Because if I'm checking this correctly right now it looks like this is being a lot of times? For the 1000 field struct case it's being executed 1001 times(cross crate cov_mark comes in really handy here)

Lukas Wirth (Jun 15 2021 at 20:24, on Zulip):

Which is definitely quadratic as it recollects all child fields again in each call for each field

Lukas Wirth (Jun 15 2021 at 20:28, on Zulip):

Exactly the same appears to be happening for fields_attrs_source_map so that explains the big time increases I got when commenting those out

Lukas Wirth (Jun 15 2021 at 20:28, on Zulip):

So I suppose salsa is kicking the results of those out of the cache immediately for some reason?

Lukas Wirth (Jun 15 2021 at 20:29, on Zulip):

Or not realizing that it can reuse the computation?(I dont really know how salsa works yet)

Lukas Wirth (Jun 15 2021 at 20:52, on Zulip):

oh wait the fixture generates one struct with n fields and n structs on the side nvm...

Lukas Wirth (Jun 15 2021 at 20:53, on Zulip):

I don't think I'll figure this out anytime soon, feels like a waste of time at this point as I'm not making progress

matklad (Jun 21 2021 at 15:59, on Zulip):

Comming back to this! I've run the following bench in realease on the current master:

#[test]
fn benchmark_syntax_highlighting_long_struct() {
    for i in 0..=20 {
        let n = i * 500;
        let fixture = bench_fixture::big_struct_n(n);
        let (analysis, file_id) = fixture::file(&fixture);
        let t = Instant::now();
        let _ = analysis.highlight(file_id);
        eprintln!("{:3} {:?}", i, t.elapsed());
    }
}

Here are the results:

  0 240.151µs
  1 37.874711ms
  2 110.355746ms
  3 217.256364ms
  4 361.15263ms
  5 539.999892ms
  6 756.224383ms
  7 1.005763744s
  8 1.294456419s
  9 1.616761095s
 10 1.979827698s
 11 2.367461069s
 12 2.820995648s
 13 3.273588743s
 14 3.767652556s
 15 4.308655111s
 16 4.941540713s
 17 5.605129736s
 18 6.257592457s
 19 6.927527017s
 20 7.656330973s

This is clearly quadratic -- doubling the number on the left quadruples the number on the right. 10 takes about 2s, 20 takes about 8s.

matklad (Jun 21 2021 at 16:03, on Zulip):

Next fascinating observation: adding return None to the actual highlighting (highlight::element function) doesn't change the timings at all. That it, whatever is slow in our syntax highlighting, it is clearly not the syntax highlighting!

matklad (Jun 21 2021 at 16:07, on Zulip):

Yeah, commenting out all this doesn't change the picture: https://github.com/rust-analyzer/rust-analyzer/blob/1b05dbba39d5a4d46f321dc962df99038cddbf21/crates/ide/src/syntax_highlighting.rs#L286-L365

matklad (Jun 21 2021 at 16:14, on Zulip):

Walking in from the other side, commenting the inside of the for event in root.value.preorder_with_tokens() { reveals that we have two indpendent sources of quadraticness here!

One is this block:

        let element = match event {
            WalkEvent::Enter(it) => it,
            WalkEvent::Leave(it) => {
                if let Some(node) = it.as_node() {
                    inject::doc_comment(hl, sema, root.with_value(node));
                }
                continue;
            }
        };

The second one is this one:

        match event.clone().map(|it| it.into_node().and_then(ast::Item::cast)) {
            WalkEvent::Enter(Some(item)) => {
                if sema.is_attr_macro_call(&item) {
                    current_attr_macro_call = Some(item);
                }
            }
            WalkEvent::Leave(Some(item)) => {
                if current_attr_macro_call == Some(item) {
                    current_attr_macro_call = None;
                }
            }
            _ => (),
        }

independently, each of those is O(N^2)

Jonas Schievink [he/him] (Jun 21 2021 at 16:19, on Zulip):

hmm, what's the expected complexity of Semantics::analyzer?

matklad (Jun 21 2021 at 16:21, on Zulip):

::analyze ? I think cached O(1)

Jonas Schievink [he/him] (Jun 21 2021 at 16:24, on Zulip):

hmm, why is the attribute macro handling O(n²) then?

matklad (Jun 21 2021 at 16:29, on Zulip):

Hm, somthing doesnt' make sense to me.. Heer's the code I've minimized this to:

    let _it = stdx::timeit("total");
    for event in root.value.preorder_with_tokens() {
        let _it = stdx::timeit("loop");
        let element = match event {
            WalkEvent::Enter(it) => it,
            WalkEvent::Leave(it) => {
                if let Some(node) = it.as_node() {
                    inject::doc_comment(hl, sema, root.with_value(node));
                }
                continue;
            }
        };
    }

And here's the output I get (filtering out times < 2 ms):

loop: 655.68ms
total: 2.00s
 17 2.11564048s
loop: 713.26ms
total: 2.25s
 18 2.373231198s
loop: 788.57ms
total: 2.46s
 19 2.591156794s
loop: 859.33ms
total: 2.74s
 20 2.885021587s

There's only one slow loop here?

matklad (Jun 21 2021 at 16:31, on Zulip):

Ah, no, it's just that rust is plenty fast -- individual loops to get into 0.3 ms range

matklad (Jun 21 2021 at 16:36, on Zulip):

Apparetntly, both to_def and .attrs are quadratic

matklad (Jun 21 2021 at 16:37, on Zulip):

Feels like a fractal, where each quadratic part consists of two independent quadratic parts

matklad (Jun 21 2021 at 16:39, on Zulip):

So, to_def for RecordField is def linear...

Lukas Wirth (Jun 21 2021 at 16:41, on Zulip):

Thats roughly how far I got, but after that I got nowhere

matklad (Jun 21 2021 at 16:43, on Zulip):

Yeah, I am now in the delightful source_to_def module. A good thing about it is that, once written, this module basically never changed. The bad thing about it is that it's so tricky that it'd be better not have been written at all

matklad (Jun 21 2021 at 16:45, on Zulip):

A fun thing, though, is that both Kotlin and Roslyn contain the code which does exactly the same -- it's a somwhat surprising essense of an ide it seems

Lukas Wirth (Jun 21 2021 at 16:51, on Zulip):

I have yet to understand that module to be honest

Lukas Wirth (Jun 21 2021 at 16:51, on Zulip):

Never really dug into it

matklad (Jun 21 2021 at 16:54, on Zulip):

I am baffled that it has empty docs tbh, that's the interesting bit!(

matklad (Jun 21 2021 at 16:58, on Zulip):

Curious! So, getting struct's source is linear...

matklad (Jun 21 2021 at 16:59, on Zulip):

We have to many traits and to few "goto definition goes to impl" :(

Jeremy Kolb (Jun 21 2021 at 17:01, on Zulip):

Does that include the fields in the struct? Your test above hints at it being related to the items

matklad (Jun 21 2021 at 17:05, on Zulip):

Quadratic SyntaxNodePtr, I welcome you, my old friend!

    pub fn to_node(&self, root: &SyntaxNode) -> SyntaxNode {
        assert!(root.parent().is_none());
        successors(Some(root.clone()), |node| {
            node.children().find(|it| it.text_range().contains_range(self.range))
        })
        .find(|it| it.text_range() == self.range && it.kind() == self.kind)
        .unwrap_or_else(|| panic!("can't resolve local ptr to SyntaxNode: {:?}", self))
    }

I've thought that this was fixed with transition to new rowan, but looks like it wasn't?

matklad (Jun 21 2021 at 17:07, on Zulip):

oh wow

matklad (Jun 21 2021 at 17:07, on Zulip):

that's going to be the most perf-improving one line change i've ever did

Lukas Wirth (Jun 21 2021 at 17:07, on Zulip):

:tada:

matklad (Jun 21 2021 at 17:11, on Zulip):

Good news: the change improves perf for n = 20 from 7.6s to 420ms. Bad news: some test hangs

matklad (Jun 21 2021 at 17:13, on Zulip):

Correction: only good news is the real one! The tests that hangs is my manual very long quadratic test :D I sense an opportunity for an epic commit message

matklad (Jun 21 2021 at 18:05, on Zulip):

https://github.com/rust-analyzer/rust-analyzer/pull/9362/commits/099b63e7c01ed9969041bef8b3b9c573c7e24bf8

Jeremy Kolb (Jun 21 2021 at 18:17, on Zulip):

it probably makes sense to doc comment child_or_token_at_range and mention that it performs a binary search

Jonas Schievink [he/him] (Jun 21 2021 at 18:19, on Zulip):

yeah, nobody but Aleksey could have noticed this without docs

matklad (Jun 22 2021 at 08:46, on Zulip):

Good call, added docs to rowan and ra.

To be fair, figuring out that this is linear is possible -- the original version used a hand-written naive linear search.

Figuring out that a faster version already exists in rowan and just needs to be enabled would be tricky, yeah

matklad (Jun 22 2021 at 12:32, on Zulip):

https://github.com/rust-analyzer/rust-analyzer/pull/9369/files documents the magic source_to_def is

Last update: Jul 27 2021 at 21:00UTC