Performance regression in 2.4

[CHR]

After updating from 2.3 to 2.4, execution time on our code base has increased from ~70 minutes to ~200 min.
The main culprits seem to be simplifyTokens1 and simplifyTemplates.
v2.3:

Tokenizer::simplifyTokens1: 11985.1s (avg. 22.5283s - 532 result(s))
Tokenizer::tokenize::simplifyTemplates: 6770.38s (avg. 13.045s - 519 result(s))

v2.4:

Tokenizer::simplifyTokens1: 40331.3s (avg. 75.8108s - 532 result(s))
Tokenizer::tokenize::simplifyTemplates: 33718.7s (avg. 64.5952s - 522 result(s))

Note that the output is from a multi-threaded run.

[Robert Reif]

Can you provide some example code? This is hard to fix without an example.

Doe this patch help?

diff --git a/lib/templatesimplifier.cpp b/lib/templatesimplifier.cpp
index c157178b0..f3a6c8691 100644
--- a/lib/templatesimplifier.cpp
+++ b/lib/templatesimplifier.cpp
@@ -2146,22 +2146,34 @@ void TemplateSimplifier::expandTemplate(
                 if (prev->strAt(-1) != "::") {
                     // adjust for current scope
                     std::string token_scope = tok3->scopeInfo()->name;
-                    std::string::size_type end = token_scope.find_last_of(" :: ");
-                    if (end != std::string::npos) {
-                        token_scope.resize(end);
-                        if (scope.empty())
-                            scope = token_scope;
-                        else
-                            scope = token_scope + " :: " + scope;
+                    if (scope != token_scope) {
+                        std::string::size_type end = token_scope.find_last_of(" :: ");
+                        if (end != std::string::npos) {
+                            token_scope.resize(end - 3);
+                            if (scope.empty())
+                                scope = token_scope;
+                            else
+                                scope = token_scope + " :: " + scope;
+                        }
                     }
                 }

                 // don't add instantiations in template definitions
                 if (templates.empty()) {
-                    if (copy)
-                        newInstantiations.emplace_back(mTokenList.back(), scope);
-                    else if (!inTemplateDefinition)
-                        newInstantiations.emplace_back(tok3, scope);
+                    const std::string & name = copy ? mTokenList.back()->str() : tok3->str();
+                    std::string::size_type offset = scope.find_last_of(" :: ");
+                    if (offset == std::string::npos)
+                        offset = 0;
+                    else
+                        offset++;
+                    // don't add recursive instantiation
+                    if (name.size() > scope.size() ||
+                        (name.size() <= scope.size() && scope.compare(offset, name.size(), name))) {
+                        if (copy)
+                            newInstantiations.emplace_back(mTokenList.back(), scope);
+                        else if (!inTemplateDefinition)
+                            newInstantiations.emplace_back(tok3, scope);
+                    }
                 }
             }

[CHR]

Sorry, the code base is proprietary and fairly large.
Doesn't this problem also show up in DACA@home? Although I don't know if you can compare runtimes against 2.3 there.
I guess I could run a nightly build if it helps.

[CHR]

So, I ran cppcheck with your patch applied (compiled with VS2019 in Release mode), and there was no improvement in runtime (~210+ min vs 200 min before).
Maybe I'll be able to run it under a profiler at some point to see where the bottlenecks are.

[ttressieres]

I have the same performance issue with my code base.
I ran Intel VTune between cppcheck 2.3 and cppcheck 2.4 compiled with VS2019 + Release with debug info

Top Hotspots

cppcheck 2.3
Function Module CPU Time
Token::multiCompare cppcheck-core.dll 197.585s
Token::Match cppcheck-core.dll 58.073s
multiComparePercent cppcheck-core.dll 33.011s
malloc_base ucrtbase.dll 19.711s
TemplateSimplifier::expandTemplate cppcheck-core.dll 17.934s
[Others] N/A* 154.145s

cppcheck 2.4
Function Module CPU Time
ScopeInfo3::findInChildren cppcheck-core.dll 848.035s
Token::multiCompare cppcheck-core.dll 253.432s
ScopeInfo3::findScope cppcheck-core.dll 137.450s
Token::Match cppcheck-core.dll 89.093s
malloc_base ucrtbase.dll 41.890s
[Others] N/A* 266.203s

findInChildren & findScope are called by Tokenizer::simplifyUsing

[Robert Reif]

simplifyUsing was changed in 2.4 to do better type lookup but the type lookup is slower. We need to change simplifyUsing to do scope caching and better type lookup like we did in templateSimplifier.