vector is very slow

Started by
29 comments, last by Nitage 17 years, 11 months ago
Quote:Original post by Thelo
I've done some benchmarks using similar code to the above, and the numbers are about in these proportions:

Using the original method: 460~480
Putting the vector static: 38~46
Using a pure array: 26~28

Putting the division inside the loop or outside it doesn't affect anything.

Since this is a very large list, that this code snippet will probably be used pretty often and potentially be a performance bottleneck (as implied by the names referring to pixels and surfaces), and that the size of the vector/array will be known at creation and fixed for the duration of the operation (again, it's a list of the pixels of a given surface), I'd simply recommend using a pure array in this situation.


Can we see your test code please, I want to try it. I'm curious as to how you got such radically different results, seeing as here the results aren't off by much, and I managed to get almost equal values by ramping up optimisations.

Advertisement
Quote:Original post by rip-off
Can we see your test code please, I want to try it. I'm curious as to how you got such radically different results, seeing as here the results aren't off by much, and I managed to get almost equal values by ramping up optimisations.
One difference between the vector and a dynamic array is that the vector as shown here default-initializes its elements to 0 while a dynamic array doesn't. Since the following loop is a simple operation, a memcpy, the complulsory memset for vectors might affect that much to the performance.
Quote:Original post by Anonymous Poster
Quote:Original post by rip-off
Can we see your test code please, I want to try it. I'm curious as to how you got such radically different results, seeing as here the results aren't off by much, and I managed to get almost equal values by ramping up optimisations.
One difference between the vector and a dynamic array is that the vector as shown here default-initializes its elements to 0 while a dynamic array doesn't. Since the following loop is a simple operation, a memcpy, the complulsory memset for vectors might affect that much to the performance.
Oh wait, I was comparing the numbers for "static vector" and "pure array".. memset definitely shouldn't take 20 times as long as memcpy ;).

Anyway, another difference is that stack-allocation is faster than the heap allocation that vector must use. But definitely shouldn't be by that much
Quote:Original post by Anonymous Poster
Quote:Original post by Anonymous Poster
Quote:Original post by rip-off
Can we see your test code please, I want to try it. I'm curious as to how you got such radically different results, seeing as here the results aren't off by much, and I managed to get almost equal values by ramping up optimisations.
One difference between the vector and a dynamic array is that the vector as shown here default-initializes its elements to 0 while a dynamic array doesn't. Since the following loop is a simple operation, a memcpy, the complulsory memset for vectors might affect that much to the performance.
Oh wait, I was comparing the numbers for "static vector" and "pure array".. memset definitely shouldn't take 20 times as long as memcpy ;).

Anyway, another difference is that stack-allocation is faster than the heap allocation that vector must use. But definitely shouldn't be by that much


Hence my curiousity :)
Quote:Original post by rip-off
Can we see your test code please, I want to try it. I'm curious as to how you got such radically different results, seeing as here the results aren't off by much, and I managed to get almost equal values by ramping up optimisations.

Sure. Here's what I used:
typedef struct {    int foo, bar, baz;    int Pitch;} tLockrect;DWORD pixellist2[1024*1024];void TestFunction() {    std::vector<DWORD> pixellist(1024 * 1024);    tLockrect lockrect;    lockrect.Pitch = 24;    DWORD dword[8] = {8, 7, 6, 5, 4, 3, 2, 1};    int denom = lockrect.Pitch/4;    for(int i =0;i<640;i++) {        for(int j=0;j<480;j++) {            int index = i*lockrect.Pitch/4 + j;            pixellist[index] = dword[index % 8];        }    }}void TestFunction2() {    static std::vector<DWORD> pixellist(1024 * 1024);    tLockrect lockrect;    lockrect.Pitch = 24;    DWORD dword[8] = {8, 7, 6, 5, 4, 3, 2, 1};    int denom = lockrect.Pitch/4;    for(int i =0;i<640;i++) {        for(int j=0;j<480;j++) {            int index = i*lockrect.Pitch/4 + j;            pixellist[index] = dword[index % 8];        }    }}void TestFunction3() {    tLockrect lockrect;    lockrect.Pitch = 24;    DWORD dword[8] = {8, 7, 6, 5, 4, 3, 2, 1};    for(int i =0;i<640;i++) {        for(int j=0;j<480;j++) {            int index = i*lockrect.Pitch/4 + j;            pixellist2[index] = dword[index % 8];        }    }}


