GNU bug report logs - #73484
31.0.50; Abolishing etags-regen-file-extensions

Previous Next

Full log

View this message in rfc822 format

From: Eli Zaretskii <eliz <at> gnu.org>
To: Francesco Potortì <pot <at> gnu.org>
Cc: dmitry <at> gutov.dev, 73484 <at> debbugs.gnu.org, spwhitton <at> spwhitton.name
Subject: bug#73484: 31.0.50; Abolishing etags-regen-file-extensions
Date: Thu, 10 Oct 2024 19:28:11 +0300

> From: Francesco Potortì <pot <at> gnu.org>
> Date: Thu, 10 Oct 2024 16:25:28 +0200
> Cc: dmitry <at> gutov.dev,
> 	73484 <at> debbugs.gnu.org,
> 	spwhitton <at> spwhitton.name
> 
>   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.

Previous Next

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