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

From: Eli Zaretskii <[email-masked]>
Date: Thu, 10 Oct 2024 19:28:11 +0300

> From: Francesco Potortì <[email-masked]>
> Date: Thu, 10 Oct 2024 16:25:28 +0200
> Cc: [email-masked],
> 	[email-masked],
> 	[email-masked]
> 
>   for (fdp = fdhead; fdp != NULL; fdp = fdp->next)
>     {
>       assert (fdp->infname != NULL);
>       if (streq (uncompressed_name, fdp->infname))
> 	goto cleanup;
>     }
> 
> This is a simple O^2 comparison, which is repeated sum(1,N,N-1)=~N^2/2, which for ~375k files means ~70G comparisons.  If you can count the number of times streq is called and 70G is a substantial portion of that number, then we have the culprit.  To check, just remove the above test and see if the running time drops.

Dmitry already made this check, and the run time did drop, see
https://debbugs.gnu.org/cgi/bugreport.cgi?bug=73484#107

> In that case, using a hash rather than a comparison would probably make sense.

Right.

> Alternatively, rather than managing file names in a single loop, do a first loop on all file names to canonicalise them, but without searching for tags (essentially, remove the call to process_file from process_file_name), then uniquify the list of canonicalised file names, then run process_file on them.

I don't think this is possible because command-line options can be
interspersed with file names, and each option affects the processing
of the files whose names follow the option.