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

["Francesco Potortì" <pot@gnu.org>]

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

Yes, sorry, I am travelling and I had missed that email.

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

If I recall correctly, etags depends on libc only.  If that is really the case, it would be nice to create an ad hoc has function without relying on additional libraries.

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

It should be possible as I have outlined above.  When the command line is parsed, process_file_name is called on each file name.  It canonicalises the current name, compares it with the previous file names, adds a new node containing the canonicalised name to a linked list and calls process_file on the file name.  It is possible to remove the last step and instead call process_file in a second loop, but I do not know if it is convenient.

The uniquify solutions would be nonparametric, if I am not wrong.  While the hash solution requires choosing the size of the hash table.

I guess that the hash solution is simpler and equally efficient in the great majority of cases, provided that the size of the hash table is appropriate.  Probably it would be reasonable to start with a 20-bit hash.  And increase that number if in some years it will look reasonable doing so.