bug#25995: 26.0.50; Mismatch between documented and actual behaviour of icomplete

bug#25995: 26.0.50; Mismatch between documented and actual behaviour of icomplete

[Alexis]

* Create a test directory containing three files: '1', '2', '3'.

* Change to that directory and run emacs -Q.

* M-x icomplete-mode

* C-x C-f

* C-j

Section 19.7.2 of the Emacs manual states:

"At any time, you can type ‘C-j’ to select the first completion in the
list."

Reading left-to-right, '1' is the first item in the list. So C-j
should visit that file. Instead, it visits '3'.

--

In GNU Emacs 26.0.50 (build 2, x86_64-pc-linux-gnu, GTK+ Version 3.22.8)
 of 2017-02-27 built on debian
Repository revision: 8db75f0ef9ad821bab0a2613bb8e549edbf14eb6
Windowing system distributor 'The X.Org Foundation', version 11.0.11901000
System Description:	Debian GNU/Linux 9.0 (stretch)

Recent messages:
For information about GNU Emacs and the GNU system, type C-h C-a.
Icomplete mode enabled

Configured features:
XPM JPEG TIFF GIF PNG RSVG IMAGEMAGICK SOUND DBUS GCONF GSETTINGS NOTIFY
GNUTLS LIBXML2 FREETYPE M17N_FLT LIBOTF XFT ZLIB TOOLKIT_SCROLL_BARS
GTK3 X11

Important settings:
  value of $LC_MESSAGES: C
  value of $LC_TIME: en_AU.UTF-8
  value of $LANG: en_AU.UTF-8
  locale-coding-system: utf-8-unix

Major mode: Lisp Interaction

Minor modes in effect:
  icomplete-mode: t
  tooltip-mode: t
  global-eldoc-mode: t
  electric-indent-mode: t
  mouse-wheel-mode: t
  tool-bar-mode: t
  menu-bar-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  blink-cursor-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  line-number-mode: t
  transient-mark-mode: t

Load-path shadows:
None found.

Features:
(shadow sort mail-extr emacsbug message puny seq byte-opt subr-x gv
bytecomp byte-compile cl-extra help-mode cconv cl-loaddefs pcase cl-lib
dired dired-loaddefs format-spec rfc822 mml easymenu mml-sec
password-cache epa derived epg epg-config gnus-util rmail rmail-loaddefs
mm-decode mm-bodies mm-encode mail-parse rfc2231 mailabbrev gmm-utils
mailheader sendmail rfc2047 rfc2045 ietf-drums mm-util mail-prsvr
mail-utils cus-start cus-load icomplete time-date mule-util tooltip
eldoc electric uniquify ediff-hook vc-hooks lisp-float-type mwheel
term/x-win x-win term/common-win x-dnd tool-bar dnd fontset image
regexp-opt fringe tabulated-list replace newcomment text-mode elisp-mode
lisp-mode prog-mode register page menu-bar rfn-eshadow isearch timer
select scroll-bar mouse jit-lock font-lock syntax facemenu font-core
term/tty-colors frame cl-generic cham georgian utf-8-lang misc-lang
vietnamese tibetan thai tai-viet lao korean japanese eucjp-ms cp51932
hebrew greek romanian slovak czech european ethiopic indian cyrillic
chinese composite charscript case-table epa-hook jka-cmpr-hook help
simple abbrev obarray minibuffer cl-preloaded nadvice loaddefs button
faces cus-face macroexp files text-properties overlay sha1 md5 base64
format env code-pages mule custom widget hashtable-print-readable
backquote dbusbind inotify dynamic-setting system-font-setting
font-render-setting move-toolbar gtk x-toolkit x multi-tty
make-network-process emacs)

Memory information:
((conses 16 103412 6170)
 (symbols 48 21091 1)
 (miscs 40 47 129)
 (strings 32 19810 4401)
 (string-bytes 1 604390)
 (vectors 16 14041)
 (vector-slots 8 478821 4680)
 (floats 8 50 66)
 (intervals 56 206 1)
 (buffers 976 11))

bug#25995: 26.0.50; Mismatch between documented and actual behaviour of icomplete

