[Tech Story] The NeverEnding Story of writing a rule for argument passing in C++

Clean Code Sonar Updates
, , ,
1

Hello everybody,

My name is Loïc Joly, and I work for SonarSource, mostly focusing on developing our C and C++ analyzer. I’m also a member of the ISO C++ Committee, which defines the next versions of the C++ language.

In this post, I’ll show you how we introduced a new rule in our C++ analyzer. While this example is about a C++ rule, I believe that this post may contain interesting insight on the craft of rule development, even if your main language is not C++. My goal is to tell the story of a new rule we developed, what issues we faced and what decisions were taken along the way. You will get to understand a little bit the craft of rule design, which is central to our activity.

If you want to comment or discuss some elements of this article, you can just reply to this message!

The NeverEnding Story of writing a rule for argument passing in C++

In C++, there are many ways to pass an argument into a function parameter. If the argument is only to be used as input, there are two ways of passing it:

  • You can pass it by value, which mean that the value of the argument will be copied into the parameter of the function
  • You can pass it by reference to const, meaning that from inside of the function, you will have direct access to the outside object, but since this access is read-only, you will not be able to alter it (except if stuff like const_cast or mutable enter the party, but this is out of scope for this discussion).

In terms of program state, these two ways of passing arguments are very similar (more on this later). Where they differ is in performance. Great, you’ll say, which one is more efficient? Unfortunately, the answer is not so simple. The goal of this article is to show you the many steps we took while developing a rule related to this situation.

What are the performance implications

Let’s see some code:

struct Student {
  int age;
  string name;
};
void displayStudent(std::ostream &os, bool fullData, Student student){
  os << student.name;
  if (fullData) {
    os << " (" << student.age << ")";
  }
}

void f() {
  Student s;
  // ...
  displayStudent(std::cout, true, s);
}

The function displayStudent accepts 3 parameters:

  • os is the stream where the data will be displayed. It is modified by the function, and therefore needs to be passed by reference. It is out of scope for this discussion.
  • fullData is passed by value. This means that when the function is called, the boolean true is copied into the fullData variable.
  • student is also passed by value, and s will also be copied into the student variable.

While it looks harmless to copy a bool, copying a Student is a different story. It implies copying all the fields of this structure. One of this fields is a string, so copying it implies dynamic allocation of memory to store the characters in that string. This is a costly operation.

On the other hand, if the function is written this way:

void displayStudent(std::ostream &os, bool const &fullData, Student const &student){
  os << student.name; // Note that the body is identical
  if (fullData) {
    os << " (" << student.age << ")";
  }
}

void f() {
  Student s;
  // ...
  displayStudent(std::cout, true, s); // No changes at the call site either 
}

Then fullData and student would be passed as reference to const. This would be great for student. It is now no longer copied, and from inside the function, student is now an alias to s, but one that cannot be used to modify s. In order to perform that, the address of s has probably been copied, but copying an address is cheap.

So, what prevents us from passing all arguments by reference to const? Well, once again, it’s performance, but it’s slightly more subtle. For instance, if we passed fullData as a bool const &, it would mean that all accesses to this variable now become indirect access (what is manipulated internally is now the address of the variable, not its value) for no gain because copying a bool is at least as cheap as copying an address… Moreover, we are now facing the issue of aliasing. Let’s take a dummy example to see the issue:

void f(int const &in, int &out) {
  if (in > 10) {
    out = 3;
  }
  if (in > 5) {
    g();
  }
}

The compiler might want to optimize the code like this:

void f(int const &in, int &out) {
  if (in > 10) {
    out = 3;
    g();
  }
  else if (in > 5) {
    g();
  }
}

But it cannot… For instance, if the code function is called that way:

int i = 12;
f(i, i);

The execution of both versions would yield a different result. We say that, in the function, in and out might be aliased, and refer to the same chunk of memory. And unless the compiler can prove that it will never happen (which it usually cannot), it prevents some optimization, even if the code is never called in the aliased context. And even for a human, it’s easier to reason on code where different variables really are different.

The common guideline, in the C++ community, is therefore the following: If the type is cheap to copy, pass by value, otherwise, pass by reference to const, unless of course you have a good reason not to do so (this unless clause obviously exists for all guidelines…).

We wanted to add to our C/C++ analyzer a rule that would help users make sure their code follows this guideline. But as you will see, even a seemingly simple guideline is not always turned easily into a rule verified by an automated tool.

Strictly following the C++ Core Guidelines

