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.bugs Subject: bug#54698: Fwd: GC mark stack Date: Mon, 27 Jun 2022 08:27:34 -0400 Message-ID: References: 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="33364"; mail-complaints-to="usenet@ciao.gmane.io" To: 54698@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Mon Jun 27 14:29:11 2022 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 1o5nra-0008SZ-Ly for geb-bug-gnu-emacs@m.gmane-mx.org; Mon, 27 Jun 2022 14:29:10 +0200 Original-Received: from localhost ([::1]:47914 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1o5nrZ-0002Xe-IV for geb-bug-gnu-emacs@m.gmane-mx.org; Mon, 27 Jun 2022 08:29:09 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:45556) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1o5nqU-0001Lf-TK for bug-gnu-emacs@gnu.org; Mon, 27 Jun 2022 08:28:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:56321) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1o5nqU-0004Gm-Ko for bug-gnu-emacs@gnu.org; Mon, 27 Jun 2022 08:28:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1o5nqU-0005Qy-Fl for bug-gnu-emacs@gnu.org; Mon, 27 Jun 2022 08:28:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Lynn Winebarger Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Mon, 27 Jun 2022 12:28:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54698 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch Original-Received: via spool by 54698-submit@debbugs.gnu.org id=B54698.165633287520869 (code B ref 54698); Mon, 27 Jun 2022 12:28:02 +0000 Original-Received: (at 54698) by debbugs.gnu.org; 27 Jun 2022 12:27:55 +0000 Original-Received: from localhost ([127.0.0.1]:50215 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o5nqM-0005QU-U6 for submit@debbugs.gnu.org; Mon, 27 Jun 2022 08:27:55 -0400 Original-Received: from mail-oi1-f171.google.com ([209.85.167.171]:45958) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o5nqJ-0005QF-I9 for 54698@debbugs.gnu.org; Mon, 27 Jun 2022 08:27:53 -0400 Original-Received: by mail-oi1-f171.google.com with SMTP id u9so12519575oiv.12 for <54698@debbugs.gnu.org>; Mon, 27 Jun 2022 05:27:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=l1FBo7BEBaG6oeH6/KwoM4pgDyHzRr9SOrv17NktjOU=; b=qSC3O7PxEUhMkk7Qf57uzPyFimJpCXAqdpGnbuY60I+00Zkq0aaYf49kv3BF7OlOB9 JfVO6FSFuu+LUqxlR8r8tVHIi3GaaUVeMaJ6IhCFU25HQCqIHzdEgvUAYw3XCbe7ttc0 ltPj92fycbdCnJiKrmwm5CmFwDwsqbFwLeVc5rAShk+Qozm/kmoCjKIdlWsW8uE8GXis 6i9994Iv88OLmAOqabznRBs55ZoZQ4wootQT7kx/iGwL4vVAHVr/2ZdAd+gy998L/eTY BT+GXiAV0gyAbpE8CI01B4KGzDWwbuCnelLjROH+/NvNAWCONsARiwr9+TbnakA8bYDw pjbQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=l1FBo7BEBaG6oeH6/KwoM4pgDyHzRr9SOrv17NktjOU=; b=IXRCf9NPcDnUUXZ2MD8b+cB9xipR96ZYMYorMmnjFG6tpd06ESnl3YkoFJZg2mdns+ td/jW1C+fBDsm5lbUZNdctSUiD4/Q+ksn2p6axD35agReRyyqkeE2xU0VmkO++/un902 R3xiTnRLqXndwNy3H/P+7U7n1/xreCeKt3qxrMVXFyYPWcZRVtmz5YizHVNkosSpN9Hx MO54CnfbcKdQExpmRPRZh7MseYXcdI6XYj3zNHREdCml7RDObv3CgtOyfvWcKzEbkOSg tlHqIhMJ0aaxN4NndHALHb7Tmw4qye8WVDGll3pFd/MD75dLjFALBKJCkQyN4cUXXUrf tdKw== X-Gm-Message-State: AJIora/0jwWM2bJWNlv4cE8PAosjno7dhvF12y4Qu3H5uppbe4wcr+cZ lP/uiuL+VHYtTaCwMcg5wg5Dcyq0bnXp+s3V3HBOlKUO X-Google-Smtp-Source: AGRyM1tsFeavtoguYjDZsvaENqQprjyOpu9G0lDbE6Ggp+FlL0oDO/hq8pKYTzFPDbkEkhl+SEkA/+3A6fSY5Yn87/A= X-Received: by 2002:a05:6808:1a96:b0:333:289e:713d with SMTP id bm22-20020a0568081a9600b00333289e713dmr7346388oib.247.1656332865374; Mon, 27 Jun 2022 05:27:45 -0700 (PDT) In-Reply-To: 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" Xref: news.gmane.io gmane.emacs.bugs:235441 Archived-At: This bug was archived, so I first sent the below to the emacs-devel list. I'm not sure what the best/most appropriate target is for the suggestion. Lynn ---------- Forwarded message --------- From: Lynn Winebarger Date: Sun, Jun 26, 2022 at 11:50 AM Subject: Re: GC mark stack To: emacs-devel On Sun, Jun 26, 2022 at 11:31 AM Lynn Winebarger wrote: > > 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. I should point out here, that with only strong references, there's only one SCC of interest (liveness) and the mark-bit is exactly the stack-traversal-ordering count I suggested as an alternative to keeping items on the stack as in the implementation described in the paper. For the more general problem of weak references, the algorithm requires explicitly tracking the SCC candidate sets and representatives. Those structures can also be "pre-allocated" in the weak reference objects if allocation during garbage collection is an issue. Lynn