[npostavs]

tags 25995 confirmed
quit

Alexis <flexibeast@gmail.com> writes:

> * Create a test directory containing three files: '1', '2', '3'.
>
> * Change to that directory and run emacs -Q.
>
> * M-x icomplete-mode
>
> * C-x C-f
>
> * C-j
>
> Section 19.7.2 of the Emacs manual states:
>
> "At any time, you can type ‘C-j’ to select the first completion in the
> list."
>
> Reading left-to-right, '1' is the first item in the list. So C-j
> should visit that file. Instead, it visits '3'.

This seems to have been introduced by [1: 65797b1].  I guess
completion-pcm--filename-try-filter should not reverse its input?

1: 2016-04-28 19:31:43 +0200 65797b1d75e9f608ffd50fd88be47a854b143bb1
  Make icomplete respect `completion-ignored-extensions'

--- i/lisp/minibuffer.el
+++ w/lisp/minibuffer.el
@@ -3257,7 +3257,7 @@ completion-pcm--filename-try-filter
                       "\\)\\'")))
       (dolist (f all)
         (unless (string-match-p re f) (push f try)))
-      (or try all))))
+      (or (nreverse try) all))))
 
 
 (defun completion-pcm--merge-try (pattern all prefix suffix)

bug#25995: 26.0.50; Mismatch between documented and actual behaviour of icomplete

[Dmitry Gutov]

On 3/10/17 1:25 AM, npostavs@users.sourceforge.net wrote:

> This seems to have been introduced by [1: 65797b1].  I guess
> completion-pcm--filename-try-filter should not reverse its input?
> 
> 1: 2016-04-28 19:31:43 +0200 65797b1d75e9f608ffd50fd88be47a854b143bb1
>    Make icomplete respect `completion-ignored-extensions'
> 
> --- i/lisp/minibuffer.el
> +++ w/lisp/minibuffer.el
> @@ -3257,7 +3257,7 @@ completion-pcm--filename-try-filter
>                         "\\)\\'")))
>         (dolist (f all)
>           (unless (string-match-p re f) (push f try)))
> -      (or try all))))
> +      (or (nreverse try) all))))

Looks good to me, thank you.

But what are the chances of this 'nreverse' (or the whole function) 
being performance-significant?

Maybe we could switch this code to `cl-delete-if'. From my testing, it's 
considerably faster than dolist+push (even without nreverse).

bug#25995: 26.0.50; Mismatch between documented and actual behaviour of icomplete

[npostavs]

[-- Attachment #1: Type: text/plain, Size: 1566 bytes --]

Dmitry Gutov <dgutov@yandex.ru> writes:

> On 3/10/17 1:25 AM, npostavs@users.sourceforge.net wrote:
>
>> --- i/lisp/minibuffer.el
>> +++ w/lisp/minibuffer.el
>> @@ -3257,7 +3257,7 @@ completion-pcm--filename-try-filter
>>                         "\\)\\'")))
>>         (dolist (f all)
>>           (unless (string-match-p re f) (push f try)))
>> -      (or try all))))
>> +      (or (nreverse try) all))))
>
> Looks good to me, thank you.
>
> But what are the chances of this 'nreverse' (or the whole function)
> being performance-significant?
>
> Maybe we could switch this code to `cl-delete-if'. From my testing,
> it's considerably faster than dolist+push (even without nreverse).

