bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Daniel Martín via Bug reports for GNU Emacs, the Swiss army knife of text editors]

When trying to search in a big project with thousands of files using
`project-find-regexp`, Emacs can synchronously block for a long time
until the results are computed for display in an *xref* buffer.

In contrast, the rgrep command and friends create a `grep-mode` buffer
and asynchronously fill it with results as they are computed by the grep
tool.  Emacs is not blocked and the user can start exploring matches
right away.

Is there a plan to eventually replace `grep-mode` with `xref-mode` in
Emacs?  If so, I think that computing results asynchronously is the most
important feature we'll lose.  When using `xref-mode` with an index
(etags, for example), the blocking is not noticeable; but when using a
grep tool the delay can be annoying if the repository is huge.

Another idea could be to use `grep-mode` for `project-find-regexp`, just
like `grep`, `lgrep`, `rgrep` and so one, but there's probably a reason
why it's using `xref-mode`.

Thanks.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Dmitry Gutov]

Hi Daniel,

On 22.09.2021 12:27, Daniel Martín via Bug reports for GNU Emacs, the 
Swiss army knife of text editors wrote:
> 
> When trying to search in a big project with thousands of files using
> `project-find-regexp`, Emacs can synchronously block for a long time
> until the results are computed for display in an *xref* buffer.
> 
> In contrast, the rgrep command and friends create a `grep-mode` buffer
> and asynchronously fill it with results as they are computed by the grep
> tool.  Emacs is not blocked and the user can start exploring matches
> right away.
> 
> Is there a plan to eventually replace `grep-mode` with `xref-mode` in
> Emacs?

No solid plan to replace everything (a lot of people will object, for 
various reasons), but it's the direction I want to see. At least in a 
core set of IDE-ish commands.

> If so, I think that computing results asynchronously is the most
> important feature we'll lose.  When using `xref-mode` with an index
> (etags, for example), the blocking is not noticeable; but when using a
> grep tool the delay can be annoying if the repository is huge.

Non-blocking UI for Xref is possible, but it requires a fair amount of 
work, possibly some low-level one. Not in the cards for Emacs 28, at least.

But maybe we could improve things another way first.

IIRC you are using macOS. I received another report recently that 
find/grep based tooling, and project-find-regexp in particular, are 
pretty slow on that OS.

When you say "block for a long time", how long are we talking about?

For reference, when a do a search across Emacs sources checkout, and 
there are few matches, it returns in ~100ms (with warm cache and SSD 
disk, to be clear).

