From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: Optimizing performance of buffer markers Date: Sat, 25 Jun 2022 04:29:08 -0400 Message-ID: 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> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="36740"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Cc: Eli Zaretskii , casouri@gmail.com, emacs-devel@gnu.org To: Ihor Radchenko Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sat Jun 25 10:31:43 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 1o51Cg-0009PD-Ev for ged-emacs-devel@m.gmane-mx.org; Sat, 25 Jun 2022 10:31:42 +0200 Original-Received: from localhost ([::1]:53498 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1o51Cd-0007Yh-VY for ged-emacs-devel@m.gmane-mx.org; Sat, 25 Jun 2022 04:31:40 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:36202) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1o51AR-00060r-78 for emacs-devel@gnu.org; Sat, 25 Jun 2022 04:29:24 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:43213) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1o51AO-00059R-VB; Sat, 25 Jun 2022 04:29:22 -0400 Original-Received: from pmg1.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 34D7810019F; Sat, 25 Jun 2022 04:29:18 -0400 (EDT) Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 65B9910012C; Sat, 25 Jun 2022 04:29:12 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1656145752; bh=r9ZE3rNdfCSuenwb79gdBjn4X9CMvjlHIuPsPdx9q/k=; h=From:To:Cc:Subject:References:Date:In-Reply-To:From; b=GhwXRnH8sV6fD5JSGFipjlUYPqyqb/RPAQWFkRRQ75WXYPleB/4FDwHO+cvv0HIq4 29E63aLBHySGP6LH1DJZ9CL0cRbvg76szvXj2gU29l6RsKuU2y6xlRHTjBrbFWedaG 0ckDRsf04WODu9tNVUOCKE8pTg++81hFbPBSNr40Un2tMi7534YZTDjeZhU6JMjaHM wCh69Z92mPaC0EFl/EPeK9PGaZtzm/HJ/Ep6WNCYFaKxZGLyd+orA/AEbP1kjRWtfT DSwb56HCJfOe1tjrzB3e7NMZFfMe5OK5B82clnHJowMgvlXieexotEfK22I7BAj4XA JKgEILOm6x/og== Original-Received: from alfajor (smb-adp02.hotspot.hub-one.net [213.174.99.150]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 155F61201CA; Sat, 25 Jun 2022 04:29:10 -0400 (EDT) In-Reply-To: <87edzdwdqt.fsf@localhost> (Ihor Radchenko's message of "Sat, 25 Jun 2022 12:47:38 +0800") Received-SPF: pass client-ip=132.204.25.50; envelope-from=monnier@iro.umontreal.ca; 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, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action 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:291587 Archived-At: > 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`. Stefan