From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: =?utf-8?Q?Gerd_M=C3=B6llmann?= Newsgroups: gmane.emacs.devel Subject: Re: MPS: dangling markers Date: Sun, 30 Jun 2024 07:02:06 +0200 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="13093"; 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: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sun Jun 30 07:10:49 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 1sNmpt-00038O-D8 for ged-emacs-devel@m.gmane-mx.org; Sun, 30 Jun 2024 07:10:49 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1sNmp7-00009r-7Y; Sun, 30 Jun 2024 01:10:01 -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 1sNmhY-0007Xn-N8 for emacs-devel@gnu.org; Sun, 30 Jun 2024 01:02:12 -0400 Original-Received: from mail-ed1-x52b.google.com ([2a00:1450:4864:20::52b]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1sNmhW-0004qi-9n; Sun, 30 Jun 2024 01:02:12 -0400 Original-Received: by mail-ed1-x52b.google.com with SMTP id 4fb4d7f45d1cf-57d10354955so2358542a12.1; Sat, 29 Jun 2024 22:02:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1719723728; x=1720328528; darn=gnu.org; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:cc:to:from:from:to:cc:subject:date:message-id:reply-to; bh=IWXmsWS4bxn8YaAgtm0C26zhSHvkDBhyxf2BH8wMkoc=; b=TvPHLL3mRAkIHZvPdbf+Cv2RAWR3V0TuoatWZeZvJi84NPJHd3/wtNabGguqu1gDVW MQ0uZ+ZM7q1sh3Vo2GXguSCQlhFUpdtKXCWeG8ZWOTPePttiAjocJv5DP21bXEmoIMl+ KDhPNyvSm2aKzNKiH5jpALwA7Yi5sUBWmFM5lQbOjBzDL6Xm0pkwpBk5iV5fIJ+/XC8c OimRg+kzPwcqohExHA7ZbVAYZzdhr315ifxL2KiCh67SXNkUIhtn3+OEl/5PPwq8i2e8 0BreREhYfxxs4GX7YjtYLzQxnscYQ9cWJDNKSFtk8k9RCIFctHR+3ftxBCvTZlsqtc6q q5jQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1719723728; x=1720328528; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:cc:to:from:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=IWXmsWS4bxn8YaAgtm0C26zhSHvkDBhyxf2BH8wMkoc=; b=uZJcmp4xqPLu/PZ9cxzIHctgVw+ho4gv3edKhd2dy+To0sB8OZRVBONc5MEo6jU7va 56lERgxeR9TMeS+l0QSQYH72xJFm40FW5CCbqV2kuioxlgHZSaAW448/nIZga0hEE/8I Tr1towALCosj81Qk8hxVMfaJwdt2UC9XC1Tz+KFO569VsoxZNS/Pe7gBuM9v0Kvbirrq MdZurR7KX4/OdjYNrQ30Rsz8QXHvNc9eHhEIWbrmNZPnYTz5EWcd3NMLCv1m7F25mqsA AhEEA8iVWYtiB+e/Upeeg2NkQIL+wYYOnzj11G/fePZt6n9Sur5JtdXpCT4q6GzbcA4t jU1g== X-Forwarded-Encrypted: i=1; AJvYcCXEOUZBHZmSO8m2um4Vy3CWo7U2Hu8xGZrD8ns+dI/bfCDZpf+MUqNe4RTA2jW4QtCdX4o8YAQbHh53l1lfUHPBPrTjNAmWNQhgojYdW7iAeRY= X-Gm-Message-State: AOJu0Yytl0pT3Gk3r1u+ZZDrrfTDNQI7kQ9AuQ6OfoikcbGKSBkC38v1 /ca+1+765Qym70prcYdqMNTI4qj/Jbayxxa0Q/Kyrtxa42JUm0sD X-Google-Smtp-Source: AGHT+IFVteJdJYL+wDoPwtO0YqX1aIgv3F6FW2cmXQTl21k7uuXD+Na+8F2T2/AlBsDkHKdIgRSAuQ== X-Received: by 2002:a05:6402:51cb:b0:57c:84fe:1acf with SMTP id 4fb4d7f45d1cf-5879f59bbf3mr1501290a12.17.1719723728052; Sat, 29 Jun 2024 22:02:08 -0700 (PDT) Original-Received: from pro2.fritz.box (pd9e36a45.dip0.t-ipconnect.de. [217.227.106.69]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-58612c83534sm2942182a12.10.2024.06.29.22.02.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 29 Jun 2024 22:02:07 -0700 (PDT) In-Reply-To: (Stefan Monnier's message of "Sat, 29 Jun 2024 18:59:15 -0400") Received-SPF: pass client-ip=2a00:1450:4864:20::52b; envelope-from=gerd.moellmann@gmail.com; helo=mail-ed1-x52b.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 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, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 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:320911 Archived-At: Stefan Monnier writes: >> 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. Yes. > 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. I'm afraid the only way to force MPS to "splat", as they call it, weak references it by requesting a full collection. Which I think we want to avoid because that is not done concurrently, the client has to wait for it to complete. > 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). Exactly what I was afraid of after seeing the number of point-markers: thousands of markers with the same position. And I agree that itree doesn't help with that, it will degenerate, and we can as well use a vector then. I must admit that I'm currently out of ideas. > [ 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