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: Sun, 26 Jun 2022 11:50:19 -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="9504"; 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:51:46 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 1o5UY6-0002KI-5Q for ged-emacs-devel@m.gmane-mx.org; Sun, 26 Jun 2022 17:51:46 +0200 Original-Received: from localhost ([::1]:40716 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1o5UY5-0000L1-12 for ged-emacs-devel@m.gmane-mx.org; Sun, 26 Jun 2022 11:51:45 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:50740) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1o5UWx-0007Xt-58 for emacs-devel@gnu.org; Sun, 26 Jun 2022 11:50:35 -0400 Original-Received: from mail-oa1-x2d.google.com ([2001:4860:4864:20::2d]:44802) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1o5UWu-00065t-5G for emacs-devel@gnu.org; Sun, 26 Jun 2022 11:50:34 -0400 Original-Received: by mail-oa1-x2d.google.com with SMTP id 586e51a60fabf-101e1a33fe3so10120228fac.11 for ; Sun, 26 Jun 2022 08:50:31 -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=3HqiM/0xEifvHeIVr0WjBUwO8IZzGBoemtj6dm+M+iQ=; b=R9CLHzXRdrzoLJrkF1uA+8A21fZIdFwm3QbOwOnHHB/6RCTGg/mfKSdupRDetFQkI5 u2nSVrMgcCmykOplAslizk1FBsEfGXbIwstn6SaImJOBw6sc/Z7Zd7NbhauAaEEP66+M 4CmtpXayM5NTc/kbj0S0cPGtWl7RDnOk4G/VB4grs3Z37oHwHTVd7p1/WlH0hIbKFoWr JVff8dp+aviqr19EglUuVr7NOQLhb7RDE8VnNBt0iIgpyuKko2XiwoSAmKvnsPelNRLr F7cs/K4jFW+iJllDus6DASEHGq//V12/UQuzdC0t41EgJuUOLxRNuaZIYhHpXdaWy+O5 raTw== 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=3HqiM/0xEifvHeIVr0WjBUwO8IZzGBoemtj6dm+M+iQ=; b=QnF2GrVfCLyEnEe6qUorrM2Ho0D7sfOVvPkWSknUGOM7eeYQwsS3N5HfgzOBef2Ink gHuo+H23aSvKzPQADDLyRN7mQm3meLZ5NQCj/IxGOpj9ZIGegUun+R9dkOWfltTioUYG fvN+lS3Ms/qg8R5aSp/xCppg0A7v8potwhKF/cmeIw1bhXtwFEPG8SczVDmER87W2f10 ZZoZthOfk3UxD3LTLer6XIcUOYwkUBiTOfKJGlXXfXAkAQTLwy3vWh2wGFgDLb7xm0QR qv/vloQA1MuiVgQa+/8odwfcwpHvDtVysOrzjX1prtFt/jFekcAs3SkI0nv4/kKPLWzv fotA== X-Gm-Message-State: AJIora8mP2YFkNwKQwCvyFFB0uS9+Jf1sGnVC4MBbZxX2t9Kn625Dmcb /X7CSFQJ6JNtfu7dnnoSuOtowQiBg2LmEng1/cVupeaQ X-Google-Smtp-Source: AGRyM1t+nZlC4ULjccD+Hrf2wundh/+r84RRobbZhgSa1CGNTg54zOo0d4v1ej72oIbVO1YR8u2+OkgHPdDV7JpAeNg= X-Received: by 2002:a05:6870:d791:b0:101:ad64:1e74 with SMTP id bd17-20020a056870d79100b00101ad641e74mr5233803oab.162.1656258629799; Sun, 26 Jun 2022 08:50:29 -0700 (PDT) In-Reply-To: Received-SPF: pass client-ip=2001:4860:4864:20::2d; envelope-from=owinebar@gmail.com; helo=mail-oa1-x2d.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:291636 Archived-At: 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