Re-implement rust-in-macro faster

[phillord]

This function is called repeatedly by syntax-ppss and so needs to be fast. We adopt a simpler mechanism for determining whether we are in a macro.

Fixes #208

[rust-highfive]

r? @mookid

(rust_highfive has picked a reviewer for you, use r? to override)

[mookid]

Thanks for working on this! before diving into the code, do you have a benchmark to compare the old vs the new version?

[phillord]

Yep, best benchmark of all. I tried it with the new version and rust-mode feels fine, while without it feels terrible.

For something slightly more formal I tried this:

(defun bench ()
  (goto-char (point-max))
  (message "%s"
           (benchmark-run 50
             (syntax-ppss-flush-cache 1)
             (syntax-ppss))))

With different benchmark forms, for elapsed, 10 and 50 times

Elapsed
new
0.204490421

old
0.497328317

benchmark-run-compiled 10
(1.3721566170000001 4 0.39234910600000106)
(4.620864861 7 0.6880264240000002)

benchmark-run 10
(1.2887137860000002 3 0.29979056699999873)
(4.579363357999999 7 0.6914120969999971)

benchmark-run 50
(6.617156954 16 1.616331799000001)
(23.228904235999998 36 3.5606590710000035)

So, only about 4 times faster by this metric. Their might be something else going on like the current implementation flushing the cache more often. I did look for this but could not find it happening.

Unwinding the recursion would probably give a bit of performance as well.

[mookid]

Unwinding the recursion would probably give a bit of performance as well.

yep, thats what I was thinking about.

[mookid]

Yep, best benchmark of all. I tried it with the new version and rust-mode feels fine, while without it feels terrible.

For something slightly more formal I tried this:

(defun bench ()
  (goto-char (point-max))
  (message "%s"
           (benchmark-run 50
             (syntax-ppss-flush-cache 1)
             (syntax-ppss))))

And for which source code do the forms run?

[phillord]

So, full code:

(defun rust-in-macro-old ()
  (save-excursion
    (when (> (rust-paren-level) 0)
      (backward-up-list)
      (rust-rewind-irrelevant)
      (or (rust-looking-back-macro)
          (and (rust-looking-back-ident)
               (save-excursion
                 (backward-sexp)
                 (rust-rewind-irrelevant)
                 (rust-looking-back-str "macro_rules!")))
          (rust-in-macro)))))

(defun rust-in-macro-new ()
  (save-excursion
    (let ((end-bound (point)))
      (when (and
             ;; Find first ! backward
             (rust-backward-to-macro-bang)
             ;; Find next paren
             (re-search-forward "[([{]" end-bound t))
        (backward-char)
        ;; Find matching paren
        (forward-list)
        ;; if point is now passed where we started, we are in a macro
        (> (point) end-bound)))))

(defvar bench-use-old t)

(defun rust-in-macro ()
  (if bench-use-old
      (rust-in-macro-old)
    (rust-in-macro-new)))

(defun bench-old ()
  (interactive)
  (let ((bench-use-old t))
    (bench)))

(defun bench-new ()
  (interactive)
  (let ((bench-use-old nil))
    (bench)))

(defun bench ()
  (goto-char (point-max))
  (message "%s"
           (benchmark-run 20
             (syntax-ppss-flush-cache 1)
             (syntax-ppss))))

Run with point in "raw_vec.rs" from liballoc I get these results

elapse
0.378334104
1.654185709

run 1
(0.390778682 0 0.0)
(1.992712346 1 0.3988344170000033)

run-compiled 1
(0.38834057 0 0.0)
(1.651837399 0 0.0)

run 5
(1.960683374 1 0.35779243200000366)
(8.343783432 1 0.3593990110000007)

run-compiled 5
(1.509828065 0 0.0)
(8.29346977 1 0.3554160189999962)

run 20
(6.496330834 1 0.36043094000000053)
(32.831416548 4 1.4240319729999982)

syntax-ppss does all the relevant calling. It's worth noting that the two implementations have different complexities; mine is linear, scaling with the number of "!" till the first macro, while the old implementation is linear with rust-paren-level. So the old one scales badly with deeply indented code, while mine scales badly with people who shout a lot in their comments.