To try it, evaluate

   (benchmark 1 '(project-find-regexp "new-collection"))

And a similar search across the Linux kernel source tree takes ~1s.

The first thing to try is to either install the latest GNU Grep and make 
sure Emacs uses it, or install ripgrep and

   (setq xref-search-program 'ripgrep)

Please report if that helps and how much.

Another benchmark to try is

   (benchmark 1 '(project-files (project-current)))

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Daniel Martín via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Dmitry Gutov <dgutov@yandex.ru> writes:
>
> IIRC you are using macOS. I received another report recently that
> find/grep based tooling, and project-find-regexp in particular, are 
> pretty slow on that OS.

Yes, this is on macOS.

>
> When you say "block for a long time", how long are we talking about?
>>
> To try it, evaluate
>
>   (benchmark 1 '(project-find-regexp "new-collection"))

I usually work on a monorepo with ~67000 tracked files (many of them big
binary files).  Here's what I get when using ripgrep as the xref search
program:

Elapsed time: 36.087181s (8.067474s in 22 GCs)

Running the same search with ripgrep from the command line takes around
6 seconds.

>
> Another benchmark to try is
>
>   (benchmark 1 '(project-files (project-current)))

Elapsed time: 1.590223s (0.432372s in 1 GCs)

Here's an ELisp profile of the first benchmark:

        8696  78% - command-execute
        8696  78%  - call-interactively
        8493  76%   - funcall-interactively
        8480  76%    - eval-expression
        8479  76%     - eval
        8479  76%      - project-find-regexp
        8227  74%       - xref--show-xrefs
        8227  74%        - xref--show-xref-buffer
        5584  50%         - #<compiled 0x140b5a40100bafc6>
        5584  50%          - apply
        5584  50%           - project--find-regexp-in-files
        5574  50%            - xref-matches-in-files
        3016  27%             - xref--convert-hits
        3000  27%              - mapcan
        2992  27%               - #<compiled -0x6cdcd56218925c3>
        2734  24%                - xref--collect-matches
        2094  18%                 - xref--collect-matches-1
         800   7%                  + xref-make-match
         774   7%                  + xref-make-file-location
         104   0%                   xref--find-file-buffer
          80   0%                   file-remote-p
          51   0%                   xref--regexp-syntax-dependent-p
         906   8%             + xref--process-file-region
         331   2%               sort
        1413  12%         + xref--analyze
        1230  11%         + xref--show-common-initialize
         249   2%       + project-files
           3   0%       + project-current
           9   0%    + minibuffer-complete
           4   0%    + execute-extended-command
         203   1%   + byte-code
        2314  20% - ...
        2314  20%    Automatic GC
          27   0% + timer-event-handler

The search time is reduced when I use a more specific search term,
presumably because the number of results is lower and the Elisp
post-processing takes less time.  Here's what I got, for example, when I
search for something with results from only one file:

Elapsed time: 6.859815s (0.864738s in 2 GCs)

Compared to the time taken by the same query from the command line
(6.5s) shows that the Elisp post-processing time is probably negligible
in this scenario.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Dmitry Gutov]

On 23.09.2021 00:58, Daniel Martín wrote:
> Dmitry Gutov <dgutov@yandex.ru> writes:
>>
>> IIRC you are using macOS. I received another report recently that
>> find/grep based tooling, and project-find-regexp in particular, are
>> pretty slow on that OS.
> 
> Yes, this is on macOS.
> 
>>
>> When you say "block for a long time", how long are we talking about?
>>>
>> To try it, evaluate
>>
>>    (benchmark 1 '(project-find-regexp "new-collection"))
> 
> I usually work on a monorepo with ~67000 tracked files (many of them big
> binary files).  Here's what I get when using ripgrep as the xref search
> program:
> 
> Elapsed time: 36.087181s (8.067474s in 22 GCs)

Thanks for testing. Did the switch to ripgrep help much?

I wonder if we should advertise this setting and recommendation more 
prominently, at least until we get auto-detection.

> Running the same search with ripgrep from the command line takes around
> 6 seconds.

Is that with an SSD?

Your project sounds respectable. The torvalds-linux repo I have checked 
out here is also 70000 files, but I guess your files are bigger.

>> Another benchmark to try is
>>
>>    (benchmark 1 '(project-files (project-current)))
> 
> Elapsed time: 1.590223s (0.432372s in 1 GCs)

That's a while (I wonder if you find 'project-find-file' usable with 
this kind of performance), but still better than I might have expected.

> Here's an ELisp profile of the first benchmark:
> 
>          8696  78% - command-execute
>          8696  78%  - call-interactively
>          8493  76%   - funcall-interactively
>          8480  76%    - eval-expression
>          8479  76%     - eval
>          8479  76%      - project-find-regexp
>          8227  74%       - xref--show-xrefs
>          8227  74%        - xref--show-xref-buffer
>          5584  50%         - #<compiled 0x140b5a40100bafc6>
>          5584  50%          - apply
>          5584  50%           - project--find-regexp-in-files
>          5574  50%            - xref-matches-in-files
>          3016  27%             - xref--convert-hits
>          3000  27%              - mapcan
>          2992  27%               - #<compiled -0x6cdcd56218925c3>
>          2734  24%                - xref--collect-matches
>          2094  18%                 - xref--collect-matches-1
>           800   7%                  + xref-make-match
>           774   7%                  + xref-make-file-location
>           104   0%                   xref--find-file-buffer
>            80   0%                   file-remote-p
>            51   0%                   xref--regexp-syntax-dependent-p
>           906   8%             + xref--process-file-region
>           331   2%               sort
>          1413  12%         + xref--analyze
>          1230  11%         + xref--show-common-initialize
>           249   2%       + project-files
>             3   0%       + project-current
>             9   0%    + minibuffer-complete
>             4   0%    + execute-extended-command
>           203   1%   + byte-code
>          2314  20% - ...
>          2314  20%    Automatic GC
>            27   0% + timer-event-handler

When you have a lot of matches, at some point Lisp overhead is going to 
show up. E.g., the searches seem almost instantaneous with up to several 
thousand matches here, but 10000s and 100000s - yeah, I have to wait.

Help with optimizations in that area (around/in xref-matches-in-files 
and xref--convert-hits) is welcome, but I'm not sure how much more we 
can squeeze.

> The search time is reduced when I use a more specific search term,
> presumably because the number of results is lower and the Elisp
> post-processing takes less time.  Here's what I got, for example, when I
> search for something with results from only one file:
> 
> Elapsed time: 6.859815s (0.864738s in 2 GCs)
> 
> Compared to the time taken by the same query from the command line
> (6.5s) shows that the Elisp post-processing time is probably negligible
> in this scenario.

It's a good result. A little suspicious, though: given that 
project-find-regexp calls project-files first, and the latter takes 
1.5s, the difference should ~ that time. But I guess rg also needs to 
traverse the directory tree, and spends some time on doing that too.

What else can be done -- again, if someone wants to investigate an 
asynchronous/nonblocking API for Xref (or using threads) -- welcome. The 
case when most of the time is spent in the subprocess is a good match. 
But I don't think we'll manage this for the upcoming release.

Another thing you can do is set up the additional ignores for the 
project. If those big binary files are not something you are interested 
in searching and touching, you could add ignore entries for them. When 
the vc project backend is in use (default), it is currently done via 
.dir-locals.el: the variable is project-vc-ignores, it's a list of 
strings that should be globs. See its docstring and the explanation in 
project-ignores's docstring.

Note that ignores also affect project-find-file.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Dmitry Gutov]

On 23.09.2021 02:09, Dmitry Gutov wrote:
> Help with optimizations in that area (around/in xref-matches-in-files 
> and xref--convert-hits) is welcome, but I'm not sure how much more we 
> can squeeze.

Meanwhile, I've pushed a couple of tweaks in a different place (the 
printing code) that should reduce the overhead somewhat.

Maybe turning those 36 seconds into 30 or even 20, depending on the 
average number of matches per file.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Daniel Martín via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Dmitry Gutov <dgutov@yandex.ru> writes:

>
> Thanks for testing. Did the switch to ripgrep help much?
>
> I wonder if we should advertise this setting and recommendation more
> prominently, at least until we get auto-detection.
>

When I set xref-search-program to 'grep, the search is almost 10x slower.

>> Running the same search with ripgrep from the command line takes around
>> 6 seconds.
>
> Is that with an SSD?

Yes, it's a fast MacBook Pro from 2017.

>
> Another thing you can do is set up the additional ignores for the
> project. If those big binary files are not something you are
> interested in searching and touching, you could add ignore entries for
> them. When the vc project backend is in use (default), it is currently
> done via .dir-locals.el: the variable is project-vc-ignores, it's a
> list of strings that should be globs. See its docstring and the
> explanation in project-ignores's docstring.
>

I sometimes do C-u C-x p g so that I can limit the search to certain
file extensions.  That helps a little bit.

So far, the command that offers me the best performance for this kind of
project grepping is `vc-git-grep`.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Dmitry Gutov]

On 24.09.2021 00:17, Daniel Martín wrote:
> Dmitry Gutov <dgutov@yandex.ru> writes:
> 
>>
>> Thanks for testing. Did the switch to ripgrep help much?
>>
>> I wonder if we should advertise this setting and recommendation more
>> prominently, at least until we get auto-detection.
>>
> 
> When I set xref-search-program to 'grep, the search is almost 10x slower.

I wonder if we could do more about this problem.

Perhaps on a platform like macOS we should consider bundling some 
up-to-date search program, be it GNU Grep or Ripgrep.

Eli, have there ever been a similar proposal under discussion? IIRC 
having to install external tools has been an issue on MS Windows as well 
for a long time. We give recommendations, but Grep has never been 
distributed together with Emacs. Any particular reason?

For comparison, VS Code bundles ripgrep. Or at least its macOS releases do.

>> Another thing you can do is set up the additional ignores for the
>> project. If those big binary files are not something you are
>> interested in searching and touching, you could add ignore entries for
>> them. When the vc project backend is in use (default), it is currently
>> done via .dir-locals.el: the variable is project-vc-ignores, it's a
>> list of strings that should be globs. See its docstring and the
>> explanation in project-ignores's docstring.
>>
> 
> I sometimes do C-u C-x p g so that I can limit the search to certain
> file extensions.  That helps a little bit.

Ignore entries are a bit more flexible: you don't need to repeat the 
preference every time. But they don't really work when you need to 
ignore only some files some of the time.

> So far, the command that offers me the best performance for this kind of
> project grepping is `vc-git-grep`.

'ripgrep' might be even faster, and there are Emacs interfaces for it 
like deadgrep (https://github.com/Wilfred/deadgrep).

But with Xref we're trying to create a consistent abstract UI that 
honors user's settings and can be used across commands, with extra 
features that can act on search results. There is no reason why it can't 
be snappy, but it's definitely more work.

(I haven't forgotten about bug#49731, BTW.)

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> Cc: 50733@debbugs.gnu.org
> From: Dmitry Gutov <dgutov@yandex.ru>
> Date: Fri, 24 Sep 2021 01:40:58 +0300
> 
> Perhaps on a platform like macOS we should consider bundling some 
> up-to-date search program, be it GNU Grep or Ripgrep.
> 
> Eli, have there ever been a similar proposal under discussion? IIRC 
> having to install external tools has been an issue on MS Windows as well 
> for a long time. We give recommendations, but Grep has never been 
> distributed together with Emacs. Any particular reason?
> 
> For comparison, VS Code bundles ripgrep. Or at least its macOS releases do.

Bundling an external program is problematic, but it can be done, of
course, provided that the license is right.  The problem is, we don't
provide macOS binaries, and we cannot rely on the fact that the
Windows binaries distribution will have its maintainer forever: we
already had periods of time without such a person.

We can recommend installing such tools, of course.

Btw, I don't understand why we focus on general-purpose text-searching
tools for these features.  Why not focus on packages like ID Utils
instead, they are so much faster.  Daniel, could you time the same
search in that large tree when xref-search-program is 'gid'?  (You'd
need to run 'mkid' first, to create the ID database, but that is
one-time, and is very fast.)  As I told many times, I think this is
the future: program language sensitive tools that use a precomputed
DB.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Juri Linkov]

> Btw, I don't understand why we focus on general-purpose text-searching
> tools for these features.  Why not focus on packages like ID Utils
> instead, they are so much faster.  Daniel, could you time the same
> search in that large tree when xref-search-program is 'gid'?  (You'd
> need to run 'mkid' first, to create the ID database, but that is
> one-time, and is very fast.)  As I told many times, I think this is
> the future: program language sensitive tools that use a precomputed
> DB.

While we have the make target `make tags` that generates the tags database
in the Emacs source tree, for trying to use ID Utils I can't find
a similar target that would create the ID database.  Is its command line
more complex than etags?

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> From: Juri Linkov <juri@linkov.net>
> Cc: Dmitry Gutov <dgutov@yandex.ru>,  50733@debbugs.gnu.org,
>   mardani29@yahoo.es
> Date: Fri, 24 Sep 2021 10:02:36 +0300
> 
> > Btw, I don't understand why we focus on general-purpose text-searching
> > tools for these features.  Why not focus on packages like ID Utils
> > instead, they are so much faster.  Daniel, could you time the same
> > search in that large tree when xref-search-program is 'gid'?  (You'd
> > need to run 'mkid' first, to create the ID database, but that is
> > one-time, and is very fast.)  As I told many times, I think this is
> > the future: program language sensitive tools that use a precomputed
> > DB.
> 
> While we have the make target `make tags` that generates the tags database
> in the Emacs source tree, for trying to use ID Utils I can't find
> a similar target that would create the ID database.

We can easily add it.

> Is its command line more complex than etags?

No, it's much more simple.  Assuming you are in the top-level
directory of the Emacs source tree, the command is just:

     mkid

That produces a file named 'ID' in that directory.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Juri Linkov]

>> Is its command line more complex than etags?
>
> No, it's much more simple.  Assuming you are in the top-level
> directory of the Emacs source tree, the command is just:
>
>      mkid
>
> That produces a file named 'ID' in that directory.

I tried to generate 'ID' with 'mkid', and then xref-find-references
works fine with it.  The only problem is that it finds occurrences
in .elc files.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> From: Juri Linkov <juri@linkov.net>
> Cc: dgutov@yandex.ru,  50733@debbugs.gnu.org,  mardani29@yahoo.es
> Date: Fri, 24 Sep 2021 18:30:56 +0300
> 
> I tried to generate 'ID' with 'mkid', and then xref-find-references
> works fine with it.  The only problem is that it finds occurrences
> in .elc files.

You can edit the id-lang.map file to ignore the *.elc files while
scanning.  Or use the -p option to mkid to exclude them.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Gregory Heytings]

>
> Btw, I don't understand why we focus on general-purpose text-searching 
> tools for these features.  Why not focus on packages like ID Utils 
> instead, they are so much faster.  Daniel, could you time the same 
> search in that large tree when xref-search-program is 'gid'?  (You'd 
> need to run 'mkid' first, to create the ID database, but that is 
> one-time, and is very fast.)  As I told many times, I think this is the 
> future: program language sensitive tools that use a precomputed DB.
>

id-tools are useful, but they do not provide the same functionality as 
grep/ripgrep.  On Emacs' trunk, mkid takes a few seconds to create a 12 MB 
database, and gid Eli returns only 4 occurrences.

This can be improved by using mkid --default-lang=text, but then mkid 
takes no less than 30 minutes (!) to create a 205 MB database, and gid Eli 
now returns 25 occurrences in ~1 second.

In comparison, rg Eli returns 6474 occurrences in < 0.1 seconds.

Moreover, incremental updates are not implemented in mkid.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> Date: Fri, 24 Sep 2021 09:00:13 +0000
> From: Gregory Heytings <gregory@heytings.org>
> cc: Dmitry Gutov <dgutov@yandex.ru>, 50733@debbugs.gnu.org, mardani29@yahoo.es
> 
> > Btw, I don't understand why we focus on general-purpose text-searching 
> > tools for these features.  Why not focus on packages like ID Utils 
> > instead, they are so much faster.  Daniel, could you time the same 
> > search in that large tree when xref-search-program is 'gid'?  (You'd 
> > need to run 'mkid' first, to create the ID database, but that is 
> > one-time, and is very fast.)  As I told many times, I think this is the 
> > future: program language sensitive tools that use a precomputed DB.
> 
> id-tools are useful, but they do not provide the same functionality as 
> grep/ripgrep.  On Emacs' trunk, mkid takes a few seconds to create a 12 MB 
> database, and gid Eli returns only 4 occurrences.
> 
> This can be improved by using mkid --default-lang=text, but then mkid 
> takes no less than 30 minutes (!) to create a 205 MB database, and gid Eli 
> now returns 25 occurrences in ~1 second.
> 
> In comparison, rg Eli returns 6474 occurrences in < 0.1 seconds.

We are talking about project.el, so the focus should be on looking for
strings that are meaningful in the programming-language context,
because that is what we need when programming.  Not looking for
arbitrary strings.  If someone wants to look for arbitrary strings,
they want "M-x grep" (with or without ripgrep), not
project-find-regexp.  The meaning of "word" or "symbol" is different
in different PLs; a tool like Grep can only approximate that, whereas
ID Utils uses the correct definition for each language.

> Moreover, incremental updates are not implemented in mkid.

It doesn't matter, as it's fast enough, and putting it on some kind of
cron job is more than enough to allow forgetting that this step
exists.

TANSTAAFL, so please let's not insist on looking for one.  We won't
find it.  Every alternative will let you pay something, so the issue
at hand is to find the alternative that is the best on balance, for
this particular feature, not one which is free of any price.

That said, you are free to use GP tools if you think it's best for
you.  And I will always prefer ID Utils.  My point is that we
shouldn't ignore solutions such as ID Utils, we should include them in
our consideration of what is "fast enough".  We shouldn't consider
only Grep, ripgrep, etc.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Dmitry Gutov]