I don't have a good sense of how the completion code fits together, so
I'm not sure how significant the performance of this function is, but in
my simplistic benchmark I found the opposite: dolist+push+nreverse is
quite a bit faster (although the difference can be swamped by GC).  So
adding `nreverse' won't be a problem.

    ~/src$ emacs -Q -batch -l emacs/bench-filter.elc
    dolist+push 1000
    Elapsed time: 0.000335s
    dolist+push 10000
    Elapsed time: 0.001951s
    dolist+push 100000
    Elapsed time: 0.056526s (0.035910s in 1 GCs)
    dolist+push+nreverse 1000
    Elapsed time: 0.000212s
    dolist+push+nreverse 10000
    Elapsed time: 0.002086s
    dolist+push+nreverse 100000
    Elapsed time: 0.019966s
    cl-delete-if 1000
    Elapsed time: 0.002174s
    cl-delete-if 10000
    Elapsed time: 0.003604s
    cl-delete-if 100000
    Elapsed time: 0.034759s


[-- Attachment #2: benchmark code --]
[-- Type: application/emacs-lisp, Size: 1948 bytes --]

bug#25995: 26.0.50; Mismatch between documented and actual behaviour of icomplete

[Dmitry Gutov]

On 6/19/17 6:28 AM, npostavs@users.sourceforge.net wrote:

> I don't have a good sense of how the completion code fits together, so
> I'm not sure how significant the performance of this function is, but in
> my simplistic benchmark I found the opposite: dolist+push+nreverse is
> quite a bit faster (although the difference can be swamped by GC).  So
> adding `nreverse' won't be a problem.

Thank you for the benchmark file. Indeed, in batch mode my results are 
similar to yours:

dolist+push 1000
Elapsed time: 0.000135s
dolist+push 10000
Elapsed time: 0.001112s
dolist+push 100000
Elapsed time: 0.011830s
dolist+push+nreverse 1000
Elapsed time: 0.000130s
dolist+push+nreverse 10000
Elapsed time: 0.001084s
dolist+push+nreverse 100000
Elapsed time: 0.011518s
cl-delete-if 1000
Elapsed time: 0.001173s
cl-delete-if 10000
Elapsed time: 0.001621s
cl-delete-if 100000
Elapsed time: 0.017909s

When running it interactively, however (M-x eval-buffer, also starting 
with 'emacs -Q'), I'm getting consistently opposite results:

dolist+push 1000
Elapsed time: 0.000836s
dolist+push 10000
Elapsed time: 0.007698s
dolist+push 100000
Elapsed time: 0.045281s
dolist+push+nreverse 1000
Elapsed time: 0.000512s
dolist+push+nreverse 10000
Elapsed time: 0.007719s
dolist+push+nreverse 100000
Elapsed time: 0.186524s (0.140654s in 1 GCs)
cl-delete-if 1000
Elapsed time: 0.002603s
cl-delete-if 10000
Elapsed time: 0.003347s
cl-delete-if 100000
Elapsed time: 0.021793s

In any case, nreverse barely affects the runtime, so please go ahead and 
push the patch. Thanks!

bug#25995: 26.0.50; Mismatch between documented and actual behaviour of icomplete

[npostavs]

tags 25995 fixed
close 25995 26.1
tags 24676 fixed
close 24676 26.1
quit

Dmitry Gutov <dgutov@yandex.ru> writes:

> When running it interactively, however (M-x eval-buffer, also starting
> with 'emacs -Q'), I'm getting consistently opposite results:

Ah, you're measuring interpreted code which will penalize the open-coded
loop more than the `cl-delete-if' call which has the loop tucked away
(and compiled).

> In any case, nreverse barely affects the runtime, so please go ahead
> and push the patch. Thanks!

Pushed to master [1: 1ed2086a03], also fixes the same issue for
`completion-pcm--all-completions' (Bug#24676).

[1: 1ed2086a03]: 2017-06-20 22:44:24 -0400
  Keep order of completion candidates (Bug#25995, Bug#24676)
  http://git.savannah.gnu.org/cgit/emacs.git/commit/?id=1ed2086a03a5f33482d2f184e57dad9e6a9d25d8

bug#25995: 26.0.50; Mismatch between documented and actual behaviour of icomplete

[Dmitry Gutov]

On 6/21/17 5:50 AM, npostavs@users.sourceforge.net wrote:

> Ah, you're measuring interpreted code which will penalize the open-coded
> loop more than the `cl-delete-if' call which has the loop tucked away
> (and compiled).

Indeed, thanks. Since eager macro-expansion landed, I don't recall 
seeing more than a 2x difference between byte-compiled and interpreted 
code, but here it is. :)

>> In any case, nreverse barely affects the runtime, so please go ahead
>> and push the patch. Thanks!
> 
> Pushed to master [1: 1ed2086a03], also fixes the same issue for
> `completion-pcm--all-completions' (Bug#24676).

Indeed!