From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Helmut Eller Newsgroups: gmane.emacs.devel Subject: Re: MPS: marker-vector Date: Tue, 06 Aug 2024 08:28:29 +0200 Message-ID: <87v80e2mia.fsf@gmail.com> References: <87le2hp6ug.fsf@localhost> <87v81455iw.fsf@gmail.com> <87jzh8djdt.fsf@gmail.com> <87a5hqsq2l.fsf_-_@gmail.com> <87bk26vfj1.fsf@protonmail.com> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="35814"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: Gerd =?utf-8?Q?M=C3=B6llmann?= , Stefan Monnier , Ihor Radchenko , emacs-devel@gnu.org To: Pip Cet Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Tue Aug 06 08:29:16 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 1sbDh5-0009Ch-Lj for ged-emacs-devel@m.gmane-mx.org; Tue, 06 Aug 2024 08:29:15 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1sbDgU-0005hw-7A; Tue, 06 Aug 2024 02:28:38 -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 1sbDgR-0005XG-BA for emacs-devel@gnu.org; Tue, 06 Aug 2024 02:28:35 -0400 Original-Received: from mail-ed1-x52e.google.com ([2a00:1450:4864:20::52e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1sbDgP-0004CA-Ll; Tue, 06 Aug 2024 02:28:35 -0400 Original-Received: by mail-ed1-x52e.google.com with SMTP id 4fb4d7f45d1cf-5a20de39cfbso233546a12.1; Mon, 05 Aug 2024 23:28:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1722925711; x=1723530511; 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=zXsUbbKIucoVquIt3+f4wqhbro5482oW5reUI45afSk=; b=Zg8myHLo5qYjswLAJUnpPCO5WnrYzUx6LqQpYDmp4wCOj6HY9HAf9evIKKPMc0h2lV jG3eijgXhhr9wv6KiwWCuEEiZzezOKaUao2xn5K8DhA85i8aQapSF26gTfIqaMZxCn3M 1b2q9vtgYFeNAh6+zrCm9i0BTmO8g6pdNjG6pHX6hG7pw0UkABeiVe/FSPizUl6V13w9 HECDjIbvXv6mz7PuqQpwvSk7+puqY2jmNIwfer3YXv8QLe/IRpYTxMWW7KrDzLHjPwUW /fOw8XGdhWDv74EMSbrbNg7sck/Uw6x101bGbRFy6dhRHinN0ym3JLUzvfS3O+LJRvmk Q5Kw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722925711; x=1723530511; 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=zXsUbbKIucoVquIt3+f4wqhbro5482oW5reUI45afSk=; b=UmZA6tPlMYT5UMqlYzGY4CfxDBux5zee0WtyV+8GtGjY+cY9IM2rJ3MhY+xtELfWVD jOscY3aVSZq3ajFwBMs7rs0pxKVTgA6LcNTYJslqSXi//VgnRUU13zZyhWSY1oFFIS85 t8gnPMYhp/eiTgurahAlK+jNydimmj0lIpjb+kssy02AUH31QrwDvPPeIWudQuehNfcU C1bqlmflx5gFvJUQysCMuP07rsDPPcNas06RVWqIBwFdS2ByqXsFzCEfMcDlRDA70nYk QkwyKCgThsGgHHg1r+5fpB78My2AI56aTvrZT9Mjy0QaKO9yHVee9mxThV9w0XjJD39N amzQ== X-Forwarded-Encrypted: i=1; AJvYcCV5XDj3TIqSY5xagBcSrdFRn+fvfTPsQW3FjsCd/kePScNuGtiNmVRUC65IY4mZHlFaCakybafgUAv3S2HQbqFw3s9L X-Gm-Message-State: AOJu0YxdHg5fhSXLNNwdRGwo3Lc3hSwFDvZ2aPb6V5T2zclRWKQLuA4N us2hnJ9u+x4zq36Q38q+n5eeKXHzmPVMEs4eQAX/4A1m+gLrYNCP4i8Epw== X-Google-Smtp-Source: AGHT+IG3fi5ZRkJcQT6tQaWYdoitlnfoIyleHdciXcw/YeO6Lh0tXcVGPDUfPxE9HkXeWDmYDJQPeA== X-Received: by 2002:a17:907:1c9e:b0:a7a:b43e:86e3 with SMTP id a640c23a62f3a-a7dc50a3bf0mr1082132166b.62.1722925710862; Mon, 05 Aug 2024 23:28:30 -0700 (PDT) Original-Received: from caladan (dialin-234199.rol.raiffeisen.net. [195.254.234.199]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a7dc9c0c557sm517824766b.53.2024.08.05.23.28.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 05 Aug 2024 23:28:30 -0700 (PDT) In-Reply-To: <87bk26vfj1.fsf@protonmail.com> (Pip Cet's message of "Mon, 05 Aug 2024 21:14:13 +0000") Received-SPF: pass client-ip=2a00:1450:4864:20::52e; envelope-from=eller.helmut@gmail.com; helo=mail-ed1-x52e.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:322424 Archived-At: On Mon, Aug 05 2024, Pip Cet wrote: >> This replaces the vector-with-free-list by a growable vector, i.e. the >> free entries are always kept at the end of the vector. > > I don't think that's entirely accurate; it's quite possible for an entry > at the beginning of the array to be splatted and remain untouched until > the next time a DO_MARKERS reaches it, which may take a long time. Indeed, that's true. > I see one somewhat theoretical problem with this patch: if a marker is > simultaneously kept in a weak hash table, it's possible for it to be > splatted from the marker vector while remaining in the weak hash table > (there's no guarantee all references will be splatted at the same time); > if it is then retrieved from the weak hash table and made to point > nowhere, we will try to remove it from the marker vector, and hit the > igc_assert. Never thought about this. Hm. I think MPS could easily guarantee that all references are splatted at the same time: we could think of splatting a reference like moving an object to address zero. MPS certainly guarantees that all references to a moved object are updated before they are seen by user code. MPS could do the same for splatted references. > The rest of my comments are tiny nits, really: > > - capacity isn't redundant on 32-bit systems Not sure what you mean. Certainly igc_header_nwords works on 32-bit systems too; and igc_header_nwords is pretty much the same as capacity. > - I'd prefer the marker index to be signed; if it is unsigned, we > don't need to assert it's >= 0, and assigning -1 to it confused me... You'd have to talk to the person who designed the struct Lisp_Marker. > - you shouldn't compare Lisp_Objects with == > - I'd prefer checking for splatted elements before deciding to grow > the vector, if we can do so efficiently Good idea. > - I find XFIXNAT easier to read when the number is guaranteed to be nonnegative > - using alloca is problematic for large vectors (which shouldn't be > dumped, thus a nit) Probably. > I wonder whether it wouldn't be faster, upon encountering a marker that > has been splatted, to fix the entire array all at once. That would > ensure that creation order is respected, and splatting is relatively > rare (and, when splatted, we can expect most of the array to have been > splatted; indeed, I suspect it'd be best to give up on the marker vector > and build a new one so the old one can be collected and we don't have to > worry about never shrinking it). Possibly. But I also decided to ignore the issue and happily let somebody else come up with a benchmark that shows that any of this matters.