This rule matches the C++ Core Guideline F.16: For “in” parameters, pass cheaply-copied types by value and others by reference to const. So, we first implemented the rule as it is described here. The most difficult part of this rule, for a static analyzer tool, is to detect if a type is cheap to copy or not. Here, the proposed criteria is the size of the parameter type:

  • (Simple) ((Foundation)) Warn when a parameter being passed by value has a size greater than 2 * sizeof(void*). Suggest using a reference to const instead.
  • (Simple) ((Foundation)) Warn when a parameter passed by reference to const has a size less than 2 * sizeof(void*). Suggest passing by value instead.

Unfortunately, when we looked at the results on real source code, this rule was triggered very often, even in cases which we believed were perfectly valid. Worse, in some cases, changing the function as advised by the rule would have led to broken code.

Let’s see what those issues were, and how we tackled them.

Excluding easy corner cases

We first started by excluding some special cases from this rule.

Prevent impossible solutions

We should not advise to pass by value a non-copyable type. Or to pass by value the argument of a copy constructor (the purpose of this constructor is to define what it means to copy an object of that type, so it cannot use copy). If a type is incomplete, there is not much that can be said about it, so we’ll skip that too.

All of those were pretty basic examples, but they needed to be taken into account nevertheless.

Templates

template<class T>
class f(T const &t);

void g() {
  f(int{});
  f(string{});
}

Should we advise to pass by value in this case, because T might be a large type? What if it is not? There are some techniques that allow defining a template function that works by copy when instantiated with small types, and by reference to const when instantiated with other, larger types (see for instance boost::call_traits<T>::param_type). However, in most cases, it’s overkill. So, we decided in the case of templates to simply ignore all parameters that are dependent.

User-defined copy constructor

We did not feel comfortable in relying only on the size of the object to estimate the cost to copy it. For instance, look at the following matrix class:

class Matrix {
  short M;
  short N;
  double *data;
  // ...
};

Its size is very small, smaller than 2 pointers, but copying it will be very expensive, since it involves copying all the doubles referenced by data (there might be thousands of them) in addition to the three bookkeeping variables M, N and data (and it also requires dynamic memory allocation). In order to avoid this situation, we decided to consider as large (and therefore requiring pass by reference to const) all classes with a non trivial copy constructor (we decided for nontrivial, instead of user-defined, because it also handles the case of a class with a Matrix member variable, even if this class does not itself define a copy constructor).

Never advising to pass by copy

Even after the classical clean-up phase, we had way too many violations. So we had another look at the situation.

One of the most glaring issues of the rule was when it asked to pass by value a type which is part of a polymorphic hierarchy:

class Shape {/*...*/};
class Circle : public Shape {/*...*/};
void draw(Shape const &shape); // The rule asks to pass by value here

Here, Shape can be very small, but it has to be passed by reference to const, because copying a Shape that is in fact a Circle would slice the circle into a Shape (assuming this is possible… If the class Shape is abstract, it would only be a compilation error, which is far better than a silently sliced data).

Another issue was more subtle:

#include "framework/Color.h"
void draw(Shape const &s, Color c);

How are you supposed to know if Color is a large type or a small one? It’s probably not too expensive to copy, but its exact size is not something you need to know all the time. And it might change on different platforms, with different framework versions, with different compiler options (even if it stays the same, our threshold depends on the size of a pointer, which may change). In fact, you can probably pass it by value, and it would be not too bad, or by reference to const, and it would be not too bad either.

What makes the matter worse, is that when a developer decides whether something is cheap to copy or not, he is usually not doing it for a variable, but for a type. If he decides that c should be passed by copy, it means that he considers Color cheap, and everywhere a Color is passed, it will be the same way. However, we are detecting this issue when a function is declared. So we will mark as problematic all functions that take the Color argument, and a developer who disagrees with this decision will have to manually ignore all those places. This would clearly not be a pleasant user experience.

We first played with the idea of a gray zone, where we would allow both pass-by-value and pass-by-reference-to-const, but finally we settled on something simpler. We will only detect pass-by-value that should be replaced by pass-by-reference-to-const, not the other way around. Why?

  • We believe that the cost of passing by value when you should have passed by reference to const is an order of magnitude more important than the other way around. This is the real issue that we want to detect in the code, with as few false positives as possible.
  • For people who want to hunt for the extra performance gain of passing by value when appropriate, we can always create another rule later, which would not be in our default quality profile, because it would inevitably create quite a few false positives.

Ignore function declarations

