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: GC mark stack Date: Sun, 26 Jun 2022 11:31:43 -0400 Message-ID: Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="3984"; mail-complaints-to="usenet@ciao.gmane.io" To: emacs-devel Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sun Jun 26 17:33:21 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 1o5UGH-0000w9-Bh for ged-emacs-devel@m.gmane-mx.org; Sun, 26 Jun 2022 17:33:21 +0200 Original-Received: from localhost ([::1]:56612 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1o5UGG-0007PO-5N for ged-emacs-devel@m.gmane-mx.org; Sun, 26 Jun 2022 11:33:20 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:47946) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1o5UEy-0006gJ-8m for emacs-devel@gnu.org; Sun, 26 Jun 2022 11:32:00 -0400 Original-Received: from mail-oi1-x22a.google.com ([2607:f8b0:4864:20::22a]:36356) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1o5UEv-0000Qs-Ne for emacs-devel@gnu.org; Sun, 26 Jun 2022 11:31:59 -0400 Original-Received: by mail-oi1-x22a.google.com with SMTP id y77so9934100oia.3 for ; Sun, 26 Jun 2022 08:31:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:from:date:message-id:subject:to; bh=1uoxx83Z3SUyYYs269UUdl/N+hVYaPPsJLvqVl8xBVo=; b=qkIHevLwG/G0pJQvY2G0c0WuMpMy3MoivfizH1ujrhGWcKu65vgpjn6olq9OkpIQLk VLvxkp32LdcW51dgdBzlLDyUjy+Vf2fbwh80PQuZDLu8/ddOtziJ/MTLtv74FriK/Hfp 33XSjC0YlVe1lvfw0WtW6fGbuc0vcWUEvcInkPzs4yaAa9Gvpj3BpRiEKtUTvmCOAvAn im/+J0A0H+1SSnNjorwyHPjEGkVDd6mndUboX79us59RTLZydKgSNbjUlCVoCzPp0alY xv/La2QmINEl4CWKJ3zFQgFv0HLCZk9k3w6lEUMJkOEbxQT8vCSaOSQ2049PScuJwLvr rSrA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=1uoxx83Z3SUyYYs269UUdl/N+hVYaPPsJLvqVl8xBVo=; b=sSVqI+CeOYJ6/lq207qVrR2f6DzxNJzpSVEQycf2kpvxhC2a2qn9jwYCXFn65i/RkX Qv3BqLGJHn7uYJkSEhvagXCECNCt556thkhLm8gXCrTBoSBOrqjAAkiDNcSBNij2yZ1w AGLXx2bVwLCUUFB1RsKfmYuNC+IWJOj4RogvCb5KYIHX3D0Hu35h47CwLF/Xb8aO6M23 SQCKGc9EM4LRfNZhmzBPDpIng1XTuyh8AQ/vM9mfytVq8sQpu8878dFJdXDM4mA6krqe qwnCdw77TdHp/c/O2oDEKsW3Rqm4aSYZasgqxnFYpXgEx6oFQdbx9qWCHfZH5Qpct+On d/+A== X-Gm-Message-State: AJIora8x9hAcjTvy2ydeFzkZ3UDCE+cF3exFnXR4OAodbyrUmW7lFueV HONr084Rls4/BDa8YPNqgxI5ddHQuu6nkBeYuXak1Jq+PoM= X-Google-Smtp-Source: AGRyM1sslxb+eAK+qLtd4VXPKf9zvHShHFCzLuiHABMcjp2rRw28dwizGBwyTb3dKMe/y8qPaPYg3lVr/pC9aFFvWGw= X-Received: by 2002:a05:6808:1a96:b0:333:289e:713d with SMTP id bm22-20020a0568081a9600b00333289e713dmr5280578oib.247.1656257515783; Sun, 26 Jun 2022 08:31:55 -0700 (PDT) Received-SPF: pass client-ip=2607:f8b0:4864:20::22a; envelope-from=owinebar@gmail.com; helo=mail-oi1-x22a.google.com X-Spam_score_int: -8 X-Spam_score: -0.9 X-Spam_bar: / X-Spam_report: (-0.9 / 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, URI_DOTEDU=1.246 autolearn=no 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:291634 Archived-At: I was reviewing alloc.c in the 28.1 source, and noted that it uses a semi-naive computation of the transitive closure of the graph of live data structures (weak hash tables is where I see it). Since the fix to https://debbugs.gnu.org/cgi/bugreport.cgi?bug=54698 (commit 7a8798de95a57c8ff85f070075e0a0176b458578) moved to using an explicit stack, I was curious if you'd considered using a variant of Tarjan's SCC algorithm, such as the one described in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.9019&rep=rep1&type=pdf , to guarantee that each edge is traversed at most once. The algorithm described never removes traversed objects from its stack (so it can tell when an object has already been traversed, even if the current link into it is not part of its SCC). The algorithm would only need to account for objects like weak hash tables, so a direct implementation would only leave those on the stack. An alternative would be to create an additional field in the objects (like weak hash table) recording the order in which they were traversed, which also makes the algorithm more efficient since there's no stack search involved when determining the SCC representative of particular node - it's just a matter of comparing their stack ordering. Of course, I don't have any idea how much time is spent on this type of recursion for weak references. The SCC-based algorithms can make a significant performance improvement compared to semi-naive calculation of transitive closure for general relational queries. It might not be so useful when you don't require an explicit enumeration of the set of answers. Lynn