From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: GC mark stack Date: Mon, 15 Aug 2022 14:17:11 -0400 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="24091"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Cc: emacs-devel To: Lynn Winebarger Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Mon Aug 15 20:19:19 2022 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 1oNegF-0005u6-0d for ged-emacs-devel@m.gmane-mx.org; Mon, 15 Aug 2022 20:19:15 +0200 Original-Received: from localhost ([::1]:55160 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oNegD-0005J1-Jv for ged-emacs-devel@m.gmane-mx.org; Mon, 15 Aug 2022 14:19:13 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:57520) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oNeeL-00047Y-9L for emacs-devel@gnu.org; Mon, 15 Aug 2022 14:17:17 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:40193) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oNeeI-0007QP-MH for emacs-devel@gnu.org; Mon, 15 Aug 2022 14:17:16 -0400 Original-Received: from pmg2.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id 431998076F; Mon, 15 Aug 2022 14:17:13 -0400 (EDT) Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id 1540C8004C; Mon, 15 Aug 2022 14:17:12 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1660587432; bh=2j6ksg3tDc8pqhfE38wEOV/ph04lbd3c6EGyzv3e+iA=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=NB+8CuKjlXKISiNHBOXesLfe0eUIWGUUQ5srIcihf4VAIExDgt5cnZVMgxLOGAKyC 7jqsV77cISHKdjHt7hmtl+O4QLVGrtp4igk4b/2JobtNzrw1yHe3owgCt/RgrEf4n5 EipIIBgu0wLnDwdLGqSM284D5kU+L4IIH4RgeeM6hQ246vjPd+1B1lWeECyVfk64jr Xrjy5QJX6QmKpgD12L9M9NT6qbE0Z8WF2AI0o60Idfz6RVUYcPHafxJ4w1zp2iaNH3 As1ID9xT7/MJGGVby0fEsos176Wrqt7EjEQ2oes1BoBahZMGSDZ32twh7fu1XkeBBG AEuFzNbTUHm+g== Original-Received: from lechazo (lechon.iro.umontreal.ca [132.204.27.242]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 0348D12049B; Mon, 15 Aug 2022 14:17:12 -0400 (EDT) In-Reply-To: (Lynn Winebarger's message of "Mon, 15 Aug 2022 13:52:23 -0400") Received-SPF: pass client-ip=132.204.25.50; envelope-from=monnier@iro.umontreal.ca; helo=mailscanner.iro.umontreal.ca X-Spam_score_int: -42 X-Spam_score: -4.3 X-Spam_bar: ---- X-Spam_report: (-4.3 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 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" Xref: news.gmane.io gmane.emacs.devel:293487 Archived-At: > If the loop can be expressed by a relational expression consisting of > a concrete relation (like "references"), composition, union, and > transitive closure, then there is a systematic way to construct an > algorithm of the type I described. I think the core of the problem is the following: In a "key weak" hash table, if a reachable object points (transitively) to an object that is a key in that table, then the value associated with that key becomes reachable. So conceptually we have a reference (an edge) from the key *object* to the value, but this reference is not actually represented in the heap. More specifically, the code that does the marking (i.e. `mark_object`) only knows about the key object itself: it doesn't know that this object is a key in a weak hash table nor what is the associated value. We could try and reify those conceptual references, e.g. in some kind of auxiliary table, but the added cost of making `mark_object` consult this table for every object it marks (at least while marking weak-refs) seems prohibitive. Stefan