Add `orderless-limit` customizable variable

[minad]

Add `orderless-limit` customizable variable

[minad]

I agree with your points. I also don't have strong enough evidence that it makes things much faster in practice. I observe a speed up for M-x and C-h v, but there the correctness issue also hurts a bit. Correctness doesn't matter so much for in-buffer completion. Think about Lsp-mode oder Vscode. Users seem to prefer fast over correct. :-P

[minad]

Some more thoughts:

• The question is if Orderless is the right place for such a feature, which is also a bit experimental. Instead one could also define some completion style wrapper (or middleware) which passes a modified predicate to the wrapped completion style to achieve a similar effect. The problem would then be that throwing the list outside of the predicate wouldn't work properly. For example the completion style highlighting, which is done after all-completions, would be jumped over.

• The idea to jump out of the predicate to short circuit the loop might be problematic for some completion tables, in particular the ones which do some post processing. The issue is the same as mentioned before for the completion style. I think for orderless-try-completion this is not a problem since there we only care about the presence of candidates and not about their exact form. It could be a problem for orderless-all-completions with orderless-limit though.

• A more conservative implementation would avoid the short circuiting and would just return nil from the predicate if the limit is exceeded. This approach would be more likely to work for all tables and could also be implemented as a wrapper completion style. The downside is only that the performance gain may not be as large.

• Maybe it would make sense to even add a variable completions-limit to minibuf.c in Emacs itself. Then one would avoid all the problems above and the solution would automatically work for all completion styles. It should be possible to implement this safely using an advice for all-completions and the short circuiting predicate trick.

[minad]

Prototype for all-completions:

(defvar completions-limit 20)

(defun completions-limit (orig str coll &optional pred hide-spaces)
  (if (functionp coll)
      (funcall coll str pred t)
    (let ((result) (limit 0))
      (catch 'completions-limit
        (funcall orig str coll
                 (lambda (&rest args)
                   (when (> limit completions-limit)
                     (throw 'completions-limit t))
                   (when (or (not pred) (apply pred args))
                     (setq args (car args) ;; first argument is key
                           args (if (consp args) (car args) args) ;; alist
                           args (if (symbolp args) (symbol-name args) args))
                     (push args result)
                     (cl-incf limit)
                     nil))
                 hide-spaces))
      (nreverse result))))

(defun with-completions-limit (&rest app)
  (unwind-protect
      (progn
        (advice-add #'all-completions :around #'completions-limit)
        (apply app))
    (advice-remove #'all-completions #'completions-limit)))

(advice-add #'orderless-all-completions :around #'with-completions-limit)

[oantolin]

Well, it bothers me a little bit that when orderless-limit is set to a number the results are incorrect by design. I guess in practice it would be fine and this is probably the sort of correctness one should be willing to sacrifice for speed. But I am not sure, I think it would also feel weird that further typing can make candidates appear that weren't there before: you can be a top 10 match for foo bar even if you are not a top 10 match for foo alone! That seems a little dangerous: you might see the whole candidate list, not find what you want, and erroneously conclude that the candidate you wanted does not exist, while maybe adding a further input component would make it appear. I guess if we added a feature like this I'd have to add some strong warnings about incorrectness in the documentation. 😛

Also, we'd have to benchmark to see if this is worth it. I think that commonly the predicate is nil (for orderless-all-completions, of course it never is for the current implementation of orderless-try -completion). I haven't benchmarked but suspect that having a nil predicate is quite a bit faster than having (lambda (_cand) t) as the predicate; in which case, you'd have to really have many more candidates than the limit for the early exit to pay for having to use a predicate at all. (I could be wrong about the nil predicate case being substantially faster.)

[oantolin]

I also think the limit would be annoying for embark-export/collect.

[minad]

Thinking about your correctness argument a bit more - this argument doesn't really hold up since we can also set completion styles to a list of styles e.g. basic and then orderless. In this case candidates can also magically appear as you enter more input. So this is a quite common (but still ugly) effect.

The prototype I've given above in
#141 (comment) also has the nice property that it doesn't suffer from any of the issues due to the predicate which I had described before.

I am only a little unsure if such a limit should actually be part of Orderless or part of some more general completion style wrapper. I've been quite happy with Orderless as my main and only style, and as toolbox to define new styles. Adding a limiter would make the toolbox a little more flexible.

I will create a patch and then we get a better perspective if this is a worthy addition or not.

[minad]

Okay, after trying this more I am giving up on the idea. Limiting the number of candidates is useful far too rarely. The problem is that limiting defeats sorting by recency. It would only work for completion tables where the candidates are already in the desired order. I believe that I had already rejected this idea at some point for this reason, but had forgotten about this problem again. For reference, see the implementation here https://github.com/minad/orderless/tree/limit.

The better alternative is to handle limiting in the backend itself, see for example minad/cape@28a2a16.

[oantolin]

this argument doesn't really hold up since we can also set completion styles to a list of styles e.g. basic and then orderless. In this case candidates can also magically appear as you enter more input. So this is a quite common (but still ugly) effect.

Oh! Right! I missed that. I'd still rather not introduce incorrectness within a single completion style, but you're completely correct in saying it's something we deal with all the time (in fact, I'm occasionally annoyed enough by it that I consider going back to '(orderless)).

Limiting the number of candidates is useful far too rarely. The problem is that limiting defeats sorting by recency.

This is a great point I hadn't thought of.

The better alternative is to handle limiting in the backend itself

I agree, that makes more sense.