Re: [PATCH] Avoid excessive function type casts with splay-trees part 2
On June 15, 2018 8:07:44 PM GMT+02:00, Bernd Edlinger
wrote:
>On 06/15/18 09:07, Richard Biener wrote:
>> On Thu, 14 Jun 2018, Bernd Edlinger wrote:
>>
>>> On 06/14/18 15:43, Richard Biener wrote:
On Fri, 8 Jun 2018, Bernd Edlinger wrote:
> Hi!
>
>
> This patch converts the splay-tree internals into a template, and
>makes
> the typed_splay_tree template really type-safe. Previously
>everything
> would break apart if KEY_TYPE or VALUE_TYPE would not be pointer
>types.
> This limitation is now removed.
>
> I took the freedom to add a remove function which is only for
> completeness and test coverage, but not (yet) used in a productive
>way.
>
>
> Bootstrapped and reg-tested on x86_64-linux-gnu.
> Is it OK for trunk?
It looks OK to me but I wonder if we can avoid some of the code
duplication due to template instantiation by deriving from a
>non-templated
base class somehow? The cc1* binaries keep growing with more and
more template use :/
>>>
>>>
>>> No problem. The first version used an approach where splay-tree
>>> exposes an extended interface with a context pointer.
>>>
>>> See: https://gcc.gnu.org/ml/gcc-patches/2018-05/msg00178.html
>>>
>>> But it has also a limitation when the value or type is a class, it
>will
>>> not be possible to cast to uintptr_t, it will fail to compile, which
>is
>>> still an improvement since the current version just casts
>incompatible
>>> function pointers, and since I had to silence the
>-Wcast-function-type
>>> the warning would not help either.
>>>
>>>
>>> If you like the original patch better than the template, I can
>cleanup
>>> the original patch as an alternative?
>>
>> No, I like the template more but wondered if we can somehow outline
>> some of the main worker code?
>>
>
>The major difficulty with that are the splay_tree_compare_fn and
>splay_tree_delete_key/value_fn callbacks which don't pass a context
>value in addition to the splay_tree_key and splay_tree_value.
>
>I thought about passing a "glue" object which contains a context
>pointer together with the true key and/or value object, but I gave
>up when I saw this in splay_tree_insert:
>
> if (sp->root)
> comparison = (*sp->comp)(sp->root->key, key);
>
> if (sp->root && comparison == 0)
> {
> /* If the root of the tree already has the indicated KEY, just
> replace the value with VALUE. */
> if (sp->delete_value)
> (*sp->delete_value)(sp->root->value);
> sp->root->value = value;
> }
>
>There is a delete_key callback missing, and sp->root->key will not
>be updated. So the resource flow of the glue objects will not work.
>
>This code simply assumes that key equality implies pointer equality,
>or the key does not need to be freed after use, but this is not the
>case with glue objects.
>
>
>So, I don't see how to use the old code in a type-safe template without
>changing the C interface.
>
>Or maybe duplicating the C implementation...
>
>Currently there are not more than two or three uses of this
>template, so it will not be a big difference anyways.
>
>But shouldn't different template functions be folded together
>when the resulting code is identical?
>
>Or is there maybe another template where optimizing the code size
>would be more profitable?
>
>
>So, I would still prefer the splay tree template unless there is a
>better idea, how to proceed.
OK, thanks for having another look.
The patch is OK as-is.
Richard.
>
>Thanks
>Bernd.
Re: [PATCH] Avoid excessive function type casts with splay-trees part 2
On 6/15/18, Bernd Edlinger wrote:
> On 06/15/18 09:07, Richard Biener wrote:
>> On Thu, 14 Jun 2018, Bernd Edlinger wrote:
>>
>>> On 06/14/18 15:43, Richard Biener wrote:
On Fri, 8 Jun 2018, Bernd Edlinger wrote:
> Hi!
>
>
> This patch converts the splay-tree internals into a template, and
> makes
> the typed_splay_tree template really type-safe. Previously everything
> would break apart if KEY_TYPE or VALUE_TYPE would not be pointer
> types.
> This limitation is now removed.
>
> I took the freedom to add a remove function which is only for
> completeness and test coverage, but not (yet) used in a productive
> way.
>
>
> Bootstrapped and reg-tested on x86_64-linux-gnu.
> Is it OK for trunk?
It looks OK to me but I wonder if we can avoid some of the code
duplication due to template instantiation by deriving from a
non-templated
base class somehow? The cc1* binaries keep growing with more and
more template use :/
>>>
>>>
>>> No problem. The first version used an approach where splay-tree
>>> exposes an extended interface with a context pointer.
>>>
>>> See: https://gcc.gnu.org/ml/gcc-patches/2018-05/msg00178.html
>>>
>>> But it has also a limitation when the value or type is a class, it will
>>> not be possible to cast to uintptr_t, it will fail to compile, which is
>>> still an improvement since the current version just casts incompatible
>>> function pointers, and since I had to silence the -Wcast-function-type
>>> the warning would not help either.
>>>
>>>
>>> If you like the original patch better than the template, I can cleanup
>>> the original patch as an alternative?
>>
>> No, I like the template more but wondered if we can somehow outline
>> some of the main worker code?
>>
>
> The major difficulty with that are the splay_tree_compare_fn and
> splay_tree_delete_key/value_fn callbacks which don't pass a context
> value in addition to the splay_tree_key and splay_tree_value.
>
> I thought about passing a "glue" object which contains a context
> pointer together with the true key and/or value object, but I gave
> up when I saw this in splay_tree_insert:
>
> if (sp->root)
> comparison = (*sp->comp)(sp->root->key, key);
>
>if (sp->root && comparison == 0)
> {
>/* If the root of the tree already has the indicated KEY, just
> replace the value with VALUE. */
>if (sp->delete_value)
> (*sp->delete_value)(sp->root->value);
>sp->root->value = value;
> }
>
> There is a delete_key callback missing, and sp->root->key will not
> be updated. So the resource flow of the glue objects will not work.
>
> This code simply assumes that key equality implies pointer equality,
> or the key does not need to be freed after use, but this is not the
> case with glue objects.
>
>
> So, I don't see how to use the old code in a type-safe template without
> changing the C interface.
>
> Or maybe duplicating the C implementation...
>
> Currently there are not more than two or three uses of this
> template, so it will not be a big difference anyways.
>
> But shouldn't different template functions be folded together
> when the resulting code is identical?
>
> Or is there maybe another template where optimizing the code size
> would be more profitable?
>
>
> So, I would still prefer the splay tree template unless there is a
> better idea, how to proceed.
>
>
While you're looking at changing splay trees, could you take a look at
bug 30920, too? It's also about splay trees:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30920
Just an idea.
Thanks!
> Thanks
> Bernd.
>
Re: [PATCH] Avoid excessive function type casts with splay-trees part 2
On 06/15/18 09:07, Richard Biener wrote:
> On Thu, 14 Jun 2018, Bernd Edlinger wrote:
>
>> On 06/14/18 15:43, Richard Biener wrote:
>>> On Fri, 8 Jun 2018, Bernd Edlinger wrote:
>>>
Hi!
This patch converts the splay-tree internals into a template, and makes
the typed_splay_tree template really type-safe. Previously everything
would break apart if KEY_TYPE or VALUE_TYPE would not be pointer types.
This limitation is now removed.
I took the freedom to add a remove function which is only for
completeness and test coverage, but not (yet) used in a productive way.
Bootstrapped and reg-tested on x86_64-linux-gnu.
Is it OK for trunk?
>>>
>>> It looks OK to me but I wonder if we can avoid some of the code
>>> duplication due to template instantiation by deriving from a non-templated
>>> base class somehow? The cc1* binaries keep growing with more and
>>> more template use :/
>>>
>>
>>
>> No problem. The first version used an approach where splay-tree
>> exposes an extended interface with a context pointer.
>>
>> See: https://gcc.gnu.org/ml/gcc-patches/2018-05/msg00178.html
>>
>> But it has also a limitation when the value or type is a class, it will
>> not be possible to cast to uintptr_t, it will fail to compile, which is
>> still an improvement since the current version just casts incompatible
>> function pointers, and since I had to silence the -Wcast-function-type
>> the warning would not help either.
>>
>>
>> If you like the original patch better than the template, I can cleanup
>> the original patch as an alternative?
>
> No, I like the template more but wondered if we can somehow outline
> some of the main worker code?
>
The major difficulty with that are the splay_tree_compare_fn and
splay_tree_delete_key/value_fn callbacks which don't pass a context
value in addition to the splay_tree_key and splay_tree_value.
I thought about passing a "glue" object which contains a context
pointer together with the true key and/or value object, but I gave
up when I saw this in splay_tree_insert:
if (sp->root)
comparison = (*sp->comp)(sp->root->key, key);
if (sp->root && comparison == 0)
{
/* If the root of the tree already has the indicated KEY, just
replace the value with VALUE. */
if (sp->delete_value)
(*sp->delete_value)(sp->root->value);
sp->root->value = value;
}
There is a delete_key callback missing, and sp->root->key will not
be updated. So the resource flow of the glue objects will not work.
This code simply assumes that key equality implies pointer equality,
or the key does not need to be freed after use, but this is not the
case with glue objects.
So, I don't see how to use the old code in a type-safe template without
changing the C interface.
Or maybe duplicating the C implementation...
Currently there are not more than two or three uses of this
template, so it will not be a big difference anyways.
But shouldn't different template functions be folded together
when the resulting code is identical?
Or is there maybe another template where optimizing the code size
would be more profitable?
So, I would still prefer the splay tree template unless there is a
better idea, how to proceed.
Thanks
Bernd.
Re: [PATCH] Avoid excessive function type casts with splay-trees part 2
On Thu, 14 Jun 2018, Bernd Edlinger wrote: > On 06/14/18 15:43, Richard Biener wrote: > > On Fri, 8 Jun 2018, Bernd Edlinger wrote: > > > >> Hi! > >> > >> > >> This patch converts the splay-tree internals into a template, and makes > >> the typed_splay_tree template really type-safe. Previously everything > >> would break apart if KEY_TYPE or VALUE_TYPE would not be pointer types. > >> This limitation is now removed. > >> > >> I took the freedom to add a remove function which is only for > >> completeness and test coverage, but not (yet) used in a productive way. > >> > >> > >> Bootstrapped and reg-tested on x86_64-linux-gnu. > >> Is it OK for trunk? > > > > It looks OK to me but I wonder if we can avoid some of the code > > duplication due to template instantiation by deriving from a non-templated > > base class somehow? The cc1* binaries keep growing with more and > > more template use :/ > > > > > No problem. The first version used an approach where splay-tree > exposes an extended interface with a context pointer. > > See: https://gcc.gnu.org/ml/gcc-patches/2018-05/msg00178.html > > But it has also a limitation when the value or type is a class, it will > not be possible to cast to uintptr_t, it will fail to compile, which is > still an improvement since the current version just casts incompatible > function pointers, and since I had to silence the -Wcast-function-type > the warning would not help either. > > > If you like the original patch better than the template, I can cleanup > the original patch as an alternative? No, I like the template more but wondered if we can somehow outline some of the main worker code? Thanks, Richard.
Re: [PATCH] Avoid excessive function type casts with splay-trees part 2
On 06/14/18 15:43, Richard Biener wrote: > On Fri, 8 Jun 2018, Bernd Edlinger wrote: > >> Hi! >> >> >> This patch converts the splay-tree internals into a template, and makes >> the typed_splay_tree template really type-safe. Previously everything >> would break apart if KEY_TYPE or VALUE_TYPE would not be pointer types. >> This limitation is now removed. >> >> I took the freedom to add a remove function which is only for >> completeness and test coverage, but not (yet) used in a productive way. >> >> >> Bootstrapped and reg-tested on x86_64-linux-gnu. >> Is it OK for trunk? > > It looks OK to me but I wonder if we can avoid some of the code > duplication due to template instantiation by deriving from a non-templated > base class somehow? The cc1* binaries keep growing with more and > more template use :/ > No problem. The first version used an approach where splay-tree exposes an extended interface with a context pointer. See: https://gcc.gnu.org/ml/gcc-patches/2018-05/msg00178.html But it has also a limitation when the value or type is a class, it will not be possible to cast to uintptr_t, it will fail to compile, which is still an improvement since the current version just casts incompatible function pointers, and since I had to silence the -Wcast-function-type the warning would not help either. If you like the original patch better than the template, I can cleanup the original patch as an alternative? Thanks Bernd.
Re: [PATCH] Avoid excessive function type casts with splay-trees part 2
On Fri, 8 Jun 2018, Bernd Edlinger wrote: > Hi! > > > This patch converts the splay-tree internals into a template, and makes > the typed_splay_tree template really type-safe. Previously everything > would break apart if KEY_TYPE or VALUE_TYPE would not be pointer types. > This limitation is now removed. > > I took the freedom to add a remove function which is only for > completeness and test coverage, but not (yet) used in a productive way. > > > Bootstrapped and reg-tested on x86_64-linux-gnu. > Is it OK for trunk? It looks OK to me but I wonder if we can avoid some of the code duplication due to template instantiation by deriving from a non-templated base class somehow? The cc1* binaries keep growing with more and more template use :/ Thanks, Richard.
Re: [PATCH] Avoid excessive function type casts with splay-trees part 2
On Fri, 2018-06-08 at 20:41 +, Bernd Edlinger wrote: > On 06/08/18 16:28, David Malcolm wrote: > > On Fri, 2018-06-08 at 14:03 +, Bernd Edlinger wrote: > > > Hi! > > > > > > > > > This patch converts the splay-tree internals into a template, and > > > makes > > > the typed_splay_tree template really type-safe. Previously > > > everything > > > would break apart if KEY_TYPE or VALUE_TYPE would not be pointer > > > types. > > > This limitation is now removed. > > > > > > I took the freedom to add a remove function which is only for > > > completeness and test coverage, but not (yet) used in a > > > productive > > > way. > > > > > > > > > Bootstrapped and reg-tested on x86_64-linux-gnu. > > > Is it OK for trunk? > > > > Was this testing done with "jit" enabled? (there's some usage of > > typed_splay_tree there, for jit's equivalent of switch statements) > > > > Note that the jit frontend isn't covered by "all" in --enable- > > languages; it has to be added manually, iirc since it requires -- > > enable-host-shared. > > > > Yes, good point. I repeated the test with --enable-host-shared > and all jit tests did pass. Thanks! Dave
Re: [PATCH] Avoid excessive function type casts with splay-trees part 2
On 06/08/18 16:28, David Malcolm wrote: > On Fri, 2018-06-08 at 14:03 +, Bernd Edlinger wrote: >> Hi! >> >> >> This patch converts the splay-tree internals into a template, and >> makes >> the typed_splay_tree template really type-safe. Previously >> everything >> would break apart if KEY_TYPE or VALUE_TYPE would not be pointer >> types. >> This limitation is now removed. >> >> I took the freedom to add a remove function which is only for >> completeness and test coverage, but not (yet) used in a productive >> way. >> >> >> Bootstrapped and reg-tested on x86_64-linux-gnu. >> Is it OK for trunk? > > Was this testing done with "jit" enabled? (there's some usage of > typed_splay_tree there, for jit's equivalent of switch statements) > > Note that the jit frontend isn't covered by "all" in --enable- > languages; it has to be added manually, iirc since it requires -- > enable-host-shared. > Yes, good point. I repeated the test with --enable-host-shared and all jit tests did pass. Thanks Bernd. > Thanks > Dave >
Re: [PATCH] Avoid excessive function type casts with splay-trees part 2
On Fri, 2018-06-08 at 14:03 +, Bernd Edlinger wrote: > Hi! > > > This patch converts the splay-tree internals into a template, and > makes > the typed_splay_tree template really type-safe. Previously > everything > would break apart if KEY_TYPE or VALUE_TYPE would not be pointer > types. > This limitation is now removed. > > I took the freedom to add a remove function which is only for > completeness and test coverage, but not (yet) used in a productive > way. > > > Bootstrapped and reg-tested on x86_64-linux-gnu. > Is it OK for trunk? Was this testing done with "jit" enabled? (there's some usage of typed_splay_tree there, for jit's equivalent of switch statements) Note that the jit frontend isn't covered by "all" in --enable- languages; it has to be added manually, iirc since it requires -- enable-host-shared. Thanks Dave
[PATCH] Avoid excessive function type casts with splay-trees part 2
Hi!
This patch converts the splay-tree internals into a template, and makes
the typed_splay_tree template really type-safe. Previously everything
would break apart if KEY_TYPE or VALUE_TYPE would not be pointer types.
This limitation is now removed.
I took the freedom to add a remove function which is only for
completeness and test coverage, but not (yet) used in a productive way.
Bootstrapped and reg-tested on x86_64-linux-gnu.
Is it OK for trunk?
Thanks
Bernd.
2018-06-08 Bernd Edlinger
* typed-splay-tree.h (typed_splay_tree::remove): New function.
(typed_splay_tree::closure,
typed_splay_tree::inner_foreach_fn, typed_splay_tree::m_inner): Deleted.
(typed_splay_tree::typed_splay_tree,
typed_splay_tree::operator =): Declared private.
(typed_splay_tree::splay_tree_key, typed_splay_tree::splay_tree_value,
typed_splay_tree::splay_tree_node_s, typed_splay_tree::KDEL,
typed_splay_tree::VDEL, typed_splay_tree::splay_tree_delete_helper,
typed_splay_tree::rotate_left, typed_splay_tree::rotate_right,
typed_splay_tree::splay_tree_splay,
typed_splay_tree::splay_tree_foreach_helper,
typed_splay_tree::splay_tree_insert,
typed_splay_tree::splay_tree_remove,
typed_splay_tree::splay_tree_lookup,
typed_splay_tree::splay_tree_predecessor,
typed_splay_tree::splay_tree_successor,
typed_splay_tree::splay_tree_min,
typed_splay_tree::splay_tree_max): Took over from splay-tree.c/.h.
(typed_splay_tree::root, typed_splay_tree::comp,
typed_splay_tree::delete_key,
typed_splay_tree::delete_value): New data members.
* typed-splay-tree.c (selftest::test_str_to_int): Add a test for
typed_splay_tree::remove.
Index: gcc/typed-splay-tree.c
===
--- gcc/typed-splay-tree.c (revision 260952)
+++ gcc/typed-splay-tree.c (working copy)
@@ -47,7 +47,10 @@ test_str_to_int ()
t.insert ("a", 1);
t.insert ("b", 2);
t.insert ("c", 3);
+ t.insert ("d", 4);
+ t.remove ("d");
+
ASSERT_EQ (1, t.lookup ("a"));
ASSERT_EQ (2, t.lookup ("b"));
ASSERT_EQ (3, t.lookup ("c"));
Index: gcc/typed-splay-tree.h
===
--- gcc/typed-splay-tree.h (revision 260952)
+++ gcc/typed-splay-tree.h (working copy)
@@ -20,8 +20,6 @@ along with GCC; see the file COPYING3. If not see
#ifndef GCC_TYPED_SPLAY_TREE_H
#define GCC_TYPED_SPLAY_TREE_H
-#include "splay-tree.h"
-
/* Typesafe wrapper around libiberty's splay-tree.h. */
template
class typed_splay_tree
@@ -44,27 +42,66 @@ class typed_splay_tree
value_type predecessor (key_type k);
value_type successor (key_type k);
void insert (key_type k, value_type v);
+ void remove (key_type k);
value_type max ();
value_type min ();
int foreach (foreach_fn, void *);
private:
- /* Helper type for typed_splay_tree::foreach. */
- struct closure
- {
-closure (foreach_fn outer_cb, void *outer_user_data)
-: m_outer_cb (outer_cb), m_outer_user_data (outer_user_data) {}
+ /* Copy and assignment ops are not supported. */
+ typed_splay_tree (const typed_splay_tree &);
+ typed_splay_tree & operator = (const typed_splay_tree &);
-foreach_fn m_outer_cb;
-void *m_outer_user_data;
+ typedef key_type splay_tree_key;
+ typedef value_type splay_tree_value;
+
+ /* The nodes in the splay tree. */
+ struct splay_tree_node_s {
+/* The key. */
+splay_tree_key key;
+
+/* The value. */
+splay_tree_value value;
+
+/* The left and right children, respectively. */
+splay_tree_node_s *left, *right;
+
+/* Used as temporary value for tree traversals. */
+splay_tree_node_s *back;
};
+ typedef splay_tree_node_s *splay_tree_node;
- static int inner_foreach_fn (splay_tree_node node, void *user_data);
+ inline void KDEL (splay_tree_key);
+ inline void VDEL (splay_tree_value);
+ void splay_tree_delete_helper (splay_tree_node);
+ static inline void rotate_left (splay_tree_node *,
+ splay_tree_node, splay_tree_node);
+ static inline void rotate_right (splay_tree_node *,
+ splay_tree_node, splay_tree_node);
+ void splay_tree_splay (splay_tree_key);
+ static int splay_tree_foreach_helper (splay_tree_node,
+ foreach_fn, void*);
+ splay_tree_node splay_tree_insert (splay_tree_key, splay_tree_value);
+ void splay_tree_remove (splay_tree_key key);
+ splay_tree_node splay_tree_lookup (splay_tree_key key);
+ splay_tree_node splay_tree_predecessor (splay_tree_key);
+ splay_tree_node splay_tree_successor (splay_tree_key);
+ splay_tree_node splay_tree_max ();
+ splay_tree_node splay_tree_min ();
static value_type node_to_value (splay_tree_node node);
- private:
- ::splay_tree m_inner;
+ /* The root of the tree. */
+ splay_tree_node root;
+
+ /* The comparision function. */
+ compare_fn comp;
+
+ /* The
