From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier via "Bug reports for GNU Emacs, the Swiss army knife of text editors" Newsgroups: gmane.emacs.bugs Subject: bug#68244: hash-table improvements Date: Sun, 07 Jan 2024 00:26:56 -0500 Message-ID: References: <170438379722.3921.9312235725296561206@vcs2.savannah.gnu.org> <20240104155642.B4A99C00344@vcs2.savannah.gnu.org> <8d49ebdc-9da7-4e70-a080-d8e892b980b6@gutov.dev> <08314177-5AE9-4352-94A0-641830B4094D@gmail.com> Reply-To: Stefan Monnier Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="3990"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= , 68244@debbugs.gnu.org, Eli Zaretskii To: Dmitry Gutov Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sun Jan 07 06:28:16 2024 Return-path: Envelope-to: geb-bug-gnu-emacs@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 1rMLhn-0000oR-PE for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 07 Jan 2024 06:28:16 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1rMLhX-0000xP-A2; Sun, 07 Jan 2024 00:27:59 -0500 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 1rMLhV-0000wy-HL for bug-gnu-emacs@gnu.org; Sun, 07 Jan 2024 00:27:57 -0500 Original-Received: from debbugs.gnu.org ([2001:470:142:5::43]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1rMLhV-00017E-8q for bug-gnu-emacs@gnu.org; Sun, 07 Jan 2024 00:27:57 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1rMLha-0005lK-J1 for bug-gnu-emacs@gnu.org; Sun, 07 Jan 2024 00:28:02 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Stefan Monnier Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 07 Jan 2024 05:28:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 68244 X-GNU-PR-Package: emacs Original-Received: via spool by 68244-submit@debbugs.gnu.org id=B68244.170460523222069 (code B ref 68244); Sun, 07 Jan 2024 05:28:02 +0000 Original-Received: (at 68244) by debbugs.gnu.org; 7 Jan 2024 05:27:12 +0000 Original-Received: from localhost ([127.0.0.1]:60564 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rMLgm-0005js-3D for submit@debbugs.gnu.org; Sun, 07 Jan 2024 00:27:12 -0500 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:4266) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rMLgk-0005jg-Jd for 68244@debbugs.gnu.org; Sun, 07 Jan 2024 00:27:11 -0500 Original-Received: from pmg3.iro.umontreal.ca (localhost [127.0.0.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id B063E440315; Sun, 7 Jan 2024 00:26:59 -0500 (EST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1704605217; bh=w2OC6ZDOa9u0J/YeRvwTDfV+BiJ9wKMIFV50rqqxw4o=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=GTPrIlAH1asqRZRM03o13qfdHBD9JLt56R9E6QXpAJAZEZin/TNaDSSjJ82/sDmhy 6CuMTkKcS9/Q+jrI2JNY6vDMh5sc6W/7s3N1ieOpFPcYEjbI6nlGwxY/zwQIOwXbq1 ceeo1OfMbqfWfrBo4xeocIvjwnhb6BCYV6AxVreL5aHcO8JtiVhhYgaHvzxcqofz8L BO6OhwRtsVh7HwRwfO938qIThvW5q0sTo2FbOBfli59FuAcBbHQM4i3de2h3pQw/OQ cqc6YRPXty3LqHE+7QTxr8bq8sXvz4bcXL9eEMeVkbscUFXXdfbygDZVwI4GFVmEuU T4Elown+T1voA== Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id BFF1344018E; Sun, 7 Jan 2024 00:26:57 -0500 (EST) Original-Received: from pastel (65-110-221-238.cpe.pppoe.ca [65.110.221.238]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 8C8C412041B; Sun, 7 Jan 2024 00:26:57 -0500 (EST) In-Reply-To: (Dmitry Gutov's message of "Sun, 7 Jan 2024 05:13:39 +0200") X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.bugs:277493 Archived-At: Side note: I think reasoning won't get us out of this: either we decide the choice is important, and then we try and do some profiling/benchmarking, or we decide it's probably not worth the effort and make an arbitrary choice under the expectation that it probably won't make any difference anyway. The use of memory allocation as a way to decide when to do the next GC is just a crude tool anyway, which can often result in bad GC decisions, anyway (e.g. typically during long periods of initialization where we allocate many objects but don't generate almost any garbage). We sadly don't have a better alternative, but being crude means that the details usually don't matter anyway. Stefan Dmitry Gutov [2024-01-07 05:13:39] wrote: > On 06/01/2024 13:34, Mattias Engdeg=E5rd wrote: >> 5 jan. 2024 kl. 16.41 skrev Dmitry Gutov : >>=20 >>>> That's a good question and it all comes down to how we interpret >>> `consing_until_gc`. Here we take the view that it should encompass all >>> parts of an allocation and this seems to be consistent with >>> existing code. >>> >>> But the existing code used objects that would need to be collected by G= C, >>> right? And the new one, seemingly, does not. >> But it does, similar to the same way that we deal with string data. > > Actually, vectors might be a better comparison. And we do increase the ta= lly > when creating a vector (inside 'allocate_vectorlike'). > >>> So I don't quite see the advantage of increasing consing_until_gc >>> then. It's like the difference between creating new strings and inserti= ng >>> strings into a buffer: new memory is used either way, but the latter >>> doesn't increase consing. >> Since we don't know exactly when objects die, we use object allocation as >> a proxy, assuming that on average A bytes die for every B bytes allocated >> and make an informed (and adjusted) guess as to what the A/B ratio might >> be. That is the basis for the GC clock. >> Buffer memory is indeed treated differently and does not advance the GC >> clock as far as I can tell. Presumably the reasoning is that buffer size >> changes make a poor proxy for object deaths. > > Perhaps we could look at it differently: what are the failure modes for n= ot > increasing the tally. > > For strings, one could allocate a handful of very long strings, taking up > a lot of memory, and if the consing tally did not take into account the > lengths of the strings, the GC might never start, and we die of OOM. > > For vectors, it almost looks different (the contained values are already > counted, and they'd usually be larger than the memory taken by one cell), > but then you could put many copies of the same value (could even be nil) > into a large vector, and we're back to the same problem. > > Could we do something like that with a hash-table? Probably not - the > hashing should at least guarantee 'eq' uniqueness. But then I suppose > someone could create an empty hash-table of a very large size. If the > internal vectors are pre-allocated, that could have the same effect as > the above. > > The same reasoning could work for buffers too, but are they actually > garbage-collected? > >> Of course we could reason that growing an existing hash table is also >> a bad proxy for object deaths, but the evidence for that is weak so I us= ed >> the same metric as for other data structures just to be on the safe side. >> >> This reminds me that the `gcstat` bookkeeping should probably include the >> hash-table ancillary arrays as well, since those counters are used to >> adjust the GC clock (see total_bytes_of_live_objects and >> consing_threshold). Will fix! >>=20 >>> It's great that the new hash tables are garbage-collected more easily a= nd >>> produce less garbage overall, but in a real program any GC cycle will >>> have to traverse the other data structures anyway. So we might be leavi= ng >>> free performance gains on the table when we induce GC cycles while no >>> managed allocations are done. I could be missing something, of course. >> So could I, and please know that your questions are much appreciated. Are >> you satisfied by my replies above, or did I misunderstand your concerns? > > Thank you. I hope I'm not too off mark with my reasoning.