We have enough information when declaring a function to decide what kind of argument passing we consider the best. So, at the beginning, we raised issues on all function declarations. This had several negative impacts:

  • We can raise the same issue several times, once for each declaration, once for the definition,
  • We can raise the issue on external code, that the developer has no control on. Detecting, automagically, that code is external is not reliable, and asking the user to consistently flag each file as internal or external would be tedious, so we wanted something else.

Therefore, we decided to raise the issue only on function definitions. You can still get the second issue on external inline functions, but in practice, this really helped in reducing the noise. But not enough…

A nice side effect of this decision is that now, we may look at the function body, if we decide it may improve the rule.

User-defined copy constructor, take 2

There are many classes that have a user-defined copy constructor, but which are still rather cheap to copy. For instance:

  • Classes where the user defined a copy constructor, but it is useless. You should not do that, and follow the rule of 0 instead. But still, it happens…
  • Some copy constructors just increment a counter in debug mode to help profiling an application…
  • Some classes use copy-on-write (for instance the QString class from Qt). For those cases, passing by reference to const would probably still be the most efficient way to work (it usually avoids taking a lock to increment a counter), but the cost of copying is not that huge and, more importantly, the users of those libraries are used to copying all the time, and even if they are wrong, they are probably not so wrong that it seriously endangers the performance of their program.

In the end, we removed the requirement that a type with a non trivial constructor should be passed by reference to const.

We are clearly not fully satisfied with that, but any other solution we thought about would have required looking at the body of the copy constructors (recursively for the member data) to try and guess what they were really doing. We believed it would be very error-prone, and that the cost-benefit analysis did not justify it.

Moreover, this decision will remove some false positives, at the cost of introducing false negatives. We usually consider this an acceptable trade-off. In other words, instead of triggering the rule when we believed you are passing by value an expensive data, we now trigger it when we know this is the case.

Future potential improvements

Templates

Currently, we don’t say anything about arguments in function templates that are dependant. But since in case of doubt it’s usually better to pass by reference to const, we might say that as soon as one of the template instances requires passing by reference to const, we should require it for the base template.

However, “usually better” does not mean “always better”. There might be situations when the template needs a lot of speed when instantiated with small types, and not care that much when it is instantiated with more heavyweight types. This is why we decided not to implement this part before getting some feedback on the rule as it is now.

User-defined constructor, take 3?

We might come up with some brilliant idea that would allow us to statically decide if a copy constructor is cheap or not. Or we may totally revisit the decisions we have taken and try a different approach. We know we have a direction for improvement here.

Useful copies

There are some cases when passing by value is more efficient than passing by reference to const. Even if the type is expensive to copy. It’s when you want to change the object, but keep the original untouched:

int mean(vector<int> data) {
  // Not the good algorithm. Just for exposition...
  std::sort(data.begin(), data.end()); // Modifies data in place
  return data[data.size()/2];
}

In that case, you will need to make a copy anyway, so you might as well do it in the parameters. Doing it that way even prevents the copy sometimes:

vector<int> readData();
int f() {
  return mean(readData());
}

In that case, the argument of mean is the temporary value returned from readData. At the point of copying the argument into the parameter, the compiler knows that, and since it is temporary, instead of performing an expensive copy, it will do a much cheaper move.

If you had written the function like this:

int mean(vector<int> const &data) {
  auto copy = data;
  // Not the good algorithm. Just for exposition...
  std::sort(copy.begin(), copy.end()); // Modifies copy in place
  return copy[copy.size()/2];
}

At the time the copy is performed, the compiler has lost the information that data is in fact a reference to a temporary, and that its internal state can be stolen. It will therefore copy, and miss the opportunity to move.

Another option in this case would be to write two overloads of the function:

int mean(vector<int> const &data);
int mean(vector<int> &&data);

But passing by copy works just as well, is simpler and more concise.

The problem is that we don’t detect this case, and we will ask the user to pass by reference to const instead. This is a known false positive case for our rule (and is documented as such).

One axis of improvement would then be to detect that the function parameter is modified inside of the function. Unfortunately, detecting that is not so simple in C++. It’s probably mathematically impossible to do so in all cases.

We can probably get good approximations, but we did not want to delay this rule, and decided to keep this as a possible future improvement, when we also have feedback on the rule’s perception by our users.

Conclusion

I wanted to share with you that when writing a rule, the most difficult part is not the code itself, but the specification of the rule, the corner cases that you will need to tackle and the gray zone for which no clear decision exist, but which nevertheless requires a decision.

All in all, we hope that this rule, along with the other rules we have added, will allow our C/C++ Analyzer v6.1 to help you write consistently better code. Please give us your feedback on this forum. Thanks for reading!

7 Likes