From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Lynn Winebarger Newsgroups: gmane.emacs.devel Subject: Re: GC mark stack Date: Mon, 15 Aug 2022 13:52:23 -0400 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="34965"; mail-complaints-to="usenet@ciao.gmane.io" Cc: emacs-devel To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Mon Aug 15 19:54:50 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 1oNeIc-0008vq-MK for ged-emacs-devel@m.gmane-mx.org; Mon, 15 Aug 2022 19:54:50 +0200 Original-Received: from localhost ([::1]:60762 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oNeIb-0008Eb-0u for ged-emacs-devel@m.gmane-mx.org; Mon, 15 Aug 2022 13:54:49 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:52732) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oNeGW-0007NG-4g for emacs-devel@gnu.org; Mon, 15 Aug 2022 13:52:40 -0400 Original-Received: from mail-pj1-x1036.google.com ([2607:f8b0:4864:20::1036]:38767) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oNeGU-00045a-IG for emacs-devel@gnu.org; Mon, 15 Aug 2022 13:52:39 -0400 Original-Received: by mail-pj1-x1036.google.com with SMTP id q9-20020a17090a2dc900b001f58bcaca95so15105554pjm.3 for ; Mon, 15 Aug 2022 10:52:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc; bh=y9F7/w6293ZxAVhF2NkOeCuGTI2sIgYsoAPVNb8uuJ8=; b=cS3Q3quuIi3hEbG09cahgPBVfjhsSIEQSvmxJEUnH7i9ZYA3EMzI1Luio7YLd88tj+ BCy3UTobgOHXKG5fe6qP7gb1G+Z0KKEDcXiE5VecwpBXyqQexj81GYAx6jRkWPNGfosY 5ZPB0lJ27EanVxQG1F57SSAOt1VnL/UGUtobN15S0xtTc8oZ6bInhmHCBZBh7/bbgrSK hPwvAEOgi/gnMfg2n/phuX6ignJ9bON9d93EoC6vH4PvwMj67jg5D1Co26KRZYsaxj+E Rw4MtmgLVN9EiXJtf416dLLUyHpAAVIL33biM/xVRx46cSHTG2JQG+zEJ8/SU+Zg4GXY l3dQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc; bh=y9F7/w6293ZxAVhF2NkOeCuGTI2sIgYsoAPVNb8uuJ8=; b=lvHj3nRfrhviHHxWVxOQkZctqdS6BHxe5zGNN8Imrh3H/S05WslNjQeLlOinkvvR/r sfiQ44/C2L1WwRZH+Ymv0nRdcYi+LvPYZKF+nOUEw2jyChKVzqazcVqhYNtRL5V9ruVd JvcJR39Wj889EIeLLeyuJDXpvFzvk3VWNiJA7jDpcgrUFACsAXc4/7JwF8TsdhYBbXMc xvI/ss2FQbXTF/5EVYyW4OyXlAXWBVQR/MV9qMVgD+Eo0gvzz5x7r2EPAZw+ydCwDOuk sES9MFKBVJYdh8Wb6NKWUjHEW1We9+7kAnCAxgQ9u7Ora0tTw4hWkAv7iKffqfKXN4q5 j+mA== X-Gm-Message-State: ACgBeo2L/bv821bqw+4YdT6cg9U3078hmXH2MK8dLI8UG2nculO50IDg l+Tw4kr2sQc8bQJN662Ap2Si9KwILf8sJPqRXU3QKCwr X-Google-Smtp-Source: AA6agR7NInAM/5k/Cr8XkWeR6aGcxmBb/tRlPcSqJOog1ZISblJ8tFAO/Kdf1Zp9r3ukDI3X1++N1wvNf0ugyVhn+7k= X-Received: by 2002:a17:902:ce11:b0:172:6f2c:a910 with SMTP id k17-20020a170902ce1100b001726f2ca910mr6254214plg.156.1660585957060; Mon, 15 Aug 2022 10:52:37 -0700 (PDT) In-Reply-To: Received-SPF: pass client-ip=2607:f8b0:4864:20::1036; envelope-from=owinebar@gmail.com; helo=mail-pj1-x1036.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, 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:293485 Archived-At: On Mon, Aug 15, 2022 at 12:28 PM Stefan Monnier wrote: > > >> Are you talking about the code in `mark_and_sweep_weak_table_contents`= ? > >> Maybe the `do .. while` loop? > > That is exactly it. Some of my characterization of the mark-sweep > > algorithm (for non-weak references) in terms of SCC calculation was > > incorrect - I don't really think about this day-to-day anymore. But, > > This `do...while` loop can be a source of performance problems, indeed, > if we have many/large weak hash tables (i.e. many weak references) since > it's O(n=C2=B2) for `n` weak references. > > AFAIK, so far this has not been a problem (I suspect in practice it's > usually O(n) because we usually don't have many cycles between weak hash > tables), so any improvement would need to be "cheap" (both in terms of > code complexity and in terms of best-case CPU&heap cost). > > > But, you can certainly calculate the SCCs of the "weakly-references *" > > (Kleene * operation intended) relation while recursing the entries of > > a weak hash table in one pass > > I'm not sure that's the case because we don't know the full set of weak > references right from the start (or at least, in order to know the full > set, we'd have to traverse all the weak references before we know for > sure that they survive). 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. And that loop sure looks like it is calculating the transitive closure of such a relation. Perhaps the confusion is because any marking of non-weak-hash-table-entries done during the calculation of the weak-reference SCCs would only be to avoid infinite cycling, not for marking liveness? The only meaningful marking would be of weak hash table entries, with the traversal order/SCC representative. As I mentioned, I purposefully have not sat down and worked through the details required to construct the relational expression. Lynn