On 24.09.2021 14:00, Eli Zaretskii wrote:
> If someone wants to look for arbitrary strings,
> they want "M-x grep" (with or without ripgrep), not
> project-find-regexp.

That's not true, sorry. project-find-regexp is for (basically) grepping 
across the project, the way it has been configured by the user (with 
ignore entries and everything). We don't make any effort to limit to 
program source code files, for example, and we want to support arbitrary 
regexps.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Gregory Heytings]

>
> We are talking about project.el, so the focus should be on looking for 
> strings that are meaningful in the programming-language context, because 
> that is what we need when programming.  Not looking for arbitrary 
> strings.
>

As Dmitry said, this isn't true.  But let's assume that it is.  The latter 
(arbitrary strings) is a superset of the former (identifiers).  In 
practice if you search for some identifier, it's not a real problem to see 
a few more matches in, say, the README or a ChangeLog file.

IMO, the one and only case where a specialized tool beats ripgrep (or just 
plain grep) is when you just want the place(s) where the identifier is 
defined.

>
> If someone wants to look for arbitrary strings, they want "M-x grep" 
> (with or without ripgrep), not project-find-regexp.  The meaning of 
> "word" or "symbol" is different in different PLs; a tool like Grep can 
> only approximate that, whereas ID Utils uses the correct definition for 
> each language.
>

That's not correct, mkid only supports a limited number of programming 
languages.  And it's not even precise: rg O_CREAT on the Emacs trunk for 
example returns 45 matches, gid O_CREAT returns 33 matches.

>> Moreover, incremental updates are not implemented in mkid.
>
> It doesn't matter, as it's fast enough, and putting it on some kind of 
> cron job is more than enough to allow forgetting that this step exists.
>

Five seconds to scan the whole Emacs trunk is IMO not fast enough (ripgrep 
does it in < 0.2 seconds).  And without incremental updates, updating the 
database would be necessary before each invocation of gid, because what 
users expect when they search for something are accurate results 
corresponding to the current state of the project, not results from, say, 
an hour ago.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> Date: Fri, 24 Sep 2021 13:18:22 +0000
> From: Gregory Heytings <gregory@heytings.org>
> cc: 50733@debbugs.gnu.org, dgutov@yandex.ru, mardani29@yahoo.es
> 
> IMO, the one and only case where a specialized tool beats ripgrep (or just 
> plain grep) is when you just want the place(s) where the identifier is 
> defined.

No, a specialized tool that uses a DB will scale much better than any
tool which searches the filesystem.  _And_ it will be more accurate
(if used correctly).

> That's not correct, mkid only supports a limited number of programming 
> languages. And it's not even precise: rg O_CREAT on the Emacs trunk for 
> example returns 45 matches, gid O_CREAT returns 33 matches.

I'm sorry, but this has NIH written all over it.  Am I right guessing
that you aren't an active user of ID Utils, and perhaps didn't even
know about it before I mentioned it?

More to the point: are you saying that a tool that returns more
matches is necessarily better?  That'd fly in the face of our
switching to the Xref package, whose explicit goal was to provide
_fewer_ matches, the ones that matter.  Look closer at those matches
which gid "missed", and you will see why it didn't show them to you.

Oh, and if ripgrep finds only 45 matches, then something is wrong with
it, because there are actually no less than 119 literal matches for
O_CREAT in the tree (not counting many binary files that also match).
So by this measure, ripgrep is also not the right tool for the job.

> Five seconds to scan the whole Emacs trunk is IMO not fast enough (ripgrep 
> does it in < 0.2 seconds).

Those 5 sec are invested only when needed, while the time it takes
Grep/ripgrep to scan the files is invested every search.  Do this
enough times, and you paid too much time.

> And without incremental updates, updating the database would be
> necessary before each invocation of gid, because what users expect
> when they search for something are accurate results corresponding to
> the current state of the project, not results from, say, an hour
> ago.

It is very easy to trigger a new mkid run from a file-notification
that watches the project tree, so that it runs in the background
without the user noticing when needed.  Puff! the problem's gone.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Dmitry Gutov]

On 24.09.2021 17:20, Eli Zaretskii wrote:

> More to the point: are you saying that a tool that returns more
> matches is necessarily better?  That'd fly in the face of our
> switching to the Xref package, whose explicit goal was to provide
> _fewer_ matches, the ones that matter.  Look closer at those matches
> which gid "missed", and you will see why it didn't show them to you.

Xref's find-definition and find-references indeed try to be more 
precise. But that's only for identifier searches.

> Oh, and if ripgrep finds only 45 matches, then something is wrong with
> it, because there are actually no less than 119 literal matches for
> O_CREAT in the tree (not counting many binary files that also match).
> So by this measure, ripgrep is also not the right tool for the job.

I'm guessing the remaining entries are somewhere in gitignore-d files?

>> Five seconds to scan the whole Emacs trunk is IMO not fast enough (ripgrep
>> does it in < 0.2 seconds).
> 
> Those 5 sec are invested only when needed, while the time it takes
> Grep/ripgrep to scan the files is invested every search.  Do this
> enough times, and you paid too much time.

FWIW, (project-find-regexp "O_CREAT") takes about 130ms here.

That's close to the perceptual "instant" time.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> Cc: 50733@debbugs.gnu.org, mardani29@yahoo.es
> From: Dmitry Gutov <dgutov@yandex.ru>
> Date: Fri, 24 Sep 2021 18:50:20 +0300
> 
> FWIW, (project-find-regexp "O_CREAT") takes about 130ms here.

"gid O_CREAT" takes 46 msec, and that's on MS-Windows.

Do we really need to keep this silly argument?  Every tool has its
advantages and disadvantages.  When used correctly, you will have only
the advantages and none of the disadvantages.  Can we agree on this
and move on, please?

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Dmitry Gutov]

On 24.09.2021 19:18, Eli Zaretskii wrote:
>> Cc:50733@debbugs.gnu.org,mardani29@yahoo.es
>> From: Dmitry Gutov<dgutov@yandex.ru>
>> Date: Fri, 24 Sep 2021 18:50:20 +0300
>>
>> FWIW, (project-find-regexp "O_CREAT") takes about 130ms here.
> "gid O_CREAT" takes 46 msec, and that's on MS-Windows.
> 
> Do we really need to keep this silly argument?  Every tool has its
> advantages and disadvantages.  When used correctly, you will have only
> the advantages and none of the disadvantages.

