Improve focus-lines speed using multi-line overlays

[jdtsmith]

This improves the speed of consult-focus-lines by:

• Storing line number + line begin & end as text properties on the line candidates to be matched.
• Extracting this information from the text properties in resulting matches.
• Using the matched line data to merge contiguous blocks of lines, substantially reducing the number of overlays needed. Overlays are not pre-allocated, but instead deleted and re-created on each new input.

To ensure every line has the 'line text property added, blank lines are collected as \n. I tested this on a file with >250,000 lines (/usr/share/dict/words). The current version does not make it to the prompt after several minutes of waiting. This is likely due to the pre-allocation of one overlay per line. This version works reasonably well on such a long file. With fewer overlays, it also modestly improves navigation speed in the buffer, likely due to reducing the need to skip over the many invisible overlays.

In addition, it:

• Correctly exits the current search on interruption
• Provides a message update during the search with the number of included/excluded lines.
• Moves point past the enclosing invisible overlay when finished [1]. Fixes #493.

[1] Note that emacs normally moves point out of invisible regions after commands, but not at/near the beginning of buffer (where it moves to (point-min), which may be hidden).

[minad]

Thank you for looking into this! I will add a few comments.

EDIT: After having looked closer, I agree with the changes overall. Can you please split the single commit in separate commits which address each of the aforementioned points separately? One commit for each of those:

1. Correct exit
2. Add message
3. Move point out of invisible overlays
4. Improved overlay implementation

This makes it easier to review and easier to fix in the future, in case something went wrong.

[jdtsmith]

OK can refactor. ~Let me know your thoughts on sort necessity and cl-labels.~ Also, one other thing I wasn't clear on that should be fixed now: the current behavior adds to the overlays on sequential focus calls, so that you can stack filters on top of each other. This might be useful, but as it is, it's broken because only one list of overlays is saved (the latest), so on "clearing" (blank input) only the most recent are unhidden.

I think the best approach is to have one level deep of filter, and so (consult-focus-lines 'show) on each new call to focus-lines. Thoughts?

[minad]

All, one other thing I wasn't clear on that should be fixed now: the current behavior adds to the overlays on sequential focus calls, so that you can stack filters on top of each other. This might be useful, but as it is, it's broken because only one list of overlays is saved (the latest), so on "clearing" (blank input) only the most recent are unhidden.

Oh, I had assumed that this works correctly. Please preserve the existing behavior. But I was also about to ask if we should improve the situation somehow. Instead of layering the overlays, combine them for better efficiency for example. I wouldn't go with the idea of stacking, which is too complex. But any of this can be addressed separately.

[jdtsmith]

All, one other thing I wasn't clear on that should be fixed now: the current behavior adds to the overlays on sequential focus calls, so that you can stack filters on top of each other. This might be useful, but as it is, it's broken because only one list of overlays is saved (the latest), so on "clearing" (blank input) only the most recent are unhidden.

Oh, I had assumed that this works correctly. Please preserve the existing behavior.

Since overlays are recreated on each call to the closure, the issues is we'll have duplicates and overlaps if we allow the old overlays to persist. BTW, I was always confused by this: taking the package-list-packages example, I don't expect to have to "clear" the search to start a new one. I just want to M-s f consult, check out some cool packages, then M-s f eldoc, check some more, etc. In fact I do that every time and spend a moment perplexed by the blank buffer. I'd strongly suggest we just adopt a "single filter at a time" approach, unless you've seen usage of stacked filters in the wild.

If that's still the approach we want, we must think about merging the new and saved overlay lists. But to do that well, it will require merging/coalescing overlays that form contiguous series. Painful, and hard to get right for all corner cases. I'd like to avoid this if at all possible.

I wouldn't go with the idea of stacking, which is too complex.

That's how I'm describing the current behavior of "add more filters blocks to the filters". So IMO current "stacking" is the default. If we really go this route, I think some feedback to the user that this is happening would be appropriate (filter in place & lines shown, for example). And then rather than merging overlays, the easiest way might in fact be to compose a filter as filter1 AND filter2, delete all overlays and regenerate. So save the former input as well. Getting pretty complicated for such a simple tool!

[minad]

Currently the behavior is quite simple and reminiscent of the consult-keep-lines behavior. Therefore it is designed like this. I prefer to keep this behavior. If you want to clear first it is easy to add such a small helper command to your config or use a keyboard macro C-u M-s u M-s u.

[jdtsmith]

Currently the behavior is quite simple and reminiscent of the consult-keep-lines behavior. Therefore it is designed like this. I prefer to keep this behavior. If you want to clear first it is easy to add such a small helper command to your config.

In that case I'd say we need:

1. A way to indicate to the user what filter(s) are already in place.
2. To compose filters rather than try to merge overlays. Something like a saved list of consult--focus-line-filter-inputs, that get prepended to the current filter (and cleared on reset), ala

   (filter_n ( ... ( filter2 (filter 2 inputs lines))))...

   Such a list would obviously help with 1 as well.

[minad]

In that case I'd say we need:

No, we don't need that here. Please let's keep this PR focused. I am open to discussing the overlay composition in a separate issue however. Currently the composition is simply achieved by reusing the existing overlays and putting all the load on the Emacs display engine. This PR should do the same.

I assume that we both agree that this is not particularly friendly, so it deserves to be improved in the next step. :)

