newbie dynamic memory problem.

[Kai-Uwe Bux]

Kai-Uwe Bux, I downloaded a recent GNU g++ STL release and here is the
vector source for your STL chaining implementation of the 2D matrix:

/**
* @brief Subscript access to the data contained in the vector.
* @param n The element for which data should be accessed.
* @return Read/write reference to data.
*
* This operator allows for easy, array-style, data access.
* Note that data access with this operator is unchecked and
out_of_range
* lookups are not defined. (For checked lookups see at().)
*/
reference operator[](size_type __n) { return *(begin() + __n); }

/**
* Returns a read/write iterator that points to the first element in
the
* vector. Iteration is done in ordinary element order.
*/
iterator begin() { return iterator (_M_start); }

/**
* @brief Provides access to the data contained in the vector.
* @param n The element for which data should be accessed.
* @return Read/write reference to data.
*
* This function provides for safer data access. The parameter is
first
* checked that it is in the range of the vector. The function
throws
* out_of_range if the check fails.
*/
reference at(size_type __n)
{ _M_range_check(__n); return (*this)[__n]; }

void _M_range_check(size_type __n) const {
if (__n >= this->size())
__throw_out_of_range("vector");
}

As you can see, this is identical to the MSVC7.1 STL code I posted the
other day. So, your argumemt about STL compiler differences doesn't
apply to this case.

I do not recall refering to "STL compiler" differences. All I said was that
one should not look at the code and jump to conclusions about the

Yes, I agree each vendor uses compiler
optimizations. The MSVC7.1 STL header files list all the compiler
optimizations. As for your tests, I haven't ran them yet. At first
glance, the matrices in your test are not large

Feel free to change the sizes. I did so. Results don't change.

and it appears you are
not using the standard linear algebra / matrix benchmarks which would
be a better test for random access of 2D matrices.

May I remind you that the point in question is *not* the performance of
these types in linear algebra applications but just the question whether a
double indirect memory access in std::vector< std::vector< T > > is less
efficient than in T**. If the point was not this narrow, the code snippets
you provided would not be significant anyway. To get evidence with regard
to this narrow question, I think, the test code fits. One could think about
testing different orders of accessing the entries to get a more detailed
picture. But that is all I would think of. Just run some variations of the
code.

However, if you feel inclined to provide the necessary arithmetic operations
based on the two data structures to run linear algebra benchmarks, feel
free to do so. I do not think it would be worthwhile. As I pointed out
elsewhere, there are high-performance linear algebra libraries out there.


Best

Kai-Uwe Bux

 

[Frank Chang]

Kai-Uwe Bux, The vectors versus arrays issue is one of those "religious
wars" which can go on and on with no real resolution. The reason I
brought up the issue of compiler differences is because the behavior of
the STL container template classes such as vector, deque....are
significantly affected by the choice of compiler, the effectiveness of
the compiler optimizations, the processor architecture, the type of
threading model(single threaded versus multi-threaded) and the choice
of memory allocation algorithms. Yes, we know you can tweak these
variables but there are many users out who may not want to spend the
time doing that. And, they will get suffer the consequences if they
try to use a STL vector of vector solution. So , for those users, it
may be better to use a template T** class.
The reason I bring up the issue about the rank of the matrix is
because as long as everything is in L2 cache, you will most likely not
find any difference between the two methods. But , once the rank of the
matrix starts to get significantly larger and the matrix cannot fit in
L2 cache, then the processor architecture, the operating system memory
management, and the memory allocation technigues(i.e. how contiguous?)
become increasingly important.

I agree with you that there are high-performance linear algebra
libraries out there. However, they are expensive. I think that between
you, Victor, Ram and Esteban, laclac1 should have enough information to
make his/her choice. Thank you for contributing your viewpoints. I
learned a lot from your posts.

 

[Kai-Uwe Bux]

Kai-Uwe Bux, The vectors versus arrays issue is one of those "religious
wars" which can go on and on with no real resolution.

