[clang-tidy] Inefficient string operation

[bittnerbarni]

Summary

This checker is to warn about the performance overhead caused by concatenating strings using the operator+ instead of basic_string's append or operator+=. It is configurable. In strict mode it matches every instance of a supposed inefficient concatenation, in non-strict mode it matches only those which are inside a loop.

[Eugene.Zelenko]

Please mention this check in docs/ReleaseNotes.rst (in alphabetical order).

docs/clang-tidy/checks/performance-inefficient-string-addition.rst

8 ↗

(On Diff #56998)

Please highlight operator+ and other class/methods with ``. Same for other places in documentation.

21 ↗

(On Diff #56998)

Please use constructor initialization instead of assignment.

58 ↗

(On Diff #56998)

Please add new line.

test/clang-tidy/performance-inefficient-string-addition.cpp

1 ↗

(On Diff #56998)

Does it really need to be C++11?

45 ↗

(On Diff #56998)

Please add new line.

[etienneb]

drive-by, some nits.

clang-tidy/performance/InefficientStringAdditionCheck.cpp

31 ↗

(On Diff #56998)

nits: I kind of prefer :

const auto BasicStringType

here and below.

74 ↗

(On Diff #56998)

nits: remove this line

docs/clang-tidy/checks/performance-inefficient-string-addition.rst

4 ↗

(On Diff #56998)

line with "===" should be the same length than title.

11 ↗

(On Diff #56998)

nits: delete one blank line

19 ↗

(On Diff #56998)

remove extra blank line (only one)

45 ↗

(On Diff #56998)

nits: spaces between operator "+"

[Eugene.Zelenko]

docs/ReleaseNotes.rst

191

Please highlight operator+ and operator+= with ``.

[alexfh]

The last diff has nothing but a 2-line change in the docs.

[bittnerbarni]

Sorry for uploading 2 line long diffs. I uploaded the whole diff now.

[etienneb]

clang-tidy/performance/InefficientStringAdditionCheck.cpp

35 ↗

(On Diff #57294)

you should swap the two parameters

hasOverloadedOperatorName("+"),
hasAnyArgument(...)

matching 'hasOverloadedOperatorName' is less expensive

41 ↗

(On Diff #57294)

this is not indented correctly.
could you run

% clang-format -style=file <your-file> -i

47 ↗

(On Diff #57294)

space after ","

54 ↗

(On Diff #57294)

You forgot a comment here?

[alexfh]

Please create a diff with the full context: http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

clang-tidy/performance/InefficientStringAdditionCheck.cpp

84 ↗

(On Diff #57346)

nit: Warning messages are not full sentences, so they should not start with a capital letter and should not end with a period.

Please also change the comma to a semicolon ;.

85 ↗

(On Diff #57346)

std::basic_string::append is correct, but is an unnecessary detail. I'd suggest changing this to string::append or to just append().

[alexfh]

clang-tidy/performance/InefficientStringAdditionCheck.cpp

28 ↗

(On Diff #57894)

s/IsStrictMode/StrictMode/

31 ↗

(On Diff #57894)

This check is only useful for C++. Please add

if (!getLangOpts().CPlusPlus)
  return;

84 ↗

(On Diff #57894)

The root of inefficiency is in unnecessary allocations of temporary strings, so maybe we should note this in the warning message, e.g. "string concatenation results in allocation of unnecessary temporary strings; consider using 'operator+=' or 'string::append()' instead".

clang-tidy/performance/InefficientStringAdditionCheck.h

24 ↗

(On Diff #57894)

Please remove the empty line.

25 ↗

(On Diff #57894)

s/Addition/Concatenation/?

33 ↗

(On Diff #57894)

const bool StrictMode;

docs/clang-tidy/checks/performance-inefficient-string-addition.rst

15 ↗

(On Diff #57894)

Please enclose std::string, std::basic_string and other inline code snippets in double backquotes.

[alexfh]

clang-tidy/performance/InefficientStringConcatenationCheck.cpp

32

clang-format -style=file, please.

67

Each additional matcher has a certain overhead, so it's usually beneficial to merge matchers, if they share common parts. In this case, matchers can be rearranged like this:

Finder->addMatcher(exprWithCleanups(
  hasAncestor(anyOf(cxxForRangeStmt(), whileStmt(), forStmt())),
  anyOf(hasDescendant(AssingOperator), hasDescendant(PlusOperatorMatcher))));

However, the really serious problem with these matchers is the liberal usage of hasDescendant matcher, which traverses the whole subtree. Nested hasDescendant matchers are even worse. Note that the subtree of a statement can be rather large, especially if you consider lambdas. Apart from performance issues, hasDescendant and hasAncestor can yield unexpected results, in particular, when lambdas or local classes are in play. It's always better to use has, if you only need to match direct children and specifically match intermediate nodes, if the descendant you're interested in is always on a fixed depths.

Please try running your check (and maybe a few others for comparison, you can use clang-tidy -enable-check-profile to get the run time) on a few large translation units to estimate its performance and measure the improvement after changing the code.

docs/clang-tidy/checks/performance-inefficient-string-concatenation.rst

7

The problem subheader is the only one here. It doesn't seem like it helps making the document more structured.

9

s/is to warn/warns/
s/strings,/strings/

21

Please make the code snippets use LLVM formatting for consistency. In particular, add a space after for and remove the line break before the opening brace.

40

Add a space before the opening brace.

[bittnerbarni]

Removed the unnecessary hasDescendant calls and simplified the checker as suggested. Tested on LLVM codebase, with minor improvements in speed (~1%).

[alexfh]

clang-tidy/performance/InefficientStringConcatenationCheck.cpp

42

s/Matcher//

49

s/Assing/Assign/

58

Please avoid unnecessary negation by putting the positive branch first, this will make the logic slightly simpler.

68

1. The anyOf(hasAncestor(A), hasAncestor(B), ...) construct is still there. Please replace it with hasAncestor(anyOf(A, B, ...)).
2. Is there really no way to change from hasDescendant / hasAncestor to more strict patterns? I believe, running the check on LLVM doesn't help finding performance issues, since LLVM specifically avoids this pattern by using Twine.

[bittnerbarni]

clang-tidy/performance/InefficientStringConcatenationCheck.cpp

68

1. I was trying to write it like you suggested since the beginning, but it says it cannot deduce the template parameter that way, what's more interesting is that clang-query accepts it.
2. It seems to me that the assignment operator is (always?) direct child of exprWithCleanups, but I'm not totally sure of that. As for the + operator it could be anywhere among the children.

[alexfh]

clang-tidy/performance/InefficientStringConcatenationCheck.cpp

51

1. No need for allOf, node matchers are implicitly "all of".
2. hasDescendant() is potentially the most expensive part here and should go after all other constraints.

69

For 1: if hasAncestor(anyOf(cxxForRangeStmt(), ...)) doesn't work, you can try hasAncestor(stmt(anyOf(cxxForRangeStmt(), ...)). In any case, repeated hasAncestor matchers don't make the check faster ;)

For 2: exprWithCleanups and other implicit nodes can be skipped using the ignoringImplicit() matchers. Leave hasAncestor for the cases, where there can actually be arbitrary nodes in the path.

Here you're matching some arbitrary intermediate node (exprWithCleanups) and then you're constraining its parents and its children. This doesn't make much sense and it's rather inefficient. Since you're interested in the operators in the first place, try rearranging the matcher like this:

cxxOperatorCallExpr(
  anyOf(AssignOperator, PlusOperator),
  hasAncestor(stmt(anyOf(cxxForRangeStmt(), whileStmt(), forStmt()))))

[bittnerbarni]

Thank you, for your valuable comments Alexander!

[alexfh]

A few more nits.

clang-tidy/performance/InefficientStringConcatenationCheck.cpp

51

The allOf(declRefExpr(x), declRefExpr(y)) construct can be replaced with declRefExpr(x, y).

55

Indentation is confusing - as though hasDeclaration is an argument of stmt. Is it a result of clang-format?

64

hasAncestor is potentially more expensive, so it should go last.

[bittnerbarni]

clang-tidy/performance/InefficientStringConcatenationCheck.cpp

56

Yes this is the result of clang-format.

[alexfh]

A couple of nits.

clang-tidy/performance/InefficientStringConcatenationCheck.cpp

52

As noted earlier, there's no need to repeat declRefExpr. This should be:

declRefExpr(BasicStringType, hasDeclaration(decl().bind("lhsStrT")))

clang-tidy/performance/InefficientStringConcatenationCheck.h

26

Please format the file with clang-format -style=llvm.

[alexfh]

Sorry for the delay. I almost missed that there was an update to the patch. Please mark addressed comments as "Done". This way it's easier for me to track changes and it's easier for you not to miss review comments.

One more thing that this check lacks is fix-it hints, however, this can be added later.

clang-tidy/performance/InefficientStringConcatenationCheck.h

27

The formatting is still off (specifically, indentation of public: and private: and the lack of an empty line before private:).

[alexfh]

Looks good. Thank you for working on this!

Do you need me to commit the patch for you?

[bittnerbarni]

Thank you for all the assistance. Could you please do that?

[Prazek]

In D20196#504394, @bittnerbarni wrote:

Thank you for all the assistance. Could you please do that?

btw obtaining commit access and commiting is very simple, so if you are planning to send us some more cool patches then I think you should get the commit access :)

[bittnerbarni]

I'm planning to submit more patches in the future, as I have time for them. So it wouldn't be in vain :)

[Prazek]

In D20196#504397, @bittnerbarni wrote:

I'm planning to submit more patches in the future, as I have time for them. So it wouldn't be in vain :)

http://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access

[Eugene.Zelenko]

Please see PR28836. In some cases check should recommend to use insert().

clang-tidy/performance/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyPerformanceModule
   FasterStringFindCheck.cpp
   ForRangeCopyCheck.cpp
   ImplicitCastInLoopCheck.cpp
+  InefficientStringConcatenationCheck.cpp
   PerformanceTidyModule.cpp
   UnnecessaryCopyInitialization.cpp
   UnnecessaryValueParamCheck.cpp
 
   LINK_LIBS
   clangAST
   clangASTMatchers
   clangBasic
   clangLex
   clangTidy
   clangTidyUtils
   )

clang-tidy/performance/InefficientStringConcatenationCheck.h

+//===--- InefficientStringConcatenationCheck.h - clang-tidy-----------*- C++
+//-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENTSTRINGCONCATENATION_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENTSTRINGCONCATENATION_H
+
+#include "../ClangTidy.h"
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+/// This check is to warn about the performance overhead arising from
+/// concatenating strings, using the operator+, instead of operator+=.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/performance-inefficient-string-concatenation.html
+class InefficientStringConcatenationCheck : public ClangTidyCheck {
+public:
+  InefficientStringConcatenationCheck(StringRef Name,
+                                      ClangTidyContext *Context);
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+  void storeOptions(ClangTidyOptions::OptionMap &Opts) override;
+
+private:
+  const bool StrictMode;
+};
+
+} // namespace performance
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENTSTRINGCONCATENATION_H

clang-tidy/performance/InefficientStringConcatenationCheck.cpp

+//===--- InefficientStringConcatenationCheck.cpp - clang-tidy--------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "InefficientStringConcatenationCheck.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+void InefficientStringConcatenationCheck::storeOptions(
+    ClangTidyOptions::OptionMap &Opts) {
+  Options.store(Opts, "StrictMode", StrictMode);
+}
+
+InefficientStringConcatenationCheck::InefficientStringConcatenationCheck(
+    StringRef Name, ClangTidyContext *Context)
+    : ClangTidyCheck(Name, Context), StrictMode(Options.get("StrictMode", 0)) {}
+
+void InefficientStringConcatenationCheck::registerMatchers(
+    MatchFinder *Finder) {
+  if (!getLangOpts().CPlusPlus)
+    return;
+
+  const auto BasicStringType =
+      hasType(cxxRecordDecl(hasName("::std::basic_string")));
+
+  const auto BasicStringPlusOperator = cxxOperatorCallExpr(
+      hasOverloadedOperatorName("+"),
+      hasAnyArgument(ignoringImpCasts(declRefExpr(BasicStringType))));
+
+  const auto PlusOperator =
+      cxxOperatorCallExpr(
+          hasOverloadedOperatorName("+"),
+          hasAnyArgument(ignoringImpCasts(declRefExpr(BasicStringType))),
+          hasDescendant(BasicStringPlusOperator))
+          .bind("plusOperator");
+
+  const auto AssignOperator = cxxOperatorCallExpr(
+      hasOverloadedOperatorName("="),
+      hasArgument(0, declRefExpr(BasicStringType,
+                                 hasDeclaration(decl().bind("lhsStrT")))
+                         .bind("lhsStr")),
+      hasArgument(1, stmt(hasDescendant(declRefExpr(
+                         hasDeclaration(decl(equalsBoundNode("lhsStrT"))))))),
+      hasDescendant(BasicStringPlusOperator));
+
+  if (StrictMode) {
+    Finder->addMatcher(cxxOperatorCallExpr(anyOf(AssignOperator, PlusOperator)),
+                       this);
+  } else {
+    Finder->addMatcher(
+        cxxOperatorCallExpr(anyOf(AssignOperator, PlusOperator),
+                            hasAncestor(stmt(anyOf(cxxForRangeStmt(),
+                                                   whileStmt(), forStmt())))),
+        this);
+  }
+}
+
+void InefficientStringConcatenationCheck::check(
+    const MatchFinder::MatchResult &Result) {
+  const auto *LhsStr = Result.Nodes.getNodeAs<DeclRefExpr>("lhsStr");
+  const auto *PlusOperator =
+      Result.Nodes.getNodeAs<CXXOperatorCallExpr>("plusOperator");
+  const auto DiagMsg =
+      "string concatenation results in allocation of unnecessary temporary "
+      "strings; consider using 'operator+=' or 'string::append()' instead";
+
+  if (LhsStr)
+    diag(LhsStr->getExprLoc(), DiagMsg);
+  else if (PlusOperator)
+    diag(PlusOperator->getExprLoc(), DiagMsg);
+}
+
+} // namespace performance
+} // namespace tidy
+} // namespace clang

clang-tidy/performance/PerformanceTidyModule.cpp

 //===--- PeformanceTidyModule.cpp - clang-tidy ----------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "../ClangTidy.h"
 #include "../ClangTidyModule.h"
 #include "../ClangTidyModuleRegistry.h"
+#include "InefficientStringConcatenationCheck.h"
 
 #include "FasterStringFindCheck.h"
 #include "ForRangeCopyCheck.h"
 #include "ImplicitCastInLoopCheck.h"
 #include "UnnecessaryCopyInitialization.h"
 #include "UnnecessaryValueParamCheck.h"
 
 namespace clang {
 namespace tidy {
 namespace performance {
 
 class PerformanceModule : public ClangTidyModule {
 public:
   void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<FasterStringFindCheck>(
         "performance-faster-string-find");
     CheckFactories.registerCheck<ForRangeCopyCheck>(
         "performance-for-range-copy");
     CheckFactories.registerCheck<ImplicitCastInLoopCheck>(
         "performance-implicit-cast-in-loop");
+    CheckFactories.registerCheck<InefficientStringConcatenationCheck>(
+        "performance-inefficient-string-concatenation");
     CheckFactories.registerCheck<UnnecessaryCopyInitialization>(
         "performance-unnecessary-copy-initialization");
     CheckFactories.registerCheck<UnnecessaryValueParamCheck>(
         "performance-unnecessary-value-param");
   }
 };
 
 // Register the PerformanceModule using this statically initialized variable.

docs/ReleaseNotes.rst

- New `performance-faster-string-find
   is a single character string literal.
 
 - New `performance-implicit-cast-in-loop
   <http://clang.llvm.org/extra/clang-tidy/checks/performance-implicit-cast-in-loop.html>`_ check
 
   Warns about range-based loop with a loop variable of const ref type where the
   type of the variable does not match the one returned by the iterator.
 
+- New `performance-inefficient-string-concatenation
+  <http://clang.llvm.org/extra/clang-tidy/checks/performance-inefficient-string-concatenation.html>`_ check
+
+  This check is to warn about the performance overhead arising from concatenating 
+  strings, using the ``operator+``, instead of ``operator+=``.
+  
 - New `performance-unnecessary-value-param
   <http://clang.llvm.org/extra/clang-tidy/checks/performance-unnecessary-value-param.html>`_ check
 
   Flags value parameter declarations of expensive to copy types that are copied
   for each invocation but it would suffice to pass them by const reference.
 
 - New `readability-avoid-const-params-in-decls
   <http://clang.llvm.org/extra/clang-tidy/checks/readability-avoid-const-params-in-decls.html>`_ check

docs/clang-tidy/checks/list.rst

.. toctree::
    modernize-shrink-to-fit
    modernize-use-auto
    modernize-use-default
    modernize-use-nullptr
    modernize-use-override
    performance-faster-string-find
    performance-for-range-copy
    performance-implicit-cast-in-loop
+   performance-inefficient-string-concatenation
    performance-unnecessary-copy-initialization
    performance-unnecessary-value-param
    readability-avoid-const-params-in-decls
    readability-braces-around-statements
    readability-container-size-empty
    readability-deleted-default
    readability-else-after-return
    readability-function-size

docs/clang-tidy/checks/performance-inefficient-string-concatenation.rst

+.. title:: clang-tidy - performance-inefficient-string-concatenation
+
+performance-inefficient-string-concatenation
+============================================
+
+This check warns about the performance overhead arising from concatenating strings using the ``operator+``, for instance:
+    
+.. code:: c++
+
+    std::string a("Foo"), b("Bar");
+    a = a + b;
+
+Instead of this structure you should use ``operator+=`` or ``std::string``'s (``std::basic_string``) class member function ``append()``. For instance:
+   
+.. code:: c++
+
+   std::string a("Foo"), b("Baz");
+   for (int i = 0; i < 20000; ++i) {
+       a = a + "Bar" + b;
+   }
+
+Could be rewritten in a greatly more efficient way like:
+
+.. code:: c++
+
+   std::string a("Foo"), b("Baz");
+   for (int i = 0; i < 20000; ++i) {
+       a.append("Bar").append(b);
+   } 
+
+And this can be rewritten too:
+
+.. code:: c++
+
+   void f(const std::string&) {}
+   std::string a("Foo"), b("Baz");
+   void g() {
+       f(a + "Bar" + b);
+   }
+
+In a slightly more efficient way like:
+
+.. code:: c++
+
+   void f(const std::string&) {}
+   std::string a("Foo"), b("Baz");
+   void g() {
+       f(std::string(a).append("Bar").append(b));
+   }

test/clang-tidy/performance-inefficient-string-concatenation.cpp

+// RUN: %check_clang_tidy %s performance-inefficient-string-concatenation %t
+
+namespace std {
+template <typename T>
+class basic_string {
+public:
+  basic_string() {}
+  ~basic_string() {}
+  basic_string<T> *operator+=(const basic_string<T> &) {}
+  friend basic_string<T> operator+(const basic_string<T> &, const basic_string<T> &) {}
+};
+typedef basic_string<char> string;
+typedef basic_string<wchar_t> wstring;
+}
+
+void f(std::string) {}
+std::string g(std::string) {}
+
+int main() {
+  std::string mystr1, mystr2;
+  std::wstring mywstr1, mywstr2;
+
+  for (int i = 0; i < 10; ++i) {
+    f(mystr1 + mystr2 + mystr1);
+    // CHECK-MESSAGES: :[[@LINE-1]]:23: warning: string concatenation results in allocation of unnecessary temporary strings; consider using 'operator+=' or 'string::append()' instead
+    mystr1 = mystr1 + mystr2;
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: string concatenation
+    mystr1 = mystr2 + mystr2 + mystr2;
+    // CHECK-MESSAGES: :[[@LINE-1]]:30: warning: string concatenation
+    mystr1 = mystr2 + mystr1;
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: string concatenation
+    mywstr1 = mywstr2 + mywstr1;
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: string concatenation
+    mywstr1 = mywstr2 + mywstr2 + mywstr2;
+    // CHECK-MESSAGES: :[[@LINE-1]]:33: warning: string concatenation
+
+    mywstr1 = mywstr2 + mywstr2;
+    mystr1 = mystr2 + mystr2;
+    mystr1 += mystr2;
+    f(mystr2 + mystr1);
+    mystr1 = g(mystr1);
+  }
+  return 0;
+}