From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.devel Subject: Re: Optimizing performance of buffer markers Date: Sat, 25 Jun 2022 11:44:34 +0300 Message-ID: <83h749b099.fsf@gnu.org> References: <2c2746e5f2558a87e8eab6f0914264a020173a9d.camel@pm.me> <27630AA3-8026-4E24-8852-ACCD9325B99D@gmail.com> <0E9E702B-B07C-4794-8498-29B9320E14CC@gmail.com> <871qvorqvv.fsf@localhost> <83tu8jq2vl.fsf@gnu.org> <87sfo37etn.fsf@localhost> <834k0jplcm.fsf@gnu.org> <878rpuwm9w.fsf@localhost> <83mteao3oj.fsf@gnu.org> <87edzmv3i0.fsf@localhost> <83k09eo1p5.fsf@gnu.org> <878rpuv17q.fsf@localhost> <83fsk2nyrm.fsf@gnu.org> <878rpr4kd4.fsf@localhost> <8335fzms6q.fsf@gnu.org> <87wndar5tt.fsf@localhost> <831qvikxqo.fsf@gnu.org> <87edzdwdqt.fsf@localhost> Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="20753"; mail-complaints-to="usenet@ciao.gmane.io" Cc: yantar92@gmail.com, casouri@gmail.com, emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sat Jun 25 10:46:02 2022 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1o51QW-0005Ci-VM for ged-emacs-devel@m.gmane-mx.org; Sat, 25 Jun 2022 10:46:01 +0200 Original-Received: from localhost ([::1]:59932 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1o51QV-0004ME-8d for ged-emacs-devel@m.gmane-mx.org; Sat, 25 Jun 2022 04:45:59 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:38106) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1o51PD-0003UE-8S for emacs-devel@gnu.org; Sat, 25 Jun 2022 04:44:44 -0400 Original-Received: from fencepost.gnu.org ([2001:470:142:3::e]:55898) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1o51PC-0002Xy-Cr; Sat, 25 Jun 2022 04:44:38 -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=B6MDGzzupv48hCDBOUyy/dRc4K2OgFsjh3kgfGFLzxs=; b=hrvpyZUqN2SK uHs8kK91kHEioYuh65RZDL78+fl1CHq47n0cYvlCfmXZflKko/m81obmfH3scfRnXA8C8Rc5YmiO0 cS1HJZ3OQiRCI8x7sivWXxgnS7y58xp6JysiaieaDcBVo9on+DLigrfTx2cEDbKhZgVoxIzM3yzzF 9XrOhpDVg0VeVQwQvfG9F3LXTaBvUZGQBCYhB68fvMNZbUN+H3JtIec9pl8yZv3vb0T/vno6dTPOe B3d5X39iygG0mIOe+8cJLaT3HKcI+sa7n03GN3To1x4CIkN2dY/Ql8URFM1hLmoKLdU8KgeLNon/W cLAW8PL+xl/p6MG8xXrhMg==; Original-Received: from [87.69.77.57] (port=2973 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1o51PB-0000Y2-5L; Sat, 25 Jun 2022 04:44:38 -0400 In-Reply-To: (message from Stefan Monnier on Sat, 25 Jun 2022 04:29:08 -0400) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:291589 Archived-At: > From: Stefan Monnier > Cc: Eli Zaretskii , casouri@gmail.com, emacs-devel@gnu.org > Date: Sat, 25 Jun 2022 04:29:08 -0400 > > > AFAIK, the most natural data structure to search for data > > before/after given key is a binary tree. There are more exotic data > > structures, like skip list, but I do not expect skip lists to be > > implemented in Emacs C code. > > BTW, most markers are actually part of overlays. And Andreas Politz > implemented an AA-tree based representation of overlays for Emacs (see > the branch `feature/noverlay`). > > So if you have performance problems due to overlays, you might want to > check the branch, make sure it solves the problem, and see if you can > get it merged once and for all into `master`. Landing that branch is indeed a very Good Thing, but AFAIU this discussion revealed that Org adds quite a few markers of its own when it parses the buffer, because it wants to track the positions of some syntactic elements of the buffer.