From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Pip Cet Newsgroups: gmane.emacs.bugs Subject: bug#29439: Quadratic complexity in sweep_markers Date: Sat, 25 Nov 2017 17:06:07 +0000 Message-ID: NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" X-Trace: blaine.gmane.org 1511629635 26022 195.159.176.226 (25 Nov 2017 17:07:15 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sat, 25 Nov 2017 17:07:15 +0000 (UTC) To: 29439@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Sat Nov 25 18:07:09 2017 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eIdv3-0005yC-Ct for geb-bug-gnu-emacs@m.gmane.org; Sat, 25 Nov 2017 18:07:09 +0100 Original-Received: from localhost ([::1]:53829 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eIdv5-0001Xn-Ci for geb-bug-gnu-emacs@m.gmane.org; Sat, 25 Nov 2017 12:07:11 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:38567) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eIduw-0001Xg-Sy for bug-gnu-emacs@gnu.org; Sat, 25 Nov 2017 12:07:03 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1eIduw-0001vE-1l for bug-gnu-emacs@gnu.org; Sat, 25 Nov 2017 12:07:02 -0500 Original-Received: from debbugs.gnu.org ([208.118.235.43]:49426) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1eIduv-0001v5-U7 for bug-gnu-emacs@gnu.org; Sat, 25 Nov 2017 12:07:01 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1eIduv-0005Rw-N0 for bug-gnu-emacs@gnu.org; Sat, 25 Nov 2017 12:07:01 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Pip Cet Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 25 Nov 2017 17:07:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 29439 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: X-Debbugs-Original-To: bug-gnu-emacs@gnu.org Original-Received: via spool by submit@debbugs.gnu.org id=B.151162961920935 (code B ref -1); Sat, 25 Nov 2017 17:07:01 +0000 Original-Received: (at submit) by debbugs.gnu.org; 25 Nov 2017 17:06:59 +0000 Original-Received: from localhost ([127.0.0.1]:58107 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eIdut-0005Rb-3p for submit@debbugs.gnu.org; Sat, 25 Nov 2017 12:06:59 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:47559) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eIdur-0005RM-FT for submit@debbugs.gnu.org; Sat, 25 Nov 2017 12:06:57 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1eIdul-0001rc-7T for submit@debbugs.gnu.org; Sat, 25 Nov 2017 12:06:52 -0500 Original-Received: from lists.gnu.org ([2001:4830:134:3::11]:41681) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1eIdul-0001rY-4W for submit@debbugs.gnu.org; Sat, 25 Nov 2017 12:06:51 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:38528) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eIduk-0001MK-7x for bug-gnu-emacs@gnu.org; Sat, 25 Nov 2017 12:06:50 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1eIduj-0001rD-Ba for bug-gnu-emacs@gnu.org; Sat, 25 Nov 2017 12:06:50 -0500 Original-Received: from mail-wm0-x232.google.com ([2a00:1450:400c:c09::232]:42786) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1eIduj-0001r5-5h for bug-gnu-emacs@gnu.org; Sat, 25 Nov 2017 12:06:49 -0500 Original-Received: by mail-wm0-x232.google.com with SMTP id 124so10380845wmv.1 for ; Sat, 25 Nov 2017 09:06:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=hzbDOmPFklbrCRZS/jLZ+jKRxCbMbWJnkmkzmREeEzw=; b=kjjHv+DdscGq/4HdI5gtfEnU0erwpzEasJs+lgXwhQ6m5Nf3y/HhbY21HypeVEkGo/ TY6imhU4vx3Fiopo3PsyXab524pss3Ggx166ZtiQD+OEZ6AMCzK9ir9p5n2tL893cdUi kzHyr6f7Sf0amm7S3YyfJGS4KFZmWdPwFv9kAFlLUMy1j9SfS+x6MXLqbY5x1jwX8q0E /cCGAjj11JakQ5XYoTgV7IpkQJnfkztpsukOsEuLVvUF/2ib3joVralWXdG4UpFGRp1f qX5nhUXjrx9KlL6nXsk19XOkNKSaeoAfhVPGym26+8MRLkW48HO8gazCwf1GEl7WIwPB JtLA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=hzbDOmPFklbrCRZS/jLZ+jKRxCbMbWJnkmkzmREeEzw=; b=cJ4D3E1TwegfrlIlQu9nobn38l0yCJBW2YkD3R5D1jfk1wYk0N5UDQCIpZDWJP+WtF GnC87mAxjpToJj6YKB4bUvECyL94VGeVtzP5FV0+qxv3epuVn3WPCX5s9dv7Q5ouBFLH wtwKRO6fifa2VgfA67H+R5dJa45SYNWgUA4dblZFA1U1vCqM9zVJKCm90NzB59Uq9hVT QxhpxTfrAdNSjUPW+LZp+831x3G5Quw7DxORSOAqpgjwLUFU24GkqSeKUuA0FPl+1ydm G3iiYQZ+kIRA3EdBiaxlu4yHPTcN6NXFDOaP/FreIU+oa2q1X02J5+y8OIVsPHIYDbfH RaWA== X-Gm-Message-State: AJaThX5I8+Iufz78lHiRpeFvUf0L7bOWVShQYXHwEQJaC9u1TorkAKTX JXNESf+UMosbuRayn3LtZyCWbP+yErDILzlmYERd0A== X-Google-Smtp-Source: AGs4zMYGLqyyZn51SgY52MGkPfrzo2EdF7cJbJCAHqEAxjKlJ1xKov0Ucg5JIKLGJug5vaIOJXjLm01+KmJoFudFVww= X-Received: by 10.80.165.109 with SMTP id z42mr43407529edb.18.1511629607987; Sat, 25 Nov 2017 09:06:47 -0800 (PST) Original-Received: by 10.80.150.6 with HTTP; Sat, 25 Nov 2017 09:06:07 -0800 (PST) X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x 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: 208.118.235.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:140361 Archived-At: I've sat on this patch for way too long, and I think I previously reported the issue, but I can't find it right now. sweep_markers() calls unchain_marker() for every unmarked marker. unchain_marker() walks the list of all markers in the buffer for every one of them. This causes performance problems during GC, since it's O(n^2) in the number of markers per buffer. I've often noticed this dominating GC time, and in one instance experienced a GC call that lasted for more than an hour. At this point I think this is an actual bug, and one that severely affects at least one user (me). Please consider fixing this.