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: MPS: dangling markers Date: Sat, 29 Jun 2024 18:59:15 -0400 Message-ID: References: <87v81u85hv.fsf@localhost> <87frsx81m2.fsf@localhost> <87cyo180y2.fsf@localhost> <874j9d7zqe.fsf@localhost> <87sewvg6lw.fsf@localhost> <86ed8fiug3.fsf@gnu.org> <86bk3jirx7.fsf@gnu.org> <868qynipph.fsf@gnu.org> <87wmm75xze.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="16849"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: Ihor Radchenko , Eli Zaretskii , emacs-devel@gnu.org, eller.helmut@gmail.com To: Gerd =?windows-1252?Q?M=F6llmann?= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sun Jun 30 01:00:36 2024 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 1sNh3c-0004Ah-ED for ged-emacs-devel@m.gmane-mx.org; Sun, 30 Jun 2024 01:00:36 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1sNh2f-0005Yp-5t; Sat, 29 Jun 2024 18:59:37 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1sNh2d-0005Yf-Js for emacs-devel@gnu.org; Sat, 29 Jun 2024 18:59:35 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1sNh2R-0007f0-E1; Sat, 29 Jun 2024 18:59:35 -0400 Original-Received: from pmg1.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 98E71100061; Sat, 29 Jun 2024 18:59:21 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1719701956; bh=MmxBA6hSy/HVuyxadQFZTARoIYPXLYdmtCmYAKqYRgw=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=c51fGReFSWgTJBPDgIizGbDV/TZc6ul11mo4EEDbmOt5EoOmf/hdzxk2ubi21wGnr LJoJNB1s5/u033NBGFmhBzuBPufQRnVhuNK9+gjcHWjWe25Tie+X0G1g9NWnp0//E3 tUX4eyZaN/QosNN0c1AnlwKh4IvW5K57LmAwN45aaeNSTNHTwRcyNamGzklRB5HD9a AMsQvxXBB/7SPrvDcaSfiI3iKk6MoDIcCae0/AkDKQiNERFxNRkRxZJ7P9JvPMeEtt bUdh3ua1eeejdPefeMzhf0Rbvhb7qL9V81sfhYZTzlkP4YBa3WnrU4lr4A/Z5Ko8xP Lz4U++kV1F3fg== Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 85BED100035; Sat, 29 Jun 2024 18:59:16 -0400 (EDT) Original-Received: from pastel (unknown [45.72.245.253]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 48E4E12014A; Sat, 29 Jun 2024 18:59:16 -0400 (EDT) In-Reply-To: ("Gerd =?windows-1252?Q?M=F6l?= =?windows-1252?Q?lmann=22's?= message of "Sat, 29 Jun 2024 23:50:01 +0200") Received-SPF: pass client-ip=132.204.25.50; envelope-from=monnier@iro.umontreal.ca; helo=mailscanner.iro.umontreal.ca X-Spam_score_int: -19 X-Spam_score: -2.0 X-Spam_bar: -- X-Spam_report: (-2.0 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, SPF_HELO_NONE=0.001, T_SPF_TEMPERROR=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-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.devel:320894 Archived-At: > Jup, it's point-marker for me. No idea who calls that so often. I think the core of the problem, then, is that currently it's completely normal to rely on the GC to "remove" markers we don't care about any more instead of explicitly removing them when we don't need them any more (with `move-marker`). So if the GC takes a long time to call `unchain_dead_markers`, we end up with a very large set of markers and it's not clear how to handle that efficiently. I understand that relying on a prompt collection of dead objects is a bad idea, but we may have to try and make sure it's prompt enough because of the legacy of code which relies on it when it comes to markers. If not, we'll have to work at a better data-structure able to handle a large set of markers. The `itree` would probably be our best best but if we end up with many markers at the very same place (which seems likely if we often call `point-marker`), we'll hit its worst case (where it goes back to O(N) tho this N is only the number of markers at a given position rather than the total number of markers). [ Another option might be to have a kind of two-level set of markers, where we keep the "recently used" markers in one data structure (optimized for adding/removing/moving/gettingtheposition) and then we demote markers that have not been recently used to a secondary data-structure optimized for "low-cost long term maintenance", kind of a like an archive of markers which are predicted to be dead. ] [ BTW, for the bytes<->chars conversion, we could also use a plain array indexed by CHARPOS/CHUNKSIZE where instead of updating the entries upon text insertion/deletion we just truncate the array to the last still-valid entry before the point of insertion/deletion. ] Stefan