From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id A4F223857C65 for ; Thu, 17 Dec 2020 00:29:56 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org A4F223857C65 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 5640C31B; Wed, 16 Dec 2020 16:29:56 -0800 (PST) Received: from localhost (e121540-lin.manchester.arm.com [10.32.98.126]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id C55F73F718; Wed, 16 Dec 2020 16:29:55 -0800 (PST) From: Richard Sandiford To: Jeff Law Mail-Followup-To: Jeff Law , gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Cc: gcc-patches@gcc.gnu.org Subject: Re: [08/23] Add an alternative splay tree implementation References: <3068cea8-2188-83b4-0a8a-e27665e245af@redhat.com> Date: Thu, 17 Dec 2020 00:29:53 +0000 In-Reply-To: <3068cea8-2188-83b4-0a8a-e27665e245af@redhat.com> (Jeff Law's message of "Wed, 2 Dec 2020 13:36:17 -0700") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-6.4 required=5.0 tests=BAYES_00, KAM_DMARC_STATUS, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 17 Dec 2020 00:29:58 -0000 Jeff Law writes: > On 11/13/20 1:15 AM, Richard Sandiford via Gcc-patches wrote: >> We already have two splay tree implementations: the old C one in >> libiberty and a templated reimplementation of it in typed-splay-tree.h. >> However, they have some drawbacks: >> >> - They hard-code the assumption that nodes should have both a key and >> a value, which isn't always true. >> >> - They use the two-phase method of lookup, and so nodes need to store >> a temporary back pointer. We can avoid that overhead by using the >> top-down method (as e.g. the bitmap tree code already does). >> >> - The tree node has to own the key and the value. For some use cases >> it's more convenient to embed the tree links in the value instead. >> >> Also, a later patch wants to use splay trees to represent an >> adaptive total order: the splay tree itself records whether node N1 >> is less than node N2, and (in the worst case) comparing nodes is >> a splay operation. >> >> This patch therefore adds an alternative implementation. The main >> features are: >> >> - Nodes can optionally point back to their parents. >> >> - An Accessors class abstracts accessing child nodes and (where >> applicable) parent nodes, so that the information can be embedded >> in larger data structures. >> >> - There is no fixed comparison function at the class level. Instead, >> individual functions that do comparisons take a comparison function >> argument. >> >> - There are two styles of comparison function, optimised for different >> use cases. (See the comments in the patch for details.) >> >> - It's possible to do some operations directly on a given node, >> without knowing whether it's the root. This includes the comparison >> use case described above. >> >> This of course has its own set of drawbacks. It's really providing >> splay utility functions rather than a true ADT, and so is more low-level >> than the existing routines. It's mostly geared for cases in which the >> client code wants to participate in the splay operations to some extent. >> >> gcc/ >> * Makefile.in (OBJS): Add splay-tree-utils.o. >> * system.h: Include when INCLUDE_ARRAY is defined. >> * selftest.h (splay_tree_cc_tests): Declare. >> * selftest-run-tests.c (selftest::run_tests): Run splay_tree_cc_tests. >> * splay-tree-utils.h: New file. >> * splay-tree-utils.tcc: Likewise. >> * splay-tree-utils.cc: Likewise. > I must admit, I'm not a fan of adding another splay tree.=C2=A0 Though I > suspect the one in libiberty will be there forever since there could > well be clients outside our source base. > > The typed_splay_tree implementation however is internal to GCC and only > has a couple users (the JIT and fixit hints).=C2=A0 Is there any chance we > could convert those two users to the new one?=C2=A0 Your cover hints that= 's > not the case, but I'm going to explicitly ask :-) Yeah, I agree it's not great to have three versions. I had a look at converting the uses of typed_splay_tree, and all of them seem to be a natural fit for the new scheme. In particular, although typed_splay_tree maps keys to values, in practice the keys are already part of the values. However, I think a natural conversion would need a couple of new helpers for =E2=80=9Cget or insert=E2=80=9D type operations. Would it be OK to wai= t until GCC 12 stage 1 for that? Thanks, Richard