Zeroing out Arrays(c++)

Discussion in 'OT Technology' started by SPACECATAZ, Apr 7, 2009.

  1. SPACECATAZ

    SPACECATAZ New Member

    Joined:
    Dec 22, 2006
    Messages:
    2,502
    Likes Received:
    0
    If I have a structure like this:

    Code:
    #include <cstring>
    using namespace std;
    
    struct Equiv
    {
        int* boss;
        int sizeOfArray;
        Equiv(int x)
        {
            sizeOfArray = x;
            memset(boss, 0, sizeof(boss));
            boss = new int[x+1];
        }
    };
    
    What would be the correct way to zero that out? I don't think I'm using memset right. The size of the array is passed into the structure.
     
  2. antiyou

    antiyou OT Supporter

    Joined:
    Jul 13, 2005
    Messages:
    25,295
    Likes Received:
    0
    Location:
    in ur base
    Set boss to NULL until you allocate memory for it, at which time you can zero out each element of boss using memset.

    boss = NULL;
    boss = new int[x]
    memset(boss, 0, sizeof(int)*x);

    and this is an integer array so I don't know why you are making the array 1 element larger than the function parameter specifies
     
    Last edited: Apr 7, 2009
  3. GOGZILLA

    GOGZILLA Double-Uranium Member

    Joined:
    Jan 16, 2003
    Messages:
    10,760
    Likes Received:
    3
    Location:
    Plantation, FL
    you want the whole array zero'd out after you create it right? the way youre doing it is youre setting sizeOfArray to x then just pointing boss at 0 which could have been just as easily done with boss = 0;

    i think you want to do is

    sizeOfArray = x;
    boss = new int[x+1];
    memset(boss, 0, (x+1)*sizeof(int));
     
  4. GOGZILLA

    GOGZILLA Double-Uranium Member

    Joined:
    Jan 16, 2003
    Messages:
    10,760
    Likes Received:
    3
    Location:
    Plantation, FL
  5. SPACECATAZ

    SPACECATAZ New Member

    Joined:
    Dec 22, 2006
    Messages:
    2,502
    Likes Received:
    0
    I'm doing Kruskal's Algorithm for my class and he specified that our array must be +1 so we start at index 1 instead of zero.

    Yeah, that's what I wanted. One my classmates said I could also do it this way.

    Code:
    struct Equiv
    {
        int* boss;
        int sizeOfArray;
        Equiv(int x)
        {
            sizeOfArray = x;
            boss = new int[x+1];
            for(int y = 0; y < x + 1; y++)
            {
                boss[y] = 0;
            }
        }
    };
    
     
  6. Limp_Brisket

    Limp_Brisket New Member

    Joined:
    Jan 2, 2006
    Messages:
    48,422
    Likes Received:
    0
    Location:
    Utah
    you could do it that way as well. although memset is a one-liner and probably more optimized than a for loop :)
     
  7. SPACECATAZ

    SPACECATAZ New Member

    Joined:
    Dec 22, 2006
    Messages:
    2,502
    Likes Received:
    0
    Duly noted. :bowdown:
     
  8. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    memset and meridians example are such a simple loops, a modern compiler would probably generate the same code in either case.
     
  9. Limp_Brisket

    Limp_Brisket New Member

    Joined:
    Jan 2, 2006
    Messages:
    48,422
    Likes Received:
    0
    Location:
    Utah
    http://www.cppreference.com/wiki/c/string/memset

     
  10. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Doesn't specify the compiler used.

    Take a look at this...

    Here's MS Visual Studio 2008's implementation of memset taken from the crt source:
    Code:
    void * __cdecl memset (
            void *dst,
            int val,
            size_t count
            )
    {
            void *start = dst;
    
    #if defined (_M_IA64) || defined (_M_AMD64)
    
            {
    
    
            __declspec(dllimport)
    
    
            void RtlFillMemory( void *, size_t count, char );
    
            RtlFillMemory( dst, count, (char)val );
    
            }
    
    #else  /* defined (_M_IA64) || defined (_M_AMD64) */
            while (count--) {
                    *(char *)dst = (char)val;
                    dst = (char *)dst + 1;
            }
    #endif  /* defined (_M_IA64) || defined (_M_AMD64) */
    
            return(start);
    }
    
    Notice it's just a simple while loop.

    Now here's two pieces of code that zero out an array. One uses a for loop, the other uses a while loop modeled after the memset source.

    loop.cpp
    Code:
    int main()
    {
    	const int LEN = 1000000;
    	char arr[LEN];
    
    	for (int i = 0; i < LEN; i++)
    	{
    		arr[i] = 0;
    	}
    
    	return 0;
    }
    

    memset.cpp
    Code:
    int main()
    {
    	const int LEN = 1000000;
    	char arr[LEN];
    
    	int i = LEN;
    	char *dst = arr;
    
    	while(i--)
    	{
    		*dst = 0;
    		dst = dst + 1;
    	}
    
    	return 0;
    }
    
    Now compile both using VC++'s speed optimaztion, and generate asm:

    cl.exe /O2 /FA loop.cpp
    cl.exe /O2 /FA memset.cpp

    loop.asm
    Code:
    ; Listing generated by Microsoft (R) Optimizing Compiler Version 15.00.21022.08 
    
    	TITLE	D:\Source\loop.cpp
    	.686P
    	.XMM
    	include listing.inc
    	.model	flat
    
    INCLUDELIB LIBCMT
    INCLUDELIB OLDNAMES
    
    PUBLIC	__$ArrayPad$
    PUBLIC	_main
    EXTRN	___security_cookie:DWORD
    EXTRN	@[email protected]:PROC
    ; Function compile flags: /Ogtpy
    ;	COMDAT _main
    _TEXT	SEGMENT
    __$ArrayPad$ = -4					; size = 4
    _main	PROC						; COMDAT
    ; File d:\source\loop.cpp
    ; Line 2
    	push	ecx
    	mov	eax, DWORD PTR ___security_cookie
    	xor	eax, esp
    	mov	DWORD PTR __$ArrayPad$[esp+4], eax
    ; Line 12
    	mov	ecx, DWORD PTR __$ArrayPad$[esp+4]
    	xor	ecx, esp
    	xor	eax, eax
    	call	@[email protected]
    	pop	ecx
    	ret	0
    _main	ENDP
    _TEXT	ENDS
    END
    

    memset.asm
    Code:
    ; Listing generated by Microsoft (R) Optimizing Compiler Version 15.00.21022.08 
    
    	TITLE	D:\Source\memset.cpp
    	.686P
    	.XMM
    	include listing.inc
    	.model	flat
    
    INCLUDELIB LIBCMT
    INCLUDELIB OLDNAMES
    
    PUBLIC	__$ArrayPad$
    PUBLIC	_main
    EXTRN	___security_cookie:DWORD
    EXTRN	@[email protected]:PROC
    ; Function compile flags: /Ogtpy
    ;	COMDAT _main
    _TEXT	SEGMENT
    __$ArrayPad$ = -4					; size = 4
    _main	PROC						; COMDAT
    ; File d:\source\memset.cpp
    ; Line 2
    	push	ecx
    	mov	eax, DWORD PTR ___security_cookie
    	xor	eax, esp
    	mov	DWORD PTR __$ArrayPad$[esp+4], eax
    ; Line 17
    	mov	ecx, DWORD PTR __$ArrayPad$[esp+4]
    	xor	ecx, esp
    	xor	eax, eax
    	call	@[email protected]
    	pop	ecx
    	ret	0
    _main	ENDP
    _TEXT	ENDS
    END
    
    Voila! Exact same code output. :)
     
  11. Limp_Brisket

    Limp_Brisket New Member

    Joined:
    Jan 2, 2006
    Messages:
    48,422
    Likes Received:
    0
    Location:
    Utah
    lol, you just wrote memset.cpp yourself and called it, of course it's going to look the same.

    you conveniently glanced over #if defined (_M_IA64) || defined (_M_AMD64)
    which uses RtlFillMemory.

    silly goose.
     
  12. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    :uh: That was the point. I proved that a for loop and the implementation of memset using a while loop generate the same code.

    As for the compiler directive, that section of code won't be compiled if I'm aiming to generate 32-bit code. Plus, how different could RtlFillMemory be? It's just another implementation of memset.
     
  13. Limp_Brisket

    Limp_Brisket New Member

    Joined:
    Jan 2, 2006
    Messages:
    48,422
    Likes Received:
    0
    Location:
    Utah
    without looking im sure it's a lot different. since the compiler directive checks for a certain instruction set, RtlFillMemory probably uses an advanced instruction that handles it with hardware rather than software, a.k.a faster.
     
  14. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    :rofl: You're just grasping at straws now.
     
  15. Limp_Brisket

    Limp_Brisket New Member

    Joined:
    Jan 2, 2006
    Messages:
    48,422
    Likes Received:
    0
    Location:
    Utah
    how is that grasping at straws? that memtest code is the definition of optimized, which is what i said.
     
  16. DouggieJ

    DouggieJ OT Supporter

    Joined:
    Nov 1, 2007
    Messages:
    8,126
    Likes Received:
    0
    Location:
    New York, NY USA
    what about calloc()
     
  17. antiyou

    antiyou OT Supporter

    Joined:
    Jul 13, 2005
    Messages:
    25,295
    Likes Received:
    0
    Location:
    in ur base
    how about you just fill a large array using both memset and looping and see which one terminates faster on average of say 100 runs...:)

    argument settled
     
  18. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Something I overlooked... I didn't look carefully enough at the generated code. The compiler actually recognized that in that small piece of code, setting an array to zero, and then doing nothing with the array accomplished nothing. Therefore it eliminated the loop and generated code that did nothing. If you add some code that accesses the array subsequent to the loop, the optimizing compiler eliminates the loop and calls memset. :o

    But, I was right. The compiler generates the same code, regardless. :p
     
  19. Limp_Brisket

    Limp_Brisket New Member

    Joined:
    Jan 2, 2006
    Messages:
    48,422
    Likes Received:
    0
    Location:
    Utah
    well, that's probably why it's called an optimizing compiler :p
     
  20. SPACECATAZ

    SPACECATAZ New Member

    Joined:
    Dec 22, 2006
    Messages:
    2,502
    Likes Received:
    0
    I just used the for loop, it kept complaining about memset.
     

Share This Page