Thread: Vector vs. array.

  1. #31
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Just a quick analyzis of the vector vs. array code generated shows:
    Code:
    // array code
    ;	COMDAT ?sum@A@@UAEHXZ
    _TEXT	SEGMENT
    ?sum@A@@UAEHXZ PROC NEAR				; A::sum, COMDAT
    ; _this$ = ecx
    
    	push	ebx
    	push	esi
    	xor	eax, eax
    	push	edi
    	add	ecx, 32					; 00000020H
    	mov	esi, 128				; 00000080H
    $L11447:
    	mov	edx, 16					; 00000010H
    $L11451:
    	mov	ebx, DWORD PTR [ecx-24]
    	mov	edi, DWORD PTR [ecx-28]
    	add	edi, ebx
    	add	edi, DWORD PTR [ecx-20]
    	add	edi, DWORD PTR [ecx-16]
    	add	edi, DWORD PTR [ecx-12]
    	add	edi, DWORD PTR [ecx-8]
    	add	edi, DWORD PTR [ecx-4]
    	add	edi, DWORD PTR [ecx]
    	add	eax, edi
    	add	ecx, 32					; 00000020H
    	dec	edx
    	jne	SHORT $L11451
    	dec	esi
    	jne	SHORT $L11447
    	pop	edi
    	pop	esi
    	pop	ebx
    	ret	0
    ?sum@A@@UAEHXZ ENDP					; A::sum
    _TEXT	ENDS
    
    // vector code:
    _TEXT	SEGMENT
    ?sum@V@@UAEHXZ PROC NEAR				; V::sum, COMDAT
    ; _this$ = ecx
    	push	esi
    	mov	esi, DWORD PTR [ecx+8]
    	push	edi
    	xor	eax, eax
    	add	esi, 4
    	mov	edi, 128				; 00000080H
    	npad	1
    $L11413:
    	mov	ecx, DWORD PTR [esi]
    	add	ecx, 8
    	mov	edx, 16					; 00000010H
    	npad	6
    $L11417:
    	add	eax, DWORD PTR [ecx-8]
    	add	eax, DWORD PTR [ecx-4]
    	add	eax, DWORD PTR [ecx]
    	add	eax, DWORD PTR [ecx+4]
    	add	eax, DWORD PTR [ecx+8]
    	add	eax, DWORD PTR [ecx+12]
    	add	eax, DWORD PTR [ecx+16]
    	add	eax, DWORD PTR [ecx+20]
    	add	ecx, 32					; 00000020H
    	dec	edx
    	jne	SHORT $L11417
    	add	esi, 16					; 00000010H
    	dec	edi
    	jne	SHORT $L11413
    	pop	edi
    	pop	esi
    	ret	0
    ?sum@V@@UAEHXZ ENDP					; V::sum
    The main difference, as I see it, is the vector has to do another indirection in the outer loop, vs. the array just doing a simple decrement operation in the second loop. I would actually expect the compiler to merge the two loops, since loading edx with 16 then using edi to loop the outer loop seems excessive, why not just load edx with 16 * 128?

    The above code is with "size" set to 128 rather than 100 as in the posted code - I doubt it makes much difference in the overall code generated, I changed to 128 to see if gcc would do some better code generation - currenly, the MS compiler beats the gcc version by running BOTH loops quicker than one of the gcc functions.

    --
    Mats
    Last edited by matsp; 06-21-2008 at 04:09 PM.
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  2. #32
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    So in essence, the compiler is able to apply further optimizations to the vector loop than the array loop.
    Clever compiler. Or is it clever code?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #33
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Elysia View Post
    So in essence, the compiler is able to apply further optimizations to the vector loop than the array loop.
    Clever compiler. Or is it clever code?
    The other way around, the array is a more compact loop than the vector [with the version of compiler I've been using, at least].

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #34
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by iMalc View Post
    I'm with dwks:
    A vector can be as fast as an array, not faster. Why? because a vector uses an array internally. Anything that proves otherwise has to be an invalid test, and there are so many ways for it to be invalid.
    I'd actually argue the reverse: contradiction of a belief or theory by a counter-example is evidence that belief or theory is incorrect (or, at best, incomplete).

  5. #35
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I'd actually argue the reverse: contradiction of a belief or theory by a counter-example is evidence that belief or theory is incorrect (or, at best, incomplete).
    A certain Albert Einstein reportedly stated that: "If the facts don't fit the theory, change the facts."

    But yes, I think the point is that we need to be sure that the counter-example is indeed a counter-example.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #36
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by laserlight View Post
    A certain Albert Einstein reportedly stated that: "If the facts don't fit the theory, change the facts."
    It was quite a time ago that I read the story of that, but I seem to recall the context was a swipe at occurrences of inconvenient facts being dismissed because of entrenched beliefs.
    Quote Originally Posted by laserlight View Post
    But yes, I think the point is that we need to be sure that the counter-example is indeed a counter-example.
    Sure. The way to check that is to explain what occurred, and make sure the supporting examples and counter-examples are evaluated on an equal footing, not to dismiss occurrences by default.

  7. #37
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    I apologize if this has been stated already. matsp, why are you comparing a statically sized 2D array with a vector of vectors that is created in a loop in the class constructor? It's not a terribly fair comparison in the first place, but it still could be useful and interesting if you used the vector's constructor to initialize it instead of a loop.

    I'm wondering what the results of using std::tr1::array (or boost::array) would be here.

    Edit: Oh... you're not timing initialization, just access.

  8. #38
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Daved View Post
    Edit: Oh... you're not timing initialization, just access.
    Correct, I'm only timing the access of the contents of both the array and the vector.

    I'd be interested to see the code of those who can achieve faster vector than array access, since I can't really see how that can be done - the only thing I can think of is:
    1. the array access is less than optimal due to some sort of alignment issues.
    2. the array access is done via for example mul operations because the array sizes is not a factor 2^n. But since the 2D array access in Visual Studio .Net translates to a 1D array access, I can't really see how that happens.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  2. Replies: 6
    Last Post: 11-09-2006, 03:28 AM
  3. [question]Analyzing data in a two-dimensional array
    By burbose in forum C Programming
    Replies: 2
    Last Post: 06-13-2005, 07:31 AM
  4. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM
  5. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM