Allocate and deallocate a vector

[jesperd]

Hi everyone.

I have made a function in C++ that uses the std::vector class.

I use the vector as the return parameter for the function.

To explain the setup, I have some boxes moving around in a 3D scene.
I want to detect overlaps between the boxes while they change their positions in the scene.
The function detects those overlaps. I use the vector as an overlap container, that tells which boxes overlaps each other.

The problem is, that this container has different length each time the boxes have been moved.

So, the implemented solution right now is:

1. create a container called overlaps by using std::vector class.

2. use reserve to allocate memory: overlaps.reserve(n)
where n is an estimate for how many overlaps that could be.
3. add overlaps between two boxes by using overlaps.push_back(make_pair(box_A,box_B)).
4. update the positions for the boxes.
5. clear the overlaps container.
6. loop back to 2.
7. until the program ends.


I'm not sure this is a good solution.
As I read the reference to the clear() function, it deallocate the whole vector container.
To avoid unnecessary time to allocate more memory when the vector container exceeds its capacity, I use the reserve() to be ensure that the memory pool is big enough to my detected overlaps. I have to do this in each loop because (if I understand i correct) the clear() deallocate the whole container.

I'm not sure how expensive it is in time to first deallocate the vector container and then again allocate it.

Another solution could be that a counter tells how many elements there is in the vector container and which position a new element should be placed. With this solution the new element just overwrite the former element at the current position. But I think this solution will be a bitch to implement in a threaded version.

So, maybe you have a solution to this. Maybe is is a bad idea to use the vector class - maybe deque...

I hope my question is clear enough and not too hard to explain :-)

/Jesper

[kbw]

I don't think clear changes the capacity of a vector, only the size. So you shouldn't need to reserve space each time.

[jsmith]

From the sounds of it, your solution already seems pretty optimal. I'm not sure how you can
make it any faster.

Not sure what the standard says, but at least the implementation of vector<>::reserve() I have
does nothing if the container already has enough space.

And as kbw says, clear() only sets an internal pointer and runs destructors of affected elements;
it does not deallocate the internal buffer.

[jesperd]

Thanks for the explanations :-)

I have made a test, where I want to look at how expensive it is to call reserve() and clear().

The test setup is:

#include <iostream>
#include <sys/time.h>
#include <time.h>
#include <sys/timeb.h>
#include <vector>


#define MY_RAND_MAX 32767

int myrand(unsigned long *next) {
    *next = *next * 1103515245 + 12345;
    return((unsigned)(*next/65536) % 32768);
}

float rand01(unsigned long *next) { 
    return( ((float)myrand(next))/((float)MY_RAND_MAX+1) );
}

  /* ---TIME ------------------------------
   * Evaluated time for program in secunds
   * and milliseconds.
   */

  struct timeb timebuffer;

  struct a_time {
    time_t time_s;
    unsigned short time_ms;
  };

  a_time startTime() {
    ftime( &timebuffer );
    a_time st;
    st.time_s  = timebuffer.time;
    st.time_ms = timebuffer.millitm;
    return(st);
  }

  void endTime(a_time &st) {
    ftime( &timebuffer );
    a_time end;
    end.time_s = timebuffer.time;
    end.time_ms = timebuffer.millitm;

    if(end.time_ms - st.time_ms < 0) {
      end.time_s = end.time_s - st.time_s - 1;
      end.time_ms = 1000 + (end.time_ms - st.time_ms);
    }
    else {
      end.time_s = end.time_s - st.time_s;
      end.time_ms = end.time_ms - st.time_ms;
    }
    std::cout << "\nTotal time : " << end.time_s << "." << end.time_ms << std::endl;
  }


int main(void) {

     struct a_time t_begin;

     std::vector <float> my_vector;
     unsigned long next = 1;
     
     unsigned int size;
     unsigned int max_size = 1000000;
     unsigned int max_loop = 5000;

// ------------------------------------------     
     t_begin = startTime();
     my_vector.reserve(size);
     
     for(unsigned i=0;i<max_loop;i++) {
         
         size = (unsigned int)(rand01(&next)*max_size);
         
         for(unsigned j=0;j<size;j++) {
             my_vector.push_back(rand01(&next));
         }
         my_vector.clear();
     }
     
     std::cout << "With reserve(), clear():";
     endTime(t_begin);

// ------------------------------------------     

     next = 1;
     my_vector.clear();
     
     t_begin = startTime();
     
     for(unsigned i=0;i<max_loop;i++) {
         
         size = (unsigned int)(rand01(&next)*max_size);
         my_vector.reserve(size);
         
         for(unsigned j=0;j<size;j++) {
             my_vector.push_back(rand01(&next));
         }
         std::vector <float>().swap(my_vector);
     }
     
     std::cout << "With reserve(), swap():";
     endTime(t_begin);

// ------------------------------------------     

     next = 1;
     my_vector.clear();
     unsigned int my_vector_pos;

     t_begin = startTime();

     my_vector.resize(max_size);
     
     for(unsigned i=0;i<max_loop;i++) {
         
         size = (unsigned int)(rand01(&next)*max_size);
         my_vector_pos = 0;
         for(unsigned j=0;j<size;j++) {
             my_vector[j] = (rand01(&next));
             my_vector_pos++;
         }
     }
     
     std::cout << "Just overwriting..:";
     endTime(t_begin);

// ------------------------------------------     

     
     return(0);
}

I have tested it on a laptop with a single core at 1.73 Ghz and with 4Gb RAM.
I have compiled the program witn -O2 flag.
The result is:

With reserve(), clear():
Total time : 44.376
With reserve(), swap():
Total time : 52.693
Just overwriting..:
Total time : 36.174

To explain the std::vector <float>().swap(my_vector) is that the constructor creates a new empty container on the fly and swap it with the old one. Then call the destructor on the old one. This case should perform the worst time, and it does.

The question is, why are there 8 seconds between just overwriting the elements in the container and using clear()?
I'm not sure if it is the call of clear() that do the difference.
I have tried to put reserve() before the outer loop in test 1 (with reserve(), clear()) without significant change in the time consumed.
So at that point you have right.

Maybe it could be some sort of cache optimization using the overwriting scheme. Nonetheless, I think I stick to the first one with reserve(), clear().

Thanks for your help.