I'm not sure we're arguing.

That was my point: it's good to be able to 'M-x project-find-regexp' 
without a pre-generated index. But make use of it in 
'xref-find-references' when the user has made such an index.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Gregory Heytings]

>> IMO, the one and only case where a specialized tool beats ripgrep (or 
>> just plain grep) is when you just want the place(s) where the 
>> identifier is defined.
>
> No, a specialized tool that uses a DB will scale much better than any 
> tool which searches the filesystem.  _And_ it will be more accurate (if 
> used correctly).
>

Sorry, but I simply don't believe this.  At least not for general regex 
searches.  I'd be interested to see some numbers to support your 
viewpoint.

>> That's not correct, mkid only supports a limited number of programming 
>> languages. And it's not even precise: rg O_CREAT on the Emacs trunk for 
>> example returns 45 matches, gid O_CREAT returns 33 matches.
>
> I'm sorry, but this has NIH written all over it.  Am I right guessing 
> that you aren't an active user of ID Utils, and perhaps didn't even know 
> about it before I mentioned it?
>

You are wrong; of course I knew about ID Utils.  I tried and compared it 
with ripgrep a few years ago, and concluded that it's a (far) less useful 
tool, at least for my purposes, for the reasons I mentioned: it works with 
a database that must be updated, which is slow, and it is not faster than 
ripgrep.

>
> More to the point: are you saying that a tool that returns more matches 
> is necessarily better?
>

The purpose of project-find-regexp is to find all matches.

>
> Look closer at those matches which gid "missed", and you will see why it 
> didn't show them to you.
>

I looked close (before you asked), and no, I don't see why some matches 
are not included.  For example it returns

lib/tempname.c:212: __GT_FILE: create the file using open(O_CREAT|O_EXCL)

but not

lib/tempname.h:47: GT_FILE: create a large file using open(O_CREAT|O_EXCL)

and it returns

