How to avoid aliasing and improve performance?

Question

In this Stack Overflow answer it is demonstrated that aliasing in C++ can slow down your code. And aliasing in C++ doesn't only apply to pointers, it applies also to references, and more generally to these types specified by the standard. Particularly, there is

an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union)

So according to my understanding, if I have code like below,

 class A{
  public:
   int val;
 };

 void foo(vector<A> & array, int & size, A & a0) {
   for(int i=0;i<size;++i) {
    array[i].val = 2*a0.val;
   }
 }

and it is possible that a0 can alias one of the elements in array, also possibly alias size because of the aforementioned quote, so a0 and size have to be loaded for each iteration resulting in a performance drop.

Then my question is what should I do to the code to avoid the aliasing, and improve the performance?
Passing by const & won't help since it won't avoid aliasing as specified by the standard. Pass a0 by value? But this will make a copying of a0 which I don't like, since in practice, class A may be very complex and copying is a very expensive option.
Is there a general solution to avoid aliasing in C++? If yes, what is it?

The proposal I reference here from [Clark Nelson is relevant](http://stackoverflow.com/a/27914489/1708801) although it is a C proposal he mentions it is relevant to WG21(C++) as well although he did not have time to provide WG21 wording. — Shafik Yaghmour, Jul 24 '15 at 02:44
I'm not too familiar with aliasing behavior but of what I'm reading, as long as the values that the function needs to read can be proven to the compiler not to be potential aliases of one another per the rules, it should avoid the overheads of refreshing the value each time. Eg, in this example (and I could be wrong) there shouldn't be aliasing because `int`, `vector` and `A` are not types that can refer to one another excepting `int&` pointing to `A::val`. — Xeren Narcy, Jul 24 '15 at 02:45
@XerenNarcy `a0` could be a reference to one of the elements of `array` — M.M, Jul 24 '15 at 03:07

Shafik Yaghmour · Accepted Answer · 2015-07-25T17:32:04.220

The issue of avoiding aliasing performance issue in C++ seems to be covered by Evolution Working Group issue 72: N4150 Alias-Set Attributes: Toward restrict-like aliasing semantics for C++, N3988 Towards restrict-like aliasing semantics for C++ N3635 Towards restrict-like semantics for C++ and N4150 was the latest version of the proposal. The EWG issue is not yet resolved but apparently is considered ready for review.

The proposal proposes C like restrict qualifiers which currently are supported by extensions in C++ by many compilers but have fuzzy areas, the proposal says amongst other things:

There is no question that the restrict qualifier benefits compiler optimization in many ways, notably allowing improved code motion and elimination of loads and stores. Since the introduction of C99 restrict, it has been provided as a C++ extension in many compilers. But the feature is brittle in C++ without clear rules for C++ syntax and semantics. Now with the introduction of C++11, functors are being replaced with lambdas and users have begun asking how to use restrict in the presence of lambdas. Given the existing compiler support, we need to provide a solution with well-defined C++ semantics, before use of some common subset of C99 restrict becomes widely used in combination with C++11 constructs.

the proposal also notes:

Without standardizing and improving the existing C99 restrict facility in C++, users typically have to jump through considerable hoops to get its effect through code rewriting through temporaries, or factoring and inlining function bodies to simulate its effect.

So it seems like there is currently no good solution, although current compilers have extensions which offer C restrict like semantics there are a lot of grey areas section 3. Issues with restrict in C++ and C covers some of the methods used to avoid aliasing but they all have flaws.

The proposal mentioned N3538 which mentions some of the techniques and flaws associated with these techniques. For example:

The simplest technique to overcoming aliasing is to copy the potentially aliasing parameter.
void rf2(type& output, const type& input) {
    type temp = input;
    output += ra1(temp);
    output += ra2(temp);
}
This technique is both more complex and less efficient than simply passing the parameter by value. While the technique can be useful when dealing with legacy interfaces, it should not be a primary technique.

This technique would apply to your case.

Note for interesting take on aliasing and the C99 restrict qualifier On the redundancy of C99's restrict.

score 1 · Answer 2 · answered Jul 24 '15 at 04:30

If the intent is that you are not expecting size or a0.val to change during the execution of foo, then you can make that explicit by having these be local values:

void foo(vector<A> & array, int size, const A & a0) {
    auto new_val = 2*a0.val;
    for(int i=0;i<size;++i) {
        array[i].val = new_val;
    }
}

Now it is clear that you are intending to set all the elements to the same value. It is clear to the reader as well as the compiler.

How to avoid aliasing and improve performance?

2 Answers2

Linked