[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

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

21

Please use constructor initialization instead of assignment.

58

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

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

11

nits: delete one blank line

19

remove extra blank line (only one)

45

nits: spaces between operator "+"

[Eugene.Zelenko]

docs/ReleaseNotes.rst

191 ↗

(On Diff #57172)

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

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

[alexfh]

clang-tidy/performance/InefficientStringConcatenationCheck.cpp

31 ↗

(On Diff #58054)

clang-format -style=file, please.

66 ↗

(On Diff #58054)

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

6 ↗

(On Diff #58054)

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

8 ↗

(On Diff #58054)

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

20 ↗

(On Diff #58054)

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.

39 ↗

(On Diff #58054)

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

41 ↗

(On Diff #59661)

s/Matcher//

48 ↗

(On Diff #59661)

s/Assing/Assign/

57 ↗

(On Diff #59661)

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

67 ↗

(On Diff #59661)

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

67 ↗

(On Diff #59661)

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

50 ↗

(On Diff #61893)

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.

68 ↗

(On Diff #61893)

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

50 ↗

(On Diff #63098)

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

54 ↗

(On Diff #63098)

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

63 ↗

(On Diff #63098)

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

[bittnerbarni]

clang-tidy/performance/InefficientStringConcatenationCheck.cpp

55 ↗

(On Diff #65384)

Yes this is the result of clang-format.

[alexfh]

A couple of nits.

clang-tidy/performance/InefficientStringConcatenationCheck.cpp

51 ↗

(On Diff #65384)

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

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

clang-tidy/performance/InefficientStringConcatenationCheck.h

25 ↗

(On Diff #65384)

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

26 ↗

(On Diff #65606)

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().

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

 .. title:: clang-tidy - performance-inefficient-string-addition
 
 performance-inefficient-string-addition
 =======================================
 
 The problem
 -----------
 This check is to warn 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:
+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));
    }