bug#73484: 31.0.50; Abolishing etags-regen-file-extensions

[Eli Zaretskii <eliz@gnu.org>]

> Date: Wed, 9 Oct 2024 21:23:37 +0300
> Cc: pot@gnu.org, spwhitton@spwhitton.name, 73484@debbugs.gnu.org
> From: Dmitry Gutov <dmitry@gutov.dev>
> 
> 'perf' shows me a profile like this:
> 
>    67.31%  etags    libc.so.6          [.] __strcmp_avx2
>    26.29%  etags    etags              [.] process_file_name
>     2.00%  etags    etags              [.] streq
>     0.96%  etags    etags              [.] strcmp@plt
>     0.32%  etags    etags              [.] readline_internal
>     0.11%  etags    etags              [.] HTML_labels
>     0.08%  etags    [kernel.kallsyms]  [k] syscall_return_via_sysret
>     0.07%  etags    [kernel.kallsyms]  [k] kmem_cache_alloc
>     0.06%  etags    [kernel.kallsyms]  [k] entry_SYSRETQ_unsafe_stack
>     0.05%  etags    [kernel.kallsyms]  [k] perf_adjust_freq_unthr_context
>     0.04%  etags    etags              [.] c_strncasecmp
> 
> So... most of the time is spent in string comparison.
> 
> Here is the nested loop, which if I comment out, makes the parse finish 
> in ~20 seconds, with all the extra files (except *.js), or in 15s when 
> using with new flags.
> 
> diff --git a/lib-src/etags.c b/lib-src/etags.c
> index a822a823a90..331e3ffe816 100644
> --- a/lib-src/etags.c
> +++ b/lib-src/etags.c
> @@ -1697,14 +1697,14 @@ process_file_name (char *file, language *lang)
>         uncompressed_name = file;
>       }
> 
> -  /* If the canonicalized uncompressed name
> -     has already been dealt with, skip it silently. */
> -  for (fdp = fdhead; fdp != NULL; fdp = fdp->next)
> -    {
> -      assert (fdp->infname != NULL);
> -      if (streq (uncompressed_name, fdp->infname))
> -	goto cleanup;
> -    }
> +  /* /\* If the canonicalized uncompressed name */
> +  /*    has already been dealt with, skip it silently. *\/ */
> +  /* for (fdp = fdhead; fdp != NULL; fdp = fdp->next) */
> +  /*   { */
> +  /*     assert (fdp->infname != NULL); */
> +  /*     if (streq (uncompressed_name, fdp->infname)) */
> +  /* 	goto cleanup; */
> +  /*   } */
> 
>     inf = fopen (file, "r" FOPEN_BINARY);
>     if (inf)
> 
> This is basically a "uniqueness" operation using linear search, O(N^2).

Yes, this seems to be a protection against the same file name
mentioned more than once on the command line..

> Is there a hash table we could use?

Something like that should do, yes.

> Or perhaps we would skip the search when the canonicalized name is the 
> same as the original one.

That's not the same as the loop above does, I think.

> > Two aspects that I found trying to understand the long scan times, and
> > I'd like to mention so they don't become forgotten:
> > 
> >   . If there are compressed files in the directory, etags will
> >     uncompress them before it attempts to identify their language.
> >     There are 20 such files in the gecko-dev tree (removing them from
> >     the list of scanned files had only minor effect on the elapsed
> >     time, but it could be different in other cases, especially if
> >     uncompressing them produces very large files).
> 
> I guess someone might ask for flag "--no-decompress", sometime.

Yes, but it's also easy to exclude them via 'find'.

> >   . Some files have their language identified by means other than their
> >     names or extensions: those are the languages that have
> >     "interpreters" defined in etags.c.  Shell scripts is one such case,
> >     but not the only one.  So when etags-regen.el passes only files
> >     with known extensions to etags, it misses those files from TAGS.
> >     As one example, the file js/src/devtools/rootAnalysis/run_complete
> >     in the gecko-dev tree is a Perl script, but has no .pl extension.
> 
> This sounds the same as the "hashbang" files that we mentioned 
> previously. It makes sense for the scan to take longer, of course, 
> proportional to the number of the detected files.

My point was that if someone wants all the Python files, say,
submitting only Python extensions to etags might miss some Python
scripts.