From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [63.128.21.124]) by sourceware.org (Postfix) with ESMTP id 3B9BD3836C44 for ; Mon, 4 Jan 2021 15:27:23 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 3B9BD3836C44 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-206-o32Ii2WbOOSKKa2UjcM8tQ-1; Mon, 04 Jan 2021 10:27:21 -0500 X-MC-Unique: o32Ii2WbOOSKKa2UjcM8tQ-1 Received: from smtp.corp.redhat.com (int-mx03.intmail.prod.int.phx2.redhat.com [10.5.11.13]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 3D26E800D55; Mon, 4 Jan 2021 15:27:20 +0000 (UTC) Received: from localhost.localdomain (ovpn-112-189.phx2.redhat.com [10.3.112.189]) by smtp.corp.redhat.com (Postfix) with ESMTP id DE8AA6091A; Mon, 4 Jan 2021 15:27:19 +0000 (UTC) Subject: Re: [08/23] Add an alternative splay tree implementation To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com References: <3068cea8-2188-83b4-0a8a-e27665e245af@redhat.com> From: Jeff Law Message-ID: Date: Mon, 4 Jan 2021 08:27:19 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.4.0 MIME-Version: 1.0 In-Reply-To: X-Scanned-By: MIMEDefang 2.79 on 10.5.11.13 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Content-Language: en-US X-Spam-Status: No, score=-5.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, NICE_REPLY_A, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, 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: Mon, 04 Jan 2021 15:27:24 -0000 On 12/16/20 5:29 PM, Richard Sandiford wrote: > 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.  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).  Is there any chance we >> could convert those two users to the new one?  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 “get or insert” type operations. Would it be OK to wait until GCC 12 > stage 1 for that? Yea, at this point deferring the conversion to gcc-12 seems to make the most sense. jeff