Then, to actually test these out (I put this in a sandbox Win32 application, hence the SetDlgItemText line)
    int i;    DWORD startTime = timeGetTime();    for (i = 0; i < 50; i++) {        TestFunction();    }    DWORD endTime = timeGetTime();    SetDlgItemText(dialogHwnd, IDC_EDIT1, int2str(endTime - startTime).c_str());


The whole thing was compiled with Visual Studio 2003, in release mode, without managed extensions. I used a global array instead of a local one to prevent the compiler from optimizing the whole operation away.
If it's always 1024*1024 you could even use a stack carray und increase the stack size in your compiler settings.
Quote:Original post by Extrarius
Quote:Original post by Thelo
Quote:Original post by Anonymous Poster
It's clearly the division you've got inside your index calculation, move this outside of your loops, it's a complete waste of cpu cycles to calculate it ever and ever again.


A division by 4 is likely to be optimized to a bitshift, which is unlikely to be a great cause of performance loss (one cycle for every iteration).
Calculating something that is loop invariant more than a single time would be a waste of CPU time. Using a compiler that doesn't optimize such things and/or optimizing it manually would be a waste of programmer time. Trying to optimize without profiling would also be a complete waste of programmer time, and considering such details as to whether it's implemented as a multiply, a shift, a load effective address, or anything else is a worse waste of programmer time.


While I'm totally with you that optimization should be done after a profiling session, I believe its good practice to move out of loops calculations that are not affected by this loop. It makes the code clearer in my opinion. For the same reason I'd rather do ++itor instead of itor++ and then optimize it after finding out I'm wasting too many cycles iterating through a list, that's the kind of thing that's really easy to do the first time.
Did any of you optimizers consider the possibility that the copied data doesn't fill the entire container (but a sub-rectangle), and that the other values do need to be zeroed out?

Anyway, the loops can be replaced with:

for (int i = 0; i < desc.Height; ++i) {  int index = i * lockrect.Pitch / 4;  std::copy(dword + index, dword + index + desc.Width, pixellist.begin() + index);}


For DWORDs, the std::copy call is likely to be transformed into memcpy or memmove behind the scenes.

Of course, if you feel like doing the compiler's job for it, or showing off, you *could* manage the loop invariants yourself:

// Note, I'm not at all sure I got this right. Which is why you shouldn't do these things.const int stride = lockrect.Pitch / 4;// I assume the Pitch is divisible by 4DWORD* last = desc.Height * stride + dword;for (DWORD* i = &pixellist[0], j = dword; j < last; i += stride, j += stride) {  std::copy(j, j + desc.Width, i);}
Here is my test. I added and changed some things, I hope you don't mind though, they shouldn't affectthe test.

