Stefan Kangas <stefankangas@HIDDEN>
to control <at> debbugs.gnu.org.
Full text available.Matt Armstrong <matt@HIDDEN>
to control <at> debbugs.gnu.org.
Full text available.Received: (at 58342) by debbugs.gnu.org; 8 Oct 2022 23:08:53 +0000 From debbugs-submit-bounces <at> debbugs.gnu.org Sat Oct 08 19:08:53 2022 Received: from localhost ([127.0.0.1]:41615 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>) id 1ohIw9-0005dw-2Z for submit <at> debbugs.gnu.org; Sat, 08 Oct 2022 19:08:53 -0400 Received: from relay6-d.mail.gandi.net ([217.70.183.198]:52135) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <matt@HIDDEN>) id 1ohIw5-0005de-25 for 58342 <at> debbugs.gnu.org; Sat, 08 Oct 2022 19:08:51 -0400 Received: (Authenticated sender: matt@HIDDEN) by mail.gandi.net (Postfix) with ESMTPSA id 1571BC0005; Sat, 8 Oct 2022 23:08:38 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1665270523; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=sCyeT3E89oQ4lwAA56PdH/uoboTuTwEWLVxmcdCq/Ig=; b=Az9j3fw3HhXcQcogRRaG2LqErptcrHpMf/vRAsABiLPw/ZSw0WeQJg8NYlKTb+Z370LYmV 7FzhSC50ov1i1DPgeuThXEYz5iH4KWADgoPczTaCOD/bJTW7ESCPuf1mf1O35rjulXes0I rbm1WDUBzrbqxXaJwW0gyA1wNKifzLpkwcC0k7LgHHRKcJKdDQVRCPGG/tVWLTZ25alZCD +dwqLBJjZ1hp4Lb2NMdyKq7eE5I0iwJZ0HDYVmEdet2O9Rh3OYEz6buag4pFeEcw4uYPG9 yay1F5MFZrudxijzb2UvQjzNL+7Mucctkjmal50JV/0mYxA1TGHyFtcu5wLkhw== Received: from matt by naz with local (Exim 4.96) (envelope-from <matt@HIDDEN>) id 1ohIvs-0055TH-1S; Sat, 08 Oct 2022 16:08:36 -0700 From: Matt Armstrong <matt@HIDDEN> To: Drew Adams <drew.adams@HIDDEN>, Stefan Monnier <monnier@HIDDEN>, Eli Zaretskii <eliz@HIDDEN> Subject: RE: [External] : bug#58342: 29.0.50; noverlay branch is O(N) for important calls In-Reply-To: <SJ0PR10MB54883A5F0C013B174264DBCAF35E9@HIDDEN> References: <87edvkcz5v.fsf@HIDDEN> <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN> <878rlrfyje.fsf@HIDDEN> <jwvwn9b606v.fsf-monnier+emacs@HIDDEN> <87a6674bg4.fsf@HIDDEN> <83zge6ltto.fsf@HIDDEN> <jwvh70e31tv.fsf-monnier+emacs@HIDDEN> <SJ0PR10MB54883A5F0C013B174264DBCAF35E9@HIDDEN> Date: Sat, 08 Oct 2022 16:08:36 -0700 Message-ID: <878rlp6hhn.fsf@HIDDEN> MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 58342 Cc: "gerd.moellmann@HIDDEN" <gerd.moellmann@HIDDEN>, "mail@HIDDEN" <mail@HIDDEN>, "58342 <at> debbugs.gnu.org" <58342 <at> debbugs.gnu.org> X-BeenThere: debbugs-submit <at> debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: <debbugs-submit.debbugs.gnu.org> List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe> List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/> List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org> List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help> List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe> Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org> X-Spam-Score: -1.7 (-) Drew Adams <drew.adams@HIDDEN> writes: >> For the potential performance problem with next-overlay-change to appear >> you need overlays to overlap, so not something like linum or nhexl-mode. > > Which is why I mentioned zones.el. > > And I don't expect it to be alone in this. > Overlays can be anywhere. For what it is worth, the use cases where this bug applies are likely to be noticeably slow in Emacs today as well.
bug-gnu-emacs@HIDDEN:bug#58342; Package emacs.
Full text available.Received: (at 58342) by debbugs.gnu.org; 8 Oct 2022 17:24:36 +0000 From debbugs-submit-bounces <at> debbugs.gnu.org Sat Oct 08 13:24:36 2022 Received: from localhost ([127.0.0.1]:41386 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>) id 1ohDYx-0003Oi-RW for submit <at> debbugs.gnu.org; Sat, 08 Oct 2022 13:24:36 -0400 Received: from mx0b-00069f02.pphosted.com ([205.220.177.32]:53320) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <drew.adams@HIDDEN>) id 1ohDYu-0003OS-SP for 58342 <at> debbugs.gnu.org; Sat, 08 Oct 2022 13:24:34 -0400 Received: from pps.filterd (m0246632.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.17.1.5/8.17.1.5) with ESMTP id 298FNw1J031588; Sat, 8 Oct 2022 17:24:29 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=from : to : cc : subject : date : message-id : references : in-reply-to : content-type : content-transfer-encoding : mime-version; s=corp-2022-7-12; bh=ihbibfGaBP+UZmJLKihEY+Dr4J14csuKuZaTd1TxPtg=; b=pLEFn+weUYYC5fu/w9App0Yfzlt8AhrHA/1Y+gmB09hx/yV9D9qVaPK3wuOco91kpvGU 2DO2iNM83ksYMFAAyDvnJ5LhaLl6uOlqScOzxdxaDBYBTmcM31tZdJ8dmpWD/1m06nMr OxvJO9nZpL8TXdVtFP+SAc1zU8HSiYp/wZ3THCR8VdJXA/mPzxkERff0D+hPBEFdgRos 2A9sEiBz42e+dmkEbCeabqAXx0bZrg3qAAYA33MTVrltIrDZn0BLPEKQbANaEXFkLiQs +uslrPPgFdsdAnqnoo05laNsEWcpGHyMCBTRj7aP7Opk1YQopK9w8e9Jl8MopACf9/gO rg== Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.appoci.oracle.com [130.35.103.27]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3k30tt0njv-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Sat, 08 Oct 2022 17:24:29 +0000 Received: from pps.filterd (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (8.17.1.5/8.17.1.5) with ESMTP id 298CUqAd022390; Sat, 8 Oct 2022 17:24:28 GMT Received: from nam04-mw2-obe.outbound.protection.outlook.com (mail-mw2nam04lp2172.outbound.protection.outlook.com [104.47.73.172]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 3k2yn8b95y-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Sat, 08 Oct 2022 17:24:28 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=BEWIwjQCnWbwdEfOQiDGPC0gRYk1+sZVDDIacZjLyv4srq+03wTfrM0Ixk71M6MZB58q4OzhUlCGhvxw+ER+x+0Xj+ylvSk+u4lVbRBaFvU7lelXRRigQ4JpSygnNcW1D+DgWkpeNUTB6GyF1giSjFTyws7Sxqk5HwPMJLZSlJBkshqcnyjYDjZ7GHt1YE8zOP7Fotx5XotPtR5vvWfIC3JyglYSAcSiCq3FvhBqSMf3FNKlWxLbWUwIu9hrtENLWj+FEyjwh/hufWyiQ7b0+T97PBP9/GqCZFJA7dvHqbWLXed3KX+5aEFdl6q+PzmfpnrK8Ar31wi3yOKZqHDjOQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=ihbibfGaBP+UZmJLKihEY+Dr4J14csuKuZaTd1TxPtg=; b=odZYUBeoeFm1V23Ho3YK5zQ7CNp2p9YmfFLK8ZU7R1y6tvs35euqOkDs0bgI+Dp9rSf7oAtl1N2fK6CvXwZh1oeN9NQ9mzHoZVdPjQiLQcnVM+X1Zj67bowKYVrVUfJQIMSGWCzLbqoEdLiiuAqlKTi0KI46i8BDolK6VeYZkPlqGSzadlhdIHejcY1t1Cz4wPZpHIQG8lzn4XC9xrND/c/NZw9XC40DeNc0pF7OWv0AEcMZEgkjznn6eV68xlG0VqbnZZO/ame0bKCj1pQWo7ee/vXEZUABqqYkYqt+pkiuLMBg/wsnb9RXHQEzMrIj/DgBYuZudY8hJIqCIhtllw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=oracle.com; dmarc=pass action=none header.from=oracle.com; dkim=pass header.d=oracle.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.onmicrosoft.com; s=selector2-oracle-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=ihbibfGaBP+UZmJLKihEY+Dr4J14csuKuZaTd1TxPtg=; b=Y5Y6BSCoaK5TIQEzyXeDrFl9xzZeS5bguRXU9RDKvP7gzm4ya9Mnyb5KsMUiyXRj7YdYuGIWp60Gq3SdNI3wK0noxBueZlP49UsM5ZwIT9P3l0BFWSyz+Sj181wv9Uim/bmd/2twNl+OrpVwRPudQ4zIJldrDhlrTA6in66HeOI= Received: from SJ0PR10MB5488.namprd10.prod.outlook.com (2603:10b6:a03:37e::19) by BN0PR10MB4918.namprd10.prod.outlook.com (2603:10b6:408:12e::9) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5709.15; Sat, 8 Oct 2022 17:24:25 +0000 Received: from SJ0PR10MB5488.namprd10.prod.outlook.com ([fe80::f319:dced:1a48:779a]) by SJ0PR10MB5488.namprd10.prod.outlook.com ([fe80::f319:dced:1a48:779a%3]) with mapi id 15.20.5709.015; Sat, 8 Oct 2022 17:24:25 +0000 From: Drew Adams <drew.adams@HIDDEN> To: Stefan Monnier <monnier@HIDDEN>, Eli Zaretskii <eliz@HIDDEN> Subject: RE: [External] : bug#58342: 29.0.50; noverlay branch is O(N) for important calls Thread-Topic: [External] : bug#58342: 29.0.50; noverlay branch is O(N) for important calls Thread-Index: AQHY2xdgZuVCzCOCGEWw/OhsTW/NCq4EvxCw Date: Sat, 8 Oct 2022 17:24:25 +0000 Message-ID: <SJ0PR10MB54883A5F0C013B174264DBCAF35E9@HIDDEN> References: <87edvkcz5v.fsf@HIDDEN> <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN> <878rlrfyje.fsf@HIDDEN> <jwvwn9b606v.fsf-monnier+emacs@HIDDEN> <87a6674bg4.fsf@HIDDEN> <83zge6ltto.fsf@HIDDEN> <jwvh70e31tv.fsf-monnier+emacs@HIDDEN> In-Reply-To: <jwvh70e31tv.fsf-monnier+emacs@HIDDEN> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ms-publictraffictype: Email x-ms-traffictypediagnostic: SJ0PR10MB5488:EE_|BN0PR10MB4918:EE_ x-ms-office365-filtering-correlation-id: 533f9483-fcac-47f4-710e-08daa951f2c2 x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: 6EFbL3ZmbBOVh9GjOSjd+U8kCn/lelRc5eM8kOtL/ziGOhKESKKCKrdmD4GbZVwfBAZTi4P4PCHo55FdRaqw9yEVHWHLNnXzcGGHqWAhCLLj1jPC6SF8dnXYg3hfztyGabCdt8BXGfhDYSyIhQHfe+2xs4QgJWyQtYWiLcMI0GKI687173d21awLf4u5F7sSCk1gKAdtuemhmeDS577xnvhbnXc63BO6AY6u3vcrg9IrRnoriNO2IOXVOIFiDbrouH7MgnK5K6RHMSCOHA7L+qSo4viv4PcLpOHb77ECT+MfSbKw75cIcg0/iqORjaoyRWWLx0dBgnURkDExshcyb4Ismw2CBo88eYEmRcOa2yOaXXWuQlCrvwZrUBmhpNJvq7kT4RhaRVla4F2pSTYh8FYSJVbQEBQE3lM72DugVIWEXUNZ9ohX4SzyHIwNi6e1tUGKNSWMcImAad9kTkUWxfUZsWl3KOiCjCnpFbyfPmxiJVZRwvKF8hLDpcZ2ezJMpgSaJKbEdaaDwoFKr4J9vpAc/IVCw3p7RcnGVfhkqNlR9+9rGeUwfSwkngEnAShltoobb0Bp+wqfgtUoVAwy1ncm7xSe/EcJIlrQgxgtyEy4Y5kOsu0EYx3nEMamtZkKjvT36K5TYnUjH81D6bag8v+MVsJY7VNrNC2qohIE7z3I2Fh3T5M3bR35DC/6UFrg0sIG7svTIKNZGSJs58HiOl79PwZUmtbjspifM7KE3i3UeDHVchyHh+WxeuUGC64ubfDIP7UEVNfd1cXsdHipHw== x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:SJ0PR10MB5488.namprd10.prod.outlook.com; PTR:; CAT:NONE; SFS:(13230022)(136003)(346002)(376002)(39860400002)(396003)(366004)(451199015)(4326008)(41300700001)(186003)(38070700005)(66946007)(66556008)(66476007)(66446008)(64756008)(8676002)(76116006)(86362001)(2906002)(52536014)(8936002)(558084003)(33656002)(44832011)(5660300002)(6506007)(7696005)(478600001)(38100700002)(122000001)(71200400001)(55016003)(110136005)(316002)(296002)(54906003)(26005)(9686003); DIR:OUT; SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?us-ascii?Q?Jqw7tg1mkrk7a6EZo8EKSwRd/TYKa4zLvn29FloHJzwE5xjgApCHzTAv9BGq?= =?us-ascii?Q?vFWzAMg2cmcyixVQKzdUDkJMWnrX9H3GOEMfnRc63kp3hO22SBUi00JH4eUT?= =?us-ascii?Q?rb0eEnQkQgIRu3orShpprle5lwClWiMs4R27t0WGictbzNCM3jnG5b20rIeP?= =?us-ascii?Q?6e/PSQhLGiU1Et1S66MctQ0M3kqn9h5rM+FinETpx2dAN8y9SMrfcC5d3BFk?= =?us-ascii?Q?Bok5KkKopUw1fJp673g2Ulh9E2yqSP1km5nSDHltc4zmZUTdIO+hCjeeb+dx?= =?us-ascii?Q?19fKa9TL+f/7LxaQ6amvhDWjv5vWxYOVHsmIN/6PKRJKiqGu1abGOsuvK/Eo?= =?us-ascii?Q?qlN/12zDqZgmw5AFMdOyeVt2CYe45cs61r1aR5hpSutRX8We82CdWEymR4uX?= =?us-ascii?Q?zkL+NuEbpQEQXvmhgKOUyueg8OOaZPJIqXPXGUM9KqdC4R2sehae4Zs/7hyd?= =?us-ascii?Q?LWI9KSxOPsWr+fy5dWe0t5zsbHsLYWmjg1UKY5j6UeALC/Zw71lGR3Cl6Qd6?= =?us-ascii?Q?Lolow3jKyh8cdEnbhXnaYpgzseylBy2h5PeYO8LgZDhgKin/RN0Erga6WIPu?= =?us-ascii?Q?zaMEhMrZrSau90u7Io7zDvC/ajwQhNYEuzM/DcyiPJHiWljO9FyBdfwe6Qoe?= =?us-ascii?Q?mk6Gv7dl2SP2Xyb5OTd1lmxPa/yEKOFg5FHwxwixvzjWLDvZPFHft0dVkyv8?= =?us-ascii?Q?0c8W3byk3GhGzS/tGubeXhJBGYAjvzKGotEQXKUgMV7q2OtNTkyBJB6DFdiZ?= =?us-ascii?Q?PkbWsZ1uXww/PatfQM1MimrQjhnjpfzPn3LSGFYcIvHRSs/2R9BZ9wCL6TvZ?= =?us-ascii?Q?NLUvbwJKGwhtKL0O+YexlLPn9au1GZ8DnFpxdxUHnA/kIh3rau+qYSCl8tvM?= =?us-ascii?Q?vxHaUktItBxyKKo4r6SfluxGsAzWCPQprvt9Cp3+bT/zonl2zBAou65kG9pX?= =?us-ascii?Q?NstBEB+XUbHtRLSmq/qUszg19g4D7H4Qq3X7Okk/nvB98Z8V6WJAIvEDliZe?= =?us-ascii?Q?0YkMQe0q+fRt9GVxA/Kb0rgUoH1hMx6BJ+m76UZvp4yxlGa/vQIOCnrfPndE?= =?us-ascii?Q?vNd/VqcOPT5xm8i7UMpzrarOVO81NeXIroB2le0cj0o/ak+S8y85/u25C0Dl?= =?us-ascii?Q?ZXpMIhPTIivCoYxJLzvX+KKoYdVtMsRyYWFXmMs0WuQsgOKSzGt5hhCLpbpd?= =?us-ascii?Q?rRsdRqx/CwbAcJkqOOsxVv4TcShFlGmxR8R5jGT3/27NlYhx2Z5G6wnVcc/D?= =?us-ascii?Q?00qdKoZYaaxBaR2MHXbq0czPrWEhIWfIleBIYzDHcjZT22yNgjCdGrXLX+YA?= =?us-ascii?Q?OctAnaIM1bHH/XGpexf3yRaT2JPPv2YQ3W2A+sL1VxWYsb90Afz/skJ1rqeg?= =?us-ascii?Q?FcCkONr1fHENgOC/6peuHyXBZ3GlxCOyPMgUnoQ9Cfr6sZUgOZCcqDPwiXIR?= =?us-ascii?Q?Hp2rqmtTTS2j9oEwQeMAiCKq5/GDYYyd9Kn+pZrolC2K2ve7sFsLMcY3h6zr?= =?us-ascii?Q?u/jefV+DrOcQNxWZ0T3q8sg1M+LCrB1eyjk7Gp6yWvH4Cqf/GT50FSff9FP4?= =?us-ascii?Q?wESRWJim5jCoYrY9uKl18go4eQ0+KgIs8X1lsaNR?= Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: oracle.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: SJ0PR10MB5488.namprd10.prod.outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 533f9483-fcac-47f4-710e-08daa951f2c2 X-MS-Exchange-CrossTenant-originalarrivaltime: 08 Oct 2022 17:24:25.6151 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-CrossTenant-userprincipalname: ZVtmb90fYI9DYsjpN8Cq8rrwojNYbL0SLHf/wpHtoDLauNFJI+0FN5zvl/N6cmTO+oLmlaaOg1+ehjBs2+rvLA== X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN0PR10MB4918 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.205,Aquarius:18.0.895,Hydra:6.0.528,FMLib:17.11.122.1 definitions=2022-10-07_04,2022-10-07_01,2022-06-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxlogscore=752 bulkscore=0 malwarescore=0 suspectscore=0 mlxscore=0 adultscore=0 phishscore=0 spamscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2209130000 definitions=main-2210080112 X-Proofpoint-GUID: OVUFSRPbaRCeNzCotUNVXz5jL2USFGlA X-Proofpoint-ORIG-GUID: OVUFSRPbaRCeNzCotUNVXz5jL2USFGlA X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 58342 Cc: "gerd.moellmann@HIDDEN" <gerd.moellmann@HIDDEN>, "matt@HIDDEN" <matt@HIDDEN>, "mail@HIDDEN" <mail@HIDDEN>, "58342 <at> debbugs.gnu.org" <58342 <at> debbugs.gnu.org> X-BeenThere: debbugs-submit <at> debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: <debbugs-submit.debbugs.gnu.org> List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe> List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/> List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org> List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help> List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe> Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org> X-Spam-Score: -1.7 (-) > For the potential performance problem with next-overlay-change to appear > you need overlays to overlap, so not something like linum or nhexl-mode. Which is why I mentioned zones.el. And I don't expect it to be alone in this. Overlays can be anywhere.
bug-gnu-emacs@HIDDEN:bug#58342; Package emacs.
Full text available.
Received: (at submit) by debbugs.gnu.org; 8 Oct 2022 13:08:29 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sat Oct 08 09:08:29 2022
Received: from localhost ([127.0.0.1]:38588 helo=debbugs.gnu.org)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
id 1oh9Z6-0001wf-RV
for submit <at> debbugs.gnu.org; Sat, 08 Oct 2022 09:08:29 -0400
Received: from lists.gnu.org ([209.51.188.17]:55800)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <monnier@HIDDEN>) id 1oh9Z2-0001wV-ND
for submit <at> debbugs.gnu.org; Sat, 08 Oct 2022 09:08:27 -0400
Received: from eggs.gnu.org ([2001:470:142:3::10]:46800)
by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <monnier@HIDDEN>)
id 1oh9Yw-00036o-W8
for bug-gnu-emacs@HIDDEN; Sat, 08 Oct 2022 09:08:23 -0400
Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:21986)
by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <monnier@HIDDEN>)
id 1oh9Yp-0004TJ-0D; Sat, 08 Oct 2022 09:08:14 -0400
Received: from pmg1.iro.umontreal.ca (localhost.localdomain [127.0.0.1])
by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id A910D100189;
Sat, 8 Oct 2022 09:08:04 -0400 (EDT)
Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1])
by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 31784100084;
Sat, 8 Oct 2022 09:08:03 -0400 (EDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca;
s=mail; t=1665234483;
bh=j77v3UBLt+ah2/HoiGyfPnLkzl0O/7/ZbG4sShHrOy8=;
h=From:To:Cc:Subject:In-Reply-To:References:Date:From;
b=XZEK223L9MwroEBZWBGn6N/vUa6d6ZuSTZmOmzKEzTGKKaru/Btkp3RWdC2wCGizz
HbHbk4hzL3GAZ+66HznMdiWLWm/Q/0c+KM/OSuKInJ2hATIcQziGRCU/WCwpR9PBg3
4reDyn+DZSlqhnqP3FsmVTJZCAChgKVaINd3PqAR5cF5xgcBo+3hsgNxWtb/Y16bEU
Ti+DC0+/RbL+LET56tZ3vVjw50TbvVprhKS5YEITAAfw9CnkZJPubNvlBk1v/g6jlK
NCQevpGJ6LfzzKYJB0eocUmwqqUT1EZl8YpAXBLPJYJYsXZmFkszCiVW+h4WX9432G
a/H6iDhXUVUmg==
Received: from pastel (65-110-220-202.cpe.pppoe.ca [65.110.220.202])
by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id E70281203FE;
Sat, 8 Oct 2022 09:08:02 -0400 (EDT)
From: Stefan Monnier <monnier@HIDDEN>
To: Eli Zaretskii <eliz@HIDDEN>
Subject: Re: 29.0.50; noverlay branch is O(N) for important calls
In-Reply-To: <83zge6ltto.fsf@HIDDEN> (Eli Zaretskii's message of "Sat, 08 Oct
2022 09:20:51 +0300")
Message-ID: <jwvh70e31tv.fsf-monnier+emacs@HIDDEN>
References: <87edvkcz5v.fsf@HIDDEN> <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN>
<878rlrfyje.fsf@HIDDEN> <jwvwn9b606v.fsf-monnier+emacs@HIDDEN>
<87a6674bg4.fsf@HIDDEN> <83zge6ltto.fsf@HIDDEN>
Date: Sat, 08 Oct 2022 09:08:02 -0400
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-SPAM-INFO: Spam detection results: 0
ALL_TRUSTED -1 Passed through trusted hosts only via SMTP
AWL -0.065 Adjusted score from AWL reputation of From: address
BAYES_00 -1.9 Bayes spam probability is 0 to 1%
DKIM_SIGNED 0.1 Message has a DKIM or DK signature,
not necessarily valid
DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature
DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's
domain
X-SPAM-LEVEL:
Received-SPF: pass client-ip=132.204.25.50;
envelope-from=monnier@HIDDEN; helo=mailscanner.iro.umontreal.ca
X-Spam_score_int: -42
X-Spam_score: -4.3
X-Spam_bar: ----
X-Spam_report: (-4.3 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1,
DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3,
SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no
X-Spam_action: no action
X-Spam-Score: -1.3 (-)
X-Debbugs-Envelope-To: submit
Cc: gerd.moellmann@HIDDEN, Matt Armstrong <matt@HIDDEN>,
bug-gnu-emacs@HIDDEN, mail@HIDDEN
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -2.3 (--)
>> Does anybody know of an Emacs package that uses a large number of
>> overlays that span large amounts of the buffer in complex ways?
>
> What are those "complex ways" you are talking about?
>
> In general, Isearch can potentially produce thousands of overlays,
> especially if you do that in a buffer where lines are truncated. But
> I don't know if that's what you are looking for.
>
> linum.el is another potential example: it produces an overlay for each
> line.
For the potential performance problem with next-overlay-change to appear
you need overlays to overlap, so not something like linum or nhexl-mode.
Maybe a package which places an overlay over every pair of matched
parentheses in a Lisp buffer?
Stefan
bug-gnu-emacs@HIDDEN:bug#58342; Package emacs.
Full text available.Received: (at submit) by debbugs.gnu.org; 8 Oct 2022 06:20:55 +0000 From debbugs-submit-bounces <at> debbugs.gnu.org Sat Oct 08 02:20:55 2022 Received: from localhost ([127.0.0.1]:38063 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>) id 1oh3Ch-000610-4X for submit <at> debbugs.gnu.org; Sat, 08 Oct 2022 02:20:55 -0400 Received: from lists.gnu.org ([209.51.188.17]:45436) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <eliz@HIDDEN>) id 1oh3Ce-00060s-Jt for submit <at> debbugs.gnu.org; Sat, 08 Oct 2022 02:20:53 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:50996) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from <eliz@HIDDEN>) id 1oh3Ce-0007z9-F0 for bug-gnu-emacs@HIDDEN; Sat, 08 Oct 2022 02:20:52 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:59278) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from <eliz@HIDDEN>) id 1oh3Cc-000351-Lx; Sat, 08 Oct 2022 02:20:50 -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=M+zMPHqx0D4K78mCus+Ri1uS0ldPQ1yU0ho2n+/YLgg=; b=GIiQj6NMkvSD4UiHpfea lzacyDqvwYqqSlHH2/7XgvnDvjKqWIJkm0U/KoVYsWAh14yGAl5ho4rPrpMHd6KxdxrJcTpHAqqeS 4DnUdn36qCk5pmQro6xQF17aWzjI6tU2SYspGUf7+HIf4MGmcQSJcQnOtSsfve0HUSVtUNHZSW9G0 VA8khZMgm7nwgxyIcUKVhGgcJz7L9gDzL0UJPLEG7mbKK28MnjEWStzYJ5ZV+6W57dNMVgc/KEmi7 O2PaFL2AYzceBqEEu3qTWlaYEv3anIf1+hgSbsQ04gFo7eHA8lBjwWOOBRGfJov3QdKo04+AnLe3G t3XNkoIS2iF76w==; Received: from [87.69.77.57] (port=3584 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from <eliz@HIDDEN>) id 1oh3Cc-0004LB-5L; Sat, 08 Oct 2022 02:20:50 -0400 Date: Sat, 08 Oct 2022 09:20:51 +0300 Message-Id: <83zge6ltto.fsf@HIDDEN> From: Eli Zaretskii <eliz@HIDDEN> To: Matt Armstrong <matt@HIDDEN> In-Reply-To: <87a6674bg4.fsf@HIDDEN> (message from Matt Armstrong on Fri, 07 Oct 2022 13:37:31 -0700) Subject: Re: 29.0.50; noverlay branch is O(N) for important calls References: <87edvkcz5v.fsf@HIDDEN> <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN> <878rlrfyje.fsf@HIDDEN> <jwvwn9b606v.fsf-monnier+emacs@HIDDEN> <87a6674bg4.fsf@HIDDEN> MIME-version: 1.0 Content-type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: submit Cc: gerd.moellmann@HIDDEN, bug-gnu-emacs@HIDDEN, mail@HIDDEN, monnier@HIDDEN X-BeenThere: debbugs-submit <at> debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: <debbugs-submit.debbugs.gnu.org> List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe> List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/> List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org> List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help> List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe> Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org> X-Spam-Score: -3.3 (---) > From: Matt Armstrong <matt@HIDDEN> > Cc: bug-gnu-emacs@HIDDEN, Andreas Politz <mail@HIDDEN>, Gerd > Möllmann <gerd.moellmann@HIDDEN>, Eli Zaretskii > <eliz@HIDDEN> > Date: Fri, 07 Oct 2022 13:37:31 -0700 > > Does anybody know of an Emacs package that uses a large number of > overlays that span large amounts of the buffer in complex ways? What are those "complex ways" you are talking about? In general, Isearch can potentially produce thousands of overlays, especially if you do that in a buffer where lines are truncated. But I don't know if that's what you are looking for. linum.el is another potential example: it produces an overlay for each line.
bug-gnu-emacs@HIDDEN:bug#58342; Package emacs.
Full text available.Received: (at 58342) by debbugs.gnu.org; 8 Oct 2022 00:27:52 +0000 From debbugs-submit-bounces <at> debbugs.gnu.org Fri Oct 07 20:27:51 2022 Received: from localhost ([127.0.0.1]:37673 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>) id 1ogxh1-000575-Es for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 20:27:51 -0400 Received: from mx0b-00069f02.pphosted.com ([205.220.177.32]:23658) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <drew.adams@HIDDEN>) id 1ogxgx-00056v-Uk for 58342 <at> debbugs.gnu.org; Fri, 07 Oct 2022 20:27:50 -0400 Received: from pps.filterd (m0246631.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.17.1.5/8.17.1.5) with ESMTP id 297MOBea030013; Sat, 8 Oct 2022 00:27:43 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=from : to : cc : subject : date : message-id : references : in-reply-to : content-type : content-transfer-encoding : mime-version; s=corp-2022-7-12; bh=XKk13VkoD5wa3NWEuTvy/KjB3RauDmCk4Kv0WgWw75Q=; b=mUdGLTlOJJMdc8JPx4JsZXAAfQeqz+tLhAIBw6UaCT/T2v6INr/GVFmH76/4jzDwb2AC 0pLUbBMhCQ/lDHlLdyUHRYRkrDujCaENBb0AYX53z8G98EZ7ruM0GXtQvm3vwZtO4beW ZEjI/KApnRRm7gzuY2DYU8MOfU9OWUFLesDSWrzUdRZatUfxcsf+PG0ekufcG9CpEknd HKo5KsTa0xPuCZG2VfaCD8fJeM+X+rIbDNKFhbpjIHLnDVIG3hT+UXdHMaHwOpKKbtL3 qG8jXOJM6IZ4/A4SNjX98v7htMCI7gnmEz5L+X5iAoph3rjSR3uzRdzoAqaC8zVkaIQw wQ== Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.appoci.oracle.com [130.35.100.223]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3jxcb30j0v-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Sat, 08 Oct 2022 00:27:43 +0000 Received: from pps.filterd (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (8.17.1.5/8.17.1.5) with ESMTP id 297M05xw002756; Sat, 8 Oct 2022 00:27:43 GMT Received: from nam10-mw2-obe.outbound.protection.outlook.com (mail-mw2nam10lp2105.outbound.protection.outlook.com [104.47.55.105]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 3jxc0dmss6-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Sat, 08 Oct 2022 00:27:43 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=ZdwU7azwjRx4MlK48NPJfWUB9H3r5AnWLWjhWqQBNlGQTcPgJmjqAROSk/5VSHXF6A1o0XDSxJuexSpcrWS9bf8VGYRjFavxqmLC+S6AoXokxB64Ka9T87nm2WTwXnfIhf7lddV7HJhPExR6Xsr6kuit+8pgnT4Mgi72+7zGMZH8TvdFEioPHR9Z/HNTv8sf0hO7gme4hEpvWx1JSQ6PXhFl6dVtOB1kgzbduB8CUN29KhHDlnt4mmvI6eQ57RITYDbPvWe84kgu0xbqXgGqYD6DC+AeIJePwUScBZDJMxGzeGzNKBYf2e79i9cSruAElPfYwx6csvTtu7ykSSty2w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=XKk13VkoD5wa3NWEuTvy/KjB3RauDmCk4Kv0WgWw75Q=; b=VrgdYN1GfmGuvmiCu1F/7Q8Y9ji9LKW8FAXjQvkCuRdXyK02j7iqSf9fPRvPKyr9gie6dkMU9r333QZo16gVJEe/iP/r3xWbn9HfV9bcmtM2cni7GQtETxeamNYUbzzGYHqQ1SbqRDvwmOtcbDv3W0padD1v1RR/C0wmPuHlTP0UvPdxb7Lrmb0RPig2vfGdaPiJMqc6ayFeIEDrnH5TaAxyJ/WRFyDLLMd/jG8LvSj0CZWFYz5L7BpMgo+1XLn7CYU+0KfwthIwekxGg1isCjfKZDWiFg7UhDN3N6E4LovB6cvO5+rqkrG3PO5uhuZJr1+lzIhqZRB4FHJQZ2Klfw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=oracle.com; dmarc=pass action=none header.from=oracle.com; dkim=pass header.d=oracle.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.onmicrosoft.com; s=selector2-oracle-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=XKk13VkoD5wa3NWEuTvy/KjB3RauDmCk4Kv0WgWw75Q=; b=mrJumK6TxjXpHitLB7ebr2F2L3Fd+xFWNP8o9nea0Qm1o+kbtV0tAoAvAkk9k7aCI77xgEqMVBbfQNf47jN12jDvRm0j76ZLZbcDqeqxkfDeSrdyFWE6dNrsG3FV9qvmoqtzEGIP5WueTYFNyJA4ntv1/pu1JTJqDaGF9vAF2jI= Received: from SJ0PR10MB5488.namprd10.prod.outlook.com (2603:10b6:a03:37e::19) by CH0PR10MB5081.namprd10.prod.outlook.com (2603:10b6:610:c2::13) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5709.15; Sat, 8 Oct 2022 00:27:40 +0000 Received: from SJ0PR10MB5488.namprd10.prod.outlook.com ([fe80::f319:dced:1a48:779a]) by SJ0PR10MB5488.namprd10.prod.outlook.com ([fe80::f319:dced:1a48:779a%4]) with mapi id 15.20.5676.036; Sat, 8 Oct 2022 00:27:40 +0000 From: Drew Adams <drew.adams@HIDDEN> To: Drew Adams <drew.adams@HIDDEN>, Matt Armstrong <matt@HIDDEN>, Stefan Monnier <monnier@HIDDEN> Subject: RE: [External] : bug#58342: 29.0.50; noverlay branch is O(N) for important calls Thread-Topic: [External] : bug#58342: 29.0.50; noverlay branch is O(N) for important calls Thread-Index: AQHY2oy2ajNuIoooHk2L42gej7CEv64Dba2ggAA1MJA= Date: Sat, 8 Oct 2022 00:27:40 +0000 Message-ID: <SJ0PR10MB5488D22C8185C8185883543CF35E9@HIDDEN> References: <87edvkcz5v.fsf@HIDDEN> <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN> <878rlrfyje.fsf@HIDDEN> <jwvwn9b606v.fsf-monnier+emacs@HIDDEN> <87a6674bg4.fsf@HIDDEN> <SJ0PR10MB5488492F4E8E60819364AB2FF35F9@HIDDEN> In-Reply-To: <SJ0PR10MB5488492F4E8E60819364AB2FF35F9@HIDDEN> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ms-publictraffictype: Email x-ms-traffictypediagnostic: SJ0PR10MB5488:EE_|CH0PR10MB5081:EE_ x-ms-office365-filtering-correlation-id: 0285264b-2bf9-458a-69fe-08daa8c3e8ce x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: l64uJ99EspLtMZRRYahwKc4HJRcziLry8AncymSzKm4LKxv5tTwp/u1tQ6DQfJZGOC41r+YPISHsjXm/W5al5zOWlFyhYqrNqn7Z62geTNIhAITzDL6LMIsSPz4oek/eLzALJNmDJar5I2fBR8RraI0gwJVjVEVqhRtbRR/YDdO1JHBuPS2r7vMlpisCBLKFFSecCWFrUisYrwoXupSox5dHsfSpRiWE0mO9TG5j+lUhClp6HqVVTYpF32Vwp1VxMOYMTuXGZkMeq1bb/KxtxVJX4KnjZhqs4sGpvOrTko2L2rKUs3ksyJTZb+D+goTeDYm8j+9osZCBQQ+xaYc13gR/2jMg7YO3lQrbHE8yrakPZIhqC3RCrDIw7BYXVmJo2mVB9JpWRxg73+CYMjeFzNbpAzETS023Z6JGJL/aiy8cznuRJwLkObw6zPntJ7AfXFnxKCH0ZXKmRXDC32ibThRgZTL4Eem0ERJu2+3zYhTjjXTF+9JTXaqkfLCCaumb53NWyw9kuyALLAJKMN4Y6lbwieGHFwkO5HmLNOQ9rcgcVaIUBEO/d/eNV/oUyUV8pM1CO6mbk2KucWbfPcBjOa67Gcc/Cuno6SJkDag9O7eIrFhwmVEnkLBBGgop2p/zHcEh5oG3rLufCRUrAwd9SwfL9je3l5q1Cu5GD5skbDR9i3uVQDTIFoX9XHo//0bjWCWvBM7mD+PYLdf1PEZfcHDYczP9p1BVz0BxELBDFDGf7R8dUPil7Mb1j3h0FgFbNZBO+FGUh/Cy2p4WkkdNLQ== x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:SJ0PR10MB5488.namprd10.prod.outlook.com; PTR:; CAT:NONE; SFS:(13230022)(366004)(39860400002)(396003)(136003)(346002)(376002)(451199015)(66899015)(8936002)(8676002)(5660300002)(2906002)(33656002)(41300700001)(4326008)(52536014)(54906003)(110136005)(66476007)(76116006)(86362001)(66446008)(66946007)(316002)(66556008)(44832011)(64756008)(122000001)(38070700005)(478600001)(71200400001)(55016003)(7696005)(6506007)(9686003)(26005)(38100700002)(186003)(83380400001); DIR:OUT; SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?us-ascii?Q?Jqq7EvrbpNHRKtgRyGavHf6WfsichlPUeOJ0w9r1yK5uU1cCvf99YaIMJXkc?= =?us-ascii?Q?ThJjqJdz5UXgJ2Qke23QNUjpp3qHeEzEgTHWuYuvXdJPY5QHjfRp8AhtFsiS?= =?us-ascii?Q?3LQH4rhYShznv0sypqLI10oyuHSM+oPszsETUts4OgKywqWt+MviQk6Uaqyc?= =?us-ascii?Q?YLXWnyaGf72AlHfQUt5zlCPRpC/6WNV8qvWdObJHo3Pz9yeB3H+4jNb5cwCX?= =?us-ascii?Q?95E9k6aLDXCgJwY2YS4Xj4z+478xolV3s5tvLs4j9RsrI81zIX4OO8YIapxN?= =?us-ascii?Q?08XII1cIbllbKZYGgO0pDnu7Zm1lqnqd2ndfVPVLtTRcCEKwzUH2HDpq5Sp6?= =?us-ascii?Q?JLlrYTX+xf1baNoBq2Kmsed6mRdYD0KXGx6wfimRploFoHvS5hJclYLuohRq?= =?us-ascii?Q?GOS5/Z84v4jgeZk2KO/MxU+QsT1jyn/uw6ua3/XoVewA9/i/dZcZVR9/5Tse?= =?us-ascii?Q?ImOiyF8D0JBF/xoMDAxf0X5VDAeYnaJYyiKovoumTOi6tgV416TOIjBaudav?= =?us-ascii?Q?Hd2h7JjyvttABb3e5vRfW6/8ydyXSXu0pzy6DtW8lZf/z26BEB7PniB4my8Z?= =?us-ascii?Q?Qn814+FOZono9U3MjISAxaIBTEoMpw2DAvfoyzRvAl06gtVXd/DZip+nkh5O?= =?us-ascii?Q?HEzeasdVsmnEbRcCsPeY379zieM5ETVV3RVrJFiYBlGnQjIt7cm6GhQxomCr?= =?us-ascii?Q?rQHVeNyA5moXPOBWugbFHEa8TFzkcgRN/YE02Azo2zY3/ppToLfkl/FC7JrI?= =?us-ascii?Q?cB8JO5EW7pz72ZZq2JRqfyVwJjC4LONFOCFe6ICndubezV9fn7nbqlt0OOKV?= =?us-ascii?Q?r+/r13kWBkJJ+AlYqAtDqzz6obWuutY76/AXEvGai1e7W/ahTLG98d87FosV?= =?us-ascii?Q?6LYgKRBjEhUcL2w0RIMogBjnNaaqRrHpT3wfNtKuUmYoaMEnl9uabXTp2NO+?= =?us-ascii?Q?Hicea6C21EQmRL4jNCVmYfxtmS2H6IqswktEizqFYgKieZGFalhOjB34c87H?= =?us-ascii?Q?oAITqG/+WqYuEbcrj0bXnL+QukfG+9yCBGkQVpwnctzkzb0avosPrjtG4u+H?= =?us-ascii?Q?3yVhLR0NZLdlILSgaKjRokwrJRmdFKX4wWwGskcyHAH1NMyAtdqfgIpEelfT?= =?us-ascii?Q?Hq4C6trA36KdYtTaCgW3yUJ0YXLjVDCHnXGACFFJISQhurZeZf/tGzCmO8sI?= =?us-ascii?Q?cBLfRL1IspsjO5zAuJ9uw/slS7rFn/a5zmC3BCVuz1tiCFgjEtIhsqi48Ab2?= =?us-ascii?Q?Hd/qSvWOaZdPjEx9hsSQfibFSZNuO8IbWdSWgC/wAsYqnNLWtcf4EcNQXvmL?= =?us-ascii?Q?69QS0y1F0iNPu/krbZzqmwW7g8ezs1x9wkuODFxeFy9JJRJM5TiZURHy6EZp?= =?us-ascii?Q?IuVLGFRAIGzgc+XYgvmJJIvpyJq//2ABajFeC60/U08NOF4aCZbyE8BkC16e?= =?us-ascii?Q?vMYGa8G1pqMcDMr3/l+O3N5i9PGApEUt5E6fHvG4lNme6aYkKuFkqT62PPQI?= =?us-ascii?Q?pA4XinH/tykuyeUDfOGYADMJ/TA+CvgpzQUi8yDXOmEmcs1IFc0z8Xur/abl?= =?us-ascii?Q?UAgUYPvKlCSWKHMpa5isJcmoqZDX0ywNkxwQkyLp?= Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: oracle.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: SJ0PR10MB5488.namprd10.prod.outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 0285264b-2bf9-458a-69fe-08daa8c3e8ce X-MS-Exchange-CrossTenant-originalarrivaltime: 08 Oct 2022 00:27:40.4121 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-CrossTenant-userprincipalname: hboqKHr6MFBxugMdPu9Mx9fUA0b+29qyxw3h6YROCAw+EeMIClpaWiUO8cNHUu9IeJMq6afDIeHwL2m1j6hyDg== X-MS-Exchange-Transport-CrossTenantHeadersStamped: CH0PR10MB5081 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.205,Aquarius:18.0.895,Hydra:6.0.528,FMLib:17.11.122.1 definitions=2022-10-07_04,2022-10-07_01,2022-06-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 phishscore=0 bulkscore=0 mlxscore=0 malwarescore=0 adultscore=0 spamscore=0 mlxlogscore=999 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2209130000 definitions=main-2210080000 X-Proofpoint-GUID: PGmZP9DF2BxzTpNhn8vx_BEEntnznxKj X-Proofpoint-ORIG-GUID: PGmZP9DF2BxzTpNhn8vx_BEEntnznxKj X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 58342 Cc: "gerd.moellmann@HIDDEN" <gerd.moellmann@HIDDEN>, "eliz@HIDDEN" <eliz@HIDDEN>, "mail@HIDDEN" <mail@HIDDEN>, "58342 <at> debbugs.gnu.org" <58342 <at> debbugs.gnu.org> X-BeenThere: debbugs-submit <at> debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: <debbugs-submit.debbugs.gnu.org> List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe> List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/> List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org> List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help> List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe> Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org> X-Spam-Score: -1.7 (-) > > Does anybody know of an Emacs package that uses a large number of > > overlays that span large amounts of the buffer in complex ways? >=20 > Sure. zones.el does (especially the version > I use, which I haven't yet exposed externally). >=20 > The point of zones.el is to manipulate arbitrary > sets of buffer zones, which can be implemented > as overlays (as one possibility). >=20 > They can overlap in any way, as the library is > a utility that you can use in any way. And you > can sort zones, unite/coalesce them, etc. It's > not at all unusual to deal with many overlapping > zones, e.g., overlays. >=20 > Dunno what the "noverlay" branch is. I haven't > seen any description of it or its purpose, > despite the many, many emails here and in > emacs-devel with "noverlay" in the Subject line. > As a result, those many messages get only an > uninformed glance from me. >=20 > But if the "noverlay" branch is supposed to deal > with overlays _in general_ in some way, then I'd > think that the case of many overlapping overlays > wouldn't necessarily be rare. Why would it be? >=20 > You can use an overlay for anything: store any > information on for buffer zone. An overlay is > just two buffer positions plus a set of > properties - any properties. _Super_ general. As an example just one use of arbitrarily positioned overlays, you can save narrowings to a set of zones (which can be overlays), and later reactivate any of them on demand. Narrowings can have any limits, of course. The overlays in a zones set can overlap in arbitrary ways, like Venn diagrams.
bug-gnu-emacs@HIDDEN:bug#58342; Package emacs.
Full text available.Received: (at 58342) by debbugs.gnu.org; 7 Oct 2022 21:58:57 +0000 From debbugs-submit-bounces <at> debbugs.gnu.org Fri Oct 07 17:58:57 2022 Received: from localhost ([127.0.0.1]:37609 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>) id 1ogvMv-0007mM-Iz for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 17:58:57 -0400 Received: from mail-wm1-f53.google.com ([209.85.128.53]:43962) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <raaahh@HIDDEN>) id 1ogvMt-0007m9-Nc for 58342 <at> debbugs.gnu.org; Fri, 07 Oct 2022 17:58:56 -0400 Received: by mail-wm1-f53.google.com with SMTP id r3-20020a05600c35c300b003b4b5f6c6bdso3286613wmq.2 for <58342 <at> debbugs.gnu.org>; Fri, 07 Oct 2022 14:58:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :sender:from:to:cc:subject:date:message-id:reply-to; bh=bZU2HPYkYYtL4WH+92bzI97i8NaMme+2UcVoBdjih9o=; b=kalwVkH1wwgbw17ttnENkUEoCQ7KUwO0ioNSh3dkv7yHNYxS3s8yTor8ng+7iK/jfy m6+u6XzdlD0J7tn+s0xP3j1BEPGex2mTDpRdLKgGcpqf29iA5TkgNh1BYRnGbsFYX0ri FJC4VjINuEb2uvq0Gs4LQVroZR9IyBir7wLWfa4fnUxauTZdNft2RLveZqcorzhLom7I TlVY72Ic3w8PCPUR5RQifTeIJf/Ql+O9wra95KFEaEeFv9ewIGdQ9x2yTnN0+Gv854bj sa6v9rbbi2XC85Df47ryUPGkVtleKWJylIBDzRhgwUGqaqCmikvIlE8+80sLyJGWQq86 XNmw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :sender:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=bZU2HPYkYYtL4WH+92bzI97i8NaMme+2UcVoBdjih9o=; b=vkz1QkQMWIohGA1CHsHkl28oiVVzTM/oFNNJatDWz/zjKue2o1CTvNtIqFTuQb/SVM 43mi0hXXcTZnuZIiH0Jj2GC0yhjYP9cw1zlDkQ0IENOHj2sVMbTuWnGqJTbzJPaUzLxv 4lRcVrAHCelkmN3s5SblQ3Txig/KfiLkR22ODx0DC1tC79nclAlwx/YlEHzCBAp3LEdU VmOgwQmFaSGTuL1sG4hAD/tnoZETYi5FO3n1LbC5VBAJD1Zgsy696xA3hrnVoBNwwy95 dSqdsR34H/+UKxZ8OeteNPoXXb5eLszBh1ut1udTFy0FECgESV+DhBtUHqyqIE1dlSUm RnCQ== X-Gm-Message-State: ACrzQf2cKPy0FM808LVRjaNuSyxuwTuVDRY9iS93BVWtAdiVE/j2I5MF +MQ3lbMgJaYNLKu6DdEy/2M= X-Google-Smtp-Source: AMsMyM540Geli3gAekdFsZV/1RP/6I0WMdELzRyU27YMnOvWKbBEalHV9ImCiFkQEiwUVXa3S0PPgw== X-Received: by 2002:a05:600c:3b8f:b0:3b4:9cdc:dbd8 with SMTP id n15-20020a05600c3b8f00b003b49cdcdbd8mr4567417wms.148.1665179929615; Fri, 07 Oct 2022 14:58:49 -0700 (PDT) Received: from [192.168.0.6] ([46.251.119.176]) by smtp.googlemail.com with ESMTPSA id az34-20020a05600c602200b003b4de550e34sm3252071wmb.40.2022.10.07.14.58.48 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 07 Oct 2022 14:58:49 -0700 (PDT) Message-ID: <ae54f718-d7fc-79a2-58e2-8f54caccc04f@HIDDEN> Date: Sat, 8 Oct 2022 00:58:47 +0300 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.2.2 Subject: Re: bug#58342: 29.0.50; noverlay branch is O(N) for important calls Content-Language: en-US To: Matt Armstrong <matt@HIDDEN>, Stefan Monnier <monnier@HIDDEN> References: <87edvkcz5v.fsf@HIDDEN> <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN> <878rlrfyje.fsf@HIDDEN> <jwvwn9b606v.fsf-monnier+emacs@HIDDEN> <87a6674bg4.fsf@HIDDEN> From: Dmitry Gutov <dgutov@HIDDEN> In-Reply-To: <87a6674bg4.fsf@HIDDEN> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -1.3 (-) X-Debbugs-Envelope-To: 58342 Cc: gerd.moellmann@HIDDEN, eliz@HIDDEN, mail@HIDDEN, 58342 <at> debbugs.gnu.org X-BeenThere: debbugs-submit <at> debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: <debbugs-submit.debbugs.gnu.org> List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe> List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/> List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org> List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help> List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe> Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org> X-Spam-Score: -2.3 (--) On 07.10.2022 23:37, Matt Armstrong wrote: > Does anybody know of an Emacs package that uses a large number of > overlays that span large amounts of the buffer in complex ways? If none > exist, maybe we can just close this bug! mmm-mode, perhaps. But that depends on what you mean by "large" and "complex". The overlay nesting scheme is usually straightforward.
bug-gnu-emacs@HIDDEN:bug#58342; Package emacs.
Full text available.Received: (at 58342) by debbugs.gnu.org; 7 Oct 2022 21:22:28 +0000 From debbugs-submit-bounces <at> debbugs.gnu.org Fri Oct 07 17:22:28 2022 Received: from localhost ([127.0.0.1]:37593 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>) id 1oguna-0006rs-Av for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 17:22:28 -0400 Received: from mx0b-00069f02.pphosted.com ([205.220.177.32]:34058) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <drew.adams@HIDDEN>) id 1ogunU-0006re-64 for 58342 <at> debbugs.gnu.org; Fri, 07 Oct 2022 17:22:24 -0400 Received: from pps.filterd (m0246632.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.17.1.5/8.17.1.5) with ESMTP id 297LFVZO031958; Fri, 7 Oct 2022 21:22:17 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=from : to : cc : subject : date : message-id : references : in-reply-to : content-type : content-transfer-encoding : mime-version; s=corp-2022-7-12; bh=GuryI7W3r2G2gIzqzrq3Dcp5N+D2kmNqclZR9/N575U=; b=EeVfgOkCDGeWBhZcOapvPhNjOjZopT2PCLoMsaoZbfx/qeMhsuiqwVlaG4bPa+CWecaH 7Wpt0EOp6uCiZHpOaFGtTLivK42ygCBBNJCCkYHrmoAGYgXjwttduaJduWL2ikmJ0/jy 0nwZVDkoJ4v4JRn1xChe9BgeDxg4JjHL2trAixWw0tAU6aOOIsLu0qc30nKzaexduRsl bg/GcUxyu4cE+5SaHS6hMimTx2IuT5+HJhX2IaT0Vp1OuQcHiWCL9RM8Jqesx8nd2d4S IfF7cdECSf9EmkHWURGY00xPpbsT0vUyXG0QSTThMFBGU+IZcc6fN6yV/HlsS7Ap/NbF uA== Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.appoci.oracle.com [130.35.100.223]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3jxd5tr6eh-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 07 Oct 2022 21:22:17 +0000 Received: from pps.filterd (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (8.17.1.5/8.17.1.5) with ESMTP id 297InP5j002629; Fri, 7 Oct 2022 21:22:16 GMT Received: from nam10-bn7-obe.outbound.protection.outlook.com (mail-bn7nam10lp2107.outbound.protection.outlook.com [104.47.70.107]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 3jxc0dhrwd-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 07 Oct 2022 21:22:16 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=dUFBy7ubs9zTwA+hUUKVHeA0LU3gEnnLd7PEzjslCtVp+LxkJ9mNypv7WXFQ2QIJWH0gXnffzEOMCw/HzQf1OPo7F+//YN6+ZauwNGODApbKG1dd856CjMEh07eAbC3Woqhm+L5WUbmQWZItCGH8RjBrNVKcRUKQdeTc3UoUcr+F4uLzBxaxF5hSe0dtbF96LzZzqB2BScHfb3ZlKmsZiy8fGB/Ia9Yf/vngl9Ci/aodWi92P4J2XQcFFsU+mfVk2CBK6TMKT64mJQ+e5iyUQCBnB0Kxuu8fcLopr+cHw9KHBLQxSGaiTSNkhkzY3N7NpElROv3O9se4ElbilFtHAg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=GuryI7W3r2G2gIzqzrq3Dcp5N+D2kmNqclZR9/N575U=; b=V3mCizI6nAjaeCP0sfSlXxJWONozGxx4FjvvsEEAYHooplsPr0xFCM8XcFoxG6qZIuueU9PXOs6TE2eg+qr7EEDbPK5FbD8VgVea993eZUjy5ObhETwtleU2c2+kEcCuj/jK8JRlSCNbCBfXLjOa7EeLYE4IAU1u5JganHzpL3y3zjpht8hN1/N3H3RS0EIZnmtcD0uB7i583dfK//YZcFC85s8gEIt8SuGiAHuQQqNDIlfzH0A8uIPm2zf6f8nwiuN3nIAOojiLOBS4Y3BUVb/qx2G2drVeLPVRNlPnkjT94fkafSoQXtfl+FmTjqAY59/A9LKEALyKUcHnNOUfTQ== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=oracle.com; dmarc=pass action=none header.from=oracle.com; dkim=pass header.d=oracle.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.onmicrosoft.com; s=selector2-oracle-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=GuryI7W3r2G2gIzqzrq3Dcp5N+D2kmNqclZR9/N575U=; b=w0jlMlr7mB0kCNk/CVFpghAzAbmyJDeOuyQYw+skHLtNhbLgNioSRHhWvVH5cRsAQp80qdTDgK/sPHQ8TKVjANAdpIBcYwoDoLh3HTLeImwowJxKkaI4g5Dwcq/xUheCDYdg94kmJ3qU0Mj7eSxokQHkFI40SR2E+LkDkwect44= Received: from SJ0PR10MB5488.namprd10.prod.outlook.com (2603:10b6:a03:37e::19) by DS7PR10MB5039.namprd10.prod.outlook.com (2603:10b6:5:3a6::16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5709.15; Fri, 7 Oct 2022 21:22:14 +0000 Received: from SJ0PR10MB5488.namprd10.prod.outlook.com ([fe80::f319:dced:1a48:779a]) by SJ0PR10MB5488.namprd10.prod.outlook.com ([fe80::f319:dced:1a48:779a%4]) with mapi id 15.20.5676.036; Fri, 7 Oct 2022 21:22:14 +0000 From: Drew Adams <drew.adams@HIDDEN> To: Matt Armstrong <matt@HIDDEN>, Stefan Monnier <monnier@HIDDEN> Subject: RE: [External] : bug#58342: 29.0.50; noverlay branch is O(N) for important calls Thread-Topic: [External] : bug#58342: 29.0.50; noverlay branch is O(N) for important calls Thread-Index: AQHY2oy2ajNuIoooHk2L42gej7CEv64Dba2g Date: Fri, 7 Oct 2022 21:22:14 +0000 Message-ID: <SJ0PR10MB5488492F4E8E60819364AB2FF35F9@HIDDEN> References: <87edvkcz5v.fsf@HIDDEN> <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN> <878rlrfyje.fsf@HIDDEN> <jwvwn9b606v.fsf-monnier+emacs@HIDDEN> <87a6674bg4.fsf@HIDDEN> In-Reply-To: <87a6674bg4.fsf@HIDDEN> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ms-publictraffictype: Email x-ms-traffictypediagnostic: SJ0PR10MB5488:EE_|DS7PR10MB5039:EE_ x-ms-office365-filtering-correlation-id: e8eb1d97-1785-4bd3-4367-08daa8aa0160 x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: fdWpUn1Gy3mIm1jbx3UOUjMbeDvzun9AtJCnZMXBzZ/EFiM0YYw68KGPnvYGtKU6XJ5Lg3hTK4scF6ecur43um6po7ukhozDHSobCWq3IfsSyg+Nav8jg2C4Lh/MdniG3nsCgXjidRiRqEiv9IhAPDeauJVSpQSYZ4BXFrVNXGCCQvymwJy8TYriiMr5V4GkJoyOtsDGHNzPsEQvJjNiInB19J5ECvn8QWMBD9kwcuojYqphRWBD77I/hrgxzILJiGlqqMAdqLMWgkrmBJLTJrvbo/0VobkEu93lf9YH4L63hHQhKmu4QJ4ekj/qVtkVASOjs9NbtZ7BLCt+RetSf1soPG1tQ0YohUi90fT41plM+n61lLBkZ6gN+KbiL6allZMha4Rm22CKWz+9VJtPH7KuBNjwDvtGWsqflD2SF0YCQDJxa4bJyMPc9bR63MIyzacHvb3vqFHpglv1Ba2R6HUmFkYrefXgpEZm3RNRjEcnpaXgAcOCLIqxJXNCKI5sbYFTHIEi1JDVV/sgiHerMjYR24niHPAILqocreZXlGZvyeI8i7CSjTPt3pwhXwxqF9VzctdPVjfGW88/FsYPunSmPUsHv/WhzaXJV7Zi0Q3rmFdPn0HRuET7xYqviwYtXpcvSIQMaSWPJqiymrIcqh5UB+m39XxzTv+f1UWn066kWF9DZHDnkWzrShjCIoTJ0QtrMnLwUhOoDzQes9D1Xl0OMFRbnWUw0/6IOHGAuZhBoKQvolpfROxBtot07SZOJmzG7srwTeVY67WzRW1g+A== x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:SJ0PR10MB5488.namprd10.prod.outlook.com; PTR:; CAT:NONE; SFS:(13230022)(366004)(376002)(346002)(136003)(396003)(39860400002)(451199015)(38070700005)(33656002)(122000001)(38100700002)(66899015)(86362001)(83380400001)(2906002)(44832011)(55016003)(6506007)(478600001)(9686003)(26005)(7696005)(186003)(52536014)(316002)(54906003)(8676002)(110136005)(71200400001)(5660300002)(76116006)(4326008)(66946007)(66476007)(66446008)(66556008)(8936002)(64756008)(41300700001); DIR:OUT; SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?us-ascii?Q?1rnX6rg3i+SD5c0WgLh7MbGPSER5nrDxyp3HHVujmWcg0ucW5PbsTJNFzAU9?= =?us-ascii?Q?lfbqQ3mh7zdhsO0s8Yi5R8k+kgJ5HK5Qni3wkq2zNb9ZkYq/ph7PlpwwsLqx?= =?us-ascii?Q?nO7/uujtoKrmRA0N1tgAjJBnauqO13iQuxoKKIbCd0P4x8RMp5nBtmFdpgJs?= =?us-ascii?Q?XSEhRYUwmlHImMluO3iOFL/u44zaxDlT7f15aG+UZV8FHay1uxnvaAVCzwuV?= =?us-ascii?Q?XxkGwjVzPAIgRWjrUL3UgZkMeE4zyw5pOktkuXClYu0/8W4KDNF2qJYB+TWX?= =?us-ascii?Q?qidaII3VBBLMuviKkaXCvrAzVzQllblwjZFvJ+gdj9PaEXPzTlbkB+76bmrM?= =?us-ascii?Q?P4VfD7P+GO1+43ZX3qtMkhn0uHkLfbNXsaYsvkcwJE+1jWs8kaVg4labA+zf?= =?us-ascii?Q?Q7sVtoGs7QIhhoA7LIZJEjR3RCHEH+fle9Q2VbrlI2t7QNsnU3bGTKu/jf+b?= =?us-ascii?Q?WSocgqfUMF5yJKzcjDKduJqBYmYmt2ml8D7sY39dGSZFptm5V3dv32CbUEaC?= =?us-ascii?Q?YVsHq+a3fbsPyqqBck/PLW2YC8Oh2Qea7WTDNRpU803GGvt/r/X2ZBgfuuQ/?= =?us-ascii?Q?YCOG9LhI7YcljUPh7MIMa67ffuJSAg4cwDoLjZTxtO4jOTbyekp+mw0vpFY8?= =?us-ascii?Q?yDvGC1xh+IELw9DwzBQs7rQAoqPQM5sQ2YiK9X5g0ob0G139dP1GoL5CQOZy?= =?us-ascii?Q?of0yZRlgLi8XRQIndNeL6xWSjzovnz57o1oD4IrUSrEcV3DEznfAqM8oCHGN?= =?us-ascii?Q?62HegoyuTocjFaYI2PrM94B4tOiWoly3oivUXg2LZWAsqFuezoS8Wrpt6ig4?= =?us-ascii?Q?6K0hC68jyomiJELDod2VGxErfQlATaTxJuAtzhfn71yOD1rJM1EqXrFg0ay2?= =?us-ascii?Q?pTTQuGNxLVA34MKOMhwtxgR+eedrFqjcBLIt2Vw8TgdUnynhKepk8x2+e6ik?= =?us-ascii?Q?WfXqe+6egIXNuhgWNgGDmIJMuQMqggQUWX3oaQVPddiyCYzJ6XnpFV+zgGpf?= =?us-ascii?Q?QUx1ZxqVee3+i0J+rkjvelrKOBCz3SFn22cMxb4Aw8pyZtpme+xd1JwHRs5g?= =?us-ascii?Q?y8Pl4o65HDQmgMg2Kv/0v334En8lHqTeaO/9eSh2mVnVRX3OfKaKXTTLORQG?= =?us-ascii?Q?G8UF1p4lA8H0++v16bKe603jF22hAMOsmjQzxSql9U+wtEvLLcR7wuWVBqlh?= =?us-ascii?Q?E7ytPOroOXXc5FWj6QmzScRNS+in3fLy+TtZ2mmgYMKOSdyy8QwsALzze8hb?= =?us-ascii?Q?3aZ7/nEq2ECqCUy46FQRFZBDfVIp9cWwQ9PH629uQjyy+/LrMycvlBuPGqCi?= =?us-ascii?Q?ukWvecRcwautyTro2yZkNqVYv5Ju51ntrnMJzBHBz0q7qW9DI3Z1W7VZDx8y?= =?us-ascii?Q?/Bh7hDZGmnl7Qf5mDVCl2QpsdMAZ4nyJ5cGkvI/dkwLuFNoIFS4q06XCXALa?= =?us-ascii?Q?qI0OyBU8wgFMzW6Yz9fVTnYLwNXq6eFzC8HqYksnWWFpHZwrkftXn81+rlsx?= =?us-ascii?Q?5VQuafg1EjgYA5ccdFliFMK+dkV0ohq2qwFAVZ3jSxOKgMkzp9KTMSwv7Zif?= =?us-ascii?Q?kTRWiMHybEdqt4vK26b+TdkGJ5y3nfh1fInEixvv?= Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: oracle.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: SJ0PR10MB5488.namprd10.prod.outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: e8eb1d97-1785-4bd3-4367-08daa8aa0160 X-MS-Exchange-CrossTenant-originalarrivaltime: 07 Oct 2022 21:22:14.6714 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-CrossTenant-userprincipalname: 3lMVLNqspSNvnzaVl0rt4NQ1KGKOXL9y2WqWSlHxhkPZGduEf0j7dVG4Qcg9KRlvQLjfHVJELJJQocpNmOG19w== X-MS-Exchange-Transport-CrossTenantHeadersStamped: DS7PR10MB5039 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.205,Aquarius:18.0.895,Hydra:6.0.528,FMLib:17.11.122.1 definitions=2022-10-07_04,2022-10-07_01,2022-06-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 phishscore=0 bulkscore=0 mlxscore=0 malwarescore=0 adultscore=0 spamscore=0 mlxlogscore=999 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2209130000 definitions=main-2210070127 X-Proofpoint-ORIG-GUID: SmDVXyj4w1VHQtxK3fv5CquCn2sxMvlp X-Proofpoint-GUID: SmDVXyj4w1VHQtxK3fv5CquCn2sxMvlp X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 58342 Cc: "gerd.moellmann@HIDDEN" <gerd.moellmann@HIDDEN>, "eliz@HIDDEN" <eliz@HIDDEN>, "mail@HIDDEN" <mail@HIDDEN>, "58342 <at> debbugs.gnu.org" <58342 <at> debbugs.gnu.org> X-BeenThere: debbugs-submit <at> debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: <debbugs-submit.debbugs.gnu.org> List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe> List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/> List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org> List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help> List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe> Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org> X-Spam-Score: -1.7 (-) > Does anybody know of an Emacs package that uses a large number of > overlays that span large amounts of the buffer in complex ways? Sure. zones.el does (especially the version I use, which I haven't yet exposed externally). The point of zones.el is to manipulate arbitrary sets of buffer zones, which can be implemented as overlays (as one possibility). They can overlap in any way, as the library is a utility that you can use in any way. And you can sort zones, unite/coalesce them, etc. It's not at all unusual to deal with many overlapping zones, e.g., overlays. Dunno what the "noverlay" branch is. I haven't seen any description of it or its purpose, despite the many, many emails here and in emacs-devel with "noverlay" in the Subject line. As a result, those many messages get only an uninformed glance from me. But if the "noverlay" branch is supposed to deal with overlays _in general_ in some way, then I'd think that the case of many overlapping overlays wouldn't necessarily be rare. Why would it be? You can use an overlay for anything: store any information on for buffer zone. An overlay is just two buffer positions plus a set of properties - any properties. _Super_ general.
bug-gnu-emacs@HIDDEN:bug#58342; Package emacs.
Full text available.Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 20:37:47 +0000 From debbugs-submit-bounces <at> debbugs.gnu.org Fri Oct 07 16:37:47 2022 Received: from localhost ([127.0.0.1]:37505 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>) id 1ogu6M-0003Uk-Q0 for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 16:37:47 -0400 Received: from lists.gnu.org ([209.51.188.17]:35384) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <matt@HIDDEN>) id 1ogu6L-0003Ud-3e for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 16:37:45 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:60588) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from <matt@HIDDEN>) id 1ogu6K-00052x-HL for bug-gnu-emacs@HIDDEN; Fri, 07 Oct 2022 16:37:44 -0400 Received: from relay3-d.mail.gandi.net ([217.70.183.195]:47097) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from <matt@HIDDEN>) id 1ogu6I-0000x9-5X; Fri, 07 Oct 2022 16:37:44 -0400 Received: (Authenticated sender: matt@HIDDEN) by mail.gandi.net (Postfix) with ESMTPSA id B06E160002; Fri, 7 Oct 2022 20:37:34 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1665175058; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=M3DFf9sMi1pjXNfSN2QBShtD3D4KWfAg6V9lhbHeygY=; b=EDk3s0nx7sMpgi925J5q8aw+486ycJsynDzj0tmnCmughOy5gwrF6ADyAQl9YPmaX1bBOD esdZiTdomxSm8N3nKjTtxBgVSKWWoa6ibus3YCzWTS/GCU6ZcH4dMmu1ikB2SC1CiCbZhY 4DHLpwLnjzOMAWEejHUaDLIrZ2gcLszQS0R4ZrQ29avLfxARa5aPe1M9MgIiQz0kxCs2JQ cpkfrvlILAj7bm0+wON0AeY3GMOWhethJkLyBHD595aCw7bNRvS2pzWpL3E3kVS5/l6yYK I8Cg29qdoAUAHqqBXBuYL1EcpFhF77jmXVeBuMjepckAitNYbmxAdrklYOk20Q== Received: from matt by naz with local (Exim 4.96) (envelope-from <matt@HIDDEN>) id 1ogu67-004Vep-31; Fri, 07 Oct 2022 13:37:31 -0700 From: Matt Armstrong <matt@HIDDEN> To: Stefan Monnier <monnier@HIDDEN> Subject: Re: 29.0.50; noverlay branch is O(N) for important calls In-Reply-To: <jwvwn9b606v.fsf-monnier+emacs@HIDDEN> References: <87edvkcz5v.fsf@HIDDEN> <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN> <878rlrfyje.fsf@HIDDEN> <jwvwn9b606v.fsf-monnier+emacs@HIDDEN> Date: Fri, 07 Oct 2022 13:37:31 -0700 Message-ID: <87a6674bg4.fsf@HIDDEN> MIME-Version: 1.0 Content-Type: text/plain Received-SPF: pass client-ip=217.70.183.195; envelope-from=matt@HIDDEN; helo=relay3-d.mail.gandi.net X-Spam_score_int: -27 X-Spam_score: -2.8 X-Spam_bar: -- X-Spam_report: (-2.8 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Spam-Score: -1.6 (-) X-Debbugs-Envelope-To: submit Cc: Gerd =?utf-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>, bug-gnu-emacs@HIDDEN, Andreas Politz <mail@HIDDEN>, Eli Zaretskii <eliz@HIDDEN> X-BeenThere: debbugs-submit <at> debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: <debbugs-submit.debbugs.gnu.org> List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe> List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/> List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org> List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help> List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe> Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org> X-Spam-Score: -2.6 (--) Stefan Monnier <monnier@HIDDEN> writes: >> This is why I keep coming back to the idea of storing both BEG and END >> positions in ordered collections at all times. > > But that comes at a non-negligible constant-factor cost :-( > > [ Maybe a "cheapish" (memory-wise) way to make it work is to add two > fields `prev` and `next` used to link the nodes into a doubly-linked > list ordered by `end` positions. We should be able to find a given > position in this list efficiently (i.e. not linear time) by relying on > the `limit` field, thus making it unnecessary to maintain a second > *tree*. ] First, we need benchmark that demonstrates a problem. You've asked for this. I've simply pointed out that there is no algorithmic protection from bad performance, but I haven't yet come up with a practical example. I understand your concerns about the costs of maintaining a separate tree, but I think this design brainstorm is getting ahead of things. I would advocate for such a "dual tree" design only if it made sense on some demonstrated engineering basis. Goals are always balancing simple code, simple design, and efficiency. Opinions can differ, but they're difficult to settle out without something concrete to talk about. Does anybody know of an Emacs package that uses a large number of overlays that span large amounts of the buffer in complex ways? If none exist, maybe we can just close this bug!
bug-gnu-emacs@HIDDEN:bug#58342; Package emacs.
Full text available.
Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 17:11:59 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Fri Oct 07 13:11:59 2022
Received: from localhost ([127.0.0.1]:37304 helo=debbugs.gnu.org)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
id 1ogqtC-00009G-RW
for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 13:11:59 -0400
Received: from lists.gnu.org ([209.51.188.17]:38602)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <monnier@HIDDEN>) id 1ogqtA-000098-9x
for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 13:11:58 -0400
Received: from eggs.gnu.org ([2001:470:142:3::10]:38154)
by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <monnier@HIDDEN>)
id 1ogqt5-0004xk-Nh
for bug-gnu-emacs@HIDDEN; Fri, 07 Oct 2022 13:11:56 -0400
Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:4863)
by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <monnier@HIDDEN>)
id 1ogqsz-0007AT-4Q; Fri, 07 Oct 2022 13:11:50 -0400
Received: from pmg1.iro.umontreal.ca (localhost.localdomain [127.0.0.1])
by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id CBE3E100142;
Fri, 7 Oct 2022 13:11:41 -0400 (EDT)
Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1])
by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id B86FB1000E7;
Fri, 7 Oct 2022 13:11:39 -0400 (EDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca;
s=mail; t=1665162699;
bh=UJH5/jsIPSWn6HQghOzveGd3ScGiWzIXQja53alX8X4=;
h=From:To:Cc:Subject:In-Reply-To:References:Date:From;
b=bUFnQKQttxThSbD/qeyvh7lKmg3h93OzvplKLlFvT5RfPEu2xjWMR26Bs+NhQwNpb
L0Qp3A4eCdXJRllZK2hLMdJe2SriBLrFe8ks9nlGYZySZi+O1r/JcaK3IEhJgvcCPU
UfSu0qTqy+P+k9r5CDxQvIMhilWXIXlzeHLKFZxtoE1qt7b1IBCm4I2+6W8xllIM+1
mRDE6nvdgBG8tdVtyJDniZetoQF4+x/3gRJ0prkUJWVr5J8G5XQbbQI0yf/pVnYYZO
fcbwgIasO9b/kEMQy0jOVgHn8sxSGcpZIcAqLHMyS9Asja2B305HNIvvpCSSO2xpWk
/myHSz3t/d5/A==
Received: from pastel (65-110-220-202.cpe.pppoe.ca [65.110.220.202])
by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 83FEA120636;
Fri, 7 Oct 2022 13:11:39 -0400 (EDT)
From: Stefan Monnier <monnier@HIDDEN>
To: Matt Armstrong <matt@HIDDEN>
Subject: Re: 29.0.50; noverlay branch is O(N) for important calls
In-Reply-To: <878rlrfyje.fsf@HIDDEN> (Matt Armstrong's message of "Fri, 07
Oct 2022 08:23:17 -0700")
Message-ID: <jwvwn9b606v.fsf-monnier+emacs@HIDDEN>
References: <87edvkcz5v.fsf@HIDDEN> <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN>
<878rlrfyje.fsf@HIDDEN>
Date: Fri, 07 Oct 2022 13:11:38 -0400
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-SPAM-INFO: Spam detection results: 0
ALL_TRUSTED -1 Passed through trusted hosts only via SMTP
AWL -0.064 Adjusted score from AWL reputation of From: address
BAYES_00 -1.9 Bayes spam probability is 0 to 1%
DKIM_SIGNED 0.1 Message has a DKIM or DK signature,
not necessarily valid
DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature
DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's
domain
KAM_SHORT 0.001 Use of a URL Shortener for very short URL
X-SPAM-LEVEL:
Received-SPF: pass client-ip=132.204.25.50;
envelope-from=monnier@HIDDEN; helo=mailscanner.iro.umontreal.ca
X-Spam_score_int: -42
X-Spam_score: -4.3
X-Spam_bar: ----
X-Spam_report: (-4.3 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1,
DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3,
SPF_HELO_NONE=0.001, T_SPF_TEMPERROR=0.01 autolearn=ham autolearn_force=no
X-Spam_action: no action
X-Spam-Score: -1.3 (-)
X-Debbugs-Envelope-To: submit
Cc: Gerd =?windows-1252?Q?M=F6llmann?= <gerd.moellmann@HIDDEN>,
bug-gnu-emacs@HIDDEN, Andreas Politz <mail@HIDDEN>,
Eli Zaretskii <eliz@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -2.3 (--)
> I would like a note or FIXME in code noting the potentially slow
> algorithm (patch sent), because it is currently well hidden behind a
> generator loop.
I'll merge it soon, yes, thanks.
> I am working on polishing off
> https://git.sr.ht/~matta/emacs-overlay-perftests. Good news is that
> redisplay is faster on the noverlay branch for the "realistic" case of
> overlaping not overlapping eachother in pathalogical ways.
Excellent, thanks.
>> [ Site note: `previous-overlay-change` is probably not very important in
>> practice, but `next-overlay-change` OTOH is indeed important because
>> it's used during redisplay. So if someone comes up with a trick to
>> speed up only one direction, it should be good enough. ]
>>
>> Maybe one way to improve the behavior is to accept the worst-case
>> bound but to try and avoid paying it over-and-over each time the
>> redisplay needs the "next change". IOW instead of a
>> `next_overlay_change` function which takes a POS and returns the next
>> change after that, the xdisp.c might benefit from having a
>> `next_overlay_changes` *generator* which takes a starting POS and
>> returns an iterator which will return (each time it's called) the
>> successive positions where there's an overlay change.
>>
>> Hopefully this way we'd pay the O(N) cost once per redisplayed window
>> rather than once per "small step in the rendering engine" (i.e. per
>> next_overlay_change).
> At the moment I can't think of a reasonable way to implement such a
> generator efficiently without, effectively, computing a temporary
> ordered collection over overlay END positions.
Indeed, the generator needs to build such a side table (I was thinking
of something like a heap datastructure). I don't see it as a problem.
> This is why I keep coming back to the idea of storing both BEG and END
> positions in ordered collections at all times.
But that comes at a non-negligible constant-factor cost :-(
[ Maybe a "cheapish" (memory-wise) way to make it work is to add two
fields `prev` and `next` used to link the nodes into a doubly-linked
list ordered by `end` positions. We should be able to find a given
position in this list efficiently (i.e. not linear time) by relying on
the `limit` field, thus making it unnecessary to maintain a second
*tree*. ]
>> Another way to do basically the same is to let next_overlay_change
>> fill up a cache of change-positions which would be flushed whenever
>> some overlay is modified/added/removed (or the current_buffer is
>> different from last time). That might be easier to use with the
>> current code since xdisp.c wouldn't need to pass around this iterator
>> (which could require significant reworks).
>
> ...possibly, but the problem with caching is the time spent filling the
> cache back up. I like the idea of storing both BEG and END positions in
> an ordered collection because in that case the (potentially slow)
> recomputation need not occur with every key press. If we're not worried
> about that kind per-key-press of delay, then I argue there is no need
> for a cache either.
I'm definitely not worried about performing one such recomputation per
key press. The problem of the O(N) issue you point out might come up
when we have to repeat that O(N) for every buffer position where there's
an "overlay change", but if it's done once per redisplay (or once per
window being redisplayed), it should be lost in the noise.
Stefan
bug-gnu-emacs@HIDDEN:bug#58342; Package emacs.
Full text available.Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 15:23:32 +0000 From debbugs-submit-bounces <at> debbugs.gnu.org Fri Oct 07 11:23:32 2022 Received: from localhost ([127.0.0.1]:37201 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>) id 1ogpCG-0005q9-8D for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 11:23:32 -0400 Received: from lists.gnu.org ([209.51.188.17]:33190) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <matt@HIDDEN>) id 1ogpCE-0005q0-T8 for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 11:23:31 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:48538) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from <matt@HIDDEN>) id 1ogpCE-00038p-LO for bug-gnu-emacs@HIDDEN; Fri, 07 Oct 2022 11:23:30 -0400 Received: from relay1-d.mail.gandi.net ([2001:4b98:dc4:8::221]:41385) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from <matt@HIDDEN>) id 1ogpCB-0005ro-CB; Fri, 07 Oct 2022 11:23:30 -0400 Received: (Authenticated sender: matt@HIDDEN) by mail.gandi.net (Postfix) with ESMTPSA id 5C83924000A; Fri, 7 Oct 2022 15:23:20 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1665156202; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=38Kty76zu4mzjoxviGedY+bjAwkq9QkUktSpekdqDX4=; b=Gy+xZRFee3m0YhNEybbL6XYAZcijzrPnY5CiWffDP2KD6vm3EYBrWTq0zXo6m7UqM2qcKj vP+RcbuHuUzPRbGQZF16id8sS4F5eKSG95lZElr4GPrUOrlQNcL1tDbxJQlQmeef26TFdV uwP5tF08OxtnT/0pgiIu6WNkZY2U5uHjLHmF1WJvYY5MblLuJym3Wec3zIya0hTLkBam7p WczqyDLy/6D+kuIiWxdE6Vz976nl5R+YdwmVl08l1/cBfzSe7WHC+S7wRnG//j4fqojKYx yiWtLcx99p5KbLjAdDcT3IiCX+p2qX7X6LSdbMf3bsmw/3VgHyGLe+aYbec4Qw== Received: from matt by naz with local (Exim 4.96) (envelope-from <matt@HIDDEN>) id 1ogpC2-004JKS-1r; Fri, 07 Oct 2022 08:23:18 -0700 From: Matt Armstrong <matt@HIDDEN> To: Stefan Monnier <monnier@HIDDEN> Subject: Re: 29.0.50; noverlay branch is O(N) for important calls In-Reply-To: <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN> References: <87edvkcz5v.fsf@HIDDEN> <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN> Date: Fri, 07 Oct 2022 08:23:17 -0700 Message-ID: <878rlrfyje.fsf@HIDDEN> MIME-Version: 1.0 Content-Type: text/plain Received-SPF: pass client-ip=2001:4b98:dc4:8::221; envelope-from=matt@HIDDEN; helo=relay1-d.mail.gandi.net X-Spam_score_int: -27 X-Spam_score: -2.8 X-Spam_bar: -- X-Spam_report: (-2.8 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Spam-Score: -1.6 (-) X-Debbugs-Envelope-To: submit Cc: Gerd =?utf-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>, bug-gnu-emacs@HIDDEN, Andreas Politz <mail@HIDDEN>, Eli Zaretskii <eliz@HIDDEN> X-BeenThere: debbugs-submit <at> debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: <debbugs-submit.debbugs.gnu.org> List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe> List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/> List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org> List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help> List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe> Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org> X-Spam-Score: -2.6 (--) To start, I don't think this issue should delay a merge to master. I don't think it is clear we need to fix anything here. I would like a note or FIXME in code noting the potentially slow algorithm (patch sent), because it is currently well hidden behind a generator loop. Stefan Monnier <monnier@HIDDEN> writes: >> Here we traverse overlays in ASCENDING order of BEG positions. The best >> we can say is that this loop executes in O(K*log(N)) time, where K is >> the MIN of number of overlays that overlap POS and the number of valid > > The core operation in itree.c is the equivalent of `overlays-in/at`. [...] Yes, and for this O(K*log(N)) performance is a good result. The key insight is that previous and next overlay changes require examining a large K (in worst case, extending all the way to the beginning or end of the buffer) because there is no ordering by END positions. > Realistic benchmarks would be most welcome. I am working on polishing off https://git.sr.ht/~matta/emacs-overlay-perftests. Good news is that redisplay is faster on the noverlay branch for the "realistic" case of overlaping not overlapping eachother in pathalogical ways. > [ Site note: `previous-overlay-change` is probably not very important in > practice, but `next-overlay-change` OTOH is indeed important because > it's used during redisplay. So if someone comes up with a trick to > speed up only one direction, it should be good enough. ] > > Maybe one way to improve the behavior is to accept the worst-case > bound but to try and avoid paying it over-and-over each time the > redisplay needs the "next change". IOW instead of a > `next_overlay_change` function which takes a POS and returns the next > change after that, the xdisp.c might benefit from having a > `next_overlay_changes` *generator* which takes a starting POS and > returns an iterator which will return (each time it's called) the > successive positions where there's an overlay change. > > Hopefully this way we'd pay the O(N) cost once per redisplayed window > rather than once per "small step in the rendering engine" (i.e. per > next_overlay_change). At the moment I can't think of a reasonable way to implement such a generator efficiently without, effectively, computing a temporary ordered collection over overlay END positions. This is why I keep coming back to the idea of storing both BEG and END positions in ordered collections at all times. > Another way to do basically the same is to let next_overlay_change > fill up a cache of change-positions which would be flushed whenever > some overlay is modified/added/removed (or the current_buffer is > different from last time). That might be easier to use with the > current code since xdisp.c wouldn't need to pass around this iterator > (which could require significant reworks). ...possibly, but the problem with caching is the time spent filling the cache back up. I like the idea of storing both BEG and END positions in an ordered collection because in that case the (potentially slow) recomputation need not occur with every key press. If we're not worried about that kind per-key-press of delay, then I argue there is no need for a cache either.
bug-gnu-emacs@HIDDEN:bug#58342; Package emacs.
Full text available.
Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 14:48:03 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Fri Oct 07 10:48:03 2022
Received: from localhost ([127.0.0.1]:37051 helo=debbugs.gnu.org)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
id 1ogodu-0004pj-LU
for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 10:48:03 -0400
Received: from lists.gnu.org ([209.51.188.17]:57130)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <monnier@HIDDEN>) id 1ogods-0004pD-3W
for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 10:48:00 -0400
Received: from eggs.gnu.org ([2001:470:142:3::10]:34330)
by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <monnier@HIDDEN>)
id 1ogodr-0000NW-PZ
for bug-gnu-emacs@HIDDEN; Fri, 07 Oct 2022 10:47:59 -0400
Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:24229)
by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <monnier@HIDDEN>)
id 1ogodp-0000HR-B6; Fri, 07 Oct 2022 10:47:58 -0400
Received: from pmg3.iro.umontreal.ca (localhost [127.0.0.1])
by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id C9A484436B2;
Fri, 7 Oct 2022 10:47:54 -0400 (EDT)
Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1])
by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 67A484436AF;
Fri, 7 Oct 2022 10:47:53 -0400 (EDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca;
s=mail; t=1665154073;
bh=eiqEQCMrS8DQancssEmJNhsxPYL8+o/mBzjkVR9Tcyw=;
h=From:To:Cc:Subject:In-Reply-To:References:Date:From;
b=dYS8ZyaEilamnYUKIxusJS+dOG5zFpmGXVS1aRpSSIAWPYDCCbHHCh9TT/BMvxz11
WvFPkAGgjL1/jdpp+uoSbhf+TtuNYwPwd98ptYHAEvX+wKfjD7wKGiO9SS3vCij+Hm
QACSdja70hCSoae6pLBXrh1wW10Ib1ocuneRtIFpruCOrFr4qfSqzldQBh7ufGR4pq
Fhb+BdKGmgNmQEuwwNeZ+Iq6SYg4BxM+AEHUjprncfqF2FKCuq07tUt8ciWHQ45KEh
zZkm4K14aW4LxJbHys5rL64Oh6IUq6XFp11kLTBjBgDD/fKh81F+ncpZrblsPvxXfH
BXxODmeE7/wig==
Received: from pastel (65-110-220-202.cpe.pppoe.ca [65.110.220.202])
by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 1B8A0120263;
Fri, 7 Oct 2022 10:47:53 -0400 (EDT)
From: Stefan Monnier <monnier@HIDDEN>
To: Eli Zaretskii <eliz@HIDDEN>
Subject: Re: 29.0.50; noverlay branch is O(N) for important calls
In-Reply-To: <83sfjzn3cx.fsf@HIDDEN> (Eli Zaretskii's message of "Fri, 07 Oct
2022 16:57:18 +0300")
Message-ID: <jwvk05b7l8x.fsf-monnier+emacs@HIDDEN>
References: <87edvkcz5v.fsf@HIDDEN> <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN>
<83tu4gnm8c.fsf@HIDDEN> <jwvpmf37o4f.fsf-monnier+emacs@HIDDEN>
<83sfjzn3cx.fsf@HIDDEN>
Date: Fri, 07 Oct 2022 10:47:51 -0400
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-SPAM-INFO: Spam detection results: 0
ALL_TRUSTED -1 Passed through trusted hosts only via SMTP
AWL -0.018 Adjusted score from AWL reputation of From: address
BAYES_00 -1.9 Bayes spam probability is 0 to 1%
DKIM_SIGNED 0.1 Message has a DKIM or DK signature,
not necessarily valid
DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature
DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's
domain
X-SPAM-LEVEL:
Received-SPF: pass client-ip=132.204.25.50;
envelope-from=monnier@HIDDEN; helo=mailscanner.iro.umontreal.ca
X-Spam_score_int: -42
X-Spam_score: -4.3
X-Spam_bar: ----
X-Spam_report: (-4.3 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1,
DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3,
SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no
X-Spam_action: no action
X-Spam-Score: -1.3 (-)
X-Debbugs-Envelope-To: submit
Cc: gerd.moellmann@HIDDEN, matt@HIDDEN, bug-gnu-emacs@HIDDEN,
mail@HIDDEN
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -2.3 (--)
>> Do you happen to know via which path it can be called (beside the obvious
>> ones when the redisplay ends up calling ELisp, such as via jit-lock)?
>
> pos_visible_p
> -> previous-single-char-property-change
Ah, thanks, indeed. Hadn't noticed this one.
> set_point_both
> -> previous-char-property-change
> -> previous-overlay-change
I knew about this one but AFAIC it doesn't count :-) because it's only
triggered when `inhibit-point-motion-hooks` is nil, and this var has
defaulted to t (and been marked obsolete) since Emacs-25.
Stefan
bug-gnu-emacs@HIDDEN:bug#58342; Package emacs.
Full text available.
Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 13:57:23 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Fri Oct 07 09:57:23 2022
Received: from localhost ([127.0.0.1]:36974 helo=debbugs.gnu.org)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
id 1ognqs-0003T5-Ry
for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 09:57:23 -0400
Received: from lists.gnu.org ([209.51.188.17]:52266)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <eliz@HIDDEN>) id 1ognqr-0003Sy-Cw
for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 09:57:21 -0400
Received: from eggs.gnu.org ([2001:470:142:3::10]:56426)
by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <eliz@HIDDEN>) id 1ognqr-0007Go-56
for bug-gnu-emacs@HIDDEN; Fri, 07 Oct 2022 09:57:21 -0400
Received: from fencepost.gnu.org ([2001:470:142:3::e]:50556)
by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <eliz@HIDDEN>)
id 1ognqq-0000Jn-51; Fri, 07 Oct 2022 09:57:20 -0400
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org;
s=fencepost-gnu-org; h=References:Subject:In-Reply-To:To:From:Date:
mime-version; bh=cOEWx/UQ5Aunqemfscfif9FoNHZI+eA5NHDUAbELaWY=; b=C60lvlANoM+x
RgDu1XUUpzvUu21jNCLlRaikx8SbdTgDw38kbBFKf9h/FiE626Uj1T+zCvkNFvnPPdASyW0/r45uA
P78CfJxKivkER+kt2MZYVF0PZfbzNuSxvDYPGlWmoy/ZIqqqf6q2b9hIKgJ2qmqWzi8fQ/Qj67cnV
pIUr9Nie4mz8KRpZ5uH1lvbAhj5wxrUm/K4PISniLJpYcmpKiW698D3OnUb3W+xkMdW5HUd/5hYy8
kuFPWZ9+lXyhCCLTvRWvGh+uS19DdhVgC97ku6dBxJKn5FL3q1gDmcLboBCZXZJCN+URgJbyQoPa6
4GeXcJghOI9OaUircrIRxA==;
Received: from [87.69.77.57] (port=2758 helo=home-c4e4a596f7)
by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <eliz@HIDDEN>)
id 1ognqp-0000aU-IP; Fri, 07 Oct 2022 09:57:19 -0400
Date: Fri, 07 Oct 2022 16:57:18 +0300
Message-Id: <83sfjzn3cx.fsf@HIDDEN>
From: Eli Zaretskii <eliz@HIDDEN>
To: Stefan Monnier <monnier@HIDDEN>
In-Reply-To: <jwvpmf37o4f.fsf-monnier+emacs@HIDDEN> (message from Stefan
Monnier on Fri, 07 Oct 2022 09:36:50 -0400)
Subject: Re: 29.0.50; noverlay branch is O(N) for important calls
References: <87edvkcz5v.fsf@HIDDEN> <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN>
<83tu4gnm8c.fsf@HIDDEN> <jwvpmf37o4f.fsf-monnier+emacs@HIDDEN>
X-Spam-Score: -2.3 (--)
X-Debbugs-Envelope-To: submit
Cc: gerd.moellmann@HIDDEN, matt@HIDDEN, bug-gnu-emacs@HIDDEN,
mail@HIDDEN
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -3.3 (---)
> From: Stefan Monnier <monnier@HIDDEN>
> Cc: matt@HIDDEN, bug-gnu-emacs@HIDDEN, mail@HIDDEN,
> gerd.moellmann@HIDDEN
> Date: Fri, 07 Oct 2022 09:36:50 -0400
>
> Eli Zaretskii [2022-10-07 10:09:39] wrote:
> >> [ Site note: `previous-overlay-change` is probably not very important in
> >> practice, but `next-overlay-change` OTOH is indeed important because
> >> it's used during redisplay.
> > previous-overlay-change is also called by redisplay (but I didn't see
> > how frequently), at least if you look at the code from the static
> > analysis POV.
>
> Do you happen to know via which path it can be called (beside the obvious
> ones when the redisplay ends up calling ELisp, such as via jit-lock)?
pos_visible_p
-> previous-single-char-property-change
-> previous-char-property-change
-> previous-overlay-change
Also:
set_point_both
-> previous-char-property-change
-> previous-overlay-change
bug-gnu-emacs@HIDDEN:bug#58342; Package emacs.
Full text available.
Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 13:37:02 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Fri Oct 07 09:37:02 2022
Received: from localhost ([127.0.0.1]:34836 helo=debbugs.gnu.org)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
id 1ognXB-0002PE-NY
for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 09:37:02 -0400
Received: from lists.gnu.org ([209.51.188.17]:57086)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <monnier@HIDDEN>) id 1ognXA-0002Oz-0E
for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 09:37:00 -0400
Received: from eggs.gnu.org ([2001:470:142:3::10]:59590)
by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <monnier@HIDDEN>)
id 1ognX7-0003zJ-LF
for bug-gnu-emacs@HIDDEN; Fri, 07 Oct 2022 09:36:59 -0400
Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:47407)
by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <monnier@HIDDEN>)
id 1ognX5-0005in-5R; Fri, 07 Oct 2022 09:36:56 -0400
Received: from pmg3.iro.umontreal.ca (localhost [127.0.0.1])
by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 5A65844368A;
Fri, 7 Oct 2022 09:36:53 -0400 (EDT)
Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1])
by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 05F7A440023;
Fri, 7 Oct 2022 09:36:52 -0400 (EDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca;
s=mail; t=1665149812;
bh=2rtk+lGufqD2fkkQokw4tPUEStp646BbDUUuLmBdBbU=;
h=From:To:Cc:Subject:In-Reply-To:References:Date:From;
b=Ppte24o06JokLHpsCGr53pZqcj5sPiiJJP8XLJXCXheRUxiDmDJF2fH6NBGIo/Ta8
DwMN8lioosbksu6C+ZLrxv2gYfLxU4g+RS3X59sAWSQF4sShsDl5TLGQojo1tPBfaU
ByPBkES75H+KVUp6rwNOzshN8juY7xCkQVdqef2qVvukD+M7SIGyqUqgMQnQ6PxksG
v0yT5asBXkTasb8j3LsdUNgeDEjhywHoZknCiH+UIHpPmwjTatO+fYdSaxk62fxzzg
AvEtAwYeNNmYFxctJyt0ZkUqyW9/zSVsbH/Q/7wr0Qm4Yz/QPdyf96RvQhUOo5XC0N
vSYHRhYrIRoLw==
Received: from pastel (65-110-220-202.cpe.pppoe.ca [65.110.220.202])
by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 5161E120BC6;
Fri, 7 Oct 2022 09:36:51 -0400 (EDT)
From: Stefan Monnier <monnier@HIDDEN>
To: Eli Zaretskii <eliz@HIDDEN>
Subject: Re: 29.0.50; noverlay branch is O(N) for important calls
In-Reply-To: <83tu4gnm8c.fsf@HIDDEN> (Eli Zaretskii's message of "Fri, 07 Oct
2022 10:09:39 +0300")
Message-ID: <jwvpmf37o4f.fsf-monnier+emacs@HIDDEN>
References: <87edvkcz5v.fsf@HIDDEN> <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN>
<83tu4gnm8c.fsf@HIDDEN>
Date: Fri, 07 Oct 2022 09:36:50 -0400
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-SPAM-INFO: Spam detection results: 0
ALL_TRUSTED -1 Passed through trusted hosts only via SMTP
AWL -0.018 Adjusted score from AWL reputation of From: address
BAYES_00 -1.9 Bayes spam probability is 0 to 1%
DKIM_SIGNED 0.1 Message has a DKIM or DK signature,
not necessarily valid
DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature
DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's
domain
X-SPAM-LEVEL:
Received-SPF: pass client-ip=132.204.25.50;
envelope-from=monnier@HIDDEN; helo=mailscanner.iro.umontreal.ca
X-Spam_score_int: -42
X-Spam_score: -4.3
X-Spam_bar: ----
X-Spam_report: (-4.3 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1,
DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3,
SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no
X-Spam_action: no action
X-Spam-Score: -1.3 (-)
X-Debbugs-Envelope-To: submit
Cc: gerd.moellmann@HIDDEN, matt@HIDDEN, bug-gnu-emacs@HIDDEN,
mail@HIDDEN
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -2.3 (--)
Eli Zaretskii [2022-10-07 10:09:39] wrote:
>> [ Site note: `previous-overlay-change` is probably not very important in
>> practice, but `next-overlay-change` OTOH is indeed important because
>> it's used during redisplay.
> previous-overlay-change is also called by redisplay (but I didn't see
> how frequently), at least if you look at the code from the static
> analysis POV.
Do you happen to know via which path it can be called (beside the obvious
ones when the redisplay ends up calling ELisp, such as via jit-lock)?
Stefan
bug-gnu-emacs@HIDDEN:bug#58342; Package emacs.
Full text available.Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 07:09:45 +0000 From debbugs-submit-bounces <at> debbugs.gnu.org Fri Oct 07 03:09:45 2022 Received: from localhost ([127.0.0.1]:34116 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>) id 1oghUP-0004NI-C7 for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 03:09:45 -0400 Received: from lists.gnu.org ([209.51.188.17]:53878) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <eliz@HIDDEN>) id 1oghUN-0004N8-J1 for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 03:09:43 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:57106) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from <eliz@HIDDEN>) id 1oghUM-0003f1-Lu for bug-gnu-emacs@HIDDEN; Fri, 07 Oct 2022 03:09:43 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:58916) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from <eliz@HIDDEN>) id 1oghUK-0005jV-JB; Fri, 07 Oct 2022 03:09:40 -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=sohigmtr9Jy8weFMFt1ANwR8kPS/TT/c/qwIYEhFegs=; b=M9JfmJFcycCbwpH6RmIj kNfvK/vyvr/CFSHg+DrxwBlblX6qpivcaC95ZZYAKR5PXdRW+XHhVZpj5TDoYUpEFlo8dBko1cbVn b6IonIu291JYRuPXYmvdYcGq0yYnUqufcG0cokIQaueDp/cj02YMq4JmNRMZ9pWUVONbtU28dIVrN PHOjmZ7BALe7KFXzTBDmDZAFz64nVaC7aIh6OkSxrHU54+dqxPqQo/Hct0qbgY+xMKC0p6aEokVHd q9JVcpXTmg0WBA5h1qVEYAmfL39UllPaY4hlDcNaj3VztWtWo6Q19FaycyqUpBIVSFyNqyLvjn/9M LTX06C7r44xH2w==; Received: from [87.69.77.57] (port=1592 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from <eliz@HIDDEN>) id 1oghUJ-000285-T8; Fri, 07 Oct 2022 03:09:40 -0400 Date: Fri, 07 Oct 2022 10:09:39 +0300 Message-Id: <83tu4gnm8c.fsf@HIDDEN> From: Eli Zaretskii <eliz@HIDDEN> To: Stefan Monnier <monnier@HIDDEN> In-Reply-To: <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN> (message from Stefan Monnier on Thu, 06 Oct 2022 21:12:26 -0400) Subject: Re: 29.0.50; noverlay branch is O(N) for important calls References: <87edvkcz5v.fsf@HIDDEN> <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN> MIME-version: 1.0 Content-type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: submit Cc: gerd.moellmann@HIDDEN, matt@HIDDEN, bug-gnu-emacs@HIDDEN, mail@HIDDEN X-BeenThere: debbugs-submit <at> debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: <debbugs-submit.debbugs.gnu.org> List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe> List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/> List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org> List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help> List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe> Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org> X-Spam-Score: -3.3 (---) > From: Stefan Monnier <monnier@HIDDEN> > Cc: bug-gnu-emacs@HIDDEN, Andreas Politz <mail@HIDDEN>, Gerd > Möllmann <gerd.moellmann@HIDDEN>, Eli Zaretskii > <eliz@HIDDEN> > Date: Thu, 06 Oct 2022 21:12:26 -0400 > > [ Site note: `previous-overlay-change` is probably not very important in > practice, but `next-overlay-change` OTOH is indeed important because > it's used during redisplay. previous-overlay-change is also called by redisplay (but I didn't see how frequently), at least if you look at the code from the static analysis POV.
bug-gnu-emacs@HIDDEN:bug#58342; Package emacs.
Full text available.
Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 01:12:43 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Thu Oct 06 21:12:43 2022
Received: from localhost ([127.0.0.1]:33903 helo=debbugs.gnu.org)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
id 1ogbus-0003Tl-RI
for submit <at> debbugs.gnu.org; Thu, 06 Oct 2022 21:12:43 -0400
Received: from lists.gnu.org ([209.51.188.17]:57728)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <monnier@HIDDEN>) id 1ogbup-0003Ta-JL
for submit <at> debbugs.gnu.org; Thu, 06 Oct 2022 21:12:42 -0400
Received: from eggs.gnu.org ([2001:470:142:3::10]:50180)
by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <monnier@HIDDEN>)
id 1ogbup-0006WD-EB
for bug-gnu-emacs@HIDDEN; Thu, 06 Oct 2022 21:12:39 -0400
Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:3471)
by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <monnier@HIDDEN>)
id 1ogbum-0002ak-CZ; Thu, 06 Oct 2022 21:12:38 -0400
Received: from pmg3.iro.umontreal.ca (localhost [127.0.0.1])
by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 8A69E443621;
Thu, 6 Oct 2022 21:12:34 -0400 (EDT)
Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1])
by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id B088A443620;
Thu, 6 Oct 2022 21:12:28 -0400 (EDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca;
s=mail; t=1665105148;
bh=Tx/76iCCMjycETgDqe49lNhg7DFAOEuWDSMqf2TVPDY=;
h=From:To:Cc:Subject:In-Reply-To:References:Date:From;
b=Yu4zGrYVxLbB1cEgiPFBZbhfePzRE8TXzvcccNQnUIDfUbEt19LXVTTBebehQsAQb
FXCv9WMn5sVCHt8p4wQ064dejLBM0FLOzmMGjDPCRzDK3MAbOhzxTxhz6VtOx8JZ/L
U43pcprlAxtmjIyhWiWo5PP5YlrZlDfEAuov1ZM/UqhX5//nmEYoOSk2051gfgmszr
ix/wAcdo8nhRNk3Pv31O/F7eujwhji/2tZ3/hNIK6YFK4KWN7JGn/1TwIE0eSON8ka
4E02jq7ZRN0uQy5aZri0ETwLFp84N4sEgy5as9daK+VoDYOTEJxGl6HI/MYmpQ7fof
6XDEmC1WyNWjw==
Received: from milanesa (65-110-220-202.cpe.pppoe.ca [65.110.220.202])
by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 6BDA812068A;
Thu, 6 Oct 2022 21:12:28 -0400 (EDT)
From: Stefan Monnier <monnier@HIDDEN>
To: Matt Armstrong <matt@HIDDEN>
Subject: Re: 29.0.50; noverlay branch is O(N) for important calls
In-Reply-To: <87edvkcz5v.fsf@HIDDEN> (Matt Armstrong's message of "Thu, 06
Oct 2022 16:25:48 -0700")
Message-ID: <jwv4jwgcvy9.fsf-monnier+emacs@HIDDEN>
References: <87edvkcz5v.fsf@HIDDEN>
Date: Thu, 06 Oct 2022 21:12:26 -0400
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-SPAM-INFO: Spam detection results: 0
ALL_TRUSTED -1 Passed through trusted hosts only via SMTP
AWL -0.019 Adjusted score from AWL reputation of From: address
BAYES_00 -1.9 Bayes spam probability is 0 to 1%
DKIM_SIGNED 0.1 Message has a DKIM or DK signature,
not necessarily valid
DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature
DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's
domain
X-SPAM-LEVEL:
Received-SPF: pass client-ip=132.204.25.50;
envelope-from=monnier@HIDDEN; helo=mailscanner.iro.umontreal.ca
X-Spam_score_int: -42
X-Spam_score: -4.3
X-Spam_bar: ----
X-Spam_report: (-4.3 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1,
DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3,
SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no
X-Spam_action: no action
X-Spam-Score: -1.3 (-)
X-Debbugs-Envelope-To: submit
Cc: Gerd =?windows-1252?Q?M=F6llmann?= <gerd.moellmann@HIDDEN>,
bug-gnu-emacs@HIDDEN, Andreas Politz <mail@HIDDEN>,
Eli Zaretskii <eliz@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -2.3 (--)
> Here we traverse overlays in ASCENDING order of BEG positions. The best
> we can say is that this loop executes in O(K*log(N)) time, where K is
> the MIN of number of overlays that overlap POS and the number of valid
The core operation in itree.c is the equivalent of `overlays-in/at`.
It's considered OK if this takes O(N) where N is the number of overlays
that are returned, since that's the best we can do.
In practice itree.c takes a bit more than O(N) for that, there's
an additional log(M) factor where M is the total number of overlays, but
it's still overall significantly better at this operation than the old
code which was O(M).
In practice the expectation is that N is relatively small. Of course,
we don't have any such guarantee, there might be cases where packages
create many overlays each of which covers almost all the buffer.
IIUC this situation is poorly handled both by the old and the new
code, tho.
Realistic benchmarks would be most welcome.
[ Site note: `previous-overlay-change` is probably not very important in
practice, but `next-overlay-change` OTOH is indeed important because
it's used during redisplay. So if someone comes up with a trick to
speed up only one direction, it should be good enough. ]
Maybe one way to improve the behavior is to accept the worst-case bound
but to try and avoid paying it over-and-over each time the redisplay
needs the "next change". IOW instead of a `next_overlay_change`
function which takes a POS and returns the next change after that, the
xdisp.c might benefit from having a `next_overlay_changes` *generator*
which takes a starting POS and returns an iterator which will return
(each time it's called) the successive positions where there's an
overlay change.
Hopefully this way we'd pay the O(N) cost once per redisplayed window
rather than once per "small step in the rendering engine" (i.e. per
next_overlay_change).
Another way to do basically the same is to let next_overlay_change fill
up a cache of change-positions which would be flushed whenever some
overlay is modified/added/removed (or the current_buffer is different
from last time). That might be easier to use with the current code
since xdisp.c wouldn't need to pass around this iterator (which could
require significant reworks).
Stefan
bug-gnu-emacs@HIDDEN:bug#58342; Package emacs.
Full text available.
Received: (at submit) by debbugs.gnu.org; 6 Oct 2022 23:26:05 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Thu Oct 06 19:26:05 2022
Received: from localhost ([127.0.0.1]:33840 helo=debbugs.gnu.org)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
id 1ogaFg-0000aF-Jb
for submit <at> debbugs.gnu.org; Thu, 06 Oct 2022 19:26:05 -0400
Received: from lists.gnu.org ([209.51.188.17]:38080)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <matt@HIDDEN>) id 1ogaFe-0000a7-G3
for submit <at> debbugs.gnu.org; Thu, 06 Oct 2022 19:26:03 -0400
Received: from eggs.gnu.org ([2001:470:142:3::10]:58024)
by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <matt@HIDDEN>) id 1ogaFd-00062I-Sh
for bug-gnu-emacs@HIDDEN; Thu, 06 Oct 2022 19:26:02 -0400
Received: from relay6-d.mail.gandi.net ([2001:4b98:dc4:8::226]:52653)
by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <matt@HIDDEN>)
id 1ogaFa-0005uz-IR; Thu, 06 Oct 2022 19:26:01 -0400
Received: (Authenticated sender: matt@HIDDEN)
by mail.gandi.net (Postfix) with ESMTPSA id 66E72C0002;
Thu, 6 Oct 2022 23:25:50 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1;
t=1665098752;
h=from:from:reply-to:subject:subject:date:date:message-id:message-id:
to:to:cc:cc:mime-version:mime-version:content-type:content-type;
bh=5jPPHht+iP/wOYNy946ljiEGfu6vROxdEzeTPdogBFA=;
b=QIo+MzHrR1XvcVpvLhYjSFJcbeBZB/7A0UDG5bvWwe17Wz03YTrvt96FlIEtt/GNkozbyU
GYiwT9mfJRv7TeECldYudUSe72LoItV+zFZMbdpg9054THBIrEM1wjgfL6x5CZEZ8rC8xj
6CTKqw1MeE6SEKMgC/ZxVH9SmvjtfyABiBXo6G3YTgDvbfPFM+gFPlBruSF3bSJ54Q9Tll
QM4joUjC/OWfH5nSijqS3/P/qd9V/X+ms3bOuEZxzukPvBXEUtplidFTkiLgPbA5sne4Bj
0HbLszCAUQVMW0JAR0BEtrhPjjU+K8Kxt4l9hwdnUPx+x2vC9qkPPkYPzQxgcw==
Received: from matt by naz with local (Exim 4.96)
(envelope-from <matt@HIDDEN>) id 1ogaFQ-0043mO-0Y;
Thu, 06 Oct 2022 16:25:48 -0700
From: Matt Armstrong <matt@HIDDEN>
To: bug-gnu-emacs@HIDDEN
Subject: 29.0.50; noverlay branch is O(N) for important calls
Date: Thu, 06 Oct 2022 16:25:48 -0700
Message-ID: <87edvkcz5v.fsf@HIDDEN>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="=-=-="
Received-SPF: pass client-ip=2001:4b98:dc4:8::226; envelope-from=matt@HIDDEN;
helo=relay6-d.mail.gandi.net
X-Spam_score_int: -27
X-Spam_score: -2.8
X-Spam_bar: --
X-Spam_report: (-2.8 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1,
DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1,
RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_NONE=0.001,
SPF_PASS=-0.001 autolearn=ham autolearn_force=no
X-Spam_action: no action
X-Spam-Score: -1.6 (-)
X-Debbugs-Envelope-To: submit
Cc: Gerd =?utf-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>,
Eli Zaretskii <eliz@HIDDEN>, Andreas Politz <mail@HIDDEN>,
Stefan Monnier <monnier@HIDDEN>
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -2.6 (--)
--=-=-=
Content-Type: text/plain
First let me preface:
A) I hope I'm wrong here, but after careful thought I've failed to
convince myself that I am, so I am either right or need help from others
to spot my flawed logic.
B) Even if I'm right the problem may not be judged serious enough to
address.
I believe that the feature/noverlay branch uses an O(N) algorithm for
next-overlay-change and previous-overlay-change. Or, more precisely,
O(MIN(N, (buffer-size))), where N is the overlay count.
Now, in "normal" cases the real world achieved performance will be fine.
If overlays form mostly disjoint intervals, without too many overlapping
overlays, without too many overlays that span large portions of the
buffer, the algorithm used will find the next/previous change quickly.
However, consider the new next_overlay_change:
1 ptrdiff_t
2 next_overlay_change (ptrdiff_t pos)
3 {
4 ptrdiff_t next = ZV;
5 struct interval_node *node;
6 ITREE_FOREACH (node, current_buffer->overlays, pos, next, ASCENDING)
7 {
8 if (node->begin > pos)
9 {
10 /* If we reach this branch, node->begin must be the least upper bound
11 of pos, because the search is limited to [pos,next) . */
12 eassert (node->begin < next);
13 next = node->begin;
14 ITREE_FOREACH_ABORT ();
15 break;
16 }
17 else if (node->begin < node->end && node->end < next)
18 {
19 next = node->end;
20 ITREE_FOREACH_NARROW (pos, next);
21 }
22 }
23 return next;
24 }
Here we traverse overlays in ASCENDING order of BEG positions. The best
we can say is that this loop executes in O(K*log(N)) time, where K is
the MIN of number of overlays that overlap POS and the number of valid
positions in the buffer after POS. It is always going to be possible to
construct pathalogical cases where lines 19-20 are taken for as many
positions as there are in the buffer after POS, since the tree is not
ordered by END.
I've attached a patch that can go in to itree.c (which, if I'm right, I
think would be good to add, especially if we decide to not improve the
data structure). I've quoted the text:
====
FIXME: this data structure is O(N) for important operations -matt
====
The amortized costs of Emacs' previous-overlay-change and
next-overlay-change functions are O(N) with this data structure.
The root problem is that we only have an order for the BEG field,
but not the END. The previous/next overlay change operations need
to find the nearest point where there is *either* an interval BEG
or END point, but there is no efficient way to narrow the search
space over END postions.
Consider the case where next-overlay-change is called at POS, all
interval BEG positions are less than pos POS and all interval END
posistions are after. These END positions have no order, and so
*every* interval must be examined. This is at least O(N). The
previous-overlay-change case is similar. The root issue is that
the iterative "narrowing" approach is not guaranteed to reduce the
search space in logarithmic time, since END is not ordered in the
tree.
One might argue that the LIMIT value will do this narrowing, but
this narrowing is O(K*log(N)) where K is the size of the result
set. If we are interested in finding the node in a range with the
smallest END, we might have to examine all K nodes in that range.
In the case of the *-overlay-channge functions, K may well be equal
to N.
Ideally, a tree based data structure for overlays would have
O(log(N)) performance for previous-overlay-change and
next-overlay-change, as these are called in performance sensitive
situations such as redisplay. The only way I can think of
achieving this is by keeping one ordering by BEG and a separate
ordering by END, and then performing logic quite similar to the
current Emacs overlays-before and overlays-after lists.
--=-=-=
Content-Type: text/x-diff
Content-Disposition: inline;
filename=0005-src-itree.c-Add-comment-describing-when-noverlay-is-.patch
From 6ca364a6ad45b1cfdcf080c492fde536975f6e09 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@HIDDEN>
Date: Thu, 6 Oct 2022 15:47:20 -0700
Subject: [PATCH 5/5] ; * src/itree.c: Add comment describing when noverlay is
O(N)
---
src/itree.c | 36 ++++++++++++++++++++++++++++++++++++
1 file changed, 36 insertions(+)
diff --git a/src/itree.c b/src/itree.c
index 79e39d6e2a..6de84ae0b8 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -62,6 +62,42 @@ Copyright (C) 2017-2022 Free Software Foundation, Inc.
complexity of O(K*log(N)) for this operation, where K is the size
of the result set and N the size of the tree.
+ ====
+ FIXME: this data structure is O(N) for important operations -matt
+ ====
+
+ The amortized costs of Emacs' previous-overlay-change and
+ next-overlay-change functions are O(N) with this data structure.
+ The root problem is that we only have an order for the BEG field,
+ but not the END. The previous/next overlay change operations need
+ to find the nearest point where there is *either* an interval BEG
+ or END point, but there is no efficient way to narrow the search
+ space over END postions.
+
+ Consider the case where next-overlay-change is called at POS, all
+ interval BEG positions are less than pos POS and all interval END
+ posistions are after. These END positions have no order, and so
+ *every* interval must be examined. This is at least O(N). The
+ previous-overlay-change case is similar. The root issue is that
+ the iterative "narrowing" approach is not guaranteed to reduce the
+ search space in logarithmic time, since END is not ordered in the
+ tree.
+
+ One might argue that the LIMIT value will do this narrowing, but
+ this narrowing is O(K*log(N)) where K is the size of the result
+ set. If we are interested in finding the node in a range with the
+ smallest END, we might have to examine all K nodes in that range.
+ In the case of the *-overlay-channge functions, K may well be equal
+ to N.
+
+ Ideally, a tree based data structure for overlays would have
+ O(log(N)) performance for previous-overlay-change and
+ next-overlay-change, as these are called in performance sensitive
+ situations such as redisplay. The only way I can think of
+ achieving this is by keeping one ordering by BEG and a separate
+ ordering by END, and then performing logic quite similar to the
+ current Emacs overlays-before and overlays-after lists.
+
==== Adjusting intervals ====
Since this data-structure will be used for overlays in an Emacs
--
2.35.1
--=-=-=--
Matt Armstrong <matt@HIDDEN>:bug-gnu-emacs@HIDDEN.
Full text available.bug-gnu-emacs@HIDDEN:bug#58342; Package emacs.
Full text available.
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997 nCipher Corporation Ltd,
1994-97 Ian Jackson.