GNU bug report logs - #78719
30.1; [PATCH] Add functions `string-common-prefix' and `string-try-completion'

Previous Next

Full log

View this message in rfc822 format

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Phil Sainty <psainty <at> orcon.net.nz>
Cc: Daniel Mendler <mail <at> daniel-mendler.de>, Eli Zaretskii <eliz <at> gnu.org>, 78719 <at> debbugs.gnu.org, drew.adams <at> oracle.com, juri <at> linkov.net
Subject: bug#78719: 30.1; [PATCH] Add functions `string-common-prefix' and `string-try-completion'
Date: Wed, 23 Jul 2025 12:49:51 -0400

> 1. STRING filter
>
>    A: small data set:
>    - filter arg took 0.06 seconds
>    - cl-loop took 0.11 seconds (1.8 times as long)
>
>    B: large data set:
>    - filter arg took 0.22 seconds
>    - cl-loop took 0.44 seconds (2 times as long)

Fair enough.

> 2. REGEXP-LIST filter
>
>    A: small data set:
>    - filter arg took 0.16 seconds
>    - cl-loop took 0.14 seconds (0.9 times as long)
>
>    B: large data set:
>    - filter arg took 0.72 seconds
>    - cl-loop took 0.65 seconds (0.9 times as long)

Interesting.  I can't think of any reason why the C-level calls to match
the regexp would be slower than going through ELisp.

What makes it even more surprising is that the ELisp code does more work:
- it allocates an intermediate list.
- it does case-insensitive matching (assuming `completion-ignore-case`
  was nil but `case-fold-search` was not).

> 3. PREDICATE filter
>
>    A: small data set:
>    - filter arg took 0.17 seconds
>    - cl-loop took 0.11 seconds (0.6 times as long)
>
>    B: large data set:
>    - filter arg took 0.76 seconds
>    - cl-loop took 0.46 seconds (0.6 times as long)

Interesting as well.  Here I suspect that the byte-compiler inlined the
`pred` into its call turning

    (benchmark-run-compiled 100
      (cl-flet ((pred (lambda (str)
                        (string-prefix-p "buf" str))))
        (string-common-prefix
         (cl-loop for str in mystrings
                  if (pred str)
                  collect str))))

into

    (benchmark-run-compiled 100
      (string-common-prefix
       (cl-loop for str in mystrings
                if (string-prefix-p "buf" str)
                collect str)))

Otherwise, I'd say that we're seeing the effect of the "fastpath" when
a bytecode function calls another bytecode function, where we avoid
the cost of leaving+entering the bytecode interpreter.

In any case, your test suggests the only advantage of the current
filtering system of `try-completion` is that the prefix filtering is
faster in C and that we will usually want to first filter with a prefix
and only after that do regexp or pred filtering on the
remaining candidates.

This said, in practice, `minibuffer.el` rarely uses those fancy
filtering system on `try-completion`: instead it uses them on
`all-completions` and then uses `try-completion` on (various parts of)
the resulting list of candidates without any filtering,


        Stefan

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.