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: Fri, 28 Jun 2024 06:07:28 +0200 Message-ID: References: <87v81u85hv.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="1911"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: emacs-devel@gnu.org, Eli Zaretskii , eller.helmut@gmail.com, Stefan Monnier To: Ihor Radchenko Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Fri Jun 28 06:08:17 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 1sN2uH-0000CO-Kk for ged-emacs-devel@m.gmane-mx.org; Fri, 28 Jun 2024 06:08:17 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1sN2tb-00010G-Gl; Fri, 28 Jun 2024 00:07:35 -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 1sN2ta-0000xy-3O for emacs-devel@gnu.org; Fri, 28 Jun 2024 00:07:34 -0400 Original-Received: from mail-ej1-x62e.google.com ([2a00:1450:4864:20::62e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1sN2tY-0003HJ-1c; Fri, 28 Jun 2024 00:07:33 -0400 Original-Received: by mail-ej1-x62e.google.com with SMTP id a640c23a62f3a-a72af03ebdfso14035966b.3; Thu, 27 Jun 2024 21:07:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1719547650; x=1720152450; 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=M6EV8rX324NEZwWwc1v/0CuF4V+5sDomQmR1+tdV2Bc=; b=kVKpqeif/IOVtmeN6TddhGNJsFj63QEn1VWmgyf3/aKl2POayjK1VchxkXdi2Usb+g bEt6GjrIfS1JkRnkSOs4cKy/DppjI4G2Fz/QrsXVXThnSsM7cX24/eH/RAf4O9SqOeXa Q3Izio5cwOXw93cxvjGeRcmpCRZqFJXhRQ3IT9vdE1yK2OsDZnsCTM43Ok5noAeBW1IC aZ5qbYfAO3P6TZk3THTMs6YyOR80kQp7g1VIkeCLHn3GrC8cZFJaWlXwFRx8Z42DkHnc yLXjTjVuyM0Vr+arkNvQsGWKoCXRVUt9aBeLe1O1SHFeB2vn/PwLpr/5qp7l8jjzyfVB g6QA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1719547650; x=1720152450; 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=M6EV8rX324NEZwWwc1v/0CuF4V+5sDomQmR1+tdV2Bc=; b=vFNMPnUbcXgIgilXsaMLiyfYLdP4igH1nSAbl47DJ0iQM/M+ahC8SO66aOj7P2TCJY e+N9EvAB9gfX4WiGYgQ+xY0Or0KKm65zRLnUeq6hWNekwn28+0da8aL1BWIz8fqzPqpk KrKrejNC8A7klzZNG9N9fGUVqEzSQm60RI2SEFhkSQfj/OrKETuYnzp6eXhupWIFnV3F /tFkEFvqfIE+HjB7LVd8CMRa979uRPWgPARuafnxh08XaZpZE/GNAMbQtdfcTbTT6VJr QOqlPgZQ6uLsHt5kbRNLHDjH3h8W7f2omQV9JbyJ38cnYOmRfofy2wqMVlwumuEz8EAX pI9g== X-Forwarded-Encrypted: i=1; AJvYcCWtQ95FXUXfmaakkeN4DJJ/eAyEa665vsxK8goSf7bKh3WulbeZiNmZSjFz/bngK3pPMsyYmbvpwYLm2yw= X-Gm-Message-State: AOJu0YwGSIWu1oPFpi3G2dO5DaQWzw0gqYTgKhQ569qYg+AR4PWXpfLC pn1taKknJ9m4tcgeR1ma1010NoR8VfgdqpzvfJ9rXblGd/ilwYtL X-Google-Smtp-Source: AGHT+IHYVd/hF0CB1DfxTvOYEIEJz56H/uZDBNfLlhIMAd+9m5JCdpTAA6vrjOx6SgdfDQhqN1GM4g== X-Received: by 2002:a17:907:d401:b0:a72:46f3:ffc4 with SMTP id a640c23a62f3a-a7246f4005cmr1094416966b.26.1719547649769; Thu, 27 Jun 2024 21:07:29 -0700 (PDT) Original-Received: from pro2.fritz.box (pd9e360da.dip0.t-ipconnect.de. [217.227.96.218]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a72ab065651sm35662866b.126.2024.06.27.21.07.28 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 27 Jun 2024 21:07:29 -0700 (PDT) In-Reply-To: <87v81u85hv.fsf@localhost> (Ihor Radchenko's message of "Thu, 27 Jun 2024 21:01:32 +0000") Received-SPF: pass client-ip=2a00:1450:4864:20::62e; envelope-from=gerd.moellmann@gmail.com; helo=mail-ej1-x62e.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:320793 Archived-At: Ihor Radchenko writes: > Related: bug#71644, bug#63040 > > When running the scratch/igc branch, I noticed a severe slowdown (10x or > more) of redisplay on my large Org buffers. > > - The redisplay manifests itself as I build agenda multiple times > (agenda creates many new markers). > > - perf points to (1) itree lookup; (2) bytepos<->charpos, which implies > that things may be related to the number of allocated markers and > overlays. > > - I observe things slowing down as the number of "PVEC_MARKER" in the > output of `igc-info' grows. > > - Forcing (igc--collect) returns speed to normal Ok, interesting. > I believe that my observation reveals one important point that may need > to be considered when using MPS: > > We may need to more careful about cases in Emacs C code that traverse > object lists that may contain unreferenced objects. Because MPS does > not perform GC as regularly as the traditional mark-and-sweep, some > unreferenced objects may remain live and present in internal data > structures for a long time. Maybe it's helpful when I describe what I do for the buffer markers, as opposed to what is done currently. In master, buffer_text::markers is a singly-linked list of Lisp_Markers, using Lisp_Marker::next. In the sweep phase of GC, in sweeo_buffers, we iterate over all buffers and remove markers from the list that were not marked during the mark phase of GC. The list itself is left alone in the mark phase, so that references from these lists don't keep markers alive. The buffer markers thus acts as a weak list. Since garbage_collect is called often enough, markers are swiftly remnoved from the marker lists. What I've done in igc so far: buffer_text::markers is a Lisp vector and Lisp_Marker::next is gone. Elements of the vector are either nil or a marker. The vector is weak, entries for markers that are not referenced from somewhere else are set to nil eventually. Adding and removing markers is done naively in O(N) where N is the size of the vector. The vectors are resized if needed by doubling their size. They are never shrunk. Iteration goes over the whole vector, ignoring nil entries. Possibly, there is some potential for improvement :-). What we can't do is hope to make this weakness more "eager" so to say. Entries in weak vectors are reset to nil, but when MPS thinks it's a good time doing that. (It's BTW the wrong mental model to think of MPS doing GC at a specific time. It's more like doing GC work all the time, concurrently.) But it's true that MPS doesn't "eagerly" reset entries in these vectors. And there's no way, to my knowledge, to force it to do that other than to trigger a full GC. Ideas welcome, or better yet implemenations :-). I'm currently not working on this. > AFAIK, at least overlays, buffers, and markers are used in C code within > object lists/trees are often traversed in full. If objects in these > lists are not regularly garbage-collected, we may end up in situation > when dead objects significantly impact performance. I believe that what > I observe locally is exactly the described scenario. Probably.