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

[Dmitry Gutov <dmitry@gutov.dev>]

On 08/10/2024 16:04, Eli Zaretskii wrote:

>>>> I think that option will be useful, but for better benchmarks and for
>>>> end usability as well, I think we need the N^2 thing fixed as well.
>>>> Maybe before the rest of the changes.
>>>
>>> If this latter part is a precodintion,
>>
>> I think we still could use the new flag, just not switch to it (no
>> extension filtering) by default yet.
> 
> OK, installed on master.  I leave it up to you whether to close the
> bug.

Thank you!

Before closing though, I'd like to look into the performance issue more.

>>> then someone else will have to
>>> work on this.  I have the new option coded and tested (and
>>> documented), but I don't intend to work on redesigning the core etags
>>> algorithms to remove the non-linear behavior, that's a much larger
>>> project which I currently cannot afford, sorry.
>>
>> Do you mind pointing at the places in the code where you already noticed
>> non-linear performance coming from?
> 
> The while-loop near line 2020, for example.

Thanks. This one must be proportional to the number of files such as 
*.y. There are only 2 in our big repo.

> Another one is the for-loop near line 1420, which deals with writing
> into TAGS the entries of files with no tags.

It's not a nested 'for' loop, though (right?), and it's called from 
'main'. That seems to mean it's just O(N) - also fine.

> There may be others, but those are what I saw.  Perhaps it is a good
> idea to profile etags while it scans the files during those 15 min, to
> see where it spends that much time, because I'm not sure even those
> loops can account for that.  It's possible there's something else at
> work here which we don't yet understand.

'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).

Is there a hash table we could use?

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

> 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.

>   . 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.