I've used this sort of bench because it's more realistic; rust-in-macro is getting called many times in many places in a buffer.

[tspiteri]

I have a large file which I loads quite slow in rust-mode. It feels even slower with this PR (e.g. instead of counting about 7 seconds for rust-format-buffer to finish, I count about 10 seconds with this PR; not very scientific I know, but still a good indication for me).

(Turning off Match Angle Brackets does make a very significant improvement without the PR, I haven't tested that with this PR.)

[tspiteri]

is linear, scaling with the number of "!" till the first macro… scales badly with people who shout a lot in their comments.

I think this is what causes the regression in my file, (count-matches "//.*!") returns 589 because of all the assertions in the doc examples in the file.

[phillord]

@tspiteri Well, if you are going to put tests into your files, then I have no sympathy for you at all. Can't you just delete them all?

I tried this with my bench code. You obviously have a faster machine than I because it takes me 70 seconds to run syntax-ppss, with current code, and indeed my PR makes that 170 seconds. Both totally unusable.

Hmm. I can think of ways of speeding this up more, but not simple ones. Let me cogitate.

[tspiteri]

@phillord

Well, if you are going to put tests into your files, then I have no sympathy for you at all.

Ouch :)

Can't you just delete them all?

They are doc examples, not tests. And the standard way to show the output of a function in a doc example is through an assertion, e.g. i32::saturating_add. And that's what I do, e.g. the Float::to_i32_saturating doc shows an example of no saturation, a saturation down, and a saturation up. Are you suggesting I should remove my examples?

I tried this with my bench code. You obviously have a faster machine than I because it takes me 70 seconds to run syntax-ppss, with current code, and indeed my PR makes that 170 seconds. Both totally unusable.

