dynamic boost::array and performance/size of STL vector
Dear list, I frequently need to use arrays with undetermined (at compile time) but constant (user specify size) size. I.e., I need something like boost::array<int> arr(5); without arr.insert etc, rather than boost::array<int,5> arr; which only accept constant array length. Of course I can use 'vector<int> arr(5)' in this case but I am worry about the performance and size overhead, specifically: 1. How is size() implemented in vector<>? I am concerned with this function since icc (intel c++ compiler) can not vectorize 'for(i=0;i<arr.size();i++)' unless arr.size() is an inlined reference to a variable. 2.Since I will have a lot of such arrays, I would also like to know how many additional variables vector<int> keeps. I.e. exactly how big is vector<int> arr(5)? It might be trivial to copy boost::array and add constructor/destructor but I do not want to re-invent the wheel. Thanks. Bo
Bo Peng wrote: I read /usr/include/c++/3.2.2/bits/stl_vector.h, here is the answer to my own questions:
1. How is size() implemented in vector<>?
end - start pointer. Not a reference to a variable. Too bad.
2.Since I will have a lot of such arrays, I would also like to know how many additional variables vector<int> keeps. I.e. exactly how big is vector<int> arr(5)?
sizeof(int)*5 + sizeof(pointer)*3 since vector keeps three pointers: start, end and end_of_storage. I am glad to find that when I initialize vector with a parameter, there is no additional storage allocated. arr.resize(5) of an empty array will not cause additional storage allocation either.
It might be trivial to copy boost::array and add constructor/destructor but I do not want to re-invent the wheel.
I am using typedef'ed vector now. I will use a modified boost::array later because I will be able to improve performance with a const size() and save some memory by using only one additional data member. Bo
that's the answer on YOUR implementation...do NOT make assumptions about how all are implemented. At Monday 2004-06-14 20:58, you wrote:
Bo Peng wrote:
I read /usr/include/c++/3.2.2/bits/stl_vector.h, here is the answer to my own questions:
1. How is size() implemented in vector<>?
end - start pointer. Not a reference to a variable. Too bad.
2.Since I will have a lot of such arrays, I would also like to know how many additional variables vector<int> keeps. I.e. exactly how big is vector<int> arr(5)?
sizeof(int)*5 + sizeof(pointer)*3 since vector keeps three pointers: start, end and end_of_storage. I am glad to find that when I initialize vector with a parameter, there is no additional storage allocated. arr.resize(5) of an empty array will not cause additional storage allocation either.
It might be trivial to copy boost::array and add constructor/destructor but I do not want to re-invent the wheel.
I am using typedef'ed vector now. I will use a modified boost::array later because I will be able to improve performance with a const size() and save some memory by using only one additional data member.
Bo
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Victor A. Wagner Jr. http://rudbek.com The five most dangerous words in the English language: "There oughta be a law"
On Mon, Jun 14, 2004 at 10:51:12PM -0700, Victor A. Wagner Jr. wrote:
that's the answer on YOUR implementation...do NOT make assumptions about how all are implemented.
I am aware of this. The implementation I checked is for gcc 3.2.2. However, there has to be some overheads (several pointers at least) in any vector implementation. Something between boost::array and std::vector can be useful. What is in my mind is a version of boost::array that can has 0 or a fixed length. It might look like: template<class T> class carray { public: size_t N; // if carray is created by carray(n,elem), do not have ownership to elems. T* elems; // constructor carray():N(0),elems(NULL){} // create array carray(size_t size):N(size){ elems = new T[size]; } // destructor ~carray(){ if(elems!=NULL) delete[] elems; } // copy constructor, // can copy from carray, boost::array or vector ... // maybe some constructors as those in vector (vec(ptr1, ptr2)) // or things like carray(int n, T* t) to assemble carray // from existing array t without copying things... ... // resize, can be called only when N=0. resize(int n){ .... } // iterators and everything else can be copied directly // from boost::array. } Bo
have you had a look at the boost::numeric::ublas::vector? you can specify a "storage" class to keep the data (for example a simple pointer to raw memory allocated with "new []") and it keeps a "size_" internal variable (to improve performance, I suppose). check: boost/numeric/ublas/vector.hpp for class vector boost/numeric/ublas/storage.hpp for class unbounded_array hope this helps. lorenzo. On Tue, Jun 15, 2004 at 01:11:05AM -0500, Bo Peng wrote:
On Mon, Jun 14, 2004 at 10:51:12PM -0700, Victor A. Wagner Jr. wrote:
that's the answer on YOUR implementation...do NOT make assumptions about how all are implemented.
I am aware of this. The implementation I checked is for gcc 3.2.2. However, there has to be some overheads (several pointers at least) in any vector implementation. Something between boost::array and std::vector can be useful.
What is in my mind is a version of boost::array that can has 0 or a fixed length. It might look like:
template<class T> class carray { public: size_t N; // if carray is created by carray(n,elem), do not have ownership to elems. T* elems; // constructor carray():N(0),elems(NULL){}
// create array carray(size_t size):N(size){ elems = new T[size]; } // destructor ~carray(){ if(elems!=NULL) delete[] elems; } // copy constructor, // can copy from carray, boost::array or vector ... // maybe some constructors as those in vector (vec(ptr1, ptr2)) // or things like carray(int n, T* t) to assemble carray // from existing array t without copying things... ... // resize, can be called only when N=0. resize(int n){ .... }
// iterators and everything else can be copied directly // from boost::array.
}
Bo
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- CH3 | N / \ N----C C==O || || | || || | CH C N--CH3 \ / \ / N C | || CH3 O
Bo Peng wrote:
Bo Peng wrote:
I read /usr/include/c++/3.2.2/bits/stl_vector.h, here is the answer to my own questions:
1. How is size() implemented in vector<>?
end - start pointer. Not a reference to a variable. Too bad.
You aren't exactly required to call size() every iteration, you know. for( int i = 0, n = v.size(); i < n; ++i ) will work fine (or 'size_t i ...' if you like unsigned). Otherwise the optimizer would need to prove that v.size() is invariant. The idiomatic approach is to use iterators, of course, but compilers didn't seem to vectorize iterator-based loops last time I tried.
participants (4)
-
Bo Peng -
Lorenzo Bolla -
Peter Dimov -
Victor A. Wagner Jr.