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

[Michael Matz <matz@suse.de>]

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.