Are there faster accessing arrays than vectors?
-
Hi all, I`ve written some convolution code and managed to get the filters and stuff going fine, the only trouble is the speed! If I so much as use a vector once in the final nested for loop (where it works out the position of the filter with regards to the image) it slows the process down considerably (and I mean considerably - instead of being instant, theres at least a couple of seconds delay). In my code I *need* to access this memory bank at least three times in the final nested for loop (once for Red, Green Blue). Delphi has dynamic arrays which do the job perfectly, I was just wondering what the best way was in VC++? I`ve thought of using pointers, performing a small sum and accessing the pointer at that position, however I`d prefer to use the [] operator as it makes my code that little bit easier to read. Any ideas on better methods for quick access to retrieving data in memory, or as to why my bloody vectors are so slow (I'm using multidimensional vectors, 2-d ones, the location of which is stored in a vector, so I`m actually using a vector of a vector of a vector, but I didn`t think this should slow it down to the amount it is doing? Also my images are quite small, if used a large image I could probably make myself a cup of tea and drink it before it finished!!!) would be much appreciated. Thanks anyway guys, Alan. "When I left you I was but the learner, now I am the Master" - Darth Vader:mad:
-
Hi all, I`ve written some convolution code and managed to get the filters and stuff going fine, the only trouble is the speed! If I so much as use a vector once in the final nested for loop (where it works out the position of the filter with regards to the image) it slows the process down considerably (and I mean considerably - instead of being instant, theres at least a couple of seconds delay). In my code I *need* to access this memory bank at least three times in the final nested for loop (once for Red, Green Blue). Delphi has dynamic arrays which do the job perfectly, I was just wondering what the best way was in VC++? I`ve thought of using pointers, performing a small sum and accessing the pointer at that position, however I`d prefer to use the [] operator as it makes my code that little bit easier to read. Any ideas on better methods for quick access to retrieving data in memory, or as to why my bloody vectors are so slow (I'm using multidimensional vectors, 2-d ones, the location of which is stored in a vector, so I`m actually using a vector of a vector of a vector, but I didn`t think this should slow it down to the amount it is doing? Also my images are quite small, if used a large image I could probably make myself a cup of tea and drink it before it finished!!!) would be much appreciated. Thanks anyway guys, Alan. "When I left you I was but the learner, now I am the Master" - Darth Vader:mad:
If your vector exists prior to the loop ( i.e. is not created or modified in terms of size inside the loop ), then I don't see why this would happen. A vector IS a pointer ( a block of continuous memory accessed using pointer offsets ), so you wouldn't get any speed doing it the pointer way, I would think. Having said that, I have always used pointer logic to step through bitmaps myself, and don't consider it hard to read. In other words, I do not speak from experience as I've only done it the alternative way you're proposing in the first place ;) Christian After all, there's nothing wrong with an elite as long as I'm allowed to be part of it!! - Mike Burston Oct 23, 2001
Sonork ID 100.10002:MeanManOz
I live in Bob's HungOut now
-
Hi all, I`ve written some convolution code and managed to get the filters and stuff going fine, the only trouble is the speed! If I so much as use a vector once in the final nested for loop (where it works out the position of the filter with regards to the image) it slows the process down considerably (and I mean considerably - instead of being instant, theres at least a couple of seconds delay). In my code I *need* to access this memory bank at least three times in the final nested for loop (once for Red, Green Blue). Delphi has dynamic arrays which do the job perfectly, I was just wondering what the best way was in VC++? I`ve thought of using pointers, performing a small sum and accessing the pointer at that position, however I`d prefer to use the [] operator as it makes my code that little bit easier to read. Any ideas on better methods for quick access to retrieving data in memory, or as to why my bloody vectors are so slow (I'm using multidimensional vectors, 2-d ones, the location of which is stored in a vector, so I`m actually using a vector of a vector of a vector, but I didn`t think this should slow it down to the amount it is doing? Also my images are quite small, if used a large image I could probably make myself a cup of tea and drink it before it finished!!!) would be much appreciated. Thanks anyway guys, Alan. "When I left you I was but the learner, now I am the Master" - Darth Vader:mad:
Depending on what you have in your vector it's quite possible you are copying the data out of the vector instead of accessing it. Can you describe what you are stroing in your vector and how you're accessing it?
Todd Smith
-
Hi all, I`ve written some convolution code and managed to get the filters and stuff going fine, the only trouble is the speed! If I so much as use a vector once in the final nested for loop (where it works out the position of the filter with regards to the image) it slows the process down considerably (and I mean considerably - instead of being instant, theres at least a couple of seconds delay). In my code I *need* to access this memory bank at least three times in the final nested for loop (once for Red, Green Blue). Delphi has dynamic arrays which do the job perfectly, I was just wondering what the best way was in VC++? I`ve thought of using pointers, performing a small sum and accessing the pointer at that position, however I`d prefer to use the [] operator as it makes my code that little bit easier to read. Any ideas on better methods for quick access to retrieving data in memory, or as to why my bloody vectors are so slow (I'm using multidimensional vectors, 2-d ones, the location of which is stored in a vector, so I`m actually using a vector of a vector of a vector, but I didn`t think this should slow it down to the amount it is doing? Also my images are quite small, if used a large image I could probably make myself a cup of tea and drink it before it finished!!!) would be much appreciated. Thanks anyway guys, Alan. "When I left you I was but the learner, now I am the Master" - Darth Vader:mad:
Yeah I`m only storing integers in the vectors, and as Christian said I can`t understand why the vectors are so slow. However, I`ve since adopted a pointer to an int system, and used a small calculation to work out the position of the relevant integer in the list that is to be used in the convolution stuff. Result - it was sh**loads faster. Just by changing from vectors to pointers made an absolutely massive difference (it was literally the difference between almost instansteously performing the convolution, and waiting a good few seconds for the *exact* same code to run through). I think it must just be because I`m accessing my vectors like so:
...
for (int i=0; i<3; i++)
for (int j=0; j<3; j++)
{
*blue = blue + *(pBits+0) * myVector[a][b];
*green = green + *(pBits+1) * myVector[a][b];
*red = red + *(pBits+2) * myVector[a][b];
}
...Instead of using myVector, I use pointers to an int (pInt - for arguments sake, and cos I like pInts of strongbow!), as follows : *(pInt+(a*width+b)); And the result is that its loads faster. Hope someone can shed some light on why this is the case, although it doesn`t matter to me now, I`d still like to know why? Thanks guys, Cheers, Alan. P.S. Christian, I think to me, you and the others who are improving their C++ vocabulary every day, reading pointer code is a *relatively* simple task. However, the reason I mentioned this before is that some of my MSc markers are real programming bone heads (the're mathematicians), so I was just thinking that such people might find it *easier* to read and *understand* the vector code, what do you reckon? I`m gonna go with the pointer stuff anyway, it just means extra explanation in the final write up. Cheers though for your advice I do appreciate it. "When I left you I was but the learner, now I am the Master" - Darth Vader:mad:
-
Yeah I`m only storing integers in the vectors, and as Christian said I can`t understand why the vectors are so slow. However, I`ve since adopted a pointer to an int system, and used a small calculation to work out the position of the relevant integer in the list that is to be used in the convolution stuff. Result - it was sh**loads faster. Just by changing from vectors to pointers made an absolutely massive difference (it was literally the difference between almost instansteously performing the convolution, and waiting a good few seconds for the *exact* same code to run through). I think it must just be because I`m accessing my vectors like so:
...
for (int i=0; i<3; i++)
for (int j=0; j<3; j++)
{
*blue = blue + *(pBits+0) * myVector[a][b];
*green = green + *(pBits+1) * myVector[a][b];
*red = red + *(pBits+2) * myVector[a][b];
}
...Instead of using myVector, I use pointers to an int (pInt - for arguments sake, and cos I like pInts of strongbow!), as follows : *(pInt+(a*width+b)); And the result is that its loads faster. Hope someone can shed some light on why this is the case, although it doesn`t matter to me now, I`d still like to know why? Thanks guys, Cheers, Alan. P.S. Christian, I think to me, you and the others who are improving their C++ vocabulary every day, reading pointer code is a *relatively* simple task. However, the reason I mentioned this before is that some of my MSc markers are real programming bone heads (the're mathematicians), so I was just thinking that such people might find it *easier* to read and *understand* the vector code, what do you reckon? I`m gonna go with the pointer stuff anyway, it just means extra explanation in the final write up. Cheers though for your advice I do appreciate it. "When I left you I was but the learner, now I am the Master" - Darth Vader:mad:
I think Tim nailed it when he mentioned copying data out of the vector. when you do a plain C array with fixed indexes like this, the compiler can generates code that references that value directly (or as an offset from the array base) - ie. it really is equivalent to
value = *(arrayBase + offset). but, with a vector, you're doing something like: find the data make a copy of the data return the data -c
-
I think Tim nailed it when he mentioned copying data out of the vector. when you do a plain C array with fixed indexes like this, the compiler can generates code that references that value directly (or as an offset from the array base) - ie. it really is equivalent to
value = *(arrayBase + offset). but, with a vector, you're doing something like: find the data make a copy of the data return the data -c
Here's the evilness of vector notice that the [] operator calls begin
reference operator[](size_type _P) {return (*(begin() + _P)); }
and begin CONSTRUCTS! an iterator. That blows.
iterator begin() {return (iterator(0, _Vec.begin())); }
Todd Smith
-
Here's the evilness of vector notice that the [] operator calls begin
reference operator[](size_type _P) {return (*(begin() + _P)); }
and begin CONSTRUCTS! an iterator. That blows.
iterator begin() {return (iterator(0, _Vec.begin())); }
Todd Smith
This is scary. Here's my test program
int data\[10\]; int sum = 0; for (int i = 0; i < 10; i++) { sum += data\[i\]; } std::vector vdata(10); for (int j = 0; j < 10; j++) { sum += vdata\[i\]; }and here's what the difference between the two assembler dumps sum = data[i] becomes
mov ecx,dword ptr [ebp-3Ch]
mov edx,dword ptr [ebp-38h]
add edx,dword ptr [ebp+ecx*4-34h]
mov dword ptr [ebp-38h],edxand the vector method sum += vdata[i] becomes
mov eax,dword ptr [ebp-3Ch]
push eax
lea ecx,[ebp-4Ch]
call @ILT+525(std::vector >::operator[]) (00401212)
mov ecx,dword ptr [ebp-38h]
add ecx,dword ptr [eax]
mov dword ptr [ebp-38h],ecx"@ILT+525(std::vector >::operator[]) (00401212)"
push ebp
mov ebp,esp
sub esp,44h
push ebx
push esi
push edi
push ecx
lea edi,[ebp-44h]
mov ecx,11h
mov eax,0CCCCCCCCh
rep stos dword ptr [edi]
pop ecx
mov dword ptr [ebp-4],ecx
mov ecx,dword ptr [ebp-4]
call @ILT+475(std::vector >::begin) (004011e0)
mov ecx,dword ptr [ebp+8]
lea eax,[eax+ecx*4]
pop edi
pop esi
pop ebx
add esp,44h
cmp ebp,esp
call __chkesp (0040e8b0)
mov esp,ebp
pop ebp
ret 4"@ILT+475(std::vector >::begin) (004011e0)"
push ebp
mov ebp,esp
sub esp,44h
push ebx
push esi
push edi
push ecx
lea edi,[ebp-44h]
mov ecx,11h
mov eax,0CCCCCCCCh
rep stos dword ptr [edi]
pop ecx
mov dword ptr [ebp-4],ecx
mov eax,dword ptr [ebp-4]
mov eax,dword ptr [eax+4]
pop edi
pop esi
pop ebx
mov esp,ebp
pop ebp
retI think I know where the 2 seconds went :omg:
Todd Smith
-
This is scary. Here's my test program
int data\[10\]; int sum = 0; for (int i = 0; i < 10; i++) { sum += data\[i\]; } std::vector vdata(10); for (int j = 0; j < 10; j++) { sum += vdata\[i\]; }and here's what the difference between the two assembler dumps sum = data[i] becomes
mov ecx,dword ptr [ebp-3Ch]
mov edx,dword ptr [ebp-38h]
add edx,dword ptr [ebp+ecx*4-34h]
mov dword ptr [ebp-38h],edxand the vector method sum += vdata[i] becomes
mov eax,dword ptr [ebp-3Ch]
push eax
lea ecx,[ebp-4Ch]
call @ILT+525(std::vector >::operator[]) (00401212)
mov ecx,dword ptr [ebp-38h]
add ecx,dword ptr [eax]
mov dword ptr [ebp-38h],ecx"@ILT+525(std::vector >::operator[]) (00401212)"
push ebp
mov ebp,esp
sub esp,44h
push ebx
push esi
push edi
push ecx
lea edi,[ebp-44h]
mov ecx,11h
mov eax,0CCCCCCCCh
rep stos dword ptr [edi]
pop ecx
mov dword ptr [ebp-4],ecx
mov ecx,dword ptr [ebp-4]
call @ILT+475(std::vector >::begin) (004011e0)
mov ecx,dword ptr [ebp+8]
lea eax,[eax+ecx*4]
pop edi
pop esi
pop ebx
add esp,44h
cmp ebp,esp
call __chkesp (0040e8b0)
mov esp,ebp
pop ebp
ret 4"@ILT+475(std::vector >::begin) (004011e0)"
push ebp
mov ebp,esp
sub esp,44h
push ebx
push esi
push edi
push ecx
lea edi,[ebp-44h]
mov ecx,11h
mov eax,0CCCCCCCCh
rep stos dword ptr [edi]
pop ecx
mov dword ptr [ebp-4],ecx
mov eax,dword ptr [ebp-4]
mov eax,dword ptr [eax+4]
pop edi
pop esi
pop ebx
mov esp,ebp
pop ebp
retI think I know where the 2 seconds went :omg:
Todd Smith
Thankyou guys, I can now finally put my mind at rest! There was me thinking my new Pentium 4 machines were bunk, when all along it was those bloody vectors! Interesting note you made with regards to the difference between an array of 10 integers and a vector of 10 Todd, even I was suprised by the excessive routine it goes through, geeze. Well, I must say cheers to all you guys for coming up with the solution, at least we all know not to use vectors in a similar situation again, AND we know why. Alan.:-D "When I left you I was but the learner, now I am the Master" - Darth Vader:mad: