From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.bugs Subject: bug#37321: 27.0.50; Excessive gc in a use case (el-search) Date: Wed, 09 Oct 2019 18:33:12 +0300 Message-ID: <83imoyue6f.fsf@gnu.org> References: <87lfv1pm5x.fsf@web.de> <874l1mc01w.fsf@web.de> <87woeidd4g.fsf@web.de> <733d0142-51ee-55df-de0c-cca7c989b370@cs.ucla.edu> <875zlgu2y8.fsf@web.de> <6d670180-e2ee-030f-ef0e-ad0c5c7a8ef5@cs.ucla.edu> <87tv8zs2r9.fsf@web.de> <83tv8zl0es.fsf@gnu.org> <87sgo3typ1.fsf@web.de> <83o8yry56c.fsf@gnu.org> <87lftvzjmr.fsf@web.de> <83k19fy4p7.fsf@gnu.org> <87pnj7xzhe.fsf@web.de> <83d0f7xwr8.fsf@gnu.org> <8736g3pg2m.fsf@web.de> <83a7abxubl.fsf@gnu.org> <87o8yqynz5.fsf@web.de> Injection-Info: blaine.gmane.org; posting-host="blaine.gmane.org:195.159.176.226"; logging-data="170763"; mail-complaints-to="usenet@blaine.gmane.org" Cc: eggert@cs.ucla.edu, 37321@debbugs.gnu.org To: Michael Heerdegen Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Wed Oct 09 20:54:17 2019 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([209.51.188.17]) by blaine.gmane.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.89) (envelope-from ) id 1iIH6F-000iHi-Jr for geb-bug-gnu-emacs@m.gmane.org; Wed, 09 Oct 2019 20:54:15 +0200 Original-Received: from localhost ([::1]:54246 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iIH6E-0001Mu-19 for geb-bug-gnu-emacs@m.gmane.org; Wed, 09 Oct 2019 14:54:14 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:41580) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iIDyV-00017F-MW for bug-gnu-emacs@gnu.org; Wed, 09 Oct 2019 11:34:04 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1iIDyU-0005Zx-Oi for bug-gnu-emacs@gnu.org; Wed, 09 Oct 2019 11:34:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:45052) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1iIDyU-0005Zt-M2 for bug-gnu-emacs@gnu.org; Wed, 09 Oct 2019 11:34:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1iIDyU-0004Eb-I5 for bug-gnu-emacs@gnu.org; Wed, 09 Oct 2019 11:34:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 09 Oct 2019 15:34:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 37321 X-GNU-PR-Package: emacs Original-Received: via spool by 37321-submit@debbugs.gnu.org id=B37321.157063521916248 (code B ref 37321); Wed, 09 Oct 2019 15:34:02 +0000 Original-Received: (at 37321) by debbugs.gnu.org; 9 Oct 2019 15:33:39 +0000 Original-Received: from localhost ([127.0.0.1]:53873 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1iIDy6-0004Dz-Ip for submit@debbugs.gnu.org; Wed, 09 Oct 2019 11:33:38 -0400 Original-Received: from eggs.gnu.org ([209.51.188.92]:60669) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1iIDy4-0004Dk-8s for 37321@debbugs.gnu.org; Wed, 09 Oct 2019 11:33:37 -0400 Original-Received: from fencepost.gnu.org ([2001:470:142:3::e]:41985) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1iIDxy-0005P2-No; Wed, 09 Oct 2019 11:33:30 -0400 Original-Received: from [176.228.60.248] (port=4768 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1iIDxx-0000Or-U5; Wed, 09 Oct 2019 11:33:30 -0400 In-reply-to: <87o8yqynz5.fsf@web.de> (message from Michael Heerdegen on Wed, 09 Oct 2019 16:47:58 +0200) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 209.51.188.43 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.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.org gmane.emacs.bugs:168742 Archived-At: > From: Michael Heerdegen > Cc: eggert@cs.ucla.edu, 37321@debbugs.gnu.org > Date: Wed, 09 Oct 2019 16:47:58 +0200 > > > AFAIK, the latter can only be done by changing your algorithms to > > produce less garbage. > > I tried to find out what code produces the most garbage. It turned out > that ca. 50% of garbage was generated by code that prevents infinite > recursion when recursing into nested structures. I use hash tables to > collect visited objects, and the hash tables cause the garbage. I tried > to reuse hash tables and clear them after each use, but this makes the > code much slower than what I win from gc. > > But 99,9% of el-searched code isn't cyclic, so the effort is for nothing > most of the time. Is there an efficient way to find out if a given > object is cyclic? The hare/tortoise method we use in data.c? Or maybe you could make your search non-recursive by using an internal queue of requests (like in BFS vs DFS)? (I wrote that based on 5 sec of thought, so maybe it makes no sense at all.)