[PATCH][RFC] Improve get_qualified_type linear list walk

[PATCH][RFC] Improve get_qualified_type linear list walk

[Richard Biener]

The following makes the C++ FEs heavy use of build_qualified_type
cheaper.  When looking at a tramp3d -fsyntax-only compile you can
see that for 470.000 build_qualified_type calls we end up
with 9.492.205 calls to check_qualified_type (thus we visit around
20 variant type candidates) ending up finding it in all but
15.300 cases that end up in build_variant_type_copy.

That's of course because the FE uses this machinery to do things like

bool
same_type_ignoring_top_level_qualifiers_p (tree type1, tree type2)
{
  if (type1 == error_mark_node || type2 == error_mark_node)
    return false;

  type1 = cp_build_qualified_type (type1, TYPE_UNQUALIFIED);
  type2 = cp_build_qualified_type (type2, TYPE_UNQUALIFIED);
  return same_type_p (type1, type2);

but so it be.  The improvement is to re-organize get_qualified_type
to put found type variants on the head of the variant list.  This
improves the number of calls to check_qualified_type to 1.215.030
thus around 2.5 candidates.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

Comments?  OK?

Richard.

2019-04-16  Richard Biener  <rguenther@suse.de>

	* tree.c (get_qualified_type): Put found type variants at the
	head of the variant list.

Index: gcc/tree.c
===================================================================
--- gcc/tree.c	(revision 270387)
+++ gcc/tree.c	(working copy)
@@ -6451,17 +6451,28 @@ check_aligned_type (const_tree cand, con
 tree
 get_qualified_type (tree type, int type_quals)
 {
-  tree t;
-
   if (TYPE_QUALS (type) == type_quals)
     return type;
 
+  tree mv = TYPE_MAIN_VARIANT (type);
+  if (check_qualified_type (mv, type, type_quals))
+    return mv;
+
   /* Search the chain of variants to see if there is already one there just
      like the one we need to have.  If so, use that existing one.  We must
      preserve the TYPE_NAME, since there is code that depends on this.  */
-  for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
-    if (check_qualified_type (t, type, type_quals))
-      return t;
+  for (tree *tp = &TYPE_NEXT_VARIANT (mv); *tp; tp = &TYPE_NEXT_VARIANT (*tp))
+    if (check_qualified_type (*tp, type, type_quals))
+      {
+	/* Put the found variant at the head of the variant list so
+	   frequently searched variants get found faster.  The C++ FE
+	   benefits greatly from this.  */
+	tree t = *tp;
+	*tp = TYPE_NEXT_VARIANT (t);
+	TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (mv);
+	TYPE_NEXT_VARIANT (mv) = t;
+	return t;
+      }
 
   return NULL_TREE;
 }

Re: [PATCH][RFC] Improve get_qualified_type linear list walk

[Michael Matz]

Hi,

On Tue, 16 Apr 2019, Richard Biener wrote:

> Comments?

I was quickly testing also with some early-outs but didn't get conclusive 
performance results (but really only superficial testing) so I'm not 
proposing it, like so:

diff --git a/gcc/cp/typeck.c b/gcc/cp/typeck.c
index 7045284..33f56f9 100644
--- a/gcc/cp/typeck.c
+++ b/gcc/cp/typeck.c
@@ -1508,6 +1508,10 @@ same_type_ignoring_top_level_qualifiers_p (tree 
   if (type1 == error_mark_node || type2 == error_mark_node)
     return false;
 
+  if (type1 == type2)
+    return true;
+  if (TYPE_MAIN_VARIANT (type1) != TYPE_MAIN_VARIANT (type2))
+    return false;
   type1 = cp_build_qualified_type (type1, TYPE_UNQUALIFIED);
   type2 = cp_build_qualified_type (type2, TYPE_UNQUALIFIED);


Ciao,
Michael.

Re: [PATCH][RFC] Improve get_qualified_type linear list walk

[Jakub Jelinek]

On Tue, Apr 16, 2019 at 04:10:11PM +0000, Michael Matz wrote:
> I was quickly testing also with some early-outs but didn't get conclusive 
> performance results (but really only superficial testing) so I'm not 
> proposing it, like so:
> 
> diff --git a/gcc/cp/typeck.c b/gcc/cp/typeck.c
> index 7045284..33f56f9 100644
> --- a/gcc/cp/typeck.c
> +++ b/gcc/cp/typeck.c
> @@ -1508,6 +1508,10 @@ same_type_ignoring_top_level_qualifiers_p (tree 
>    if (type1 == error_mark_node || type2 == error_mark_node)
>      return false;
>  
> +  if (type1 == type2)
> +    return true;
> +  if (TYPE_MAIN_VARIANT (type1) != TYPE_MAIN_VARIANT (type2))
> +    return false;

Is this second one correct though?  Doesn't comptypes return for various
cases true even if the TYPE_MAIN_VARIANT is different?

>    type1 = cp_build_qualified_type (type1, TYPE_UNQUALIFIED);
>    type2 = cp_build_qualified_type (type2, TYPE_UNQUALIFIED);

	Jakub

Re: [PATCH][RFC] Improve get_qualified_type linear list walk

[Richard Biener]

On April 16, 2019 6:10:11 PM GMT+02:00, Michael Matz <matz@suse.de> wrote:
>Hi,
>
>On Tue, 16 Apr 2019, Richard Biener wrote:
>
>> Comments?
>
>I was quickly testing also with some early-outs but didn't get
>conclusive 
>performance results (but really only superficial testing) so I'm not 
>proposing it, like so:

Btw, this caller accounts for 30% of the calls to cp_build_qualified_type of which not all end up in build_qualified_type. 

>diff --git a/gcc/cp/typeck.c b/gcc/cp/typeck.c
>index 7045284..33f56f9 100644
>--- a/gcc/cp/typeck.c
>+++ b/gcc/cp/typeck.c
>@@ -1508,6 +1508,10 @@ same_type_ignoring_top_level_qualifiers_p (tree 
>   if (type1 == error_mark_node || type2 == error_mark_node)
>     return false;
> 
>+  if (type1 == type2)
>+    return true;
>+  if (TYPE_MAIN_VARIANT (type1) != TYPE_MAIN_VARIANT (type2))
>+    return false;
>   type1 = cp_build_qualified_type (type1, TYPE_UNQUALIFIED);
>   type2 = cp_build_qualified_type (type2, TYPE_UNQUALIFIED);
>
>
>Ciao,
>Michael.

Re: [PATCH][RFC] Improve get_qualified_type linear list walk

[Richard Biener]

On April 16, 2019 6:14:45 PM GMT+02:00, Jakub Jelinek <jakub@redhat.com> wrote:
>On Tue, Apr 16, 2019 at 04:10:11PM +0000, Michael Matz wrote:
>> I was quickly testing also with some early-outs but didn't get
>conclusive 
>> performance results (but really only superficial testing) so I'm not 
>> proposing it, like so:
>> 
>> diff --git a/gcc/cp/typeck.c b/gcc/cp/typeck.c
>> index 7045284..33f56f9 100644
>> --- a/gcc/cp/typeck.c
>> +++ b/gcc/cp/typeck.c
>> @@ -1508,6 +1508,10 @@ same_type_ignoring_top_level_qualifiers_p
>(tree 
>>    if (type1 == error_mark_node || type2 == error_mark_node)
>>      return false;
>>  
>> +  if (type1 == type2)
>> +    return true;
>> +  if (TYPE_MAIN_VARIANT (type1) != TYPE_MAIN_VARIANT (type2))
>> +    return false;
>
>Is this second one correct though?  Doesn't comptypes return for
>various
>cases true even if the TYPE_MAIN_VARIANT is different?

I think it is not equivalent. I thought about adding a flag to comptypes to ignore toplevel qualifiers on-the-fly. 

Richard. 


>>    type1 = cp_build_qualified_type (type1, TYPE_UNQUALIFIED);
>>    type2 = cp_build_qualified_type (type2, TYPE_UNQUALIFIED);
>
>	Jakub

Re: [PATCH][RFC] Improve get_qualified_type linear list walk

[Richard Biener]

On Tue, 16 Apr 2019, Michael Matz wrote:

> Hi,
> 
> On Tue, 16 Apr 2019, Richard Biener wrote:
> 
> > Comments?
> 
> I was quickly testing also with some early-outs but didn't get conclusive 
> performance results (but really only superficial testing) so I'm not 
> proposing it, like so:
> 
> diff --git a/gcc/cp/typeck.c b/gcc/cp/typeck.c
> index 7045284..33f56f9 100644
> --- a/gcc/cp/typeck.c
> +++ b/gcc/cp/typeck.c
> @@ -1508,6 +1508,10 @@ same_type_ignoring_top_level_qualifiers_p (tree 
>    if (type1 == error_mark_node || type2 == error_mark_node)
>      return false;
>  
> +  if (type1 == type2)
> +    return true;

This one reduces the number of get_qualified_type calls
by about 10%.  Probably worth doing.

Another smallish improvement is using strip_top_quals which
does nothing for ARRAY_TYPE.

Btw, the new get_qualified_type shows (with the above patch applied)

   if (TYPE_QUALS (type) == type_quals)
     return type; // 0.3% hit

   tree mv = TYPE_MAIN_VARIANT (type);
   if (check_qualified_type (mv, type, type_quals))
     return mv; // 43.8% hit

for the C++ FE the LRU cache effectively moves the unqualified
variants first in the variant list.  Since we always first
build the unqualified variants before the qualified ones
the unqualified ones tend to be at the end of the list.  That's
clearly bad for the C++ pattern of repeatedly looking up the
unqualified type variant from a type.  Of course a direct
shortcut would be much cheaper here (but it obviously isn't
the main variant due to TYPE_NAME differences).

So do you think the change to get_qualified_type is OK?  Or
do we absolutely want to avoid changing the variant list from
a function like this?

Thanks,
Richard.

Re: [PATCH][RFC] Improve get_qualified_type linear list walk

[Michael Matz]

Hi,

On Wed, 17 Apr 2019, Richard Biener wrote:

> for the C++ FE the LRU cache effectively moves the unqualified
> variants first in the variant list.  Since we always first
> build the unqualified variants before the qualified ones
> the unqualified ones tend to be at the end of the list.  That's
> clearly bad for the C++ pattern of repeatedly looking up the
> unqualified type variant from a type.  Of course a direct
> shortcut would be much cheaper here (but it obviously isn't
> the main variant due to TYPE_NAME differences).
> 
> So do you think the change to get_qualified_type is OK?  Or
> do we absolutely want to avoid changing the variant list from
> a function like this?

I think changing the variant list in this accessor should be okay.  For it 
not to be okay some callers would have to remember a particular subset of 
that list and also care about the order of that subset.  That would be 
fragile no matter what.

I had the additional idea to only move the non-qualified variant to the 
front, i.e. not really LRU.  By that we would slowly establish the 
invariant that unqualified variants are early in the list; or 
alternatively add a combination of build_variant_type_copy+set_type_quals 
which would establish that invariant directly.  But unlike a real LRU 
cache it's harder to see if this brings similar benefits as the scheme is 
then lopsided towards the specific case of looking up unqualified 
variants.


Ciao,
Michael.

Re: [PATCH][RFC] Improve get_qualified_type linear list walk

[Michael Matz]

Hi,

On Tue, 16 Apr 2019, Jakub Jelinek wrote:

> > +  if (type1 == type2)
> > +    return true;
> > +  if (TYPE_MAIN_VARIANT (type1) != TYPE_MAIN_VARIANT (type2))
> > +    return false;
> 
> Is this second one correct though?  Doesn't comptypes return for various
> cases true even if the TYPE_MAIN_VARIANT is different?

Right, that was a thinko.  As I said, I rushed this somewhat :)


Ciao,
Michael.

Re: [PATCH][RFC] Improve get_qualified_type linear list walk

[Jeff Law]

On 4/16/19 6:55 AM, Richard Biener wrote:
> 
> The following makes the C++ FEs heavy use of build_qualified_type
> cheaper.  When looking at a tramp3d -fsyntax-only compile you can
> see that for 470.000 build_qualified_type calls we end up
> with 9.492.205 calls to check_qualified_type (thus we visit around
> 20 variant type candidates) ending up finding it in all but
> 15.300 cases that end up in build_variant_type_copy.
> 
> That's of course because the FE uses this machinery to do things like
> 
> bool
> same_type_ignoring_top_level_qualifiers_p (tree type1, tree type2)
> {
>   if (type1 == error_mark_node || type2 == error_mark_node)
>     return false;
> 
>   type1 = cp_build_qualified_type (type1, TYPE_UNQUALIFIED);
>   type2 = cp_build_qualified_type (type2, TYPE_UNQUALIFIED);
>   return same_type_p (type1, type2);
> 
> but so it be.  The improvement is to re-organize get_qualified_type
> to put found type variants on the head of the variant list.  This
> improves the number of calls to check_qualified_type to 1.215.030
> thus around 2.5 candidates.
> 
> Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
> 
> Comments?  OK?
> 
> Richard.
> 
> 2019-04-16  Richard Biener  <rguenther@suse.de>
> 
> 	* tree.c (get_qualified_type): Put found type variants at the
> 	head of the variant list.
Seems quite reasonable to me.   I just hope we don't find a case where
this is the exact worst case behavior ;-)

jeff

Re: [PATCH][RFC] Improve get_qualified_type linear list walk

[Marc Glisse]

On Wed, 17 Apr 2019, Jeff Law wrote:

>> 	* tree.c (get_qualified_type): Put found type variants at the
>> 	head of the variant list.
> Seems quite reasonable to me.   I just hope we don't find a case where
> this is the exact worst case behavior ;-)

That seems unlikely. Competitive analysis of the list update problem shows 
that the move-to-front strategy is 2-competitive. Here we also have 
insertions so the problem is different, but still close.

-- 
Marc Glisse