C++ STL valarrays vs. vectors

[Michael Aramini]

I need to represent 1D and 2D arrays of numeric or bool types in a C++
program. The sizes of the arrays in my intended application are
dynamic in the sense that they are not known at compile time, so I'd
like to use an STL container class template such as valarray or vector
to represent 1D arrays, and valarrays or vectors of valarrays or
vectors to represent 2D arrays.

As I said the sizes of the arrays in my intended application are
dynamic in that they are determined at run time, but on the other hand
I don't anticipate the need to continually resize a given array during
a given call to the routine in which it is declared. The thing that's
more important to my application is speed. Is there a significant
different between the element access speeds of valarrays vs. vectors?

For 1D arrays, the choices are:
valarray<type> vs. vector<type>

For 2D arrays, the choices are:
valarray< valarray<type> > vs. valarray< vector<type> > vs.
vector< valarray<type> > vs. vector < vector<type> >

In my application, type is will be a scalar type such as bool, double,
int, or size_t.

The code is initially being targeted for Linux, but it may also be
ported to another UNIX such as IRIX, or perhaps even Windows, so I'd
like to keep things portable by using an STL container rather than one
from some operating system specific template library.

-Michael

 

[Cy Edmunds]

I need to represent 1D and 2D arrays of numeric or bool types in a C++
program. The sizes of the arrays in my intended application are
dynamic in the sense that they are not known at compile time, so I'd
like to use an STL container class template such as valarray or vector
to represent 1D arrays, and valarrays or vectors of valarrays or
vectors to represent 2D arrays.

As I said the sizes of the arrays in my intended application are
dynamic in that they are determined at run time, but on the other hand
I don't anticipate the need to continually resize a given array during
a given call to the routine in which it is declared. The thing that's
more important to my application is speed. Is there a significant
different between the element access speeds of valarrays vs. vectors?

For 1D arrays, the choices are:
valarray<type> vs. vector<type>

For 2D arrays, the choices are:
valarray< valarray<type> > vs. valarray< vector<type> > vs.
vector< valarray<type> > vs. vector < vector<type> >

In my application, type is will be a scalar type such as bool, double,
int, or size_t.

The code is initially being targeted for Linux, but it may also be
ported to another UNIX such as IRIX, or perhaps even Windows, so I'd
like to keep things portable by using an STL container rather than one
from some operating system specific template library.

-Michael

I'm not aware of any serious access speed difference between valarray and
vector. However, I would say that overall valarray is not as well thought
out a design as vector.

For 2D arrays you have other options too. For instance you can allocate a
one dimensional array and compute the index from the row and column indices.
Whether that's faster or not depends on the algorithms you intend to apply.
For copying a matrix, for instance, it will almost certainly be faster.

I recommend you search around for some numeric libraries before writing your
own 2D array type. This has been done before.

 

[E. Robert Tisdale]

I need to represent 1D and 2D arrays of numeric or bool types in a C++
program. The sizes of the arrays in my intended application are
dynamic in the sense that they are not known at compile time, so I'd
like to use an STL container class template such as valarray or vector
to represent 1D arrays, and valarrays or vectors of valarrays or
vectors to represent 2D arrays.

As I said the sizes of the arrays in my intended application are
dynamic in that they are determined at run time, but on the other hand
I don't anticipate the need to continually resize a given array
during a given call to the routine in which it is declared.
The thing that's more important to my application is speed.

Standard vector class templates are for *flexible* arrays of any type.
Each of the vectors in a vector of vectors could have different lengths.
They will only cause you trouble
if you really need *rigid*, *rectangular* arrays of numbers.
In which case, standard valarray class templates are a better choice.

Is there a significant different
between the element access speeds of valarrays vs. vectors?

It depends upon the implementation
but valarrays were designed for the kind of optimizations
that are required for high performance numerical applications.

For 1D arrays, the choices are:
valarray<type> vs. vector<type>

For 2D arrays, the choices are:
valarray< valarray<type> > vs. valarray< vector<type> > vs.
vector< valarray<type> > vs. vector < vector<type> >

No. Use

valarray<type>

and standard slice templates to "view" it as a matrix [tensor].
See Bjarne Stroustrup, "The C++ Programming Language: Third Edition",
Chapter 22 Numerics, Section 4 Vector Arithmetic, pages 662-79.

In my application, type is will be a scalar type such as bool, double,
int, or size_t.

The code is initially being targeted for Linux, but it may also be
ported to another UNIX such as IRIX, or perhaps even Windows, so I'd
like to keep things portable by using an STL container rather than one
from some operating system specific template library.

