Re: Contiguous allocation of multi-dimensional vector
From: nw
Hi,
We've been having a discussion at work and I'm wondering if anyone
here would care to offer an opinion or alternative solution. Aparently
in the C programming HPC community it is common to allocate
multidimentional arrays like so:
int *v_base = (int *) malloc(1000000*sizeof(int));
int **v = (int **) malloc(1000*sizeof(int *));
for(int i=0;i<1000;i++) {
v[i] = v_base+(i*1000);
}
Hmmmm, back in the day, I wouldn't have bothered with v. Any cell can
be
directly calculated for an array of v[HEIGHT, WIDTH] with WIDTH * (row
- 1)
+ column. Of course, memory was at a premium.
The logic behind this is that the entire multi-dimensional array will
be contiguous in memory and therefore it is more likely that the whole
array will be loaded in to cache, improving access time.
and there is only one allocation per array (malloc/free can be pretty
time
consuming). Of course, on the other side of the fence, it may be
easier to
come up to 1000 4000 byte blocks than one 4000000 byte block.
The following workaround I believe will simulate similar behaviour
using the STL:
vector<int> v_base(1000000);
vector<int *> v;
for(int i=0;i<1000;i++) {
v.push_back(&v_base[0]+(i*1000));
}
However will obviously break if you use insert or remove anywhere, and
doesn't seem like a great idea. The standard way of allocating this
two dimensional array as I understand it is:
This is a non-issue because you would never insert or delete in a
multidimensional
array unless you were explicitly supporting ragged arrays and that is
a
different sort of problem.
vector<vector<int> > v(1000,vector<int>(1000));
So I guess my question is this: Is there any advantage to allocating
the vector contiguously or should the normal STL allocation method
place the vectors contiguously in memory? Is there likely to be much
vector overhead placed between the 1d vector<int>s such as the size of
the array?
My gut feeling is that the normal STL way will produce similar
results, and the tests I've done seem to back this up, but I'd be
interested in hearing other peoples opinions.
Any suggestions gratefully received and my apologies if this has been
asked previously or in the FAQ and I missed it.
The best answer would depend upon what you are using the arrays for.
The
problem with a vector of vectors is that you lose a lot of locality of
reference
and therefore may well have more cache misses; there is another layer
of indirection; and since insert/erase is available, you have the
possibility
of turning your multidimensional array into a ragged array without
even
half trying.
The good news is that this is C++ and you can wrap whatever logic you
choose
in a class and only allow the operations which make sense.
Personally, I
would probably start off with something like:
template <typename T, size_t N, size_t M>
struct marray
{
typedef size_t size_type;
typedef T value_type;
typedef T& reference;
typedef const T& const_reference;
reference at(size_type x, size_type y)
{
return m_array[x,y];
}
const_reference at(size_type x, size_type y) const
{
return m_array[x,y];
}
private:
T m_array[N,M];
};
And flesh it out with what I needed (iterators, row_iterators, etc).
Then I
could choose whether I wanted it dynamic or not and it would be a
single
allocation either way. If I needed a ragged array, well that would be
different.
joe