[jdtsmith]

In that case I'd say we need:

No, we don't need that here. Please let's keep this PR focused. I am open to discussing the overlay composition in a separate issue however. Currently the composition is simply achieved by reusing the existing overlays and putting all the load on the Emacs display engine. This PR should do the same.

There was never overlap before because you had only one overlay per line. Overlays can now be thousands of lines long or more. I suppose I can just let overlays overlap willy nilly and let emacs sort it out (as there's no such thing as "double invisible"). Feels wrong...

I assume that we both agree that this is not particularly friendly, so it deserves to be improved in the next step. :)

Yes. Here's a potential UI I sketched up for later:

[minad]

There was never overlap before because you had only one overlay per line. Overlays can now be thousands of lines long or more. I suppose I can just let overlays overlap willy nilly and let emacs sort it out (as there's no such thing as "double invisible"). Feels wrong...

Well, with the current implementation you can also get two overlays at the same place both saying "invisible". If this is wrong or not is debatable. Emacs allows me to do this. I doubt that having overlaps is an issue here, as far as I understood the performance issue for Emacs is the sheer number of overlays. And since we are getting that number down we will be better than before, with overlap or without.

[jdtsmith]

The ugly overlap deed is done. Seems to work; can you give a quick test?

[minad]

I found one issue. Narrowing didn't work. I also simplified it a little bit on the go, see https://github.com/minad/consult/commit/92fd226ba8c87543d6e08632c980722cf79f67f7. I would appreciate if you give it a thorough test.

[jdtsmith]

How was narrowing fixed?

Also, this is indeed simple, but does not produce correct results for not matches at the end. E.g. consider:

aaa
bbb
aaa
bbb
ccc
ccc
ccc

with input ! c. The reason is the clever new "out of matches" end finisher never gets a chance to run when block-end = point-max.

[minad]

Thanks, for checking! Fixed. See the latest commits.

[jdtsmith]

Well, now:

aaa

bbb

ccc

Search: ^$. This is because blank lines have to be substituted for \n, or they can contain no text property. It's tricky to get this right (took me a while!). So maybe:

@@ -3042,3 +3042,3 @@ INITIAL is the initial input."
                           beg (cdr prop)
-                          end (+ 1 beg (length match))))
+                          end (+ 1 beg (if (eq (aref match 0) ?\n) 0 (length match)))))
                   (unless (eq ind (1+ old-ind))

[minad]

This issue was introduced by the unrelated optimization https://github.com/minad/consult/commit/21501968fe3256ad23ed09b98d5e6bc435a9f69f. The "\n" hack you used does not seem like such a good idea, since it breaks other edge cases like searching for \`\'. I'd like to replace this with something else.

~In principle we could use cons pairs instead of text properties, since the filter function (based on completion styles) can handle this. However unfortunately the consult-selectrum filter function cannot as far as I know :(~ (EDIT: No that wouldn't work since the filter returns only the plain strings in any case.)

[minad]

Hmm, or maybe your proposed fix to check for "\n" handles all the scenarios? I will merge this for now. (EDIT: see https://github.com/minad/consult/commit/181b941a2eaa7d17e474e7ef8aa7aaacb64acbfd)

[jdtsmith]

Yep, you are re-treading the slippery path I traversed ;). Only text properties survive. You can also check that length is 1, but given the construction of lines, they will never have a newline character other than if blank.

[minad]

That's not exactly true. The minor optimization 21501968fe3256ad23ed09b98d5e6bc435a9f69f goes a little bit beyond, I've fallen off the cliff which you managed to avoid. Anyways dissecting the code again is what I call a thorough review. ;)

Generally I try to avoid a finalization step if I can pull it inside the loop. And inverted behavior can also be unified usually (the not case we have here).

[jdtsmith]

I just meant the pitfalls I encountered. And great work finding a way to avoid finalization — I agree that's not ideal. With the latest, it's a pretty lean and mean (and simple!) algorithm: good teamwork.

One thing I've noticed playing with long files is that while-no-input doesn't seem to do much for you. The reason is that it is wrapping the relatively inexpensive (i.e. not so heavy) part of the algorithm: the completion-all-completions match. The fix was easy and in fact simplifies things even further; see #497.

[minad]

it's a pretty lean and mean (and simple!) algorithm: good teamwork.

Yes, thank you for that! By overhauling the code again I played the ball back to you for another review. :)

One thing I've noticed playing with long files is that while-no-input doesn't seem to do much for you. The reason is that it is wrapping the relatively inexpensive (i.e. not so heavy) part of the algorithm: the completion-all-completions match. The fix was easy and in fact simplifies things even further; see #497.

Yes, I am aware of this. Filtering is usually the heaviest part, e.g., in Vertico. But here the overlay creation may be more costly. I have some doubts about this though, see #497.

[oantolin]

Woah, did you guys know about the built-in rtree library? It provides an efficient tree-based data structure for storing sets of disjoints intervals of numbers and common operations for these sets. Maybe it could be used to implement the "update overlays" approach in a way that isn't horribly inconvenient.

[minad]

I don't know about this library. But I doubt that we need anything sophisticated here. The current implementation is straightforward. We don't implement overlay updates/merging.

[oantolin]

We don't implement overlay updates/merging.

I know it's not currently done, I was just saying that perhaps with that library's help it wouldn't be hard to do so. But now that I look more at the API, probably not.

[minad]

I know it's not currently done, I was just saying that perhaps with that library's help it wouldn't be hard to do so.

Sure, I understood you that way. I'd argue that the current implementation is good enough. It is much more usable than before. Also consult-keep-lines temporarily unlocks read-only buffers now. I am much more happy with these two commands now. :)

But @jdtsmith has some ideas on how to improve the UI (#496).

[jdtsmith]

The latest greatly reduces the number of overlays used, and cuts out the "shortest match" bottleneck by making all the expensive operations (overlays included) interruptible. So no longer do you type a single letter and wait a while for it to update.

If we wanted to make focus-lines a fancier tool that allows stacking/unstacking multiple filters, maybe a library like rtree could be useful. Right now, multiple rounds of filtering just create independent overlays and let the display engine sort it out. With orderless, I claim even that is unnecessary (as you can stack include & exclude filters all in one filtering level). Part of the UI issue is that allowing multiple independent sequential rounds of filtering will complicate keeping track of how many lines are still showing, whereas with "one level of filtering only", it's trivial.

BTW, in another thread someone mentioned the power of embark-export + focus-lines + marginalia for selecting on "all metadata", which hadn't occurred to me. The one issue I found is that embark-export is quite slow on large lists of the sort I'd like to filter this way (e.g. C-h v C, E), maybe because it's building a customize widget for each variable.

[oantolin]

I think that the annotators are the slowest part of embark export. You normally don't notice how slow they are because Vertico, Selectrum or Icomplete-vertical annotate only 10 candidates or so at a time. But embark collect or the built-in *Completions* buffer annotate all candidates and then you can really tell it takes a while.

[minad]

@jdtsmith

If we wanted to make focus-lines a fancier tool that allows stacking/unstacking multiple filters, maybe a library like rtree could be useful. Right now, multiple rounds of filtering just create independent overlays and let the display engine sort it out. With orderless, I claim even that is unnecessary (as you can stack include & exclude filters all in one filtering level). Part of the UI issue is that allowing multiple independent sequential rounds of filtering will complicate keeping track of how many lines are still showing, whereas with "one level of filtering only", it's trivial.

To be honest, I am not sure I want this. consult-keep-lines and consult-focus-lines are simple tools, which aim to be better keep-lines commands. We should not make them arbitrarily complex. The commands should solve the most common need that users have! For now I think having a "count/total" indicator is a good idea, as proposed in #496.

BTW, in another thread someone mentioned the power of embark-export + focus-lines + marginalia for selecting on "all metadata", which hadn't occurred to me. The one issue I found is that embark-export is quite slow on large lists of the sort I'd like to filter this way (e.g. C-h v C, E), maybe because it's building a customize widget for each variable.

Actually consult-focus-lines and consult-keep-lines were specifically developed for the embark-collect-snapshot workflow described by @oantolin. At that time I didn't want to implement a consult-descbinds command. If I recall correctly, we argued that it is better to have a general export an post filtering functionality. Basically consult-focus-lines closes the loop back to completion again, since after the snapshot the filtering functionality is lost. The irony is that in the end we still got embark-bindings. :)

@oantolin

I think that the annotators are the slowest part of embark export. You normally don't notice how slow they are because Vertico, Selectrum or Icomplete-vertical annotate only 10 candidates or so at a time. But embark collect or the built-in Completions buffer annotate all candidates and then you can really tell it takes a while.

Yes, but for the rare occasions one uses this it is good enough. Recently I didn't make much use of the filter by annotation functionality. The snapshot of all candidates (despite being slow) is great for testing Marginalia annotators, M-x, or C-h v and then snapshot everything :laughing:

[jdtsmith]

consult-keep-lines and consult-focus-lines are simple tools, which aim to be better keep-lines commands

I agree on keeping it simple. In fact I advocate making focus-lines even more simple: only one filter allowed at a time (new filter overrides any previous). For people who want/need to add multiple filters, recommending an orderless search like Focus lines: keep ![0-9]\{2,\} or similar is a good workaround. It is now perfectly fast enough to build this up interactively. And it will make count/total trivial to do.

M-x, or C-h v and then snapshot everything 😆

Oops I forgot the distinction between export and collect snapshot. For me, even exporting after a variable search like consult is a 5-10s affair. I think it must be because of the fancy customize interface. Must remember collect...

BTW, somebody should make a gist with "awesome consult + embark + marginalia + orderless tricks" and one-liners. Probably could post on reddit and collect a bunch of these from people's workflows.

[oantolin]

Oh, sorry, I read your earlier comment too quickly and didn't notice you said export! Yeah, it's probably slow for different reasons than collect. 😛

[oantolin]

I agree on keeping it simple. In fact I advocate making focus-lines even more simple: only one filter allowed at a time (new filter overrides any previous).

I'd like that for consult-focus-line, but I also like it being semantically similar to keep-lines. One of those two wishes will go unfulfilled.

[minad]

@jdtsmith

For people who want/need to add multiple filters, recommending an orderless search like...

Note that you cannot assume Orderless.

BTW, somebody should make a gist with "awesome consult + embark + marginalia + orderless tricks" and one-liners. Probably could post on reddit and collect a bunch of these from people's workflows.

These tricks should be put in the respective wikis. This is why the wikis exist.

@oantolin

I'd like that for consult-focus-line, but I also like it being semantically similar to keep-lines. One of those two wishes will go unfulfilled.

Since we've already got the version which is semantically similar to keep-lines it will stay that way. This makes it harder or less efficient to implement the count/total indicator, but I also argue that we don't really need that.