struct tLockrect{    int foo, bar, baz;    int Pitch;};// made it global to make the functions easierDWORD dword[8] = {8, 7, 6, 5, 4, 3, 2, 1};// normal vector testvoid TestFunction1(){    std::vector<DWORD> pixellist1(640 * 480);    tLockrect lockrect;    lockrect.Pitch = 24;        for(int i =0;i<640;i++) {        for(int j=0;j<480;j++) {            int index = i*lockrect.Pitch/4 + j;            pixellist1[index] = dword[index % 8];        }    }}// static vector testvoid TestFunction2(){    static std::vector<DWORD> staticpixellist(640 * 480);    tLockrect lockrect;    lockrect.Pitch = 24;    for(int i =0;i<640;i++) {        for(int j=0;j<480;j++) {            int index = i*lockrect.Pitch/4 + j;            staticpixellist[index] = dword[index % 8];        }    }}// normal array testvoid TestFunction3(){    DWORD pixellist2[640*480];    tLockrect lockrect;    lockrect.Pitch = 24;    for(int i =0;i<640;i++) {        for(int j=0;j<480;j++) {            int index = i*lockrect.Pitch/4 + j;            pixellist2[index] = dword[index % 8];        }    }}// dynamic array testvoid TestFunction4(){    DWORD *pixellist4 = new DWORD[640*480];        tLockrect lockrect;    lockrect.Pitch = 24;    for(int i =0;i<640;i++) {        for(int j=0;j<480;j++) {            int index = i*lockrect.Pitch/4 + j;            pixellist4[index] = dword[index % 8];        }    }        delete pixellist4;}// global array testDWORD pixellist5[640*480];void TestFunction5(){        tLockrect lockrect;    lockrect.Pitch = 24;    for(int i =0;i<640;i++) {        for(int j=0;j<480;j++) {            int index = i*lockrect.Pitch/4 + j;            pixellist5[index] = dword[index % 8];        }    }}// global vector teststd::vector<DWORD> pixellist6(640 * 480);void TestFunction6(){    tLockrect lockrect;    lockrect.Pitch = 24;    for(int i =0;i<640;i++) {        for(int j=0;j<480;j++) {            int index = i*lockrect.Pitch/4 + j;            pixellist6[index] = dword[index % 8];        }    }}#define test(x) { \     startTime = SDL_GetTicks(); \     for( int i = 0 ; i < 50 ; ++i )\     {\         TestFunction##x();\     }\     t##x##time += SDL_GetTicks() - startTime; \             }                void runTests(){    DWORD t1time = 0, t2time = 0, t3time = 0, t4time = 0, t5time = 0, t6time = 0;    for( int j = 0; j < 50 ; ++j )    {        DWORD startTime;        test(1);        test(2);        test(3);        test(4);        test(5);        test(6);    }    cout << "time for test1 was " << t1time << std::endl;    cout << "time for test2 was " << t2time << std::endl;    cout << "time for test3 was " << t3time << std::endl;    cout << "time for test4 was " << t4time << std::endl;    cout << "time for test5 was " << t5time << std::endl;    cout << "time for test6 was " << t6time << std::endl;}


Some sample results:

time for test1 was 12950time for test2 was 2490time for test3 was 2470time for test4 was 9873time for test5 was 2887time for test6 was 2904time for test1 was 12974time for test2 was 2489time for test3 was 2474time for test4 was 9885time for test5 was 2892time for test6 was 2870time for test1 was 12927time for test2 was 2481time for test3 was 2492time for test4 was 9811time for test5 was 2899time for test6 was 2902time for test1 was 12955time for test2 was 2483time for test3 was 2510time for test4 was 9869time for test5 was 2896time for test6 was 2898time for test1 was 12926time for test2 was 2483time for test3 was 2481time for test4 was 9828time for test5 was 2881time for test6 was 2869



However, there is the issue of scope... Only the functions here that use globals actaully have output. You cannot return stack variables, so here I think passing a vector reference would be the "fastest" way of doing something actaully useful. A static array of known size is very limiting, why not use a vector instead, to give you more options later on.

After all, this test shows that the main speed problems were caused by the obtaining, releasing and ( not demonstrated but probably ) the zeroing of the elements.

Also, in your test you overallocated the vector, compared to the amount of space used. The vectors ctor must zero that extra space, so that biases your results. Also, making the array a global instead of a stack variable also changes the results.
Just a quick note for those interested:

In the latest STL implementation by MS in VC++ 2005, bounds checking is done even in release builds by default. To disable this behavior, you must #define _SCL_SECURE to be 0 before including any STL headers.

This topic is closed to new replies.

Advertisement