That difference seems a bit excessive, did you byte compile before measuring? (I'm not really knowledgeable of the elisp environment, but this is the equivalent of the Rust "Are you using --release?", and I always have to look up how to do it when I need it.)

[phillord]

"Are you suggesting I should remove my examples?"

It was my attempt at humour. I thought that the statement was outrageous enough not be taken seriously. Apologies!

"did you byte compile before measuring?"

No, although I have given it a go now and it still takes ages. Byte-compiling doesn't normally make that much difference, especially when most of the time is spent regexp matching and moving around the buffer which is mostly likely in this case. It takes 0.24 seconds with (setq rust-match-angle-brackets nil). The performance crappiness here, I believe, remains that we are operating in at least quadratic time to identify macro scope, when it should be possible with a linear scan.

Again, I will cogitate.

[tspiteri]

I tried to have a look, but the syntax stuff is all very alien to me. One idea I had is that in one “operation” there will be multiple calls to rust-in-macro, and they will all keep on looking back until either they're out of nested parens (old) or out of bangs (new). But I think they keep looking over the same text. So maybe at the start of the operation initialize a variable bound to 0, and then any time rust-in-macro returns false, set bound to the position. Then, whenever for example there is a call to backward-up-list or rewind-irreleveant (old) or search-backward (new), if the position is before bound we know that we don't need to keep on looking.

I don't know if this works or not, as I don't know how syntax works or what an “operation” is.

[phillord]

I tried to have a look, but the syntax stuff is all very alien to me. One idea I had is that in one “operation” there will be multiple calls to rust-in-macro, and they will all keep on looking back until either they're out of nested parens (old) or out of bangs (new).

Yep, that's exactly the problem. In your file, rust-in-macro is called around 900 times to syntax parse the entire file.

But I think they keep looking over the same text. So maybe at the start of the operation initialize a variable bound to 0, and then any time rust-in-macro returns false, set bound to the position. Then, whenever for example there is a call to backward-up-list or rewind-irreleveant (old) or search-backward (new), if the position is before bound we know that we don't need to keep on looking.

I don't know if this works or not, as I don't know how syntax works or what an “operation” is.

The functions are a bit baroque, but it's syntax-ppss which is forcing the buffer parse to happen. This in turn calls rust-syntax-propertize which finally calls rust-in-macro. It would be worse if syntax-ppss was not cached, but the cache does get dropped regularly. I suspect that rust-in-macro gets called in some other places as well.

I tried something like your idea. I identify the scope of all macros in rust-syntax-propertize, then rust-in-macro just checks whether point is in any of these scopes. Identification of scopes is done, but simply searching for ! followed by \w+[({ and then matching forward to the matching brace. It works, in that it brings the parse down to 4 seconds (from 70) on your very big file. Which is lovely, but for reasons I cannot fathom, it breaks indentation.

So this might be a good way forward if I can work out the breakage.

https://github.com/phillord/rust-mode/tree/fix-broken/faster-in-macro

[phillord]

This is another solution that is now nearly working. It finds the scopes in a linear scan and then uses them to answer rust-in-macro. It uses a safe cache through a let binding. There should be no problems with cache invalidation.

It needs a small extension (it does not cope with macro-rules which seems to have a bespoke syntax); and I will optimize further using the start and end parameters of syntax-propretize which should reduce it to a linear scan of the visible area. Nearly there I think.

[phillord]

So this is the performance for the latest patch. Still 6 times slower than with match-angle-brackets to nil, but a lot faster than the current implementation. Still does not handle macro_rules yet, which will slow it down a bit more, unfortunately.

;; big.rs
;; run-5
;; old, new, match-angle-brackets
;; (395.52657388100005 7 3.090328318999994)
;; (20.047772558 7 2.9489682509999966)
;; (3.7125402989999996 2 0.8323715489999941)

[tspiteri]

I tried this and it works great! (To test it I added

(and (looking-at rust-re-ident)
     (goto-char (match-end 0))
     (skip-chars-forward " \t\n\r")
     (eq ?\{ (char-after)))

after the checks for ?\[, ?\( and ?\{.)

Now rust-in-macro + rust-macro-scope are using less than rust-is-lt-char-operator and about the same as the rust-in-str-or-cmnt directly inside rust-ordinary-lt-gt-p.

- rust-syntax-propertize                            186  41%
 - rust-ordinary-lt-gt-p                            149  33%
  + rust-is-lt-char-operator                         79  17%
  + rust-in-str-or-cmnt                              45  10%
  + rust-in-macro                                    20   4%
  + rust-paren-level                                  5   1%
 + rust-macro-scope                                  29   6%

[mookid]

HI Phil, thanks for that work!

I am reviewing the patch during the weekend.

[tspiteri]

I was testing some, and this reduced test case seems to confuse it:

x! { 1 < 12 }

I looked into it and I believe that when we first assume all [<>] are parens and then suppress afterwards, we are confusing things as then (forward-list) inside rust-macro-scope is confused and thinks the < matches the }. So I tried to remove ?< and ?> from rust-mode-syntax-table and then inside rust-syntax-propertize add the text property instead of removing it.

This fixed things for me, but then the electric pairs test failed, presumably because electric pairs look at the syntax table which now has no < and >, so it is broken. Maybe there's a better way to unconfuse the use of forward-list in rust-macro-scope without breaking the syntax table, but I don't know.

[tspiteri]

I managed to get it to work by using with-syntax-table inside rust-macro-scope.

https://github.com/tspiteri/rust-mode/commits/both-opts

[phillord]

I've updated it with a some more tests cases and stopped it breaking on unbalanced buffers. I will address the comments above next!

[phillord]

@tspiteri With this example,

x! { 1 < 12 }

Can you tell me what it is you find is confused? I can't see what is wrong.

[tspiteri]

@phillord Before the balance fixes (so on commit 05a7ef6), if I created a file with only that content, the brackets would be detected as an unmatched { and a mismatched < }. That has already been fixed by your do-not-require-balance fix.

[phillord]

As far as I can see, we are complete now, except for one question depending on the outcome of https://github.com/rust-lang/rust-mode/pull/373 and a big squash. I am afraid I have made the code review above a bit of a mess, but are there any other needed fixes.

[phillord]

Found a bug yesterday. I'd like to use this in practice for a week (didn't write much rust in the last few days because I have been doing lisp) to see if anything else uncovers. @tspiteri I presume you are using it in real life also?

[tspiteri]

@phillord Yes I'm using it as well. In fact I had thought there was an issue with some highlighting near the point, but it turns out it was lsp-mode that was causing the issue - I have had no issues yet using rust-mode without lsp-mode, but I'll keep on using it and will let you know if anything else comes up.

[phillord]

@phillord Yes I'm using it as well. In fact I had thought there was an issue with some highlighting near the point, but it turns out it was lsp-mode that was causing the issue - I have had no issues yet using rust-mode without lsp-mode, but I'll keep on using it and will let you know if anything else comes up.

That might also have been the bug from yesterday; errors during syntax highlighting are demoted, and only show as messages, but leave the highlighting broken.

[tspiteri]

It could be: I can't reproduce it today while two days ago I could easily. What threw me off is that when I disabled lsp-mode just to make sure, for some reason I wasn't be able to reproduce it.

On another note, I found an issue with nested macros:

macro_rules! outer {
    () => { vec![] };
}
// rust-macro-scope returns ((46 48) (20 31))
// which correspond to ("[]" "{\n    () =>")

[tspiteri]

A false positive for rust-macro-scope occurs with the bitwise complement of a bracketed expression.

fn foo<T>() {
    if !(mem::size_of::<T>() > 8) {
        bar()
    }
}
// rust-macro-scope returns ((23, 45))
// which corresponds to ("(mem::size_of::<T>() >")

[tspiteri]

And in the previous test case above, there was also a mismatch with the "> 8" bit but it did not hurt bracket matching. However below there is a mismatch which does break bracket matching. (This time the exclamation mark is in a proper macro to keep the issues separate.)

fn foo<T>() {
    if mac!(mem::size_of::<T>() < 8) {
        bar()
    }
}
// rust-macro-scope returns ((26, 75))
// which corresponds to ("(mem ... bar()\n    }\n}")

[phillord]

@tspiteri Well, that's hard. It depends on how rigid and accurate we want to be. Consider this:

fn foo<T>() {
    if !(mem::size_of::<T>() > 8) {
        bar()
    }

    dbg !(mem::size_of::<T>() > 8) {
        bar()
    }

    dbg!{hello}
}

I can distinguish between the if and last dbg!{} straight-forwardly using rust-looking-back-macro. But between the first dbg with a space (dbg !), well that's harder. I guess it rust achieves this because if is a keyword.

I'm a bit loath to add that sort of complexity into the checking, so my suggestion would be to fix this but accept that it breaks the second usage dbg !(). WDYT?

[tspiteri]

I agree with your wariness to complexity, and I like your solution. After all dbg !() is quite uncommon and I think considered bad style. Handling it would not be worth any loss of performance and potential bugs from the extra complexity.

[phillord]

I'll do that they. I actually had to check whether dbg !() was valid syntax when I wrote the first version of it.

[phillord]

@tspiteri

macro_rules! outer {
    () => { vec![] };
}
;; returns ((38 40) (20 45)))

I think this is working as I expected. So, something appears to have fixed this in the last few days.

Been a long haul, this fix, but nearly there, I hope!

[tspiteri]

I opened the files I had left for those cases and bracket matching works as expected in them.

I've been using this and basically now I can leave Match Angle Brackets On for large files like big.rs with the same feel as with it off, so for me it's already there. And I wouldn't worry about the corner cases: the worse it would probably do is maybe break some bracket matching around some weird macros, but even without this patch, I used to get mismatched brackets all the time when I used Angle Brackets On; in fact I get the feeling that even bracket matching has improved, not just performance.

[phillord]

I have written some code now with this and @tspiteri hasn't found anything else, so I think we are good to go here. If we find any other problems, I can fix them on master.

Once I have squashed -- sorry, forgot!

And complete

[mookid]

I can fix them on master.

Indeed.

If you prefer to preserve some history feel free to push again.

Thanks @phillord and @tspiteri for the work on this!

[tspiteri]

Thanks @phillord!