array contiguous block of memory

[mop]

Trying to garner a feel for the issue with arrays and contiguous block of memory. So now consider


// definition of class Matrix
template <class T> class Matrix
{
protected:
// Data Fields
int rowNum, colNum;
Vector<T> *mat;

// more stuff
};

template <class T> Matrix<T>::Matrix(int r, int c)
: rowNum(r), colNum(c), mat(new Vector<T>[r])
{
assert(mat != NULL);
for (int i=0; i<r; i++) mat[i].resize(c);
}

// Here's resize that's being called in Matrix constructor.

template <class T> void Vector<T>::resize(int length)
{
int i;
T zero(0);
T *newData = new T[length]; assert(newData != NULL);

if (length <= size)
for (i=0; i<length; i++) newData[i] = data[i];
else
{
for (i=0; i<size; i++) newData[i] = data[i];

for (i=size; i<length; i++) newData[i] = zero;
}
delete[] data;
size = length;
data = newData;
}


Further consider a 2 x 2 matrix type T. The implementation allocates 2 rows then resizes said rows by 2 T.

This is where things start to go wrong.
"mat(new Vector<T>[r])" (with r=2) allocates enough space to store 2 objects of type Vector<T>. If Vector<T> is implemented as a resizable array, then enough space is allocated for 2 * (length indicator + pointer). Assuming a
typical 32-bit platform, this will be 2*(4+4) = 16 octets.

The calls to resize() in the Matrix<T> constructor make that the pointer members of the corresponding Vector<T> objects each point at a fresh piece of memory that is large enough to hold 2 objects of type T.

The memory is in now way contiguous. In essence the rows and coloumns could look like


(2* T) (2* T)
+---------+---------+ +---------+---------+
|@0x300|@0x304| |@0x220|@0x224|
| | | | | |
| | | | | |
+---------+---------+ +---------+---------+



Assumign a 32 bit machine where the sizeof (int) is 4 bytes.

I could envision the performance loss here ( as opposed to allocating the length in one shot) but really is it even worth cosidering?

[kuphryn]

Everything counts as you design high-performance applications.

Kuphryn

[Yves M]

Originally posted by mop
I could envision the performance loss here ( as opposed to allocating the length in one shot) but really is it even worth cosidering?
Since you are bringing the issue up, it may well be worth the trouble to do things differently. It does depend on the sort of applications your matrix class will have, of course.

In any case, a good idea would be not to worry about potential memory problems and performance penalties right now. The thing is that your matrix class should be able to change internally, while the public interfaces remain the same. Then if later you find that one of the bottlenecks in your application is in there, you can still change it. Once you have a clear idea what uses you put the class to, you may have a better idea to see how it should be done.

[Paul McKenzie]

I agree with Yves here. The first thing to worry about is to get your Matrix class working, and worry about performance later.

You could have used a std::vector<> and not worry about optimization details. Once you have a working application, then you profile your code (the release version, not the debug version) to see where, if any, bottlenecks are.

For example:

#include <vector>
template <class T> class Matrix
{
protected:
// Data Fields
int rowNum, colNum;
std::vector<T> *mat;

// more stuff
};

template <class T> Matrix<T>::Matrix(int r, int c)
: rowNum(r), colNum(c), mat(new std::vector<T>(r))
{
assert(mat != NULL);
for (int i=0; i<r; i++) mat[i].resize(c);
}

Then, you don't worry about the resize(), since it is built in already. Don't be surprised if vector's resize() is faster than your version (in release mode).

Regards,

Paul McKenzie

[mop]

Truly appreaciate the response. Yves, Kup and as always Paul thanks

Bye the way, I'm doing embedded work on a DSP and long story short. The compiler does not support std::vector in fact no STL support is available.


I've perused one of my texts (ordered more that'll show up anytime) but in the interim I'm still not sure I'm following what the "<>" mean as outlined below?


friend ostream& operator << <> (ostream&,const Vector<T>&);


One other thing. I realize its overloading of the stream operator << but lets suppose I had Vector<int> aa(5);

later

std::cout << aa << std::endl


The above now equates to
aa.operator<< ( .. // what gets passed in here ?? )

[Paul McKenzie]

Originally posted by mop
Truly appreaciate the response. Yves, Kup and as always Paul thanks

Bye the way, I'm doing embedded work on a DSP and long story short. The compiler does not support std::vector in fact no STL support is available. Well, the best thing to do is to have the same interface as std::vector. At the very least, if you port to another compiler, or if support of STL is added to your current compiler, your code that uses your vector class won't have to change.
I've perused one of my texts (ordered more that'll show up anytime) but in the interim I'm still not sure I'm following what the "<>" mean as outlined below?


friend ostream& operator << <> (ostream&,const Vector<T>&);

Hmm...
I've seen similar syntax that uses <> for calling a template function, and have the compiler figure out what the arguments to the template should be based on the actual arguments of the function:

template <typename T>
void foo( T const & arg1, T const & arg2)
{
}

int main()
{
foo<>(1,2); // calls foo<int>(1,2)
}

I've never seen <> used for what you are doing. Why not post the entire the code in question?

Regards,

Paul McKenzie