ansaurus

Question

Why is pointer access slower than vector::iterator access? (compiler code generation)

Answer 1

A:

Looking at the assembly generated for the inner loops, they are essentially identical except for one register change. I wouldn't expect any timing difference on that basis.

            g_read_size = *j; 
00  movzx       ecx,word ptr [esi]  
00  mov         dword ptr [g_read_size (4060B0h)],ecx  
            side_effect(); 
00  call        side_effect (401020h)  
00  add         esi,2  
00  cmp         esi,edi  
00  jne         raw_iterator_loop+30h (4028A0h)

            g_read_size = *j;  
00  movzx       eax,word ptr [esi]   
00  mov         dword ptr [g_read_size (4060B0h)],eax   
            side_effect();  
00  call        side_effect (401020h)   
00  add         esi,2   
00  cmp         esi,edi   
00  jne         vector_iterator_loop+21h (4027F1h)

I had a similar question on code timing where I couldn't explain a difference in two pieces of code. I never got a definitive answer on that one, although in the end I convinced myself that it was a case of code alignment. http://stackoverflow.com/questions/688325/how-can-adding-code-to-a-loop-make-it-faster

Mark Ransom 2010-10-14 17:01:09

Answer 2

A:

Try changing PodType from int to size_t. The conversion there complicates the loop initialization code.

ybungalobill 2010-10-14 17:02:09

Answer 3

+1 A:

The compiler has no way to know that side_effect() doesn't change obj->pData. Storing things that cannot change in local variables can speed up tight loops, especially when functions that the compiler cannot analyze are called inside the loop.

p.S.: this affects raw_loop and vector_loop. raw_loop can be "fixed" by using local variables, vector_loop can't. It can't, because there will be an array-pointer inside the vector, and the compiler also has no way of knowing that nothing will change the array-pointer inside the vector. After all, side_effect could call e.g. push_back(). Of course, if the compiler can inline any of the loop-functions, it could possibly optimize better. E.g. if the used vector is a local variable who's address isn't known outside the function, and only passed to the loop functions. Then the compiler could again know that side_effect cannot change the vector (because it cannot know it's address), and optimize better. -> Make sure the compiler cannot inline the function if you want to optimize it for non-inlining cases.

pgroke 2010-10-14 17:04:09

Answer 4

A:

I would have expected the optimizer to be smart enough to remove any differences, but typically a decrement-and-compare-to-zero is faster than a comparison to a non-zero pointer.

e.g.

void countdown_loop(int n, RawX* obj)
{
    if (!n) return;
    size_t const wc = obj->wCount;
    if (!wc) return;
    PodType* const first = obj->pData;
    do {
        side_effect();
        size_t i = wc;
        PodType* p = first;
        do {
            g_read_size = *p;
            side_effect();
            ++p;
        } while (--i);
        side_effect();
    } while (--n);
}

Ben Voigt 2010-10-14 17:09:52

Answer 5

+1 A:

One concrete reason for the difference in instructions generated is that Visual C++ vector has members _Myfirst and _Mylast (corresponding to begin() and end()) that simplify the loop setup.

In the raw case, the compiler has to do actual pointer math to set up the required start and end locals.

It's feasible that this complicates register usage enough to make the vector code faster.

Steve Townsend 2010-10-14 17:12:03

Answer 6

+6 A:

While my version of the generated machine code is different from yours (MSVC++ 2005), one difference between the two variants is pretty much the same as in your code:

In vector version of the code the "end iterator" value is pre-calculated and stored as a member of std::vector object, so the inner loop simply loads the readily available value.
In raw pointer version the "end iterator" value is calculated explicitly in the header of the inner cycle (by a lea instruction used to implement multiplication), meaning that each iteration of the outer cycle performs that calculation again and again.

If you re-implement your raw_iterator_loop as follows (i.e. pull the calculation of the end pointer out of the outer loop)

void raw_iterator_loop(const int n, RawX* obj)
{
    PodType *e = obj->pData+size_t(obj->wCount);

    for(int i=0; i!=n; ++i) {
        side_effect();
        for(PodType *j=obj->pData; j!=e; ++j) {
            g_read_size = *j;
            side_effect();
        }
        side_effect();
    }
}

(or even store and maintain the end pointer in your class) you should end up with a more "fair" comparison.

AndreyT 2010-10-14 17:14:18

Yay! That makes sense: *the "end iterator" value is pre-calculated and stored as a member of std::vector object* ... I forgot that the vector stores the end pointer and not the size!

Martin 2010-10-14 17:28:33

Marking this as answer because it explains the assembly differences.

Martin 2010-10-14 18:11:17

Answer 7

+1 A:

Your timings might reflect the fact that the initial raw_loop pays the cost for loading the cache. Do you get similar timings if you reorder the tests to do the vector tests first (Or you could throw out the first iteration, or make each test a separate program).

Joe Valenzuela 2010-10-14 17:19:28

ansaurus

tags:

views:

answers:

Why is pointer access slower than vector::iterator access? (compiler code generation)

related questions