[gcc r14-11200] libstdc++: backport inline keyword on std::find

[Tamar Christina]

https://gcc.gnu.org/g:e4a9fb7448a687f4fd7e621942006c2820b803d6

commit r14-11200-ge4a9fb7448a687f4fd7e621942006c2820b803d6
Author: Tamar Christina <tamar.christina@arm.com>
Date:   Fri Jan 10 21:37:40 2025 +0000

    libstdc++: backport inline keyword on std::find
    
    This is a backport version of the same patch as
    g:18aff7644ad1e44dc146d36a2b7e397977aa47ac
    
    In GCC 12 there was a ~40% regression in the performance of hashmap->find.
    
    This regression came about accidentally:
    
    Before GCC 12 the find function was small enough that IPA would inline it even
    though it wasn't marked inline.  In GCC-12 an optimization was added to perform
    a linear search when the entries in the hashmap are small.
    
    This increased the size of the function enough that IPA would no longer inline.
    Inlining had two benefits:
    
    1.  The return value is a reference. so it has to be returned and dereferenced
        even though the search loop may have already dereference it.
    2.  The pattern is a hard pattern to track for branch predictors.  This causes
        a large number of branch misses if the value is immediately checked and
        branched on. i.e. if (a != m.end()) which is a common pattern.
    
    The patch fixes both these issues by adding the inline keyword to _M_locate
    to allow the inliner to consider inlining again.
    
    This and the other patches have been ran through serveral benchmarks where
    the size, number of elements searched for and type (reference vs value) etc
    were tested.
    
    The change shows no statistical regression, but an average find improvement of
    ~27% and a range between ~10-60% improvements.
    
    Thanks,
    Tamar
    
    libstdc++-v3/ChangeLog:
    
            * include/bits/hashtable.h (find): Add inline keyword.

Diff:
---
 libstdc++-v3/include/bits/hashtable.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 834288c747c2..f5f421d2fd32 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -1723,7 +1723,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename _ExtractKey, typename _Equal,
 	   typename _Hash, typename _RangeHash, typename _Unused,
 	   typename _RehashPolicy, typename _Traits>
-    auto
+    auto inline
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
     find(const key_type& __k)
@@ -1746,7 +1746,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename _ExtractKey, typename _Equal,
 	   typename _Hash, typename _RangeHash, typename _Unused,
 	   typename _RehashPolicy, typename _Traits>
-    auto
+    auto inline
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
     find(const key_type& __k) const