Thread: realloc performance

  1. #1
    C++11 User Tux0r's Avatar
    Join Date
    Nov 2008
    Location
    Sweden
    Posts
    135

    realloc performance

    veci.h
    Code:
    #ifndef _VECI_
    #define _VECI_
    
    #include <stddef.h>
    
    typedef struct {
    	size_t size;
    	int *elements;
    } veci;
    
    void *v_new();
    void v_free(veci*);
    void v_push(veci*,int);
    void v_pop(veci*);
    size_t v_size(veci*);
    void v_clear(veci*);
    
    #endif
    veci.c
    Code:
    #include "veci.h"
    
    #include <stdlib.h>
    
    void *v_new() {
    	return calloc(1,sizeof(veci));
    }
    
    void v_free(veci *vec) {
    	free(vec->elements);
    	free(vec);
    }
    
    void v_push(veci *vec, int val) {
    	++vec->size;
    	vec->elements=realloc(vec->elements,sizeof(int)*vec->size);
    	vec->elements[vec->size-1]=val;
    }
    
    void v_pop(veci *vec) {
    	--vec->size;
    	vec->elements=realloc(vec->elements,sizeof(int)*vec->size);
    }
    
    size_t v_size(veci *vec) {
    	return vec->size;
    }
    
    void v_clear(veci *vec) {
    	vec->elements=realloc(vec->elements,0);
    	vec->size=0;
    }
    test file vector.c
    Code:
    #include "veci.h"
    
    #include <stdio.h>
    
    int main() {
    	//Create a new int vector
    	veci *myvec=v_new();
    
    	//Push some values
    	for(int i=0; i<8; ++i)
    		v_push(myvec,i*10);
    
    	//Remove last
    	v_pop(myvec);
    
    	//Print the content
    	for(size_t i=0; i<v_size(myvec); ++i)
    		printf("%d\n",myvec->elements[i]);
    
    	//Free the int vector
    	v_free(myvec);
    
    	return 0;
    }
    Is there a nice way to lessen number of bytes allocated in this example?

  2. #2
    Banned
    Join Date
    Dec 2008
    Posts
    49
    I dunno dude, you may wish to consider over allocating if anything. Reallocating data is tricky and slow business. Not to mention you are not even correctly using realloc().

  3. #3
    C++11 User Tux0r's Avatar
    Join Date
    Nov 2008
    Location
    Sweden
    Posts
    135
    Quote Originally Posted by MattW View Post
    Not to mention you are not even correctly using realloc().
    It would be more constructive if you could tell me why.

  4. #4
    Banned
    Join Date
    Dec 2008
    Posts
    49
    Code:
    void realloc_or_die(void **p, size_t size)
    {
      void *tmp = realloc(*p, size);
      if(tmp)
      {
        *p = tmp;
        return;
      }
    
      free(*p);
      exit(1);
    }
    
    void v_push(veci *vec, int val) {
    	++vec->size;
                    vec->elements=realloc_or_die((void **)&vec->elements, sizeof(int)*vec->size);
    	vec->elements[vec->size-1]=val;
    }
    You should also ditch the realloc() in pop. You need not size down your array since when you "push" it, you are going to re-increment it. But realloc doesn't always necessarily allocate nor deallocate physical space. You do not necessarily know with any predictable certainty when malloc() has already over-allocated (which it typically does in order to preserve alignment anyway).

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Aside from what has been said earlier: realloc essentially does this:
    Code:
    void *realloc(void *ptr, size_t newsize)
    {
         size_t oldsize = sizefromptr(ptr);   // This knows how malloc stores the allocated size. 
         if (newsize > oldsize)
         {
             void *newptr = malloc(newsize);
             if (!newptr)
                return NULL;
             memcpy(newptr, oldptr, oldsize);
             free(oldptr);
             return newptr;
          }
          return oldptr;
    }
    As you can see, there is a memcpy for every growth of the memory - which can take some significant time if the size is large.

    [A real realloc is a bit more complex than that, but for illustration purposes, I kept it really simple - but most of the time, realloc doesn't genuinely shrink the memory unless it's a HUGE amount smaller].

    An optimized approach may be to grow the size by doubling it [or adding half again, a quarter or four times - benchmarking a few differnet variants and comparing performance and memory usage will tell you what's the best version]. Of course, this means that you have to have two variables - one to keep track of the size of the vector space, and one to keep track of how much of the space is actually used. But it will make it many times faster for large sizes.

    --
    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.

  6. #6
    C++11 User Tux0r's Avatar
    Join Date
    Nov 2008
    Location
    Sweden
    Posts
    135
    Ok. Is this better than before though:

    Code:
    #ifndef _VECI_
    #define _VECI_
    
    #include <stddef.h>
    
    typedef struct {
    	size_t size;
    	int *elements;
    } veci;
    
    void *v_new();
    void v_free(veci**);
    void v_push(veci*,int);
    void v_pop(veci*);
    size_t v_size(veci*);
    void v_clear(veci*);
    
    #endif
    Code:
    #include "veci.h"
    
    #include <stdlib.h>
    
    void *v_new() {
    	return calloc(1,sizeof(veci));
    }
    
    void v_free(veci **vec) {
    	if(*vec==NULL)
    		return;
    
    	free((*vec)->elements);
    	free(*vec);
    
    	*vec=NULL;
    }
    
    void v_push(veci *vec, int val) {
    	++vec->size;
    	vec->elements=realloc(vec->elements,sizeof(int)*vec->size);
    	vec->elements[vec->size-1]=val;
    }
    
    void v_pop(veci *vec) {
    	--vec->size;
    }
    
    size_t v_size(veci *vec) {
    	return vec->size;
    }
    
    void v_clear(veci *vec) {
    	if(vec==NULL)
    		return;
    
    	free(vec->elements);
    	vec->elements=NULL;
    	vec->size=0;
    }
    Code:
    #include "veci.h"
    
    #include <stdio.h>
    
    int main() {
    	//Create a new int vector
    	veci *myvec=v_new();
    
    	//Push some values
    	for(int i=0; i<8; ++i)
    		v_push(myvec,i*10);
    
    	//Remove last
    	v_pop(myvec);
    
    	//Print the content
    	for(size_t i=0; i<v_size(myvec); ++i)
    		printf("%d\n",myvec->elements[i]);
    
    	//Free the int vector
    	v_free(&myvec);
    
    	return 0;
    }

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Yes, that's better - but read what I posted.

    --
    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.

  8. #8
    C++11 User Tux0r's Avatar
    Join Date
    Nov 2008
    Location
    Sweden
    Posts
    135
    Quote Originally Posted by matsp View Post
    Yes, that's better - but read what I posted.

    --
    Mats
    Yeah I'm gonna go with the power of two doubling!

  9. #9
    C++11 User Tux0r's Avatar
    Join Date
    Nov 2008
    Location
    Sweden
    Posts
    135
    Code:
    #ifndef _VECI_
    #define _VECI_
    
    #include <stddef.h>
    
    typedef struct {
    	size_t size;
    	size_t alloc_size;
    	int *elements;
    } veci;
    
    void *v_new();
    void v_push(veci*,int);
    void v_pop(veci*);
    size_t v_size(veci*);
    void v_clear(veci*);
    void v_free(veci**);
    
    #endif
    Code:
    #include "veci.h"
    
    #include <stdlib.h>
    
    void *v_new() {
    	return calloc(1,sizeof(veci));
    }
    
    void v_push(veci *vec, int val) {
    	++vec->size;
    
    	if(vec->size > vec->alloc_size) {
    		if(vec->alloc_size==0)
    			vec->alloc_size=4;
    		else
    			vec->alloc_size*=2;
    
    		vec->elements=realloc(vec->elements,sizeof(int)*vec->alloc_size);
    	}
    
    	vec->elements[vec->size-1]=val;
    }
    
    void v_pop(veci *vec) {
    	--vec->size;
    }
    
    size_t v_size(veci *vec) {
    	return vec->size;
    }
    
    void v_clear(veci *vec) {
    	vec->size=0;
    
    	if(vec==NULL)
    		return;
    
    	free(vec->elements);
    	vec->elements=NULL;
    }
    
    void v_free(veci **vec) {
    	if(*vec==NULL)
    		return;
    
    	free((*vec)->elements);
    	free(*vec);
    
    	*vec=NULL;
    }
    Code:
    #include "veci.h"
    
    #include <stdio.h>
    
    int main() {
    	//Create a new int vector
    	veci *myvec=v_new();
    
    	//Push some int's
    	for(int i=0; i<8; ++i)
    		v_push(myvec,i*10);
    
    	//Pop last
    	v_pop(myvec);
    
    	//Print the content
    	for(size_t i=0; i<v_size(myvec); ++i)
    		printf("%d\n",myvec->elements[i]);
    
    	v_free(&myvec);
    
    	return 0;
    }
    is that good enough?

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I'd add a "if (size == 0) free(vec->elements);" in the v_pop() function too.
    And set alloc_size to zero in the clear and pop functions.

    --
    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.

  11. #11
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > vec->elements=realloc(vec->elements,sizeof(int)*vec->alloc_size);
    Use a temp pointer, so you can check that you have got the new memory, before trashing your only pointer to the old memory.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. did i understood right this explantion of realloc..
    By transgalactic2 in forum C Programming
    Replies: 3
    Last Post: 10-24-2008, 07:26 AM
  2. Performance and footprint of virtual function
    By George2 in forum C++ Programming
    Replies: 8
    Last Post: 01-31-2008, 07:34 PM
  3. File map performance
    By George2 in forum C++ Programming
    Replies: 8
    Last Post: 01-04-2008, 04:18 AM
  4. using realloc
    By bobthebullet990 in forum C Programming
    Replies: 14
    Last Post: 12-06-2005, 05:00 PM
  5. Realloc inappropriate for aligned blocks - Alternatives?
    By zeckensack in forum C Programming
    Replies: 2
    Last Post: 03-20-2002, 02:10 PM