C++ array access optimization

c++, optimization

Solution

I think loop unrolling is the booster.You may google it for detailed info.

Of course modulus operation can be slow..You may test it by replacing

src[i%srcsize] 

with

src[i] 

for the sake of timing tests.

Problem

Im modding an open-source project(powder toy) and always compiling with /O2 (maximize speed) option, SSE2 code generation enabled and just inspected this: ``` void membwand(void * destv, void * srcv, size_t destsize, size_t srcsize) { size_t i; unsigned char * dest = (unsigned char*)destv; unsigned char * src = (unsigned char*)srcv; for(i = 0; i < destsize; i++){ dest[i] = dest[i] & src[i%srcsize]; } } ``` Here I replaced below lines ``` membwand(gravy, gravmask, size_dst, size_src); membwand(gravx, gravmask, size_dst, size_src); // gravy, gravx and gravmask are 1MB each ``` with ``` membwand2(gravy,gravx, gravmask, size_dst, size_src); // sizes are same, why not put all in a single function? ``` which is implemented as: ``` void membwand2(void * destv1, void * destv2,void * srcv, size_t destsize, size_t srcsize) { if(destsize!=srcsize) { size_t i; unsigned char * dest1 = (unsigned char*)destv1; unsigned char * dest2 = (unsigned char*)destv2; unsigned char * src = (unsigned char*)srcv; for(i = 0; i < destsize; i++) { dest1[i] = dest1[i] & src[i%srcsize]; dest2[i] = dest2[i] & src[i%srcsize]; } } else { size_t i; unsigned char * dest1 = (unsigned char*)destv1;unsigned char * dest2 = (unsigned char*)destv2; unsigned char * src = (unsigned char*)srcv; unsigned char tmpChar0=0;unsigned char tmpChar1=0;unsigned char tmpChar2=0; unsigned char tmpChar3=0;unsigned char tmpChar4=0;unsigned char tmpChar5=0; unsigned char tmpChar6=0;unsigned char tmpChar7=0;unsigned char tmpChar8=0; unsigned char tmpChar9=0;unsigned char tmpChar10=0;unsigned char tmpChar11=0; unsigned char tmpChar12=0;unsigned char tmpChar13=0;unsigned char tmpChar14=0; unsigned char tmpChar15=0;unsigned char tmpChar16=0;unsigned char tmpChar17=0; unsigned char tmpChar18=0;unsigned char tmpChar19=0;unsigned char tmpChar20=0; unsigned char tmpChar21=0;unsigned char tmpChar22=0;unsigned char tmpChar23=0; unsigned char tmpChar24=0;unsigned char tmpChar25=0;unsigned char tmpChar26=0; unsigned char tmpChar27=0;unsigned char tmpChar28=0;unsigned char tmpChar29=0; unsigned char tmpChar30=0;unsigned char tmpChar31=0; for(i = 0; i < destsize; i+=32) { tmpChar0=src[i];tmpChar1=src[i+1];tmpChar2=src[i+2];tmpChar3=src[i+3]; tmpChar4=src[i+4];tmpChar5=src[i+5];tmpChar6=src[i+6];tmpChar7=src[i+7]; tmpChar8=src[i+8];tmpChar9=src[i+9];tmpChar10=src[i+10];tmpChar11=src[i+11]; tmpChar12=src[i+12];tmpChar13=src[i+13];tmpChar14=src[i+14];tmpChar15=src[i+15]; tmpChar16=src[i+16];tmpChar17=src[i+17];tmpChar18=src[i+18];tmpChar19=src[i+19]; tmpChar20=src[i+20];tmpChar21=src[i+21];tmpChar22=src[i+22];tmpChar23=src[i+23]; tmpChar24=src[i+24];tmpChar25=src[i+25];tmpChar26=src[i+26];tmpChar27=src[i+27]; tmpChar28=src[i+28];tmpChar29=src[i+29];tmpChar30=src[i+30];tmpChar31=src[i+31]; dest1[i] = dest1[i] & tmpChar0; dest1[i+1] = dest1[i+1] & tmpChar1; dest1[i+2] = dest1[i+2] & tmpChar2; dest1[i+3] = dest1[i+3] & tmpChar3; dest1[i+4] = dest1[i+4] & tmpChar4; dest1[i+5] = dest1[i+5] & tmpChar5; dest1[i+6] = dest1[i+6] & tmpChar6; dest1[i+7] = dest1[i+7] & tmpChar7; dest1[i+8] = dest1[i+8] & tmpChar8; dest1[i+9] = dest1[i+9] & tmpChar9; dest1[i+10] = dest1[i+10] & tmpChar10; dest1[i+11] = dest1[i+11] & tmpChar11; dest1[i+12] = dest1[i+12] & tmpChar12; dest1[i+13] = dest1[i+13] & tmpChar13; dest1[i+14] = dest1[i+14] & tmpChar14; dest1[i+15] = dest1[i+15] & tmpChar15; dest1[i+16] = dest1[i+16] & tmpChar16; dest1[i+17] = dest1[i+17] & tmpChar17; dest1[i+18] = dest1[i+18] & tmpChar18; dest1[i+19] = dest1[i+19] & tmpChar19; dest1[i+20] = dest1[i+20] & tmpChar20; dest1[i+21] = dest1[i+21] & tmpChar21; dest1[i+22] = dest1[i+22] & tmpChar22; dest1[i+23] = dest1[i+23] & tmpChar23; dest1[i+24] = dest1[i+24] & tmpChar24; dest1[i+25] = dest1[i+25] & tmpChar25; dest1[i+26] = dest1[i+26] & tmpChar26; dest1[i+27] = dest1[i+27] & tmpChar27; dest1[i+28] = dest1[i+28] & tmpChar28; dest1[i+29] = dest1[i+29] & tmpChar29; dest1[i+30] = dest1[i+30] & tmpChar30; dest1[i+31] = dest1[i+31] & tmpChar31; dest2[i] = dest2[i] & tmpChar0; dest2[i+1] = dest2[i+1] & tmpChar1; dest2[i+2] = dest2[i+2] & tmpChar2; dest2[i+3] = dest2[i+3] & tmpChar3; dest2[i+4] = dest2[i+4] & tmpChar4; dest2[i+5] = dest2[i+5] & tmpChar5; dest2[i+6] = dest2[i+6] & tmpChar6; dest2[i+7] = dest2[i+7] & tmpChar7; dest2[i+8] = dest2[i+8] & tmpChar8; dest2[i+9] = dest2[i+9] & tmpChar9; dest2[i+10] = dest2[i+10] & tmpChar10; dest2[i+11] = dest2[i+11] & tmpChar11; dest2[i+12] = dest2[i+12] & tmpChar12; dest2[i+13] = dest2[i+13] & tmpChar13; dest2[i+14] = dest2[i+14] & tmpChar14; dest2[i+15] = dest2[i+15] & tmpChar15; dest2[i+16] = dest2[i+16] & tmpChar16; dest2[i+17] = dest2[i+17] & tmpChar17; dest2[i+18] = dest2[i+18] & tmpChar18; dest2[i+19] = dest2[i+19] & tmpChar19; dest2[i+20] = dest2[i+20] & tmpChar20; dest2[i+21] = dest2[i+21] & tmpChar21; dest2[i+22] = dest2[i+22] & tmpChar22; dest2[i+23] = dest2[i+23] & tmpChar23; dest2[i+24] = dest2[i+24] & tmpChar24; dest2[i+25] = dest2[i+25] & tmpChar25; dest2[i+26] = dest2[i+26] & tmpChar26; dest2[i+27] = dest2[i+27] & tmpChar27; dest2[i+28] = dest2[i+28] & tmpChar28; dest2[i+29] = dest2[i+29] & tmpChar29; dest2[i+30] = dest2[i+30] & tmpChar30; dest2[i+31] = dest2[i+31] & tmpChar31; } } } ``` Omp wall clock timings were 17ms for two-lines version and 1.5ms for one-line version. (after several thousand iterations) Question: What could have cause the 9x speed-up? Data re-use of src[] or cache-utilization? Maybe code was not fit for vectorizing before, and unrolling enabled it, could it be the missing modulus operation for indexing? Should I add #pragma omp on top of loop? Edit: #pragma omp parallel for num_threads(4) made it worse somehow. Maybe just 1MB is not hiding multithread overhead? Edit2: ommiting the modulus operator made it 2.5 ms but the performance increase from 2.5ms to 1.5ms (~%60 increase) must have come from unrolling/cache/... Note: enabling "favor fast code", enabling whole program optimization, full optimization(/Ox) and enabling intrinsics did not change the speed(maybe enabling SSE2 and /O2 was enough) CPU: FX8150 IDE: Msvc

Original source