1

Current data structure

I have a code in which the data structure is represented by two vectors of classes A1 and A2 respectively.

vector<A1> v1;
vector<A2> v2;

The slow part of my code (about 80% of the total runtime) consists at iterating over these vectors and applying the method funA1 on elements of v1 and funA2 on elements of v2.

double result = 0;
for (int i = 0 ; i < v1.size() ; i++)
{
  results *= v1[i].funA1();
}
for (int i = 0 ; i < v2.size() ; i++)
{
  results *= v2[i].funA2();
}

Reshaping the data structure

While the data structure uses these two vectors, the intuition would rather to using a single vector that mixes the data type A1 and A2. Using two different vectors brings a loss of readability and maintenance elsewhere in the code.

I thought I could merge them into a single vector. The idea would be to make A1 and A2 siblings classes of a parent class A and use vector<A> v as single vector. I would define a virtual fun in the class A and override it in both A1 and A2 so that I could do

double result = 0;
for (int i = 0 ; i < v.size() ; i++)
{
  results *= v[i].fun();
}

Question

In the first case, the methods funA1 and funA2 can be inlined by the compiler (in fact I inlined them myself as they are very simple functions).

In the second case I am afraid inlining would not be possible. Is this correct?

Will the compiler manage to inline the method fun?

Of course the loss of performance might be negligible and I should test it but I would like to know whether it seems a priori worth it before trying to make all the modifications.

Remi.b
  • 17,389
  • 28
  • 87
  • 168

5 Answers5

4

The answer is a definite "Maybe". The only way to tell if your compiler does actually inline the call, is to compile it, and look at the assembly listing. It all depends on the complexity of fun (where "complexity" is a very compiler-specific metric).

Personally, unless this is the most time-critical portion of your application, I wouldn't worry about it. Function calls are not that expensive. As always, write your code for clarity and readability, and then optimize afterwards.

Martin Bonner supports Monica
  • 28,528
  • 3
  • 51
  • 88
  • 1
    I agree: profiling is the best way to gain insight as to where your program is actually spending the majority of its time (and therefore where you should be focusing your efforts). – Marco A. Mar 21 '17 at 07:37
2

The short answer is "no". Your requirement to have the instances of the vector with differing types works against the compiler being able to inline virtual function calls.

Assuming A1 and A2 are derived from A, instances of A1 and A2 cannot safely be stored into a std::vector<A>. The result of doing that will be object slicing (e.g. only copy the A parts of each object into the std::vector<A>). Such a thing will not compile if A is an abstract class (i.e. has any pure virtual functions). If A is not abstract, then the static type of all the objects in the std::vector<A> is A - so calling v[i].fun() will call A::fun() for every element. So A1::fun() and A2::fun() will never be called.

If you store addresses of objects in a std::vector<A *>, then v[i]->fun() will call the virtual function based on the actual type of the object. However, this cannot be inlined by the compiler, since the function to be called is determined at run time based on the actual type of each object in the vector (i.e. the type of each object is unknown to the compiler). Similarly comments if you use a std::vector<std::unique_ptr<A>>.

Note: There are other issues of storing pointers to polymorphic class A in a std::vector<A *> or a std::vector<std::unique_ptr<A>>, such as the need for A to have a virtual destructor, for the lifetime of the objects to be managed correctly, etc. If you are going to use such an approach, you need to account for those things - otherwise the result will be undefined behaviour.

If you want help optimising performance of your code, you will need to provide a lot more information (e.g. information about HOW you have profiled, what the types A, A1, A2 are, what the functions are doing, etc).

Peter
  • 35,646
  • 4
  • 32
  • 74
  • I was more expecting a "no" than a "maybe", so I upvote! But of course I notice that there is conflicting believes among the answers so far. I appreciate the extra explanations. Thanks – Remi.b Mar 21 '17 at 15:20
1

You're proposing making A::fun virtual, and having two overrides A1::fun and A2::fun, have one call, and then expect the compiler to inline both A1::fun and A2::fun in that one call?

That's optimistic. Not impossible, though.

MSalters
  • 173,980
  • 10
  • 155
  • 350
0

From the point of computational speed, it's better to go with separate vectors. Inlining virtual functions requires devirtualization, and although compilers often do it, it's hard to provide any guarantees.

Apart from that, there are caches (instruction and data), prefetchers, branch predictors - all those can benefit from homogenous traverse.

If you absolutely need to merge the vectors, you can try to append one to another, so that objects of one type would clump together. Perhaps you even can still do two separate traversals for two parts of the large vector, and avoid the virtaul calls.

In any case your best bet is to profile everything you can and determine whether the performance loss is acceptable (or noticeable at all).

Also as @Someprogrammerdude mentioned, std::accumulate comes to mind when looking at your code:)

Ap31
  • 3,244
  • 1
  • 18
  • 25
-2

the complier will inline simple function in Class. eg: A function just have return. So for your question, I think it do not.

blueMonster
  • 1
  • 1