Not for me. For me this is just an empirical question that can be decided by
measurement. I do not make a general statement. I am perfectly prepared to

The reason I
brought up the issue of compiler differences is because the behavior of
the STL container template classes such as vector, deque....are
significantly affected by the choice of compiler, the effectiveness of
the compiler optimizations, the processor architecture, the type of
threading model(single threaded versus multi-threaded) and the choice
of memory allocation algorithms.
Agreed.

Yes, we know you can tweak these
variables but there are many users out who may not want to spend the
time doing that. And, they will get suffer the consequences if they
try to use a STL vector of vector solution. So , for those users, it
may be better to use a template T** class.

The operative word being *may*. However, you seem to suggest that T** should
be the default pick for those interested in performance but to lazy to
tinker. Now, to me this bias toward T** is entirely non-obvious: Instead of
trusting std::vector<T> to handle memory allocation and access efficiently,
these users would simply put their faith in new/delete, which are in no way
less implementation specific. If performance is really of importance there
is no way around testing and tweaking.

The reason I bring up the issue about the rank of the matrix is
because as long as everything is in L2 cache, you will most likely not
find any difference between the two methods. But , once the rank of the
matrix starts to get significantly larger and the matrix cannot fit in
L2 cache, then the processor architecture, the operating system memory
management, and the memory allocation technigues(i.e. how contiguous?)
become increasingly important.

The more reason to not just trust new/delete: std::vector<> allows for
specifing an allocator and the default allocator used by vector could (and
in good STL implementations probably will) be optimized for allocating
arrays which new/delete might not be.


In the end, I can only repeat myself: you need to benchmark. There is no
reason to prefer T** a priori for performance. Of course, there is also no
reason to go with std::vector from a performance point of view. However,
keep in mind that performance is not everything. When it comes to writing
code that is supposed to be easy to understand, I would opt for std::vector
any day.


Best

Kai-Uwe Bux

 

[Frank Chang]

Kai-Uwe Bux, You state this is an empirical question which can be
decided by measurement only. I totally agree with you but to
empirically resolve this issue would be a truly awesome undertaking. We
would have to consider all types of matrices, dense, sparse,etc as well
as all the major matrix library methods(LU decomposition, matrix
inversion, singular value decompostion,etc ) for small, medium and
large rank. Alternatively, we could look at some commercial and open
source matrix class libraries and study them,
This is what I have found this morning, The commercial high
performance linear algebra libraries use platform specific assembly
language. For these libraries, vector of vector or array
implementations in C++ are not a consideration. Next, I wrote a small
C++ program on MSVC 7.1 using the Boost/ublas template matrix class. I
found that Boost provides two implementations of matrices, a
vector_of_vector class as well a single dimensional array (rows *
columns) class. I am trying to find out for you now why the Boost/Ublas
authors provide both an array and vector of vector classe instead of
just a vector of vector class template.
However, the authors of these C++ classes clearly warn users
that these two classes are intended only for dense matrices. Currently,
Boost/Ublas is developing a generalized matrix class which can handle
large sparse matrices where it is important to have very fast access to
any element and to be to insert elements randomly as well as
independently.
With respect to memory allocation issues, I alluded to the same
issue yesterday that the STL vector class allows the user to use a
default memory allocator as well as a custom memory allocator. Please
take a look at this link ,
http://proj-clhep.web.cern.ch/proj-clhep/Workshop-2003/11. The authors
infer that the memory allocation issues of new versus malloc are
important for matrices with small rank. For matrices of large rank,
other issues(i.e. temporaries) become more important.
With regard to your final remark, I agree with you that
benchmarking is important but a proper benchmark should take into
account all the factors I mentioned earlier.

 

[Frank Chang]

Kai-Uwe Bux, The link should be proj-clhep.web.cern.ch/
proj-clhep/Workshop-2003/uBlas.ppt. I apologize for the error.