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 12:28:17 -0400 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="37728"; 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 18:42:25 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 1oNdAX-0009dH-7s for ged-emacs-devel@m.gmane-mx.org; Mon, 15 Aug 2022 18:42:25 +0200 Original-Received: from localhost ([::1]:47434 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oNdAW-0007UI-09 for ged-emacs-devel@m.gmane-mx.org; Mon, 15 Aug 2022 12:42:24 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:34356) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oNcx4-0006S1-Vm for emacs-devel@gnu.org; Mon, 15 Aug 2022 12:28:32 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:21464) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oNcx2-0006p4-9f for emacs-devel@gnu.org; Mon, 15 Aug 2022 12:28:29 -0400 Original-Received: from pmg1.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id CDBB3100138; Mon, 15 Aug 2022 12:28:25 -0400 (EDT) Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 59BA510002A; Mon, 15 Aug 2022 12:28:20 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1660580900; bh=TREgIwU3IxVOJ57ANb0OxTDvEcBi9AQ6tpVrZTLUhGU=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=ObOhjQ1GaBzqGSdg3VrXIXFPkSTJ/rUdELpvxYFd9BeHCfdL0mxIIIybDG/TY32xM rykTfM8m3jE5wHB2r/wlpfcLUFS8d7xFw7edaBxz2KkwgDqjJF8pmaF/5pyriV9tgD NkEHTnSTAMsUqYrHgMc89HfHBk8C0tMOdIjBz4ph1sRw4VGglPHMbt/KTiVeariYJ9 PNBtjFjjURgLDtvw0CGbrI6Aav581Ub+mlL4YfKfy7NgfkXj4eJgeyC+B0EK2MSaUL v9r5Vsgehkk7odnacMeB4qtOoFTa6MYxOz0sQhATKIdH3+alU0c5JOeZQ50kML7Sts fQkVz4mLapkEg== Original-Received: from lechazo (lechon.iro.umontreal.ca [132.204.27.242]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 37C2D1203B8; Mon, 15 Aug 2022 12:28:20 -0400 (EDT) In-Reply-To: (Lynn Winebarger's message of "Mon, 15 Aug 2022 10:51:56 -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:293484 Archived-At: >> 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=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). Stefan