Take a look at
The C++ Scalar, Vector, Matrix and Tensor class Library (SVMTL)

http://www.netwood.net/~edwin/svmtl/

and
The Object-Oriented Numerics Page

http://www.oonumerics.org/oon/

Probably the best approach is to implement vector and matrix classes
based upon standard valarray templates as Bjarne suggests.

 

[Kevin Goodsell]

I need to represent 1D and 2D arrays of numeric or bool types in a C++
program. The sizes of the arrays in my intended application are
dynamic in the sense that they are not known at compile time, so I'd
like to use an STL container class template such as valarray or vector
to represent 1D arrays, and valarrays or vectors of valarrays or
vectors to represent 2D arrays.

As I said the sizes of the arrays in my intended application are
dynamic in that they are determined at run time, but on the other hand
I don't anticipate the need to continually resize a given array during
a given call to the routine in which it is declared. The thing that's
more important to my application is speed. Is there a significant
different between the element access speeds of valarrays vs. vectors?

In general, use vector for your everyday array-type data structure.
valarrays are intended for mathematical operations (they are more
similar to mathematical vectors). vector access is extremely fast, on
par with built-in arrays. (In practice vectors are implemented as
dynamic arrays - this is not an explicit requirement, but it's the only
practical choice.)

-Kevin

 

[foo]

I need to represent 1D and 2D arrays of numeric or bool types in a C++
program. The sizes of the arrays in my intended application are
dynamic in the sense that they are not known at compile time, so I'd
like to use an STL container class template such as valarray or vector
to represent 1D arrays, and valarrays or vectors of valarrays or
vectors to represent 2D arrays.

As I said the sizes of the arrays in my intended application are
dynamic in that they are determined at run time, but on the other hand
I don't anticipate the need to continually resize a given array during
a given call to the routine in which it is declared. The thing that's
more important to my application is speed. Is there a significant
different between the element access speeds of valarrays vs. vectors?

For 1D arrays, the choices are:
valarray<type> vs. vector<type>

For 2D arrays, the choices are:
valarray< valarray<type> > vs. valarray< vector<type> > vs.
vector< valarray<type> > vs. vector < vector<type> >

In my application, type is will be a scalar type such as bool, double,
int, or size_t.

The code is initially being targeted for Linux, but it may also be
ported to another UNIX such as IRIX, or perhaps even Windows, so I'd
like to keep things portable by using an STL container rather than one
from some operating system specific template library.

-Michael

You can use the following class for a two dimensional array.
template < class T, int ROW_T = 0, int COL_T = 0 >
class dynamic_2d_array
{
public:
dynamic_2d_array(int row, int col):m_row(row),m_col(col),
m_data((row!=0&&col!=0)?new T[row*col]:NULL){}
dynamic_2d_array():m_row(ROW_T),m_col(COL_T), m_data(new
T[ROW_T*COL_T])
{if (!COL_T || !ROW_T) {int x[ROW_T] = {{ROW_T}};int y[COL_T] =
{{x[0]}};}}
~dynamic_2d_array(){if(m_data) delete []m_data;}
T* operator[](int i) {return (m_data + (m_col*i));}
T const*const operator[](int i) const {return (m_data +
(m_col*i));}
private:
const int m_row;
const int m_col;
T* m_data;
};

If you look at the following link, there's code for test performance
on the above class and other methods.

http://www.axter.com/faq/topic.asp?TOPIC_ID=60&FORUM_ID=4&CAT_ID=9

The above link has code for performing test on C-Style Static 2D
array, C-Syle Dynamic 2D array, vector<vector<obj> > , and the above
dynamic_2d_array class.

In the test, the dynamic_2d_array class out performmed the vector
method when accessing the data via operator[].
However, the vector method out performmed all the other methods when
accessing the data via iterators.

 

[{AGUT2} {H}-IWIK]

I'm not aware of any serious access speed difference between valarray and

vector. However, I would say that overall valarray is not as well thought
out a design as vector.

Lo cy

Alex

 

[Cy Edmunds]

Lo cy

Alex

Ya never know when the gamers are gonna sneak in... lol hi

 

[mjm]

Blitz++ by Todd Veldhuizen seems to be the most highly optimized C++
array library around:
http://www.oonumerics.org
However there is a learning curve involved, compile times are very
slow
(template meta prgramming) and you need a very capable C++ compiler
(KAI, SGI and maybe now also Intel).

