🔒 Locked 🎮 Unity

performence issues (std::vector, memcpy etc)

Started by GameGo Jan 14, 2007 at 3:47 AM 7 replies 1.2k views

Original Post

Jan 14, 2007 at 3:47 AM

i have written a small program to test the performence of different methods for assigning elements of std::vector. ( environment: amd 3000+, vc++ 8.0, windows xp), below is the code patch //////////////////////////////////////////////////// int count = 100; int size = 100000; vector v1, v2, v3; //case 1 sw1.Start(); //stopwatch for performence for(int i = 0; i < count ; i++) { for(int j = 0; j < size; j++) v1.push_back(j); } sw1.Stop(); cout<<sw1.GetTime()<<endl; //case 2 sw2.Start(); for(int i = 0; i < count ; i++) { v2.resize((i+1) * size); memcpy(&v2[i*size], t, sizeof(int)*size); } sw2.Stop(); cout<<sw2.GetTime()<<endl; //case 3 sw3.Start(); int k = 0; for(int i = 0; i < count ; i++) { v2.resize((i+1) * size); for(int j = 0; j < size; j++) v2[k++] = t[j]; } sw3.Stop(); cout<<sw3.GetTime()<<endl; //case 4 sw4.Start(); for(int i = 0; i < count ; i++) { v3.reserve((i+1) * size); for(int j = 0; j < size; j++) v3.push_back(j); } sw4.Stop(); cout<<sw4.GetTime()<<endl; ======================================================= the result is: (s) case1: 0.238482 case2: 0.312511 case3: 0.087241 case4: 4.76303 What suprised me most is that case 2 is so slow compared with case3, memcpy 's performence is worse than "for " loop ! anybody can explain this ? Thanks

joanusdmentia

Jan 14, 2007 at 4:16 AM

Ignoring the fact that these sorts of performance 'tests' are next to useless, it looks like your cases are mixed up. Also check that you're compiling in release mode, not debug mode. What I would have expected is that cases 2 and 3 would have nearly identical times with case 4 maybe being a little slower (all three should all boil down to nearly the same thing with any decent optimising compiler, which vc8 is), and case 1 being considerably slower (since it has to perform a number of reallocations as it dynamically sizes the vector).

Brother Bob

Jan 14, 2007 at 4:16 AM

The time for case 2 is for 100 memory allocations of increasingly larger blocks followed by a memcpy. The time for case 3 is filling the vector 100 times with a loop variable.

Since the vector is already large enough from case 2, case 3 doesn't need to allocate anything.

Julian90

Jan 14, 2007 at 4:24 AM

-1) Artificial performance comparisons like this are generally useless as the method that is most effecient will vary in different situations.

0) place the code between [ source ] and [ /source ] without the spaces

1) For your stated purposes this

Quote:

//case 2sw2.Start();for(int i = 0; i < count ; i++){    v2.resize((i+1) * size);    memcpy(&v2[i*size], t, sizeof(int)*size);}sw2.Stop();cout << sw2.GetTime() << endl;

is fundamentaly flawed as memcopy will only produce the desired result of "assigning elements to std::vector" when you have a vector of PoD's, a safer corrected version would be

sw2.Start();for(int i = 0; i < count ; i++){    v2.resize((i+1) * size);    {        std::vector<int>::iterator start = v2.begin() + i*size        std::copy(start, start + t);    }}sw2.Stop();cout << sw2.GetTime() << endl;

2) The most likely reason for Case 3's superior performance in comparison to Case 2's is that in Case 3 std::vector is able to take advantage of its knowledge of the types of the elements that it is copying to produce superiour code from a performance perspective whearas in Case 2 memcpy has no knowledge of the types being copied, all it knows is it is copying a chunk of memory, and hence cannot take advantage of that knowledge. The revised Case 2 that i posted above would in all likely hood outperform both versions as std::copy is able to take advantage of both the type information and the fact that it is copying a series of elements (Case 3 only knows the type and the origonal Case 2 only knows it is copying a chunk of memory)

Edit: oh didnt notice the mistake of reusing the same vector in Case 2 and Case 3 still std::copy should be identicle if not better from a performance perspective and is definatly safer then memcpy

Zipster

Jan 14, 2007 at 4:25 AM

You probably meant to use different vectors for case 2 and case 3, which is why you're getting unexpected results. Bob summed up why.

GameGo

Jan 14, 2007 at 4:27 AM

sorry i do make a mistake in the program. : )

in case 3, i should use another vector.

ok. now. there is no performence difference with case 2,3

Zahlman

Jan 14, 2007 at 11:20 AM

The previous AP has it - case 1 is faster because in cases 2 and 3 you are defeating the exponential reallocation scheme. The *proper* way to make use of .resize() or .reserve() would be outside the loop (and you want .reserve() here because it does you no good to initialize all those elements first).

// a sensible replacement for cases 2 and 3sw2.Start();v2.reserve(i * size); // no idea where your +1 correction factor was coming fromfor(int i = 0; i < count; i++) {  // can't memcpy() into reserved space, but you can do this:  std::copy(t, t + size, std::back_inserter<int>(v2));}sw2.Stop();cout<<sw2.GetTime()<<endl;// OR, resizing and then doing "plain" copying:sw2.Start();v2.resize(i * size); // no idea where your +1 correction factor was coming fromfor(int i = 0; i < count; i++) {  std::copy(t, t + size, v2.begin() + size * i);}sw2.Stop();cout<<sw2.GetTime()<<endl;

Note that std::copy can let you work in memcpy-like ways (and indeed also works on plain arrays), will optimize into the same code memcpy would when that's possible, and will behave safely and correctly otherwise (e.g. if you copy a container of std::strings). Oh, and you never have to worry about the sizeof() the element type. It wins in many ways and loses only when your compiler sucks; so don't use memcpy() in C++ code. (Similarly, replace memset() with std::fill().) These algorithms live in .