lib/open.c:99: /* Fail if one of O_CREAT, O_WRONLY, O_RDWR is specified and the filename

but not

lisp/gnus/nnmaildir.el:387: ;; If Emacs had O_CREAT|O_EXCL, we could return number-open here.

>
> Oh, and if ripgrep finds only 45 matches, then something is wrong with 
> it, because there are actually no less than 119 literal matches for 
> O_CREAT in the tree (not counting many binary files that also match). So 
> by this measure, ripgrep is also not the right tool for the job.
>

No, there are exactly 45 matches of "O_CREAT" on a fresh clone of the 
trunk.

>> Five seconds to scan the whole Emacs trunk is IMO not fast enough 
>> (ripgrep does it in < 0.2 seconds).
>
> Those 5 sec are invested only when needed, while the time it takes 
> Grep/ripgrep to scan the files is invested every search.  Do this enough 
> times, and you paid too much time.
>

Did you read the numbers I mentioned earlier?  rg O_CREAT is as fast as 
gid O_CREAT.  And this is without regexes; rg O.*CREAT is three times 
faster than gid O.*CREAT.

>> And without incremental updates, updating the database would be 
>> necessary before each invocation of gid, because what users expect when 
>> they search for something are accurate results corresponding to the 
>> current state of the project, not results from, say, an hour ago.
>
> It is very easy to trigger a new mkid run from a file-notification that 
> watches the project tree, so that it runs in the background without the 
> user noticing when needed.  Puff! the problem's gone.
>

Your "very easy" solution is still, IMO, an unnecessary complexity, with 
little (if any) benefit.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> Date: Fri, 24 Sep 2021 16:24:50 +0000
> From: Gregory Heytings <gregory@heytings.org>
> cc: 50733@debbugs.gnu.org, dgutov@yandex.ru, mardani29@yahoo.es
> 
> > Look closer at those matches which gid "missed", and you will see why it 
> > didn't show them to you.
> 
> I looked close (before you asked), and no, I don't see why some matches 
> are not included.  For example it returns
> 
> lib/tempname.c:212: __GT_FILE: create the file using open(O_CREAT|O_EXCL)
> 
> but not
> 
> lib/tempname.h:47: GT_FILE: create a large file using open(O_CREAT|O_EXCL)
> 
> and it returns
> 
> lib/open.c:99: /* Fail if one of O_CREAT, O_WRONLY, O_RDWR is specified and the filename
> 
> but not
> 
> lisp/gnus/nnmaildir.el:387: ;; If Emacs had O_CREAT|O_EXCL, we could return number-open here.

Hint: they are all in comments.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Gregory Heytings]

>>> Look closer at those matches which gid "missed", and you will see why 
>>> it didn't show them to you.
>>
>> I looked close (before you asked), and no, I don't see why some matches 
>> are not included.  For example it returns
>>
>> lib/tempname.c:212: __GT_FILE: create the file using open(O_CREAT|O_EXCL)
>>
>> but not
>>
>> lib/tempname.h:47: GT_FILE: create a large file using open(O_CREAT|O_EXCL)
>>
>> and it returns
>>
>> lib/open.c:99: /* Fail if one of O_CREAT, O_WRONLY, O_RDWR is specified and the filename
>>
>> but not
>>
>> lisp/gnus/nnmaildir.el:387: ;; If Emacs had O_CREAT|O_EXCL, we could return number-open here.
>
> Hint: they are all in comments.
>

Hint: read again, and look closer.  gid returns some matches in comments, 
some not.  For no apparent reason.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> Date: Fri, 24 Sep 2021 17:52:06 +0000
> From: Gregory Heytings <gregory@heytings.org>
> cc: 50733@debbugs.gnu.org, dgutov@yandex.ru, mardani29@yahoo.es
> 
> > Hint: they are all in comments.
> >
> 
> Hint: read again, and look closer.  gid returns some matches in comments, 
> some not.  For no apparent reason.

Of course, there is a reason, you just don't understand it (and
generally think about gid as if it were a general-purpose text-search
utility).

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Gregory Heytings]

>> Hint: read again, and look closer.  gid returns some matches in 
>> comments, some not.  For no apparent reason.
>
> Of course, there is a reason, you just don't understand it
>

Who told you that I'm talking about myself?  FWIW, I understand the 
reason, but it's a completely non-apparent one, that isn't documented 
anywhere.  And it's not one that would make sense to most users.

>
> (and generally think about gid as if it were a general-purpose 
> text-search utility).
>

Who told you that I'm talking about myself?  I do not think of gid as a 
general-purpose text-search utility, but what most users want (and what 
project-find-regexp needs) is an efficient, easy to use and understand, 
predictable general-purpose text-search utility.  ripgrep is one such 
utility, idutils is not.  And, once again, ripgrep is, from a user point 
of view, as fast as or faster than idutils, and does not require any 
plumbing behind the scenes.

Out of curiosity, because of your "it doesn't scale" remark, I just 
compared the efficiency of ripgrep and idutils on the latest Linux kernel 
tarball (1.4 GB in 78464 files):

mkid takes 31 seconds

rg O_CREAT takes 0.18 seconds
gid O_CREAT takes 0.02 seconds
rg O.?CREAT takes 0.18 seconds
gid O.?CREAT takes 0.93 seconds
rg O.*CREAT takes 0.19 seconds
gid O.*CREAT takes 1.73 seconds

Isn't idutils the one that doesn't scale?

The only case in which idutils is faster (if one does not take the time 
that was spent to build the database into account, and if one considers 
that it's okay to ignore some matches in comments) is a plain identifier; 
from a user viewpoint getting an answer in 0.2 seconds on such a big code 
base is as good as getting an answer in 0.02 seconds.  It's slower, much 
slower in all other cases, whenever a regexp is used --- which is what 
project-find-regexp is all about.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> Date: Fri, 24 Sep 2021 21:49:35 +0000
> From: Gregory Heytings <gregory@heytings.org>
> cc: 50733@debbugs.gnu.org, dgutov@yandex.ru, mardani29@yahoo.es
> 
> >> Hint: read again, and look closer.  gid returns some matches in 
> >> comments, some not.  For no apparent reason.
> >
> > Of course, there is a reason, you just don't understand it
> 
> Who told you that I'm talking about myself?  FWIW, I understand the 
> reason, but it's a completely non-apparent one, that isn't documented 
> anywhere.  And it's not one that would make sense to most users.

What would you like to document about it? that sometimes false
positives do happen?  Does any other similar utility ever does
something like that in its documentation?  Dealing with false
positives is for the users of the utility, because only they know
which ones are false.

Or are you saying that having N false positive is somehow worse than
having M > N false positive, because some theoretical users might not
understand why they see some of the N false positives but not the
others?  (I say "theoretical" because evidently you didn't have a
problem understanding the reason.)

> Out of curiosity, because of your "it doesn't scale" remark, I just 
> compared the efficiency of ripgrep and idutils on the latest Linux kernel 
> tarball (1.4 GB in 78464 files):
> 
> mkid takes 31 seconds
> 
> rg O_CREAT takes 0.18 seconds
> gid O_CREAT takes 0.02 seconds
> rg O.?CREAT takes 0.18 seconds
> gid O.?CREAT takes 0.93 seconds
> rg O.*CREAT takes 0.19 seconds
> gid O.*CREAT takes 1.73 seconds
> 
> Isn't idutils the one that doesn't scale?

No.  You compare apples with oranges.

> The only case in which idutils is faster (if one does not take the time 
> that was spent to build the database into account, and if one considers 
> that it's okay to ignore some matches in comments) is a plain identifier; 
> from a user viewpoint getting an answer in 0.2 seconds on such a big code 
> base is as good as getting an answer in 0.02 seconds.  It's slower, much 
> slower in all other cases, whenever a regexp is used --- which is what 
> project-find-regexp is all about.

See what I mean?  Even when it's better, it's worse.  Perfect
reasoning.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Gregory Heytings]

>> Out of curiosity, because of your "it doesn't scale" remark, I just 
>> compared the efficiency of ripgrep and idutils on the latest Linux 
>> kernel tarball (1.4 GB in 78464 files):
>>
>> mkid takes 31 seconds
>>
>> rg O_CREAT takes 0.18 seconds
>> gid O_CREAT takes 0.02 seconds
>> rg O.?CREAT takes 0.18 seconds
>> gid O.?CREAT takes 0.93 seconds
>> rg O.*CREAT takes 0.19 seconds
>> gid O.*CREAT takes 1.73 seconds
>>
>> Isn't idutils the one that doesn't scale?
>
> No.  You compare apples with oranges.
>

No.  I compare apples with apples.  I compare regexp searches in a code 
base with regexp searches in a code base.  Because this is a thread about 
regexp searches in a code base.  It's you who started talking about 
oranges instead, namely searching for identifiers in a code base.

>> The only case in which idutils is faster (if one does not take the time 
>> that was spent to build the database into account, and if one considers 
>> that it's okay to ignore some matches in comments) is a plain 
>> identifier; from a user viewpoint getting an answer in 0.2 seconds on 
>> such a big code base is as good as getting an answer in 0.02 seconds. 
>> It's slower, much slower in all other cases, whenever a regexp is used 
>> --- which is what project-find-regexp is all about.
>
> See what I mean?  Even when it's better, it's worse.  Perfect reasoning.
>

Perfect reading.  Nowhere did I say that it's worse when it's better.  I 
said that from a user viewpoint, a tool that is 155 ms faster in one (and 
only one) case, and slower in all other cases, is worse, and that from a 
user viewpoint this single "155 ms faster case" does not matter enough to 
justify the use of a more complex tool.

Note that Emacs takes some time (55 ms for a search for O_CREAT on the 
Emacs trunk) to read, process and display the output, which must be taken 
into account to calculate the perceived difference between search tool 
candidates.

Some more detailed numbers:

1. on Emacs' trunk (4759 files, 174 MB)

gid O_CREAT : 10 ms
gid O[A-Z_]CREAT : 75 ms
gid O.?CREAT : 70 ms
gid O.*CREAT : 70 ms

rg O_CREAT : 25 ms
rg O[A-Z_]CREAT : 25 ms
rg O.?CREAT : 25 ms
rg O.*CREAT : 25 ms

rg -w O_CREAT : 30 ms
rg -w O[A-Z_]CREAT : 30 ms
rg -w O.?CREAT : 30 ms
rg -w O.*CREAT : 30 ms

2. on the latest Linux kernel tarball (78464 files, 1.4 GB)

gid O_CREAT : 25 ms
gid O[A-Z_]CREAT : 1375 ms
gid O.?CREAT : 930 ms
gid O.*CREAT : 1730 ms

rg O_CREAT : 180 ms
rg O[A-Z_]CREAT : 185 ms
rg O.?CREAT : 185 ms
rg O.*CREAT : 185 ms

rg -w O_CREAT : 185 ms
rg -w O[A-Z_]CREAT : 190 ms
rg -w O.?CREAT : 190 ms
rg -w O.*CREAT : 190 ms

I initially reacted to your paragraph:

>
> Btw, I don't understand why we focus on general-purpose text-searching 
> tools for these features.  Why not focus on packages like ID Utils 
> instead, they are so much faster.  Daniel, could you time the same 
> search in that large tree when xref-search-program is 'gid'?  (You'd 
> need to run 'mkid' first, to create the ID database, but that is 
> one-time, and is very fast.)  As I told many times, I think this is the 
> future: program language sensitive tools that use a precomputed DB.
>

It should now be clear that idutils is not "so much faster", it is 
marginally faster in one case, and slower in all other cases.  And it 
doesn't do what project-find-regexp needs, because it ignores (most, but 
not all) tokens in comments (oh, BTW, including tokens in comments has 
been on its TODO for at least 20 years).  Creating the ID database is also 
not "very fast", and the ID database cannot be updated incrementally (oh, 
BTW, incremental database updates has been on its TODO list for at least 
20 years).  In short, it's an outdated tool, that isn't maintained 
anymore, and that can't be the future.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> Date: Mon, 27 Sep 2021 00:43:05 +0000
> From: Gregory Heytings <gregory@heytings.org>
> cc: 50733@debbugs.gnu.org, dgutov@yandex.ru, mardani29@yahoo.es
> 
> >> rg O_CREAT takes 0.18 seconds
> >> gid O_CREAT takes 0.02 seconds
> >> rg O.?CREAT takes 0.18 seconds
> >> gid O.?CREAT takes 0.93 seconds
> >> rg O.*CREAT takes 0.19 seconds
> >> gid O.*CREAT takes 1.73 seconds
> >>
> >> Isn't idutils the one that doesn't scale?
> >
> > No.  You compare apples with oranges.
> 
> No.  I compare apples with apples.  I compare regexp searches in a code 
> base with regexp searches in a code base.

There are different implementations of regexp searches in a code
base.  Are you saying that they all are "apples" for the purpose of
comparing scalability?  Then why not compare IDUtils with Grep?

To get back to the issue at hand: we are talking (or at least I was
talking) about scalability of an algorithm, not about some particular
implementation of the algorithm.  Ripgrep is a multithreaded program,
whereas idutils is single-threaded.  So for a fair comparison of
scalability of these two main ideas: file-based search vs DB search,
you need at the very least to limit ripgrep to a single thread.  And
then you need to run each program on code bases of various sizes,
preferably those which differ by orders of magnitude or close to that,
and see their O(n) behavior.  And exclude from your comparison
command-line options that require IDUtils to access the files in
addition to the DB.  That would be at least an approximation to
comparing apples to apples.  For an even better approximation, one
should analyze the implementations of regexp search in each program
and see if there aren't any significant differences there, or in any
other aspects of the implementation that could significantly affect
the speed.  If there are such aspects, then the study of scalability
should either account for the differences or implement the same regexp
etc. algorithms in both programs before comparing them.

But frankly, I don't understand why this all would be needed at all,
because it should be absolutely clear that searching the files in the
filesystem will always scale worse than reading a well-indexed DB.
IDUtils is an example of the latter, and it beats many utilities that
search the files, including ripgrep, as long as it doesn't need to
access the files themselves.  But even if it doesn't always beat them
(which you didn't yet demonstrate), it just means the ideas of its
design should be taken further and/or implemented better, that's all.

> Because this is a thread about regexp searches in a code base.

As should be clear from what I wrote at the beginning of this
sub-thread, it is about scalability of the various algorithms for such
searches, not about specific programs:

> > Btw, I don't understand why we focus on general-purpose text-searching 
> > tools for these features.  Why not focus on packages like ID Utils 
> > instead, they are so much faster.  Daniel, could you time the same 
> > search in that large tree when xref-search-program is 'gid'?  (You'd 
> > need to run 'mkid' first, to create the ID database, but that is 
> > one-time, and is very fast.)  As I told many times, I think this is the 
> > future: program language sensitive tools that use a precomputed DB.
> 
> It should now be clear that idutils is not "so much faster", it is 
> marginally faster in one case, and slower in all other cases.  And it 
> doesn't do what project-find-regexp needs, because it ignores (most, but 
> not all) tokens in comments (oh, BTW, including tokens in comments has 
> been on its TODO for at least 20 years).  Creating the ID database is also 
> not "very fast", and the ID database cannot be updated incrementally (oh, 
> BTW, incremental database updates has been on its TODO list for at least 
> 20 years).  In short, it's an outdated tool, that isn't maintained 
> anymore, and that can't be the future.

I said that such tools are the future, not that IDUtils itself is
necessarily the future (though it could be, if someone picks up its
development).  Again, this is about looking for the best tools for
this job, and I still stand by my opinion: focusing only on
general-purpose search tools is sub-optimal.  We should be on the
lookout for the other kind, and support those of them that exist at
least as well as we support Grep and its ilk.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Gregory Heytings]

>
> To get back to the issue at hand: we are talking (or at least I was 
> talking) about scalability of an algorithm, not about some particular 
> implementation of the algorithm.
>

Are you now again shifting the discussion to something else, a theoretical 
comparison between various algorithms?

>
> Ripgrep is a multithreaded program, whereas idutils is single-threaded. 
> So for a fair comparison of scalability of these two main ideas: 
> file-based search vs DB search, you need at the very least to limit 
> ripgrep to a single thread.  And then you need to run each program on 
> code bases of various sizes, preferably those which differ by orders of 
> magnitude or close to that, and see their O(n) behavior.  And exclude 
> from your comparison command-line options that require IDUtils to access 
> the files in addition to the DB.  That would be at least an 
> approximation to comparing apples to apples.
>

You're asking me to disable everything that makes ripgrep a modern tool, 
and to disable everything that makes idutils an outdated tool, to make the 
outdated tool shine in comparison?  Interesting viewpoint.

>
> But frankly, I don't understand why this all would be needed at all, 
> because it should be absolutely clear that searching the files in the 
> filesystem will always scale worse than reading a well-indexed DB.
>

Which is precisely what I don't believe.  It is, at least to me, not at 
all "absolutely clear" when you look at the whole picture, IOW, when you 
include the necessity to create and keep a database up to date in your 
comparison, the added complexity of that solution, and the purpose of the 
tool.

>
> IDUtils is an example of the latter, and it beats many utilities that 
> search the files, including ripgrep, as long as it doesn't need to 
> access the files themselves.  But even if it doesn't always beat them 
> (which you didn't yet demonstrate), it just means the ideas of its 
> design should be taken further and/or implemented better, that's all.
>

I provided you with many numbers and comparisons, which IMO demonstrate 
what they were meant to demonstrate.  A tool which finds matches for a 
regexp in a O(100 MB) code base in O(10 ms), and in a O(1 GB) code base in 
O(100 ms), is clearly good enough in practice.  (Note that I made these 
comparisons on a six or seven years old laptop, these numbers would be 
even lower on a more recent machine.)

I'm still waiting for some numbers from you to demonstrate *your* 
viewpoint.

>
> I said that such tools are the future, not that IDUtils itself is 
> necessarily the future (though it could be, if someone picks up its 
> development).
>

Is it not simply because it's not useful/better in practice that nobody is 
picking its development (and pretty much nobody is using it)?

>
> Again, this is about looking for the best tools for this job, and I 
> still stand by my opinion: focusing only on general-purpose search tools 
> is sub-optimal.
>

The message to which you replied and which started this subtread did not 
suggest to "focus only on general-purpose search tools", it suggested to 
focus only on *one* particular general-purpose search tool, ripgrep, which 
is currently the best tool for the job, and to bundle it with Emacs.  It 
has a public domain license, so I guess it should be possible.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> Date: Mon, 27 Sep 2021 09:23:28 +0000
> From: Gregory Heytings <gregory@heytings.org>
> cc: 50733@debbugs.gnu.org, dgutov@yandex.ru, mardani29@yahoo.es
> 
> > To get back to the issue at hand: we are talking (or at least I was 
> > talking) about scalability of an algorithm, not about some particular 
> > implementation of the algorithm.
> 
> Are you now again shifting the discussion to something else, a theoretical 
> comparison between various algorithms?

That was the original intent, so there's no change in subject on my
side.  Apologies if that wasn't clear enough.

> > Ripgrep is a multithreaded program, whereas idutils is single-threaded. 
> > So for a fair comparison of scalability of these two main ideas: 
> > file-based search vs DB search, you need at the very least to limit 
> > ripgrep to a single thread.  And then you need to run each program on 
> > code bases of various sizes, preferably those which differ by orders of 
> > magnitude or close to that, and see their O(n) behavior.  And exclude 
> > from your comparison command-line options that require IDUtils to access 
> > the files in addition to the DB.  That would be at least an 
> > approximation to comparing apples to apples.
> 
> You're asking me to disable everything that makes ripgrep a modern tool, 
> and to disable everything that makes idutils an outdated tool, to make the 
> outdated tool shine in comparison?  Interesting viewpoint.

That's the _only_ valid viewpoint when talking about scalability of
algorithms.  Aspects not relevant to the algorithm being examined
should not affect the comparison.  Comparing a multithreaded
implementation with a single-threaded one is like comparing programs
running on two very different computers, from the performance POV.

> > IDUtils is an example of the latter, and it beats many utilities that 
> > search the files, including ripgrep, as long as it doesn't need to 
> > access the files themselves.  But even if it doesn't always beat them 
> > (which you didn't yet demonstrate), it just means the ideas of its 
> > design should be taken further and/or implemented better, that's all.
> 
> I provided you with many numbers and comparisons, which IMO demonstrate 
> what they were meant to demonstrate.  A tool which finds matches for a 
> regexp in a O(100 MB) code base in O(10 ms), and in a O(1 GB) code base in 
> O(100 ms), is clearly good enough in practice.

"Good enough in practice" is not the issue at hand.  No one in their
right mind will argue that ripgrep's performance is not good enough in
practice, for the tree sizes that we are talking about.

But the scalability you measured is approximately O(n), as expected
from a tool that accesses the files while searching.  IDUtils' gid
basically runs in O(1) time.  I've just run it on a tree with 17MB of
code in 400 files (ID database size 54KB) and on a tree with 1.4GB of
code in 40,000 files (DB size 13.5MB), and I get the same time for the
same search: 15ms.  No algorithm that actually accesses most or all of
the files in the tree can scale like that.

And if the above still doesn't convince you, then please forgive me,
but I'll bow out of this.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Gregory Heytings]

>
> But the scalability you measured is approximately O(n), as expected from 
> a tool that accesses the files while searching.  IDUtils' gid basically 
> runs in O(1) time.  I've just run it on a tree with 17MB of code in 400 
> files (ID database size 54KB) and on a tree with 1.4GB of code in 40,000 
> files (DB size 13.5MB), and I get the same time for the same search: 
> 15ms.  No algorithm that actually accesses most or all of the files in 
> the tree can scale like that.
>

Of course a table lookup is O(1) and a search is O(n).  If and only if you 
forget the time it takes to build the table and to keep it up to date. 
According to my tests, 1 call to mkid followed by 100 calls to gid is 
still slower than 100 calls to rg; the "break-even point" is somewhere 
around 200 searches.

I agree with you on one point: it is perhaps possible to make rg even 
faster with a database cache.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> Date: Mon, 27 Sep 2021 12:25:04 +0000
> From: Gregory Heytings <gregory@heytings.org>
> cc: 50733@debbugs.gnu.org, dgutov@yandex.ru, mardani29@yahoo.es
> 
> Of course a table lookup is O(1) and a search is O(n).  If and only if you 
> forget the time it takes to build the table and to keep it up to date. 

That time is irrelevant, because it doesn't delay the search.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Gregory Heytings]

>> Of course a table lookup is O(1) and a search is O(n).  If and only if 
>> you forget the time it takes to build the table and to keep it up to 
>> date.
>
> That time is irrelevant, because it doesn't delay the search.
>

Of course it does.  The most important requirement of any search tool 
(regexp or not) is that it must display results that correspond to the 
current version of the files.  Even a daemon that watches the tree and 
calls mkid in the background when files in the tree have changed isn't 
enough, the results will regularly be wrong during N seconds (where N 
depends on the size of the tree, for example, on my laptop, 30 for a 1 GB 
tree).

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> Date: Mon, 27 Sep 2021 19:36:54 +0000
> From: Gregory Heytings <gregory@heytings.org>
> cc: 50733@debbugs.gnu.org, dgutov@yandex.ru, mardani29@yahoo.es
> 
> >> Of course a table lookup is O(1) and a search is O(n).  If and only if 
> >> you forget the time it takes to build the table and to keep it up to 
> >> date.
> >
> > That time is irrelevant, because it doesn't delay the search.
> >
> 
> Of course it does.  The most important requirement of any search tool 
> (regexp or not) is that it must display results that correspond to the 
> current version of the files.  Even a daemon that watches the tree and 
> calls mkid in the background when files in the tree have changed isn't 
> enough, the results will regularly be wrong during N seconds (where N 
> depends on the size of the tree, for example, on my laptop, 30 for a 1 GB 
> tree).

And you always change your files in significant enough ways with such
frequency?  Then yes, IDUtils is probably not for you, too bad.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Gregory Heytings]

>> Of course it does.  The most important requirement of any search tool 
>> (regexp or not) is that it must display results that correspond to the 
>> current version of the files.  Even a daemon that watches the tree and 
>> calls mkid in the background when files in the tree have changed isn't 
>> enough, the results will regularly be wrong during N seconds (where N 
>> depends on the size of the tree, for example, on my laptop, 30 for a 1 
>> GB tree).
>
> And you always change your files in significant enough ways with such 
> frequency?  Then yes, IDUtils is probably not for you, too bad.
>

Again I'm not talking about myself.  I only say that a search tool which 
displays wrong results (not even "Try again later") is not the right tool 
for most users.  Nobody would understand that, for example, after a git 
pull, a git checkout, or a git apply, they have to wait "some time" before 
doing a search.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Dmitry Gutov]

On 27.09.2021 15:25, Gregory Heytings wrote:
> I agree with you on one point: it is perhaps possible to make rg even 
> faster with a database cache.

Here's a relevant discussion: 
https://github.com/BurntSushi/ripgrep/issues/1497

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> Cc: 50733@debbugs.gnu.org, mardani29@yahoo.es
> From: Dmitry Gutov <dgutov@yandex.ru>
> Date: Mon, 27 Sep 2021 15:58:53 +0300
> 
> On 27.09.2021 15:25, Gregory Heytings wrote:
> > I agree with you on one point: it is perhaps possible to make rg even 
> > faster with a database cache.
> 
> Here's a relevant discussion: 
> https://github.com/BurntSushi/ripgrep/issues/1497

Yes, that would be a killer app: fast DB creation and lightning-fast
searches.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Gregory Heytings]

>>> I agree with you on one point: it is perhaps possible to make rg even 
>>> faster with a database cache.
>>
>> Here's a relevant discussion: 
>> https://github.com/BurntSushi/ripgrep/issues/1497
>
> Yes, that would be a killer app: fast DB creation and lightning-fast 
> searches.
>

Indeed, if it is actually possible.  I'd be curious to see whether and how 
much a database would improve ripgrep's performance.  Using a database 
does not come for free.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Dmitry Gutov]

On 24.09.2021 20:49, Eli Zaretskii wrote:
> Hint: they are all in comments.

It's not an obvious choice, BTW: whether to show references to the 
identifier in comments.

Personally, I think I prefer the current behavior of 
xref-find-references when using Grep for searching.

Because, when you are renaming a function, you don't want to forget the 
references to its name in comments across the project.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> Cc: 50733@debbugs.gnu.org, mardani29@yahoo.es
> From: Dmitry Gutov <dgutov@yandex.ru>
> Date: Fri, 24 Sep 2021 21:17:24 +0300
> 
> On 24.09.2021 20:49, Eli Zaretskii wrote:
> > Hint: they are all in comments.
> 
> It's not an obvious choice, BTW: whether to show references to the 
> identifier in comments.
> 
> Personally, I think I prefer the current behavior of 
> xref-find-references when using Grep for searching.

I won't argue about personal preferences.  IMO, it isn't a matter of
preference, it's a matter of matching between a job you have to do and
the best tool for that job.

> Because, when you are renaming a function, you don't want to forget the 
> references to its name in comments across the project.

Renaming identifiers is not the only job that needs these outputs.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Dmitry Gutov]

On 24.09.2021 09:34, Eli Zaretskii wrote:
>> Cc: 50733@debbugs.gnu.org
>> From: Dmitry Gutov <dgutov@yandex.ru>
>> Date: Fri, 24 Sep 2021 01:40:58 +0300
>>
>> Perhaps on a platform like macOS we should consider bundling some
>> up-to-date search program, be it GNU Grep or Ripgrep.
>>
>> Eli, have there ever been a similar proposal under discussion? IIRC
>> having to install external tools has been an issue on MS Windows as well
>> for a long time. We give recommendations, but Grep has never been
>> distributed together with Emacs. Any particular reason?
>>
>> For comparison, VS Code bundles ripgrep. Or at least its macOS releases do.
> 
> Bundling an external program is problematic, but it can be done, of
> course, provided that the license is right.  The problem is, we don't
> provide macOS binaries, and we cannot rely on the fact that the
> Windows binaries distribution will have its maintainer forever: we
> already had periods of time without such a person.

If we just bundled GNU find and GNU grep in both distributions (or, for 
macOS, tell the distributors to do that), that would improve OOTB 
behavior for many users. It's not like there's a real chance that the 
user would prefer some different version of Grep, for example.

What is the concern about the presence of the current maintainer? Would 
we do something different if he leaves? We'd probably need to find 
another maintainer, no?

> We can recommend installing such tools, of course.

Maybe we could do better?

> Btw, I don't understand why we focus on general-purpose text-searching
> tools for these features.  Why not focus on packages like ID Utils
> instead, they are so much faster.  Daniel, could you time the same
> search in that large tree when xref-search-program is 'gid'?  (You'd
> need to run 'mkid' first, to create the ID database, but that is
> one-time, and is very fast.) 

There is no such option in xref-search-program. If you can suggest an 
appropriate invocation for xref-search-program-alist, I can try and add it.

But I thought id-tools are for scanning for identifiers, not for 
arbitrary regexp searches?

 >  As I told many times, I think this is
 > the future: program language sensitive tools that use a precomputed
 > DB.

xref-find-references implies some language-awareness. 
project-find-regexp does not.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> Cc: mardani29@yahoo.es, 50733@debbugs.gnu.org
> From: Dmitry Gutov <dgutov@yandex.ru>
> Date: Fri, 24 Sep 2021 14:40:51 +0300
> 
> > Bundling an external program is problematic, but it can be done, of
> > course, provided that the license is right.  The problem is, we don't
> > provide macOS binaries, and we cannot rely on the fact that the
> > Windows binaries distribution will have its maintainer forever: we
> > already had periods of time without such a person.
> 
> If we just bundled GNU find and GNU grep in both distributions (or, for 
> macOS, tell the distributors to do that), that would improve OOTB 
> behavior for many users. It's not like there's a real chance that the 
> user would prefer some different version of Grep, for example.

You don't need to convince me, I have all of those installed, and
couldn't do without them.  The difficulties are practical, not
principal.

> What is the concern about the presence of the current maintainer? Would 
> we do something different if he leaves? We'd probably need to find 
> another maintainer, no?

Yes, and the question is: will we succeed, and how quickly?  We
already had a period of time without one, which means having no one is
not a theoretical danger.

> > Btw, I don't understand why we focus on general-purpose text-searching
> > tools for these features.  Why not focus on packages like ID Utils
> > instead, they are so much faster.  Daniel, could you time the same
> > search in that large tree when xref-search-program is 'gid'?  (You'd
> > need to run 'mkid' first, to create the ID database, but that is
> > one-time, and is very fast.) 
> 
> There is no such option in xref-search-program.

Hmm... I'm sure this worked in the past, at least for
xref-find-references?  Or does that use a different variable?

> If you can suggest an 
> appropriate invocation for xref-search-program-alist, I can try and add it.

Just "gid -r <R>".  But if this could run in an arbitrary directory,
there should also be a "-f .../ID" argument, telling it where to find
the ID database (usually, in the project's root).

> But I thought id-tools are for scanning for identifiers, not for 
> arbitrary regexp searches?

They can scan for identifiers that match regular expressions, where
"identifier" is defined by each file's PL.

>  >  As I told many times, I think this is
>  > the future: program language sensitive tools that use a precomputed
>  > DB.
> 
> xref-find-references implies some language-awareness. 
> project-find-regexp does not.

Are you sure people indeed use project-find-regexp _only_ for
language-agnostic searches?

Anyway, maybe we need a separate command, or a different (but similar)
tool, one that indexes the tokens in the project files instead of
scanning all of the files each time anew.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Dmitry Gutov]

On 24.09.2021 15:02, Eli Zaretskii wrote:

> You don't need to convince me, I have all of those installed, and
> couldn't do without them.  The difficulties are practical, not
> principal.

Bundling extra tools affects the size of the distribution, for example. 
I figured that's something you might have an opinion on.

>> What is the concern about the presence of the current maintainer? Would
>> we do something different if he leaves? We'd probably need to find
>> another maintainer, no?
> 
> Yes, and the question is: will we succeed, and how quickly?  We
> already had a period of time without one, which means having no one is
> not a theoretical danger.

I'm not sure how that affects our opinion on bundling, though.

>>> Btw, I don't understand why we focus on general-purpose text-searching
>>> tools for these features.  Why not focus on packages like ID Utils
>>> instead, they are so much faster.  Daniel, could you time the same
>>> search in that large tree when xref-search-program is 'gid'?  (You'd
>>> need to run 'mkid' first, to create the ID database, but that is
>>> one-time, and is very fast.)
>>
>> There is no such option in xref-search-program.
> 
> Hmm... I'm sure this worked in the past, at least for
> xref-find-references?  Or does that use a different variable?

Different variable, yes: semantic-symref-tool.

It affects xref-find-references.

>> If you can suggest an
>> appropriate invocation for xref-search-program-alist, I can try and add it.
> 
> Just "gid -r <R>".  But if this could run in an arbitrary directory,
> there should also be a "-f .../ID" argument, telling it where to find
> the ID database (usually, in the project's root).

Anyway, it seems the most pressing problem is not the performance of the 
external tool (ripgrep is quite fast, for example). But our 
post-processing of the results, when there are a lot of them.

id-tools (or alternatives) could help avoid the "fetch all project 
files" step, though. At the cost of extra manual management, which I 
personally don't like much.

>> But I thought id-tools are for scanning for identifiers, not for
>> arbitrary regexp searches?
> 
> They can scan for identifiers that match regular expressions, where
> "identifier" is defined by each file's PL.
> 
>>   >  As I told many times, I think this is
>>   > the future: program language sensitive tools that use a precomputed
>>   > DB.
>>
>> xref-find-references implies some language-awareness.
>> project-find-regexp does not.
> 
> Are you sure people indeed use project-find-regexp _only_ for
> language-agnostic searches?

Oh, I use it for all kinds of searches. The point is not being limited 
in the search input or the choice of files to search.

Instead, we can and will add UI for specifying extra filters for the 
results.

> Anyway, maybe we need a separate command, or a different (but similar)
> tool, one that indexes the tokens in the project files instead of
> scanning all of the files each time anew.

"Tokens" implies searching only for identifiers, no?

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> Cc: mardani29@yahoo.es, 50733@debbugs.gnu.org
> From: Dmitry Gutov <dgutov@yandex.ru>
> Date: Fri, 24 Sep 2021 15:22:39 +0300
> 
> On 24.09.2021 15:02, Eli Zaretskii wrote:
> 
> > You don't need to convince me, I have all of those installed, and
> > couldn't do without them.  The difficulties are practical, not
> > principal.
> 
> Bundling extra tools affects the size of the distribution, for example. 
> I figured that's something you might have an opinion on.

I doubt that the size of the distribution matters much these days.
Especially since tools like Grep usually have very small sizes of the
binary distribution.

> >> What is the concern about the presence of the current maintainer? Would
> >> we do something different if he leaves? We'd probably need to find
> >> another maintainer, no?
> > 
> > Yes, and the question is: will we succeed, and how quickly?  We
> > already had a period of time without one, which means having no one is
> > not a theoretical danger.
> 
> I'm not sure how that affects our opinion on bundling, though.

It might mean that bundling won't happen for mundane reasons.

> > Just "gid -r <R>".  But if this could run in an arbitrary directory,
> > there should also be a "-f .../ID" argument, telling it where to find
> > the ID database (usually, in the project's root).
> 
> Anyway, it seems the most pressing problem is not the performance of the 
> external tool (ripgrep is quite fast, for example). But our 
> post-processing of the results, when there are a lot of them.

Yes.

> id-tools (or alternatives) could help avoid the "fetch all project 
> files" step, though. At the cost of extra manual management, which I 
> personally don't like much.

Why is that a problem?  We have midnight.el which could be part of the
solution.

> > Anyway, maybe we need a separate command, or a different (but similar)
> > tool, one that indexes the tokens in the project files instead of
> > scanning all of the files each time anew.
> 
> "Tokens" implies searching only for identifiers, no?

For ID Utils, yes (although in text files those are words).  For some
other similar tool it could be something else.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Dmitry Gutov]

On 24.09.2021 16:06, Eli Zaretskii wrote:

>>>> What is the concern about the presence of the current maintainer? Would
>>>> we do something different if he leaves? We'd probably need to find
>>>> another maintainer, no?
>>>
>>> Yes, and the question is: will we succeed, and how quickly?  We
>>> already had a period of time without one, which means having no one is
>>> not a theoretical danger.
>>
>> I'm not sure how that affects our opinion on bundling, though.
> 
> It might mean that bundling won't happen for mundane reasons.

All right. But we can ask.

Before we do that,

Daniel, could you do a couple of benchmarks specifically with GNU Grep?

There are instructions for installing it here: 
https://apple.stackexchange.com/a/193300

Ripgrep might be faster (at least on some inputs), but even if we 
supported it for all kinds of searches (which we currently don't), we 
really won't get auto-detection into Emacs 28, so if GNU Grep's 
performance is within ~20%, we should focus on it first.

To improve OOTB performance across the board.

>> id-tools (or alternatives) could help avoid the "fetch all project
>> files" step, though. At the cost of extra manual management, which I
>> personally don't like much.
> 
> Why is that a problem?  We have midnight.el which could be part of the
> solution.

As Gregory mentioned, users often expect the results to be up-to-date, 
especially when it concerns a command as common as "find regexp". Doing 
it on cron is not ideal.

But of course we're free to add extra knobs for particular power users.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> Cc: 50733@debbugs.gnu.org
> Date: Wed, 22 Sep 2021 23:58:42 +0200
> From:  Daniel Martín via "Bug reports for GNU Emacs,
>  the Swiss army knife of text editors" <bug-gnu-emacs@gnu.org>
> 
> > When you say "block for a long time", how long are we talking about?
> >>
> > To try it, evaluate
> >
> >   (benchmark 1 '(project-find-regexp "new-collection"))
> 
> I usually work on a monorepo with ~67000 tracked files (many of them big
> binary files).  Here's what I get when using ripgrep as the xref search
> program:
> 
> Elapsed time: 36.087181s (8.067474s in 22 GCs)
> 
> Running the same search with ripgrep from the command line takes around
> 6 seconds.

How many matches does that report?

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Daniel Martín via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Eli Zaretskii <eliz@gnu.org> writes:

>> 
>> I usually work on a monorepo with ~67000 tracked files (many of them big
>> binary files).  Here's what I get when using ripgrep as the xref search
>> program:
>> 
>> Elapsed time: 36.087181s (8.067474s in 22 GCs)
>> 
>> Running the same search with ripgrep from the command line takes around
>> 6 seconds.
>
> How many matches does that report?

~70400 matches spread across ~3700 files.  Perhaps it's an extreme case
(I used a generic search term, "color").  I tried a more specific search
term ("clang analyzer") which returned 30 matches across 14 files.
Here's the benchmark:

Elapsed time: 10.176629s (0.946311s in 2 GCs)

I guess the command could signal ongoing progress somehow, to assure the
 user that Emacs is actually working and not frozen.

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Dmitry Gutov]

On 23.09.2021 23:42, Daniel Martín wrote:
> Eli Zaretskii <eliz@gnu.org> writes:
> 
>>>
>>> I usually work on a monorepo with ~67000 tracked files (many of them big
>>> binary files).  Here's what I get when using ripgrep as the xref search
>>> program:
>>>
>>> Elapsed time: 36.087181s (8.067474s in 22 GCs)
>>>
>>> Running the same search with ripgrep from the command line takes around
>>> 6 seconds.
>>
>> How many matches does that report?
> 
> ~70400 matches spread across ~3700 files.  Perhaps it's an extreme case
> (I used a generic search term, "color").  I tried a more specific search
> term ("clang analyzer") which returned 30 matches across 14 files.
> Here's the benchmark:
> 
> Elapsed time: 10.176629s (0.946311s in 2 GCs)

30 matches means parsing and printing the matches won't be a bottleneck. 
Just fetching the file names, sending it to the search process, and the 
search itself.

> I guess the command could signal ongoing progress somehow, to assure the
>   user that Emacs is actually working and not frozen.

I suppose we could add some messages like in the patch below.

It's a simple approach where "done" is printed after the search is done 
and the results are parsed, but before they have been printed.

So there can still be a perceptible delay when your search gets 10s of 
1000s of hits or more.

diff --git a/lisp/progmodes/project.el b/lisp/progmodes/project.el
index 68beedad3d..2b69fb7d57 100644
--- a/lisp/progmodes/project.el
+++ b/lisp/progmodes/project.el
@@ -851,9 +851,11 @@ project-or-external-find-regexp
  (defun project--find-regexp-in-files (regexp files)
    (unless files
      (user-error "Empty file list"))
+  (message "Searching...")
    (let ((xrefs (xref-matches-in-files regexp files)))
      (unless xrefs
        (user-error "No matches for: %s" regexp))
+    (message "Searching... done")
      xrefs))

  (defvar project-regexp-history-variable 'grep-regexp-history)

bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Eli Zaretskii]

> From: Daniel Martín <mardani29@yahoo.es>
> Cc: 50733@debbugs.gnu.org,  dgutov@yandex.ru
> Date: Thu, 23 Sep 2021 22:42:32 +0200
> 
> >> Elapsed time: 36.087181s (8.067474s in 22 GCs)
> >> 
> >> Running the same search with ripgrep from the command line takes around
> >> 6 seconds.
> >
> > How many matches does that report?
> 
> ~70400 matches spread across ~3700 files.  Perhaps it's an extreme case
> (I used a generic search term, "color").  I tried a more specific search
> term ("clang analyzer") which returned 30 matches across 14 files.
> Here's the benchmark:
> 
> Elapsed time: 10.176629s (0.946311s in 2 GCs)

This means processing 70K lines of output takes 28 - 9 = 19 seconds,
which is the lion's share of the run time in those situations.  9 sec
to scan the files and 8 sec to GC.

> I guess the command could signal ongoing progress somehow, to assure the
>  user that Emacs is actually working and not frozen.

Currently, that's impossible, because we never return to the main loop
while we wait for the process to terminate, so no Lisp can run during
that time.  That'd require to add a new hook, which the call-process
machinery would call while we wait, or maybe even a C-level function
to report the progress directly.  Shouldn't be too hard, I think, see
wait_for_termination.