If speed is really that important but C++ is not mandatory think about
Fortran.

 

[Jerry Coffin]

[ ... ]

Standard vector class templates are for *flexible* arrays of any type.
Each of the vectors in a vector of vectors could have different lengths.
They will only cause you trouble
if you really need *rigid*, *rectangular* arrays of numbers.
In which case, standard valarray class templates are a better choice.

This may be true, but I've yet to see real evidence of it.

[ ... ]

It depends upon the implementation
but valarrays were designed for the kind of optimizations
that are required for high performance numerical applications.

Yes and no -- valarrays were really designed to work well with vector
machines (which ARE used primarily for high-performance numerical
applications). Unfortunately, they generally do NOT work particularly
well with most current architectures.

The basic difference is simple: on a vector machine, you generally want
to apply a single operation to an entire array at a time, then apply the
next operation to the entire array, and so on until you've applied all
the operations you need to the entire array. The basic definition of a
vector machine is that it can apply a single operation to a number of
elements in parallel. The prototypical vector machine is the Cray,
which has 3 sets of 64 registers each -- it can be loading one set of 64
registers, applying a single operation to another set of 64, and storing
the third set of 64 all at the same time. A valarray fits this pattern
beautifully, so with a machine like this, you _should_ get excellent
efficiency with it.

The basic problem with this design is that it requires a LOT of
bandwidth to memory. A typical modern machine has an extremely fast
CPU, but the main memory is a LOT slower, with a cache to make up the
difference. On a machine like this, optimal usage is almost exactly the
opposite -- you want to load a single value, apply _all_ your operations
to it, then go on to the next value. On such a machine, most of the
operations supported by valarray perform quite poorly, and the only way
to get decent performance is to treat a valarray just about like a
vector.

 

[Sean Dettrick]

For 1D arrays, the choices are:
valarray<type> vs. vector<type>

For 2D arrays, the choices are:
valarray< valarray<type> > vs. valarray< vector<type> > vs.
vector< valarray<type> > vs. vector < vector<type> >

If speeds is of the essence, I would suggest you measure the times
yourself.
Also consider building classes so that the underlying STL class
(vector, valarray, deque) can be changed without effecting the rest of
your code.

For 2D and 3D arrays, I have found it is faster to use a 1D
vector<double> with a computed index (kept track of manually) than to
use vector < vector<type> > or
vector < vector< vector<type> > >. In the 3D case, a 1D vector is
MUCH faster than a 3D vector. In the 2D case, the speed difference
was about 10% I think.

In my application, type is will be a scalar type such as bool, double,
int, or size_t.

Then you need to read about the well known caveat about vector<bool>

The code is initially being targeted for Linux, but it may also be
ported to another UNIX such as IRIX, or perhaps even Windows, so I'd
like to keep things portable by using an STL container rather than one
from some operating system specific template library.

Sounds like you'll be using a lot of different compilers - beware that
valarray is not always well supported. I found vector and valarray
had the same speed, but valarray wasn't fully supported by all
compilers.

Finally, if you ever plan to interface to legacy C or fortran code, a
1D vector<> has the advantage that its contents are guaranteed to be
contiguous in memory. That simplifies any such interface
considerably.

Sean

 

[vrambati]

Originally posted by Sean Dettrick

If speeds is of the essence, I would suggest you measure the times

Also consider building classes so that the underlying STL class

(vector, valarray, deque) can be changed without effecting the rest of

your code.

For 2D and 3D arrays, I have found it is faster to use a 1D

vector<double> with a computed index (kept track of manually) than to

use vector < vector<type> > or

vector < vector< vector<type> > >. In the 3D case, a 1D vector is

MUCH faster than a 3D vector. In the 2D case, the speed difference

was about 10% I think.

Question: Instead of using a vector<vector<type>> for a 2d array,
we can also use vector<anothertype>, where "anothertype" has two
members of "type".

My question: Is this way of implementation is more efficient then
having a long vector of 1d with a computed index in order to manage 2d
vector?.

Quick replies for this question will be very useful to me. Thanks in
advance.





Then you need to read about the well known caveat about vector<bool>

(e.g. in the Meyers book), and consider using deque<bool> for the bool





Sounds like you'll be using a lot of different compilers - beware that

valarray is not always well supported. I found vector and valarray

had the same speed, but valarray wasn't fully supported by all


Finally, if you ever plan to interface to legacy C or fortran code, a

1D vector<> has the advantage that its contents are guaranteed to be

contiguous in memory. That simplifies any such interface

Sean