ghostd0g

Jan 15, 2007 at 8:07 AM

if your really need it (Premature optimization == root of all evil), the "AMD Athlon Processor x86 Code Optimization Guide" might help. helped us in some cases.

#define TINY_BLOCK_COPY     64#define IN_CACHE_COPY       64  * 1024#define UNCACHED_COPY       197 * 1024#define CACHEBLOCK          0x80#define PREFETCH_DIST       600#define DEST                [esp + 16]#define SOURCE              [esp + 20]#define NROFBYTES           [esp + 24]__declspec(naked) void* MemCopy(void* /* dest */, const void* /* src */, unsigned /* nrOfBytes */){    __asm    {        push        esi        push        edi        push        ebx        mov         ecx, NROFBYTES        mov         edi, DEST        mov         esi, SOURCE        mov         ebx, ecx        cmp         ecx, TINY_BLOCK_COPY        jb          $memcpy_ic_3        cmp         ecx, 32 * 1024        jbe         $memcpy_do_align        cmp         ecx, 64 * 1024        jbe         $memcpy_align_done$memcpy_do_align:        mov         ecx, 8        sub         ecx, edi        and         ecx, 111b        sub         ebx, ecx        neg         ecx        add         ecx, offset $memcpy_align_done        jmp         ecxalign 4        movsb        movsb        movsb        movsb        movsb        movsb        movsb        movsb$memcpy_align_done:        mov         ecx, ebx        shr         ecx, 6        jz          $memcpy_ic_2        cmp         ecx, IN_CACHE_COPY / 64        jae         $memcpy_uc_testalign 16$memcpy_ic_1:        prefetchnta [esi + PREFETCH_DIST]             prefetchnta [esi + PREFETCH_DIST + 32]        movq        mm0, [esi+ 0]        movq        mm1, [esi+ 8]        movq        mm2, [esi+16]        movq        mm3, [esi+24]        movq        mm4, [esi+32]        movq        mm5, [esi+40]        movq        mm6, [esi+48]        movq        mm7, [esi+56]        movq        [edi+ 0], mm0        movq        [edi+ 8], mm1        movq        [edi+16], mm2        movq        [edi+24], mm3        movq        [edi+32], mm4        movq        [edi+40], mm5        movq        [edi+48], mm6        movq        [edi+56], mm7        add         esi, 64        add         edi, 64         dec         ecx        jnz         $memcpy_ic_1$memcpy_ic_2:        mov         ecx, ebx$memcpy_ic_3:        shr         ecx, 2        and         ecx, 1111b        neg         ecx        add         ecx, offset $memcpy_last_few        jmp         ecx$memcpy_uc_test:        cmp         ecx, UNCACHED_COPY / 64        jae         $memcpy_bp_1$memcpy_64_test:        or          ecx, ecx        jz          $memcpy_ic_2align 16$memcpy_uc_1:        prefetchnta [esi + PREFETCH_DIST]              prefetchnta [esi + PREFETCH_DIST + 32]         movq        mm0, [esi+ 0]        movq        mm1, [esi+ 8]        movq        mm2, [esi+16]        movq        mm3, [esi+24]        movq        mm4, [esi+32]        movq        mm5, [esi+40]        movq        mm6, [esi+48]        movq        mm7, [esi+56]        movntq      [edi+ 0], mm0        movntq      [edi+ 8], mm1        movntq      [edi+16], mm2        movntq      [edi+24], mm3        movntq      [edi+32], mm4        movntq      [edi+40], mm5        movntq      [edi+48], mm6        movntq      [edi+56], mm7        add         esi, 64         add         edi, 64         dec         ecx        jnz         $memcpy_uc_1        jmp         $memcpy_ic_2$memcpy_bp_1:         cmp         ecx, CACHEBLOCK        jl          $memcpy_64_test        mov         eax, CACHEBLOCK / 2        add         esi, CACHEBLOCK * 64align 16$memcpy_bp_2:        mov         edx, [esi- 32]        mov         edx, [esi- 64]        mov         edx, [esi- 96]        mov         edx, [esi-128]        sub         esi, 128             dec         eax                  jnz         $memcpy_bp_2         mov         eax, CACHEBLOCKalign 16$memcpy_bp_3:        /*        prefetchnta [esi + PREFETCH_DIST]             prefetchnta [esi + PREFETCH_DIST + 32]        */        movq        mm0, [esi+ 0]        movq        mm1, [esi+ 8]        movq        mm2, [esi+16]        movq        mm3, [esi+24]        movq        mm4, [esi+32]        movq        mm5, [esi+40]        movq        mm6, [esi+48]        movq        mm7, [esi+56]        movntq      [edi+ 0], mm0        movntq      [edi+ 8], mm1        movntq      [edi+16], mm2        movntq      [edi+24], mm3        movntq      [edi+32], mm4        movntq      [edi+40], mm5        movntq      [edi+48], mm6        movntq      [edi+56], mm7        add         esi, 64        add         edi, 64        dec         eax                       jnz         $memcpy_bp_3              sub         ecx, CACHEBLOCK        jmp         $memcpy_bp_1align 4        movsd        movsd        movsd        movsd        movsd        movsd        movsd        movsd        movsd        movsd        movsd        movsd        movsd        movsd        movsd        movsd$memcpy_last_few:        mov         ecx, ebx        and         ecx, 11b        jz          $memcpy_final        rep         movsb$memcpy_final:        emms            sfence          mov         eax, DEST        pop         ebx                 pop         edi        pop         esi        ret    }}

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.