From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.bugs Subject: bug#73484: 31.0.50; Abolishing etags-regen-file-extensions Date: Thu, 10 Oct 2024 19:28:11 +0300 Message-ID: <86frp32a90.fsf@gnu.org> References: <87tteaznog.fsf@zephyr.silentflame.com> <87jzezzg87.fsf_-_@zephyr.silentflame.com> <37e4b3cd-6363-4f55-9921-92a1182679dc@gutov.dev> <86ttdy50ja.fsf@gnu.org> <75fe4289-da41-454d-ba92-22a92ea7002f@gutov.dev> <86frpe2186.fsf@gnu.org> <8e305b6d-8ca8-4437-990f-183ebc007d18@gutov.dev> <865xqa1ggi.fsf@gnu.org> <86ttdtzoof.fsf@gnu.org> <8d7dc133-9828-4023-821f-e4403f899f81@gutov.dev> <86ttdsxt6x.fsf@gnu.org> <52cb1caa-9e7e-45df-b328-d60948d397f6@gutov.dev> <864j5rxca1.fsf@gnu.org> <87a5fiijy9.fsf@tucano.isti.cnr.it> <86jzelvjh4.fsf@gnu.org> <8b6560a9-e2d6-42ae-ac1d-014700f21804@gutov.dev> <86wmiktzez.fsf@gnu.org> <86ldyzucdd.fsf@gnu.org> <021c625b-adc9-4e19-819c-fe929583e503@gutov.dev> <86ed4ru41x.fsf@gnu.org> <8d86f23e-fdc3-45a5-b3c8-cd4670813e21@gutov.dev> <86ploasq35.fsf@gnu.org> <3e63f532-c6af-4923-880b-01a32cc667ec@gutov.dev> <878quwix4c.fsf@tucano.isti.cnr.it> <86ldyw3467.fsf@gnu.org> <875xq0icqa.fsf@tucano.isti.cnr.it> <86y12w1hjp.fsf@gnu.org> <874j5khw6f.fsf@tucano.isti.cnr.it> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="6617"; mail-complaints-to="usenet@ciao.gmane.io" Cc: dmitry@gutov.dev, 73484@debbugs.gnu.org, spwhitton@spwhitton.name To: Francesco =?UTF-8?Q?Potort=C3=AC?= Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Thu Oct 10 18:29:10 2024 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1syw2H-0001UY-Je for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 10 Oct 2024 18:29:09 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1syw22-0001km-38; Thu, 10 Oct 2024 12:28:54 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1syw20-0001kd-S0 for bug-gnu-emacs@gnu.org; Thu, 10 Oct 2024 12:28:52 -0400 Original-Received: from debbugs.gnu.org ([2001:470:142:5::43]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1syw1y-0005Qs-CI for bug-gnu-emacs@gnu.org; Thu, 10 Oct 2024 12:28:52 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=debbugs.gnu.org; s=debbugs-gnu-org; h=MIME-version:References:In-Reply-To:From:Date:To:Subject; bh=tpG2CqdiUKDgUXI8pHyuSJPhTNJXhvrnQc//MbX3Klo=; b=lg18BuSi25wJX0xNREHuERV1dUilLHhIMgAV93ZEDiDgzzQyb6FK+IQae9o4y07Qnz6JNI2AqjpruH1+dVbvIu1rzwp1Px7i8GqiK3d6URluuAqLAeWQD4TWOE2FtUGlFAmYRSq98lW5ScbPSNrDeqZ+Pyq+9TtXl6Wk/6A7S2zTwMNbuVk+vMwtJwXPyq/Y6hkuzj3bQiyi682JIi4ITHiG+p2e18K5jxEsGzqmKWIPyRiFznaU3Mb/vtUIHr+PKMlzl1b6Qg5Iq9m1thMW50WRqyiTKBWRXEmozWL3m4BRHUa02YIuCwudTsllPJ/Jl02hCd5ySHrjRoEG7nFIpg==; Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1syw29-000379-RL for bug-gnu-emacs@gnu.org; Thu, 10 Oct 2024 12:29:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 10 Oct 2024 16:29:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 73484 X-GNU-PR-Package: emacs Original-Received: via spool by 73484-submit@debbugs.gnu.org id=B73484.172857771711931 (code B ref 73484); Thu, 10 Oct 2024 16:29:01 +0000 Original-Received: (at 73484) by debbugs.gnu.org; 10 Oct 2024 16:28:37 +0000 Original-Received: from localhost ([127.0.0.1]:60311 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1syw1l-00036N-6w for submit@debbugs.gnu.org; Thu, 10 Oct 2024 12:28:37 -0400 Original-Received: from eggs.gnu.org ([209.51.188.92]:60102) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1syw1i-000367-Ek for 73484@debbugs.gnu.org; Thu, 10 Oct 2024 12:28:35 -0400 Original-Received: from fencepost.gnu.org ([2001:470:142:3::e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1syw1Q-0005MG-6I; Thu, 10 Oct 2024 12:28:16 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=tpG2CqdiUKDgUXI8pHyuSJPhTNJXhvrnQc//MbX3Klo=; b=IfwAqZ+We+aMl+kypxtL v1X4DZ/2EkuM5JrAL+hlDyIYpxi8aGmJCkuKBYlWQCGW0mvUayvpKjTdna6zXGmMvO6lIhDO7p81Q MbdbXV15NlhmfvtGGaGuhVJ3yBaIugWJyrCjebF+Y5ci1tO+ocARoI5vPBeYyydgUCtfFailW4EO9 tSpK1iJPm4U/DI+Pk1tb4JXofD/aCKHweEbw6DcxtJdC4qt06q5FlY6YfzuM0ZrX0NUALgS4w+HTg KrZ/eQCbqbhCzNMr1IpNPqO8SHhS6ekqYytduJxOcqvX0v+6qBVL1oFWvdM52bLvxErr6DtBLXCV3 1mMZCuIk1+2PNg==; In-Reply-To: <874j5khw6f.fsf@tucano.isti.cnr.it> (message from Francesco =?UTF-8?Q?Potort=C3=AC?= on Thu, 10 Oct 2024 16:25:28 +0200) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.bugs:293291 Archived-At: > From: Francesco Potort́ > 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 > 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.