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: weak hash tables Date: Fri, 05 Jul 2024 05:50:28 +0200 Message-ID: References: <-plQctKgNkvp-LJ9ov2QAiXQKxd9V-hI0yz_opRGxQtbknubCjH4rH2-ymgbw_Qr1ZhB1rtlmiEW8XtuIVNr7nR_Yj20AH6WkH6kUGp68g0=@protonmail.com> <_mNcR6ailVKpYHLxgfo_tJlYGeR0AQIzQWluspYYp5_g5pIIKkHLNfFkklQQgOKNiVW8jn8NS3i2dJ7_B2Qyx9v-Dq3MQ9mP8HNL30UWsqY=@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="7328"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: Helmut Eller , Eli Zaretskii , Emacs Devel To: Pip Cet Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Fri Jul 05 05:51:31 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 1sPZyt-0001iQ-ES for ged-emacs-devel@m.gmane-mx.org; Fri, 05 Jul 2024 05:51:31 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1sPZy0-0003ux-3C; Thu, 04 Jul 2024 23:50:36 -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 1sPZxz-0003ua-2d for emacs-devel@gnu.org; Thu, 04 Jul 2024 23:50:35 -0400 Original-Received: from mail-ej1-x62d.google.com ([2a00:1450:4864:20::62d]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1sPZxx-0006SW-9B; Thu, 04 Jul 2024 23:50:34 -0400 Original-Received: by mail-ej1-x62d.google.com with SMTP id a640c23a62f3a-a77c2d89af8so88735666b.2; Thu, 04 Jul 2024 20:50:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1720151430; x=1720756230; 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=xqVUCKS22d5B5dEwv3oCVm9b/7/GE22zmVvK6A/tn4w=; b=NvQG2ZcnJuVACyyZzDCVhR6/sk8o91vXRsWV+dh8MwYRHeR0UOtT1g6xwp13kX1XJZ FdP0tbATNOeLDzAg3XN+4G6Rqs1J0btCAyfTsPwdvXEyzi5idCEr4YJywhy2gttEXl24 yo2B+k1TqWUqQoIol3CpdpGJMCm1LQblVbCGhTX8K+U5phH6jiS/KyB3if75+LO3FaXC O/mzmYskoH0KYE2AhEwaCPSL3cJfQ6vcjRBluSfULGOqWT+4cpwxq7Qu3KH+BbgmOSA/ tKdrK0ca/CJURpCx+ty1qostHVtk7v1FRx22wsWJLehuoEBHlLSBgS+q7sffIfk22vsl fe2g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1720151430; x=1720756230; 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=xqVUCKS22d5B5dEwv3oCVm9b/7/GE22zmVvK6A/tn4w=; b=CcdCjtNanmxjfsaGeyi3KdGdMbODexR0MhLwFYtxC4K4DULmD5gf5cf1x6659JFXOm W7JAr5Y6a3vOEzrAP33dW5OLzsPB+dAl7Jqwz+sBoi81cGjiOqMFQsOwirp1fBlqm0N8 xIhh74uqKxx5t58Orp5O0WKrZO0O1otso23pltoLz0S97+KPVXuDckaTrxQsBX0Hs8rx rAqoirzNbHLrRD2FhnFa3VYbOaIP5w36PGEwqwid2c6dmnd8TmQ8u04WKFlLWfphQ/2A HysB1l2ADiQTVC2ZBqco63UBGfZH0fMKPA4/ZmfF0nsPsVtyAxwgdoH7KG/S7PiwrXzd q0BA== X-Forwarded-Encrypted: i=1; AJvYcCVPOzCecsrXZDK4iy/AZnppzZ3ks5d99Sqog7BA0uV4QANLorxTRgmRmXKOMrUbXBgVFhfSRvKZDyjEmIJAA80XwnnMdq6nSbWNDWyxH8zwEgY= X-Gm-Message-State: AOJu0Yzkkmxe8yqKU4y0+3IYwyZf9E7CFD8+4mS6UobPFOPlfobumWce Y+fum3QE9gMeoliVLTV+kx8KOXIK8/ptS8ErhcBffQYx6A40esi8IOm4vg== X-Google-Smtp-Source: AGHT+IEk+6kYl3avGkxAty5ZTPHsz/XIqSi0zNHIzhwYOSzP0o4bhcYJ3TO4nzItoQ57/kMsdDZxtw== X-Received: by 2002:a17:906:31c1:b0:a75:115a:25d0 with SMTP id a640c23a62f3a-a77ba70a896mr195352566b.50.1720151430201; Thu, 04 Jul 2024 20:50:30 -0700 (PDT) Original-Received: from pro2.fritz.box (p4fe3a3bd.dip0.t-ipconnect.de. [79.227.163.189]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a77cfa7359bsm9702166b.7.2024.07.04.20.50.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 04 Jul 2024 20:50:29 -0700 (PDT) In-Reply-To: (Pip Cet's message of "Thu, 04 Jul 2024 20:05:19 +0000") Received-SPF: pass client-ip=2a00:1450:4864:20::62d; envelope-from=gerd.moellmann@gmail.com; helo=mail-ej1-x62d.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:321366 Archived-At: Pip Cet writes: >> Ah, I thought what you wrote in the other mail was related to the >> IA-32 software emulation shit^Wrequirement, sorry. > > It's both: > > 1. change the IGC header to be a uint64_t, because bitfields don't always behave as expected. > 2. use the low-order bits to distinguish extended external extra dependency headers from ordinary one-word headers. (This fixes the remaining IA32 bug) > 3. keep track of an extra dependency (or a hash table thereof) in the exthdr > 4. implement key-or-value weakness > 5. implement two-stage finalization and get rid of SPLAT_PVEC > 6. give all objects an IGC header (which is now just a struct { uint64_t }) and get rid of igc_has_header > 7. use two-stage finalization to shrink weak hash tables which lose their contents > > I've done (1)-(4) and (5) for bignums. It all seems to work, though two-stage finalization really is in two stages: you've got to collect several times until the bignums are actually freed. > > I'll be honest, this is mostly to see (a) whether MPS can do it (it > can!) and (b) for some Ideas I Have which probably won't ever come to > fruition. The idea here is that every object (even conses) can keep > alive an extra object (which, in turn, can keep alive other objects) > while it is allocated (not just while it is reachable). No extra > memory is used until the extra object actually becomes non-nil, which > doesn't happen, for bignums, until they become unreachable. Once > they're deallocated, the extra object possibly becomes unreachable, so > it's queued for finalization, which it does by freeing the bignum > PVEC's exthdr and the bignum data itself. Thanks for the overview. > >> > So if we (puthash a b key-or-value-hash), we'd make `a' keep alive` b' >> > and vice versa, but once they're no longer strongly reachable from >> > other objects, they'd be collected. (I've tried this, it works). >> > >> > And we could finalize objects appearing in weak hash tables. >> > >> > This would cause some memory fragmentation (xmalloc isn't moving), but >> > I don't think that's much of an issue: if you're using exotic weak >> > hashes, you're already creating unmovable allocations in >> > weak_hash_pool; if you're debugging, you probably don't care. >> > >> > However, the functional gains are minimal and so far no one has >> > demanded key-or-value hashes... >> >> This all gets rather complicated :-/. I'm depressed. > > I do realize it's very complicated. As I said, it's about a Big Idea > that I had a while ago, but which I couldn't implement back then > because mark-and-sweep GC made it impossible. I'm still trying to > think of a way to use the external header to find and store retaining > paths... > > I'm attaching the (ugly bit manipulation) code just in case I've > convinced you, but I've got to admit I'm not fully convinced myself. > I've got to sleep over it. Feel free, of course, not to read it :-) I have read it, as far as I can read patches which I'm not good at. And I find it ugly and one could encapsulate things so nicely in C++, but I digress :-). Maybe this will surprise you, but probably not: I'd say put it in if you decide you want to after sleeping over it. I hate giving advice (and I'm sometimes lying), but in this case I can only say follow your ideas and have fun. Don't wait until you're 70. If my MPS experiment was good only for that purpose, it was worth it for me. Honesty demands that I add that that would also be good for me: I said right from the start that I won't maintain _anything_ and lately that I really really feel I need to have a break from this MPS stuff, so I'd love if you could take over and realize yoiur ideas. As usual my 2 cents. Thanks for your work!