I have four classes representing an inheritance and composition hierarchy:
class A{
//Structure here not important
}
class B : public A{
int a;
shared_ptr<C> c;
}
class C{
shared_ptr<D> d;
}
class D{
std::list<int> e;
}
I then have a vector<shared_ptr<A>>
, I iterate though and sum the *begin()
values from the two D std::list<int>
objects:
for(int i = 0; i< vec.size(); i++){
shared_ptr<B> b = vec[i];
shared_ptr<C> c = b->c;
sum += *(c->d->e.begin());
}
I am trying to work out how many separate cache line accesses could be made per each loop iteration (if we assume the worst-case scenario where each level of indirection/pointer is stored in a different cache line).
So far I have calculated 7.25 different cache lines per iteration:
shared_ptr<A>
to vec[i]
(this is 0.25 because sizeof(shared_ptr<A>)/64
)A
object vec[i]
points toshared_ptr<C>
c points toC
object c
points toshared_ptr<D>
object for dD d
d
's std::list<int> e
pointerd
's *begin()
dataIs there anything I have missed? I am unsure if the objects created on the stack inside the loop (b
and c
) could be stored in different cache lines to the pointers they are accessing (vec[i]
and b->c
).
Answer added to complement conversation in the comments
here is your loop with some comments:
for(int i = 0; i< vec.size(); i++){
shared_ptr<B> b = vec[i]; // create 1 copy of vec[i] - increments share cout
shared_ptr<C> c = b->c; // create 1 copy of b->c - increments share cout
sum1 += *(c->d1->e.begin()); // merely dereference pointer
sum2 += *(c->d2->e.begin()); // merely dereference pointer
}
you can save some copies, and therefore some cache line misses if you write it like this:
for(int i = 0; i< vec.size(); i++){
// take reference only - no copy.
//const means I promise not to modify the pointer object.
const shared_ptr<B>& b = vec[i];
// take reference only - no copy.
//const means I promise not to modify the pointer object.
const shared_ptr<C>& c = b->c; // dereference b (which is really vec[i])
sum1 += *(c->d1->e.begin()); // merely dereference pointer
sum2 += *(c->d2->e.begin()); // merely dereference pointer
}