Search code examples
c++performancepointerscpucpu-cache

How many different pointers/levels of indirection are accessed here?


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:

  1. Accessing the shared_ptr<A> to vec[i] (this is 0.25 because sizeof(shared_ptr<A>)/64)
  2. Accessing the A object vec[i] points to
  3. Accessing the shared_ptr<C> c points to
  4. Accessing the C object c points to
  5. Accessing the shared_ptr<D> object for d
  6. Accessing the object D d
  7. Accessing d's std::list<int> e pointer
  8. Accessing d's *begin() data

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


Solution

  • 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
    }