From: Jeff Law <law@redhat.com>
To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com
Subject: Re: [08/23] Add an alternative splay tree implementation
Date: Wed, 2 Dec 2020 13:36:17 -0700 [thread overview]
Message-ID: <3068cea8-2188-83b4-0a8a-e27665e245af@redhat.com> (raw)
In-Reply-To: <mptima98yfz.fsf@arm.com>
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 <array> 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 :-)
As for the implementation, I've got no real concerns there. If there's
issues, I'm sure you'll deal with them.
Jeff
next prev parent reply other threads:[~2020-12-02 20:36 UTC|newest]
Thread overview: 88+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-11-13 8:10 [00/23] Make fwprop use an on-the-side RTL SSA representation Richard Sandiford
2020-11-13 8:11 ` [01/23] vec: Silence clang warning Richard Sandiford
2020-11-25 19:58 ` Jeff Law
2020-11-13 8:12 ` [02/23] rtlanal: Remove noop_move_p REG_EQUAL condition Richard Sandiford
2020-11-25 20:00 ` Jeff Law
2020-11-13 8:12 ` [03/23] reginfo: Add a global_reg_set Richard Sandiford
2020-11-25 20:01 ` Jeff Law
2020-11-13 8:13 ` [04/23] Move iterator_range to a new iterator-utils.h file Richard Sandiford
2020-11-25 20:02 ` Jeff Law
2020-11-13 8:13 ` [05/23] Add more iterator utilities Richard Sandiford
2020-11-25 20:12 ` Jeff Law
2020-11-13 8:14 ` [06/23] Add an RAII class for managing obstacks Richard Sandiford
2020-11-25 20:15 ` Jeff Law
2020-11-13 8:14 ` [07/23] Add a class that multiplexes two pointer types Richard Sandiford
2020-11-25 20:23 ` Jeff Law
2020-11-26 16:15 ` Richard Sandiford
2020-11-30 1:28 ` Jeff Law
2020-11-25 23:33 ` Martin Sebor
2020-11-26 17:06 ` Richard Sandiford
2020-11-27 18:12 ` Richard Sandiford
2020-11-28 0:17 ` Martin Sebor
2020-12-17 0:17 ` Richard Sandiford
2020-12-17 14:21 ` Tom Tromey
2020-12-17 15:38 ` Richard Sandiford
2020-12-17 15:44 ` Nathan Sidwell
2021-01-04 15:32 ` Jeff Law
2020-11-13 8:15 ` [08/23] Add an alternative splay tree implementation Richard Sandiford
2020-12-02 20:36 ` Jeff Law [this message]
2020-12-17 0:29 ` Richard Sandiford
2021-01-04 15:27 ` Jeff Law
2021-01-01 8:25 ` Andreas Schwab
2021-01-04 14:53 ` Richard Sandiford
2021-01-04 15:02 ` Andreas Schwab
2021-01-04 15:42 ` Richard Sandiford
2021-01-05 12:13 ` Richard Biener
2020-11-13 8:15 ` [09/23] Add a cut-down version of std::span (array_slice) Richard Sandiford
2020-11-30 19:56 ` Jeff Law
2022-08-03 15:13 ` Martin Jambor
2022-08-03 15:31 ` Richard Sandiford
2022-08-10 16:03 ` Martin Jambor
2022-08-11 6:58 ` Richard Biener
2022-08-16 7:59 ` Richard Sandiford
2020-11-13 8:16 ` [10/23] Tweak the way that is_a is implemented Richard Sandiford
2020-12-02 5:15 ` Jeff Law
2020-11-13 8:16 ` [11/23] Split update_cfg_for_uncondjump out of combine Richard Sandiford
2020-11-30 6:14 ` Jeff Law
2020-11-13 8:17 ` [12/23] Export print-rtl.c:print_insn_with_notes Richard Sandiford
2020-11-25 20:24 ` Jeff Law
2020-11-13 8:18 ` [13/23] recog: Split out a register_asm_p function Richard Sandiford
2020-11-25 20:24 ` Jeff Law
2020-11-13 8:18 ` [14/23] simplify-rtx: Put simplify routines into a class Richard Sandiford
2020-11-30 19:54 ` Jeff Law
2020-11-13 8:19 ` [15/23] recog: Add a validate_change_xveclen function Richard Sandiford
2020-11-30 20:03 ` Jeff Law
2020-11-13 8:19 ` [16/23] recog: Add a way of temporarily undoing changes Richard Sandiford
2020-11-25 20:27 ` Jeff Law
2020-12-17 0:22 ` Richard Sandiford
2020-11-13 8:20 ` [17/23] recog: Add a class for propagating into insns Richard Sandiford
2020-12-03 22:32 ` Jeff Law
2020-11-13 8:20 ` [18/23] recog: Add an RAII class for undoing insn changes Richard Sandiford
2020-11-25 20:27 ` Jeff Law
2020-11-13 8:20 ` [19/23] rtlanal: Add some new helper classes Richard Sandiford
2020-12-13 17:30 ` Jeff Law
2020-12-14 16:37 ` Richard Sandiford
2020-12-14 20:02 ` Jeff Law
2020-11-13 8:21 ` [20/23] rtlanal: Add simple_regno_set Richard Sandiford
2020-11-25 20:31 ` Jeff Law
2020-12-17 0:47 ` Richard Sandiford
2021-01-04 15:28 ` Jeff Law
2020-11-13 8:22 ` [21/23] doc: Add documentation for rtl-ssa Richard Sandiford
2020-11-30 6:26 ` Jeff Law
2020-11-13 8:23 ` [PATCH 22/23] Add rtl-ssa Richard Sandiford
2020-12-16 3:31 ` Jeff Law
2020-12-17 0:33 ` Richard Sandiford
2020-12-19 20:01 ` Jeff Law
2020-11-13 8:24 ` [PATCH 23/23] fwprop: Rewrite to use RTL SSA Richard Sandiford
2020-12-16 3:52 ` Jeff Law
2020-12-17 0:34 ` Richard Sandiford
2020-11-25 19:58 ` [00/23] Make fwprop use an on-the-side RTL SSA representation Jeff Law
2020-11-26 16:03 ` Richard Sandiford
2020-11-27 15:56 ` Michael Matz
2020-11-27 16:31 ` Richard Sandiford
2020-11-30 21:13 ` Jeff Law
2020-12-01 0:03 ` Michael Matz
2020-12-01 10:15 ` Richard Sandiford
2020-12-02 0:25 ` Jeff Law
2020-11-30 6:45 ` Jeff Law
2020-11-30 14:12 ` Richard Sandiford
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=3068cea8-2188-83b4-0a8a-e27665e245af@redhat.com \
--to=law@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=richard.sandiford@arm.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).