* [PATCH] `completing-read` - allow history=t, sorting improvements
@ 2021-04-19 18:02 Daniel Mendler
2021-04-19 19:14 ` Stefan Monnier
0 siblings, 1 reply; 10+ messages in thread
From: Daniel Mendler @ 2021-04-19 18:02 UTC (permalink / raw)
To: emacs-devel@gnu.org
[-- Attachment #1: Type: text/plain, Size: 166 bytes --]
I attached patches for minibuffer.el which address these points:
1. Allow history=t to disable the `completing-read` history
2. Sorting improvements
Daniel Mendler
[-- Attachment #2: 0001-completing-read-If-HIST-is-the-symbol-t-history-is-n.patch --]
[-- Type: text/x-diff, Size: 3556 bytes --]
From 6b68a42ef77fcb4c07e5a110e4c77be10985852b Mon Sep 17 00:00:00 2001
From: Daniel Mendler <mail@daniel-mendler.de>
Date: Mon, 19 Apr 2021 08:20:50 +0200
Subject: [PATCH 1/6] completing-read: If HIST is the symbol `t', history is
not recorded.
* lisp/minibuffer.el (completion-all-sorted-completions): Check if
`minibuffer-history-variable` is `t`
* src/minibuf.c (completing-read): Update docstring
* doc/lispref/minibuf.texi: Update documentation of
`read-from-minibuffer` and `completing-read`
---
doc/lispref/minibuf.texi | 13 ++++++++-----
lisp/minibuffer.el | 2 +-
src/minibuf.c | 3 ++-
3 files changed, 11 insertions(+), 7 deletions(-)
diff --git a/doc/lispref/minibuf.texi b/doc/lispref/minibuf.texi
index d16409d6c8..e922f1836b 100644
--- a/doc/lispref/minibuf.texi
+++ b/doc/lispref/minibuf.texi
@@ -167,8 +167,10 @@ Text from Minibuffer
The argument @var{history} specifies a history list variable to use
for saving the input and for history commands used in the minibuffer.
-It defaults to @code{minibuffer-history}. You can optionally specify
-a starting position in the history list as well. @xref{Minibuffer History}.
+It defaults to @code{minibuffer-history}. If @var{history} is the
+symbol @code{t}, history is not recorded. You can optionally specify
+a starting position in the history list as well. @xref{Minibuffer
+History}.
If the variable @code{minibuffer-allow-text-properties} is
non-@code{nil}, then the string that is returned includes whatever text
@@ -1107,9 +1109,10 @@ Minibuffer Completion
@code{minibuffer-local-must-match-map} if @var{require-match} is
non-@code{nil}. @xref{Completion Commands}.
-The argument @var{history} specifies which history list variable to use for
-saving the input and for minibuffer history commands. It defaults to
-@code{minibuffer-history}. @xref{Minibuffer History}.
+The argument @var{history} specifies which history list variable to
+use for saving the input and for minibuffer history commands. It
+defaults to @code{minibuffer-history}. If @var{history} is the symbol
+@code{t}, history is not recorded. @xref{Minibuffer History}.
The argument @var{initial} is mostly deprecated; we recommend using a
non-@code{nil} value only in conjunction with specifying a cons cell
diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index c900b0d7ce..06a5e1e988 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -1390,7 +1390,7 @@ completion-all-sorted-completions
(t
;; Prefer shorter completions, by default.
(setq all (sort all (lambda (c1 c2) (< (length c1) (length c2)))))
- (if (minibufferp)
+ (if (and (minibufferp) (not (eq minibuffer-history-variable t)))
;; Prefer recently used completions and put the default, if
;; it exists, on top.
(let ((hist (symbol-value minibuffer-history-variable)))
diff --git a/src/minibuf.c b/src/minibuf.c
index a3c1b99bf3..f025817276 100644
--- a/src/minibuf.c
+++ b/src/minibuf.c
@@ -2023,7 +2023,8 @@ DEFUN ("completing-read", Fcompleting_read, Scompleting_read, 2, 8, 0,
(This is the only case in which you should use INITIAL-INPUT instead
of DEF.) Positions are counted starting from 1 at the beginning of
the list. The variable `history-length' controls the maximum length
- of a history list.
+ of a history list. If HIST is the symbol `t', history is not
+ recorded.
DEF, if non-nil, is the default value or the list of default values.
--
2.20.1
[-- Attachment #3: 0002-minibuffer.el-Use-completion-message-instead-of-mini.patch --]
[-- Type: text/x-diff, Size: 1318 bytes --]
From 42a99f69032b801a402d716280a50b4e27d1238f Mon Sep 17 00:00:00 2001
From: Daniel Mendler <mail@daniel-mendler.de>
Date: Mon, 19 Apr 2021 15:40:00 +0200
Subject: [PATCH 2/6] minibuffer.el: Use completion--message instead of
minibuffer-message
* minibuffer.el: Use completion--message consistently for the messages
"Incomplete", "Sole completion" and "No completions".
---
lisp/minibuffer.el | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 06a5e1e988..e4da79ad2b 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -1423,7 +1423,7 @@ minibuffer-force-complete-and-exit
;; test-completion, then we shouldn't exit, but that should be rare.
(lambda ()
(if minibuffer--require-match
- (minibuffer-message "Incomplete")
+ (completion--message "Incomplete")
;; If a match is not required, exit after all.
(exit-minibuffer)))))
@@ -2008,7 +2008,7 @@ minibuffer-completion-help
;; the sole completion, then hide (previous&stale) completions.
(minibuffer-hide-completions)
(ding)
- (minibuffer-message
+ (completion--message
(if completions "Sole completion" "No completions")))
(let* ((last (last completions))
--
2.20.1
[-- Attachment #4: 0003-completion-all-sorted-completions-Fix-sorting-perfor.patch --]
[-- Type: text/x-diff, Size: 2785 bytes --]
From 1a7d149642baafd7785a126cdf2644eff5b51149 Mon Sep 17 00:00:00 2001
From: Daniel Mendler <mail@daniel-mendler.de>
Date: Mon, 19 Apr 2021 08:43:41 +0200
Subject: [PATCH 3/6] completion-all-sorted-completions: Fix sorting
performance bug
* lisp/minibuffer.el (completion-all-sorted-completions): Use hash
table for sorting by history position, O(m+n*log(n)) instead of
O(m*n*log(n)) with history length `m` and candidate length `n`.
---
lisp/minibuffer.el | 33 +++++++++++++++++++++++++--------
1 file changed, 25 insertions(+), 8 deletions(-)
diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index e4da79ad2b..d728c791d3 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -1393,14 +1393,31 @@ completion-all-sorted-completions
(if (and (minibufferp) (not (eq minibuffer-history-variable t)))
;; Prefer recently used completions and put the default, if
;; it exists, on top.
- (let ((hist (symbol-value minibuffer-history-variable)))
- (setq all
- (sort all
- (lambda (c1 c2)
- (cond ((equal c1 minibuffer-default) t)
- ((equal c2 minibuffer-default) nil)
- (t (> (length (member c1 hist))
- (length (member c2 hist))))))))))))
+ (let* ((hist (symbol-value minibuffer-history-variable))
+ (hash (make-hash-table :test #'equal :size (length hist)))
+ (index 0)
+ (def (car-safe minibuffer-default)))
+ ;; Record history positions in hash
+ (dolist (c hist)
+ (unless (gethash c hash)
+ (puthash c index hash))
+ (cl-incf index))
+ (when (stringp def)
+ (puthash def -1 hash))
+ ;; Decorate elements with history position
+ (let ((c all))
+ (while c
+ (setcar c (cons (gethash (car c) hash
+ most-positive-fixnum)
+ (car c)))
+ (pop c)))
+ (setq all (sort all #'car-less-than-car))
+ ;; Drop decoration from the elements
+ (let ((c all))
+ (while c
+ (setcar c (cdar c))
+ (pop c)))))))
+
;; Cache the result. This is not just for speed, but also so that
;; repeated calls to minibuffer-force-complete can cycle through
;; all possibilities.
--
2.20.1
[-- Attachment #5: 0004-completion-all-sorted-completions-Respect-completion.patch --]
[-- Type: text/x-diff, Size: 3079 bytes --]
From 827c17d1645cce8d37a4a65369bea29e36681f3e Mon Sep 17 00:00:00 2001
From: Daniel Mendler <mail@daniel-mendler.de>
Date: Mon, 19 Apr 2021 13:06:54 +0200
Subject: [PATCH 4/6] completion-all-sorted-completions: Respect completion
boundaries
* lisp/minibuffer.el (completion-all-sorted-completions): When
building the hash of history positions drop the prefix as determined
by `completion-boundaries`. For file completions drop everything
behind the first "/".
---
lisp/minibuffer.el | 36 +++++++++++++++++++++++++++++-------
1 file changed, 29 insertions(+), 7 deletions(-)
diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index d728c791d3..c7aec9665e 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -1396,14 +1396,36 @@ completion-all-sorted-completions
(let* ((hist (symbol-value minibuffer-history-variable))
(hash (make-hash-table :test #'equal :size (length hist)))
(index 0)
- (def (car-safe minibuffer-default)))
- ;; Record history positions in hash
- (dolist (c hist)
- (unless (gethash c hash)
- (puthash c index hash))
- (cl-incf index))
+ (def (car-safe minibuffer-default))
+ (bounds (completion-boundaries
+ (substring string 0 (- (point) start))
+ minibuffer-completion-table
+ minibuffer-completion-predicate
+ ""))
+ (pre (substring string 0 (car bounds)))
+ (pre-len (length pre)))
+ ;; Default comes first.
(when (stringp def)
- (puthash def -1 hash))
+ (setq hist (cons def hist)))
+ ;; Record history positions in hash
+ (if (equal "" pre)
+ (progn
+ (dolist (c hist)
+ (unless (gethash c hash)
+ (puthash c index hash))
+ (cl-incf index)))
+ ;; Remove prefix from history strings, in order to
+ ;; handle completion boundaries.
+ (dolist (c hist)
+ (when (string-prefix-p pre c)
+ ;; Special handling of file name candidates:
+ ;; Drop everything after the first / after the prefix.
+ (let ((pos (and minibuffer-completing-file-name
+ (string-match-p "/" c pre-len))))
+ (setq c (substring c pre-len (and pos (1+ pos)))))
+ (unless (gethash c hash)
+ (puthash c index hash)))
+ (cl-incf index)))
;; Decorate elements with history position
(let ((c all))
(while c
--
2.20.1
[-- Attachment #6: 0005-completion-all-sorted-completions-Sort-candidates-in.patch --]
[-- Type: text/x-diff, Size: 3144 bytes --]
From 23f306510c4a00b539607b9e57486c7fb72f37bf Mon Sep 17 00:00:00 2001
From: Daniel Mendler <mail@daniel-mendler.de>
Date: Mon, 19 Apr 2021 13:17:23 +0200
Subject: [PATCH 5/6] completion-all-sorted-completions: Sort candidates in a
single pass
* lisp/minibuffer.el (completion-all-sorted-completions): Decorate
each candidate with history position and length such that the list can
be sorted in a single pass.
---
lisp/minibuffer.el | 23 ++++++++++++++---------
1 file changed, 14 insertions(+), 9 deletions(-)
diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index c7aec9665e..7146604ab4 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -1388,11 +1388,9 @@ completion-all-sorted-completions
(sort-fun
(setq all (funcall sort-fun all)))
(t
- ;; Prefer shorter completions, by default.
- (setq all (sort all (lambda (c1 c2) (< (length c1) (length c2)))))
(if (and (minibufferp) (not (eq minibuffer-history-variable t)))
- ;; Prefer recently used completions and put the default, if
- ;; it exists, on top.
+ ;; Sort first by history position and then by length.
+ ;; Put the default, if it exists, on top.
(let* ((hist (symbol-value minibuffer-history-variable))
(hash (make-hash-table :test #'equal :size (length hist)))
(index 0)
@@ -1426,19 +1424,26 @@ completion-all-sorted-completions
(unless (gethash c hash)
(puthash c index hash)))
(cl-incf index)))
- ;; Decorate elements with history position
+ ;; Decorate each candidate with (index<<13) +
+ ;; length. This way we sort first by index and then
+ ;; by length. We assume that the candidates are
+ ;; shorter than 2^13 characters and that the
+ ;; history is shorter than 2^16 entries.
(let ((c all))
(while c
- (setcar c (cons (gethash (car c) hash
- most-positive-fixnum)
- (car c)))
+ (setcar c (cons
+ (+ (lsh (gethash (car c) hash #xFFFF) 13)
+ (length (car c)))
+ (car c)))
(pop c)))
(setq all (sort all #'car-less-than-car))
;; Drop decoration from the elements
(let ((c all))
(while c
(setcar c (cdar c))
- (pop c)))))))
+ (pop c))))
+ ;; Sort only by length if no history is available.
+ (setq all (sort all (lambda (c1 c2) (< (length c1) (length c2))))))))
;; Cache the result. This is not just for speed, but also so that
;; repeated calls to minibuffer-force-complete can cycle through
--
2.20.1
[-- Attachment #7: 0006-completion-all-sorted-completions-Sort-alphabeticall.patch --]
[-- Type: text/x-diff, Size: 2679 bytes --]
From 4c657dcd79ee641193ea952cd4c1a01d842aa395 Mon Sep 17 00:00:00 2001
From: Daniel Mendler <mail@daniel-mendler.de>
Date: Mon, 19 Apr 2021 13:25:43 +0200
Subject: [PATCH 6/6] completion-all-sorted-completions: Sort alphabetically
* lisp/minibuffer.el (completion-all-sorted-completions): Sort by
history position, length and alphabetically.
---
lisp/minibuffer.el | 18 +++++++++++++-----
1 file changed, 13 insertions(+), 5 deletions(-)
diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 7146604ab4..f0277bf4fc 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -1389,8 +1389,9 @@ completion-all-sorted-completions
(setq all (funcall sort-fun all)))
(t
(if (and (minibufferp) (not (eq minibuffer-history-variable t)))
- ;; Sort first by history position and then by length.
- ;; Put the default, if it exists, on top.
+ ;; Sort first by history position, then by length,
+ ;; then alphabetically. Put the default, if it exists,
+ ;; on top.
(let* ((hist (symbol-value minibuffer-history-variable))
(hash (make-hash-table :test #'equal :size (length hist)))
(index 0)
@@ -1436,14 +1437,21 @@ completion-all-sorted-completions
(length (car c)))
(car c)))
(pop c)))
- (setq all (sort all #'car-less-than-car))
+ (setq all (sort all (lambda (c1 c2)
+ (or (< (car c1) (car c2))
+ (and (= (car c1) (car c2))
+ (string< (cdr c1) (cdr c2)))))))
;; Drop decoration from the elements
(let ((c all))
(while c
(setcar c (cdar c))
(pop c))))
- ;; Sort only by length if no history is available.
- (setq all (sort all (lambda (c1 c2) (< (length c1) (length c2))))))))
+ ;; Sort only by length and alphabetically if no history
+ ;; is available.
+ (setq all (sort all (lambda (c1 c2)
+ (or (< (length c1) (length c2))
+ (and (= (length c1) (length c2))
+ (string< c1 c2)))))))))
;; Cache the result. This is not just for speed, but also so that
;; repeated calls to minibuffer-force-complete can cycle through
--
2.20.1
^ permalink raw reply related [flat|nested] 10+ messages in thread
* Re: [PATCH] `completing-read` - allow history=t, sorting improvements
2021-04-19 18:02 [PATCH] `completing-read` - allow history=t, sorting improvements Daniel Mendler
@ 2021-04-19 19:14 ` Stefan Monnier
2021-04-19 19:36 ` Daniel Mendler
0 siblings, 1 reply; 10+ messages in thread
From: Stefan Monnier @ 2021-04-19 19:14 UTC (permalink / raw)
To: Daniel Mendler; +Cc: emacs-devel@gnu.org
Hi Daniel,
> 1. Allow history=t to disable the `completing-read` history
Thanks, pushed.
I see that this was really just a bug fix: t already prevented adding
the result to "the history", there was just one place where the code
burped when encountering this special "history var".
> From 42a99f69032b801a402d716280a50b4e27d1238f Mon Sep 17 00:00:00 2001
> From: Daniel Mendler <mail@daniel-mendler.de>
> Date: Mon, 19 Apr 2021 15:40:00 +0200
> Subject: [PATCH 2/6] minibuffer.el: Use completion--message instead of
> minibuffer-message
>
> * minibuffer.el: Use completion--message consistently for the messages
> "Incomplete", "Sole completion" and "No completions".
> ---
> lisp/minibuffer.el | 4 ++--
> 1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
> index 06a5e1e988..e4da79ad2b 100644
> --- a/lisp/minibuffer.el
> +++ b/lisp/minibuffer.el
> @@ -1423,7 +1423,7 @@ minibuffer-force-complete-and-exit
> ;; test-completion, then we shouldn't exit, but that should be rare.
> (lambda ()
> (if minibuffer--require-match
> - (minibuffer-message "Incomplete")
> + (completion--message "Incomplete")
> ;; If a match is not required, exit after all.
> (exit-minibuffer)))))
>
> @@ -2008,7 +2008,7 @@ minibuffer-completion-help
> ;; the sole completion, then hide (previous&stale) completions.
> (minibuffer-hide-completions)
> (ding)
> - (minibuffer-message
> + (completion--message
> (if completions "Sole completion" "No completions")))
>
> (let* ((last (last completions))
> --
> 2.20.1
I don't have a strong opinion on this patch, but I have the impression
that there might have been a good reason for the difference (i.e. the
above two cases could be considered "more serious" than those using
`completion--message`).
I would personally gladly get rid of `completion-show-inline-help`, so
I'm not the right person to judge if the above patch is doing the right
thing or not.
I pushed your "use a hash-table" patch to fix the N² complexity.
> From 827c17d1645cce8d37a4a65369bea29e36681f3e Mon Sep 17 00:00:00 2001
> From: Daniel Mendler <mail@daniel-mendler.de>
> Date: Mon, 19 Apr 2021 13:06:54 +0200
> Subject: [PATCH 4/6] completion-all-sorted-completions: Respect completion
> boundaries
>
> * lisp/minibuffer.el (completion-all-sorted-completions): When
> building the hash of history positions drop the prefix as determined
> by `completion-boundaries`. For file completions drop everything
> behind the first "/".
> ---
> lisp/minibuffer.el | 36 +++++++++++++++++++++++++++++-------
> 1 file changed, 29 insertions(+), 7 deletions(-)
>
> diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
> index d728c791d3..c7aec9665e 100644
> --- a/lisp/minibuffer.el
> +++ b/lisp/minibuffer.el
> @@ -1396,14 +1396,36 @@
> (let* ((hist (symbol-value minibuffer-history-variable))
> (hash (make-hash-table :test #'equal :size (length hist)))
> (index 0)
> - (def (car-safe minibuffer-default)))
> + (def (car-safe minibuffer-default))
> + (bounds (completion-boundaries
> + (substring string 0 (- (point) start))
> + minibuffer-completion-table
> + minibuffer-completion-predicate
> + ""))
> + (pre (substring string 0 (car bounds)))
> + (pre-len (length pre)))
> + ;; Default comes first.
> + (when (stringp def)
> + (setq hist (cons def hist)))
> ;; Record history positions in hash
> + (if (equal "" pre)
> + (progn
> (dolist (c hist)
> (unless (gethash c hash)
> (puthash c index hash))
> - (cl-incf index))
> - (when (stringp def)
> - (puthash def -1 hash))
> + (cl-incf index)))
> + ;; Remove prefix from history strings, in order to
> + ;; handle completion boundaries.
> + (dolist (c hist)
> + (when (string-prefix-p pre c)
> + ;; Special handling of file name candidates:
> + ;; Drop everything after the first / after the prefix.
> + (let ((pos (and minibuffer-completing-file-name
> + (string-match-p "/" c pre-len))))
> + (setq c (substring c pre-len (and pos (1+ pos)))))
> + (unless (gethash c hash)
> + (puthash c index hash)))
> + (cl-incf index)))
> ;; Decorate elements with history position
> (let ((c all))
> (while c
I think I'm fine with this patch, but at that point, this sorting code
*really* needs to be moved out into a separate function (already the
previous patch, which I just pushed, was borderline in this respect).
Also, I think this should come with a test case.
> From 23f306510c4a00b539607b9e57486c7fb72f37bf Mon Sep 17 00:00:00 2001
> From: Daniel Mendler <mail@daniel-mendler.de>
> Date: Mon, 19 Apr 2021 13:17:23 +0200
> Subject: [PATCH 5/6] completion-all-sorted-completions: Sort candidates in a
> single pass
>
> * lisp/minibuffer.el (completion-all-sorted-completions): Decorate
> each candidate with history position and length such that the list can
> be sorted in a single pass.
Does this result in a measurable difference?
The assumptions about maximum size and length aren't ideal, so unless
there's a clear performance argument, I think we're better off sticking
to the multiple passes.
> * lisp/minibuffer.el (completion-all-sorted-completions): Sort by
> history position, length and alphabetically.
I'd expect this will not make a big difference in most cases, but the
fact that it results in a more deterministic outcome is very welcome.
If you rebase this patch on top of the current minibuffer.el, I'll be
happy to push it.
> - (setq all (sort all #'car-less-than-car))
> + (setq all (sort all (lambda (c1 c2)
> + (or (< (car c1) (car c2))
> + (and (= (car c1) (car c2))
> + (string< (cdr c1) (cdr c2)))))))
Here also: have you compared the performance of multiple calls to `sort`
vs a single call to sort with a more costly comparison function?
I'd expect the difference to be negligible (and having a separate
alphabetical sort at the beginning would save us from having to handle
it twice (i.e. in the two different branches)).
Stefan
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] `completing-read` - allow history=t, sorting improvements
2021-04-19 19:14 ` Stefan Monnier
@ 2021-04-19 19:36 ` Daniel Mendler
2021-04-19 20:15 ` Stefan Monnier
0 siblings, 1 reply; 10+ messages in thread
From: Daniel Mendler @ 2021-04-19 19:36 UTC (permalink / raw)
To: Stefan Monnier; +Cc: emacs-devel@gnu.org
Hi Stefan,
thank you for pushing. I will adjust the patches which are still
relevant and resubmit them.
On 4/19/21 9:14 PM, Stefan Monnier wrote:
>> 1. Allow history=t to disable the `completing-read` history
> Thanks, pushed.
> I see that this was really just a bug fix: t already prevented adding
> the result to "the history", there was just one place where the code
> burped when encountering this special "history var".
Yes, also the documentation of `minibuffer-variable` specifies the
meaning of `t`.
>> * minibuffer.el: Use completion--message consistently for the messages
>> "Incomplete", "Sole completion" and "No completions".
> I don't have a strong opinion on this patch, but I have the impression
> that there might have been a good reason for the difference (i.e. the
> above two cases could be considered "more serious" than those using
> `completion--message`).
>
> I would personally gladly get rid of `completion-show-inline-help`, so
> I'm not the right person to judge if the above patch is doing the right
> thing or not.
For me the point was mostly to get this clarified, therefore I included
it here. Note that the messages "Sole completion" and "No completions"
are already shown at some other places via `completion--done` which uses
`completion--message` itself, but on a different code path.
>> * lisp/minibuffer.el (completion-all-sorted-completions): When
>> building the hash of history positions drop the prefix as determined
>> by `completion-boundaries`. For file completions drop everything
>> behind the first "/".
> I think I'm fine with this patch, but at that point, this sorting code
> *really* needs to be moved out into a separate function (already the
> previous patch, which I just pushed, was borderline in this respect).
> Also, I think this should come with a test case.
Okay, I agree with splitting up the large function. I will add a test case.
>> * lisp/minibuffer.el (completion-all-sorted-completions): Sort by
>> history position, length and alphabetically.
> I'd expect this will not make a big difference in most cases, but the
> fact that it results in a more deterministic outcome is very welcome.
> If you rebase this patch on top of the current minibuffer.el, I'll be
> happy to push it.
I will send an updated patch.
>> From 23f306510c4a00b539607b9e57486c7fb72f37bf Mon Sep 17 00:00:00 2001
>> From: Daniel Mendler <mail@daniel-mendler.de>
>> Date: Mon, 19 Apr 2021 13:17:23 +0200
>> Subject: [PATCH 5/6] completion-all-sorted-completions: Sort candidates in a
>> single pass
> Does this result in a measurable difference?
> The assumptions about maximum size and length aren't ideal, so unless
> there's a clear performance argument, I think we're better off sticking
> to the multiple passes.
>> * lisp/minibuffer.el (completion-all-sorted-completions): Sort by
>> history position, length and alphabetically.
> Here also: have you compared the performance of multiple calls to `sort`
> vs a single call to sort with a more costly comparison function?
> I'd expect the difference to be negligible (and having a separate
> alphabetical sort at the beginning would save us from having to handle
> it twice (i.e. in the two different branches)).
Agree generally. It makes a difference if one uses car-less-than-car,
since then the comparison function is fast. The difference is less
pronounced if one includes the lambdas which sort alphabetically (this
is on non-native, on native the picture could be different).
The important change is really the quadratic one. However in my Vertico
package (and in other continuously updating UIs), the big bottleneck of
the UI still is the sorting for many candidates, even when including
optimizations. Therefore I am using a vertico-sort-threshold there.
Maybe there are potential improvements on a lower level?
Daniel
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] `completing-read` - allow history=t, sorting improvements
2021-04-19 19:36 ` Daniel Mendler
@ 2021-04-19 20:15 ` Stefan Monnier
2021-04-19 20:44 ` Daniel Mendler
0 siblings, 1 reply; 10+ messages in thread
From: Stefan Monnier @ 2021-04-19 20:15 UTC (permalink / raw)
To: Daniel Mendler; +Cc: emacs-devel@gnu.org
>>> * minibuffer.el: Use completion--message consistently for the messages
>>> "Incomplete", "Sole completion" and "No completions".
>> I don't have a strong opinion on this patch, but I have the impression
>> that there might have been a good reason for the difference (i.e. the
>> above two cases could be considered "more serious" than those using
>> `completion--message`).
>> I would personally gladly get rid of `completion-show-inline-help`, so
>> I'm not the right person to judge if the above patch is doing the right
>> thing or not.
>
> For me the point was mostly to get this clarified, therefore I included it
> here. Note that the messages "Sole completion" and "No completions" are
> already shown at some other places via `completion--done` which uses
> `completion--message` itself, but on a different code path.
Oh, I see now that this var comes from:
commit 369e974dc086452033227a5d350c357602c6274e
Author: Chong Yidong <cyd@stupidchicken.com>
Date: Sun Apr 10 17:31:14 2011 -0400
Fix bad interaction between icomplete and completion inline help (Bug#5849).
* lisp/minibuffer.el (completion-show-inline-help): New var.
(completion--do-completion, minibuffer-complete)
(minibuffer-force-complete, minibuffer-complete-word): Inhibit
minibuffer messages if completion-show-inline-help is nil.
* lisp/icomplete.el (icomplete-mode): Bind completion-show-inline-help
to avoid interference from inline help.
I mistakenly thought it was a user config inherited from way-back which
I just preserved when I moved the code from minibuf.c to minibuffer.el.
So you're right we should use it everywhere. I pushed your patch.
> Agree generally. It makes a difference if one uses car-less-than-car, since
> then the comparison function is fast. The difference is less pronounced if
> one includes the lambdas which sort alphabetically (this is on non-native,
> on native the picture could be different).
Note that the separate alphabetical sorting can be done with (sort all
#'string-lessp) so it should also be fast ;-)
> The important change is really the quadratic one.
Yes, thank you for that fix, indeed.
> However in my Vertico package (and in other continuously updating
> UIs), the big bottleneck of the UI still is the sorting for many
> candidates, even when including optimizations.
> Therefore I am using a vertico-sort-threshold there.
> Maybe there are potential improvements on a lower level?
If O(N log N) is still too slow, then I think it's safe to say that the
problem is that N is too large: we can try and shave off a factor of `c`
or even the `log N` by optimizing the implementation, but that just
pushes the "too large" a bit further and sooner or later you'll have to
bite the bullet and introduce some "threshold" beyond which you reduce
the functionality.
In theory, if we want to optimize the speed as much as possible without
reducing the functionality, we could try to:
- first partition the set of candidates between those that appear in the
history and those that don't. This is linear time.
- sort the ones that appear in the history based on their position
there: no need to check length or alphabetic order in this case.
This is O(N log N) but the N should be significantly smaller.
- If you have enough candidates already to fill the display you can stop
at this point and just use those candidates.
- the remaining candidates can be sorted by their length, putting
together same-length candidates into sublists. This could even be
more-or-less linear time with some kind of bucket sort.
- Finally sort each of those sublists according to lexicographic order
This is again O(N log N) but again the N should be significantly
smaller and we can stop as soon as we've found enough candidates to
fill the display.
Stefan
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] `completing-read` - allow history=t, sorting improvements
2021-04-19 20:15 ` Stefan Monnier
@ 2021-04-19 20:44 ` Daniel Mendler
2021-04-19 21:52 ` Stefan Monnier
0 siblings, 1 reply; 10+ messages in thread
From: Daniel Mendler @ 2021-04-19 20:44 UTC (permalink / raw)
To: Stefan Monnier; +Cc: emacs-devel@gnu.org
On 4/19/21 10:15 PM, Stefan Monnier wrote:
>> However in my Vertico package (and in other continuously updating
>> UIs), the big bottleneck of the UI still is the sorting for many
>> candidates, even when including optimizations.
>> Therefore I am using a vertico-sort-threshold there.
>> Maybe there are potential improvements on a lower level?
>
> If O(N log N) is still too slow, then I think it's safe to say that the
> problem is that N is too large: we can try and shave off a factor of `c`
> or even the `log N` by optimizing the implementation, but that just
> pushes the "too large" a bit further and sooner or later you'll have to
> bite the bullet and introduce some "threshold" beyond which you reduce
> the functionality.
N is not that large. I want the sorting to be reasonably fast for the
the candidate sets which occur now in Emacs. But if this get improved,
people may throw more candidates at it and then we will end up again
with a threshold.
> In theory, if we want to optimize the speed as much as possible without
> reducing the functionality, we could try to:
> - first partition the set of candidates between those that appear in the
> history and those that don't. This is linear time.
> - sort the ones that appear in the history based on their position
> there: no need to check length or alphabetic order in this case.
> This is O(N log N) but the N should be significantly smaller.
> - If you have enough candidates already to fill the display you can stop
> at this point and just use those candidates.
> - the remaining candidates can be sorted by their length, putting
> together same-length candidates into sublists. This could even be
> more-or-less linear time with some kind of bucket sort.
> - Finally sort each of those sublists according to lexicographic order
> This is again O(N log N) but again the N should be significantly
> smaller and we can stop as soon as we've found enough candidates to
> fill the display.
Yes, we can do bucketing/radix sort by length. However I was looking for
a solution which cuts down the constants enough such that the solution
is good enough for the candidate sets we have now. By moving more of the
algorithm to elisp I will also get some larger constants which may
neglect the benefits until one reaches a large N.
Daniel
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] `completing-read` - allow history=t, sorting improvements
2021-04-19 20:44 ` Daniel Mendler
@ 2021-04-19 21:52 ` Stefan Monnier
2021-04-19 22:29 ` Daniel Mendler
0 siblings, 1 reply; 10+ messages in thread
From: Stefan Monnier @ 2021-04-19 21:52 UTC (permalink / raw)
To: Daniel Mendler; +Cc: emacs-devel@gnu.org
> N is not that large. I want the sorting to be reasonably fast for the the
> candidate sets which occur now in Emacs.
Yes, but the log N factor in sorting is even much smaller.
You can basically treat it as a constant.
> But if this get improved, people may throw more candidates at it and
> then we will end up again with a threshold.
That's the main point, indeed: rather than try to handle larger sets, we
want to avoid larger sets. That's why we have
`icomplete-show-matches-on-no-input` and `company-minimum-prefix-length`
(tho there can be other approaches like pushing the processing of sets
to a separate async process).
Stefan
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] `completing-read` - allow history=t, sorting improvements
2021-04-19 21:52 ` Stefan Monnier
@ 2021-04-19 22:29 ` Daniel Mendler
2021-04-19 22:55 ` Stefan Monnier
0 siblings, 1 reply; 10+ messages in thread
From: Daniel Mendler @ 2021-04-19 22:29 UTC (permalink / raw)
To: emacs-devel; +Cc: Stefan Monnier
[-- Attachment #1: Type: text/plain, Size: 1673 bytes --]
On 4/19/21 11:52 PM, Stefan Monnier wrote:
>> But if this get improved, people may throw more candidates at it and
>> then we will end up again with a threshold.
>
> That's the main point, indeed: rather than try to handle larger sets, we
> want to avoid larger sets.
I agree - it is always good to cut off a large amount of the work early on.
> That's why we have
> `icomplete-show-matches-on-no-input` and `company-minimum-prefix-length`
> (tho there can be other approaches like pushing the processing of sets
> to a separate async process).
Yes, these are reasonable settings. However many people like to see
candidates up front, me included (at least currently, taste changes) -
like in Ido, Ivy, Selectrum, Vertico etc. Then I am not very fond of
operations happening after some idle time. Having an input limits feels
more deterministic.
If Emacs can be made such that it fits for different usage patterns
that's great. But I would not over do it in optimizing for a million
candidates - therefore my poor man's "solution" of a threshold in Vertico.
Btw, I attached the updated patch for the boundaries. I am not sure if
the approach I took there is a good one, this works only in restricted
set of scenarios (not with partial-completion/initials unfortunately).
So this should be discussed.
Then you mentioned test cases - to clarify, do you want to see some kind
of integration test where a mockup minibuffer-completion-table is set-up
and the results of `completion-all-sorted-completions` are checked, or
some smaller tests of the helper functions? I looked briefly into
test/lisp/minibuffer.el - the test should probably go there?
Daniel
[-- Attachment #2: 0002-completion-all-sorted-completions-Add-completion-bou.patch --]
[-- Type: text/x-diff, Size: 3913 bytes --]
From a09ea8f4eb9a341f6c4ab090ec0c49acf070589a Mon Sep 17 00:00:00 2001
From: Daniel Mendler <mail@daniel-mendler.de>
Date: Tue, 20 Apr 2021 00:01:44 +0200
Subject: [PATCH] completion-all-sorted-completions: Add completion boundary
support
Remove the completion prefix from the history elements. This is a
heuristic which does not work for all completion styles. In
particular when using partial-completion or initials, the candidates
contain directories. Is there a better more general solution?
minibuffer.el (completion-all-sorted-completions): The history is
preprocessed by the function `minibuffer--sort-preprocess-history`.
---
lisp/minibuffer.el | 49 +++++++++++++++++++++++++++++++++++++---------
1 file changed, 40 insertions(+), 9 deletions(-)
diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 4ed596430c..d340aec98b 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -1381,6 +1381,42 @@ minibuffer--sort-by-length-alpha
(and (= (length c1) (length c2))
(string< c1 c2))))))
+(defun minibuffer--sort-preprocess-history (start string)
+ "Preprocess history, remove completion prefixes.
+STRING is the minibuffer content.
+START is the start position of the completion."
+ (let* ((def (car-safe minibuffer-default))
+ (hist (symbol-value minibuffer-history-variable))
+ (hist (if def (cons def hist) hist))
+ (bounds (completion-boundaries
+ (substring string 0 (- (point) start))
+ minibuffer-completion-table
+ minibuffer-completion-predicate
+ ""))
+ (pre (substring string 0 (car bounds)))
+ (pre-len (length pre)))
+ ;; Preprocess history if completion boundaries are used
+ (cond
+ ;; Special handling of file name candidates.
+ ;; Drop prefix and everything after the first "/".
+ (minibuffer-completing-file-name
+ (setq hist (delq nil
+ (mapcar
+ (lambda (c)
+ (when (string-prefix-p pre c)
+ (let ((pos (string-match-p "/" c pre-len)))
+ (substring c pre-len (and pos (1+ pos))))))
+ hist))))
+ ;; Drop prefix before the completion boundary
+ ((/= pre-len 0)
+ (setq hist
+ (delq nil (mapcar
+ (lambda (c)
+ (when (string-prefix-p pre c)
+ (substring c pre-len)))
+ hist))))
+ (t hist))))
+
(defun completion-all-sorted-completions (&optional start end)
(or completion-all-sorted-completions
(let* ((start (or start (minibuffer-prompt-end)))
@@ -1410,21 +1446,16 @@ completion-all-sorted-completions
(setq all (delete-dups all))
(setq last (last all))
- (cond
- (sort-fun
- (setq all (funcall sort-fun all)))
- (t
+ (if sort-fun
+ (setq all (funcall sort-fun all))
;; Sort first by length and alphabetically.
(setq all (minibuffer--sort-by-length-alpha all))
-
;; Sort by history position, put the default, if it
;; exists, on top.
(when (and (minibufferp) (not (eq minibuffer-history-variable t)))
- (let ((def (car-safe minibuffer-default))
- (hist (symbol-value minibuffer-history-variable)))
(setq all (minibuffer--sort-by-position
- (if def (cons def hist) hist)
- all))))))
+ (minibuffer--sort-preprocess-history start string)
+ all))))
;; Cache the result. This is not just for speed, but also so that
;; repeated calls to minibuffer-force-complete can cycle through
--
2.20.1
^ permalink raw reply related [flat|nested] 10+ messages in thread
* Re: [PATCH] `completing-read` - allow history=t, sorting improvements
2021-04-19 22:29 ` Daniel Mendler
@ 2021-04-19 22:55 ` Stefan Monnier
2021-04-19 23:47 ` Daniel Mendler
0 siblings, 1 reply; 10+ messages in thread
From: Stefan Monnier @ 2021-04-19 22:55 UTC (permalink / raw)
To: Daniel Mendler; +Cc: emacs-devel
> Btw, I attached the updated patch for the boundaries. I am not sure if the
> approach I took there is a good one, this works only in restricted set of
> scenarios (not with partial-completion/initials unfortunately). So this
> should be discussed.
See my comment below.
> Then you mentioned test cases - to clarify, do you want to see some kind of
> integration test where a mockup minibuffer-completion-table is set-up and
> the results of `completion-all-sorted-completions` are checked,
I think that's what we'd want, yes.
> I looked briefly into
> test/lisp/minibuffer.el - the test should probably go there?
^^^
-tests
Yes, indeed.
> +(defun minibuffer--sort-preprocess-history (start string)
> + "Preprocess history, remove completion prefixes.
> +STRING is the minibuffer content.
> +START is the start position of the completion."
> + (let* ((def (car-safe minibuffer-default))
> + (hist (symbol-value minibuffer-history-variable))
> + (hist (if def (cons def hist) hist))
> + (bounds (completion-boundaries
> + (substring string 0 (- (point) start))
> + minibuffer-completion-table
> + minibuffer-completion-predicate
> + ""))
Actually, the caller has the info we need already in the (cdr last),
which it throws away in:
(when last
(setcdr last nil)
This info also has the advantage of working with partial-completion
because it comes from the completion-style output rather than from the
completion-table.
[ If (cdr last) is nil it's equivalent to 0. ]
> + (pre (substring string 0 (car bounds)))
> + (pre-len (length pre)))
> + ;; Preprocess history if completion boundaries are used
> + (cond
> + ;; Special handling of file name candidates.
> + ;; Drop prefix and everything after the first "/".
> + (minibuffer-completing-file-name
I hope that using (cdr last) will make it unnecessary to use such a hack.
If not, then please try and use the `category` from `md` rather than
`minibuffer-completing-file-name` which I consider as obsolete (tho it's
not marked as such yet).
Stefan
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] `completing-read` - allow history=t, sorting improvements
2021-04-19 22:55 ` Stefan Monnier
@ 2021-04-19 23:47 ` Daniel Mendler
2021-04-20 1:55 ` Stefan Monnier
0 siblings, 1 reply; 10+ messages in thread
From: Daniel Mendler @ 2021-04-19 23:47 UTC (permalink / raw)
To: Stefan Monnier; +Cc: emacs-devel
On 4/20/21 12:55 AM, Stefan Monnier wrote:
>> +(defun minibuffer--sort-preprocess-history (start string)
>> + "Preprocess history, remove completion prefixes.
>> +STRING is the minibuffer content.
>> +START is the start position of the completion."
>> + (let* ((def (car-safe minibuffer-default))
>> + (hist (symbol-value minibuffer-history-variable))
>> + (hist (if def (cons def hist) hist))
>> + (bounds (completion-boundaries
>> + (substring string 0 (- (point) start))
>> + minibuffer-completion-table
>> + minibuffer-completion-predicate
>> + ""))
>
> Actually, the caller has the info we need already in the (cdr last),
> which it throws away in:
>
> (when last
> (setcdr last nil)
> This info also has the advantage of working with partial-completion
> because it comes from the completion-style output rather than from the
> completion-table.
Yes, right. The base size, even better. I will use that instead!
> [ If (cdr last) is nil it's equivalent to 0. ]
I stumbled over this just today, when I had assumed that the cdr always
has an integer. But the docs say it "may" have that.
>> + (pre (substring string 0 (car bounds)))
>> + (pre-len (length pre)))
>> + ;; Preprocess history if completion boundaries are used
>> + (cond
>> + ;; Special handling of file name candidates.
>> + ;; Drop prefix and everything after the first "/".
>> + (minibuffer-completing-file-name
>
> I hope that using (cdr last) will make it unnecessary to use such a hack.
> If not, then please try and use the `category` from `md` rather than
> `minibuffer-completing-file-name` which I consider as obsolete (tho it's
> not marked as such yet).
I will check. I still believe a tiny hack is needed because of the final
slash. And the advantage of dropping everything behind the slash is that
accesses to files influence the position of their parent directory (if
one considers that an advantage).
Thanks for letting me know about the `minibuffer-completing-file-name`
variable. There is also `minibuffer-completing-symbol`. Shall we mark
them as obsolete? I wondered why they exist but I took them thankfully
as an easy way to access the category. I will revert this then in my
packages.
Daniel
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] `completing-read` - allow history=t, sorting improvements
2021-04-19 23:47 ` Daniel Mendler
@ 2021-04-20 1:55 ` Stefan Monnier
0 siblings, 0 replies; 10+ messages in thread
From: Stefan Monnier @ 2021-04-20 1:55 UTC (permalink / raw)
To: Daniel Mendler; +Cc: emacs-devel
>> I hope that using (cdr last) will make it unnecessary to use such a hack.
>> If not, then please try and use the `category` from `md` rather than
>> `minibuffer-completing-file-name` which I consider as obsolete (tho it's
>> not marked as such yet).
> I will check. I still believe a tiny hack is needed because of the final
> slash.
I suggest you explain why with a concise example in a comment.
As I said, I strive to eliminate such backend-specific hacks, and while
I haven't managed to eliminate them all, I find it's important to
document them well.
> And the advantage of dropping everything behind the slash is that
> accesses to files influence the position of their parent directory (if one
> considers that an advantage).
I don't really understand what you're describing, but it reminds me of
something else: for entries which aren't found in the history, we could
look for "similar" entries. So, e.g. if you recently used many `gnus-*`
commands recently, the other `gnus-*` commands would also be bumped up
in the list. But this probably requires much more sophisticated code
than what we have currently (e.g. computing some kind of "distance"
between strings and weighing the value of a candidate based on its
distance to the various history entries). We could start with
a distance based on the "length of common prefix", (length
(try-completion "" (list candidate (nth i history)))) which would need
to be combined with `i` somehow. And if we want to avoid the N²
behavior, we'll need to use something like `radix-tree`.
> Thanks for letting me know about the `minibuffer-completing-file-name`
> variable. There is also `minibuffer-completing-symbol`. Shall we mark them
> as obsolete?
We should, but first we need to correct the places where we still use them.
> I wondered why they exist but I took them thankfully as an easy
> way to access the category.
They predate the `completion-metadata`.
Stefan
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2021-04-20 1:55 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-04-19 18:02 [PATCH] `completing-read` - allow history=t, sorting improvements Daniel Mendler
2021-04-19 19:14 ` Stefan Monnier
2021-04-19 19:36 ` Daniel Mendler
2021-04-19 20:15 ` Stefan Monnier
2021-04-19 20:44 ` Daniel Mendler
2021-04-19 21:52 ` Stefan Monnier
2021-04-19 22:29 ` Daniel Mendler
2021-04-19 22:55 ` Stefan Monnier
2021-04-19 23:47 ` Daniel Mendler
2021-04-20 1:55 ` Stefan Monnier
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).