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]

Re: C++ STL valarrays vs. vectors

"Michael Aramini" <M.Aramini@Veri zon.net> wrote in message
news:SeS4b.1682 0$zL5.11807@nwr dny02.gnilink.n et...[color=blue]
> 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
>[/color]

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.

--
Cy

http://home.rochester.rr.com/cyhome/

[E. Robert Tisdale]

Re: C++ STL valarrays vs. vectors

Michael Aramini wrote:
[color=blue]
> 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.[/color]

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.
[color=blue]
> Is there a significant different
> between the element access speeds of valarrays vs. vectors?[/color]

It depends upon the implementation
but valarrays were designed for the kind of optimizations
that are required for high performance numerical applications.
[color=blue]
> 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> >[/color]

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.
[color=blue]
> 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.[/color]

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.

[foo]

Re: C++ STL valarrays vs. vectors

Michael Aramini <M.Aramini@Veri zon.net> wrote in message news:<SeS4b.168 20$zL5.11807@nw rdny02.gnilink. net>...[color=blue]
> 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[/color]

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_arra y
{
public:
dynamic_2d_arra y(int row, int col):m_row(row) ,m_col(col),
m_data((row!=0& &col!=0)?new T[row*col]:NULL){}
dynamic_2d_arra y():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_arr ay(){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<o bj> > , and the above
dynamic_2d_arra y class.

In the test, the dynamic_2d_arra y 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.

[Kevin Goodsell]

Re: C++ STL valarrays vs. vectors

Michael Aramini wrote:
[color=blue]
> 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?
>[/color]

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
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[{AGUT2} {H}-IWIK]

Re: C++ STL valarrays vs. vectors

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

Lo cy :)

Alex

--
Reply to:alex an.ti livingstone sp@am btinternet.com cutting the usual...

[Cy Edmunds]

Re: C++ STL valarrays vs. vectors

"{AGUT2} {H}-IWIK" <alexan.tilivin gstonesp@ambtin ternet.com> wrote in
message news:opruu3pwdb p508op@mercury. nildram.net...[color=blue][color=green]
> > I'm not aware of any serious access speed difference between valarray[/color][/color]
and[color=blue][color=green]
> > vector. However, I would say that overall valarray is not as well[/color][/color]
thought[color=blue][color=green]
> > out a design as vector.[/color]
>
> Lo cy :)
>
> Alex
>
> --
> Reply to:alex an.ti livingstone sp@am btinternet.com cutting the usual...[/color]

Ya never know when the gamers are gonna sneak in... lol hi
--
Cycho{HHR}

http://home.rochester.rr.com/cyhome/

[mjm]

Re: C++ STL valarrays vs. vectors

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]

Re: C++ STL valarrays vs. vectors

In article <3F540A80.30802 08@jpl.nasa.gov >,
E.Robert.Tisdal e@jpl.nasa.gov says...

[ ... ]
[color=blue]
> 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.[/color]

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

[ ... ]
[color=blue]
> It depends upon the implementation
> but valarrays were designed for the kind of optimizations
> that are required for high performance numerical applications.[/color]

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.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Sean Dettrick]

Re: C++ STL valarrays vs. vectors

Michael Aramini <M.Aramini@Veri zon.net> wrote in message news:<SeS4b.168 20$zL5.11807@nw rdny02.gnilink. net>...[color=blue]
>
> 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> >
>[/color]

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.
[color=blue]
> In my application, type is will be a scalar type such as bool, double,
> int, or size_t.[/color]

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
case.
[color=blue]
> 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.[/color]

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]

Re: C++ STL valarrays vs. vectors


Originally posted by Sean Dettrick
[color=blue]
> Michael Aramini <M.Aramini@Veri zon.net> wrote in message
> news:<SeS4b.168 20$zL5.11807@nw rdny02.gnilink. net>...[/color]
[color=blue][color=green]
> >[/color][/color]
[color=blue][color=green]
> > For 1D arrays, the choices are:[/color][/color]
[color=blue][color=green]
> > valarray<type> vs. vector<type>[/color][/color]
[color=blue][color=green]
> >[/color][/color]
[color=blue][color=green]
> > For 2D arrays, the choices are:[/color][/color]
[color=blue][color=green]
> > valarray< valarray<type> > vs. valarray< vector<type> >[/color]
> vs.[/color]
[color=blue][color=green]
> > vector< valarray<type> > vs. vector < vector<type> >[/color][/color]
[color=blue][color=green]
> >[/color][/color]
[color=blue]
>[/color]
[color=blue]
> If speeds is of the essence, I would suggest you measure the times[/color]
[color=blue]
> yourself.[/color]
[color=blue]
> Also consider building classes so that the underlying STL class[/color]
[color=blue]
> (vector, valarray, deque) can be changed without effecting the rest of[/color]
[color=blue]
> your code.[/color]
[color=blue]
>[/color]
[color=blue]
> For 2D and 3D arrays, I have found it is faster to use a 1D[/color]
[color=blue]
> vector<double> with a computed index (kept track of manually) than to[/color]
[color=blue]
> use vector < vector<type> > or[/color]
[color=blue]
> vector < vector< vector<type> > >. In the 3D case, a 1D vector is[/color]
[color=blue]
> MUCH faster than a 3D vector. In the 2D case, the speed difference[/color]
[color=blue]
> was about 10% I think.[/color]
[color=blue]
>[/color]
[color=blue]
> Question: Instead of using a vector<vector<t ype>> for a 2d array,
> we can also use vector<anothert ype>, where "anothertyp e" has two
> members of "type".[/color]
[color=blue]
>[/color]
[color=blue]
> 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?.[/color]
[color=blue]
>[/color]
[color=blue]
> Quick replies for this question will be very useful to me. Thanks in
> advance.[/color]
[color=blue]
>[/color]
[color=blue]
> -Vijaya.[/color]
[color=blue]
>[/color]
[color=blue][color=green]
> > In my application, type is will be a scalar type such as bool,[/color]
> double,[/color]
[color=blue][color=green]
> > int, or size_t.[/color][/color]
[color=blue]
>[/color]
[color=blue]
> Then you need to read about the well known caveat about vector<bool>[/color]
[color=blue]
> (e.g. in the Meyers book), and consider using deque<bool> for the bool[/color]
[color=blue]
> case.[/color]
[color=blue]
>[/color]
[color=blue][color=green]
> > The code is initially being targeted for Linux, but it may also[/color]
> be[/color]
[color=blue][color=green]
> > ported to another UNIX such as IRIX, or perhaps even Windows, so[/color]
> I'd[/color]
[color=blue][color=green]
> > like to keep things portable by using an STL container rather[/color]
> than one[/color]
[color=blue][color=green]
> > from some operating system specific template library.[/color][/color]
[color=blue]
>[/color]
[color=blue]
> Sounds like you'll be using a lot of different compilers - beware that[/color]
[color=blue]
> valarray is not always well supported. I found vector and valarray[/color]
[color=blue]
> had the same speed, but valarray wasn't fully supported by all[/color]
[color=blue]
> compilers.[/color]
[color=blue]
>[/color]
[color=blue]
> Finally, if you ever plan to interface to legacy C or fortran code, a[/color]
[color=blue]
> 1D vector<> has the advantage that its contents are guaranteed to be[/color]
[color=blue]
> contiguous in memory. That simplifies any such interface[/color]
[color=blue]
> considerably.[/color]
[color=blue]
>[/color]

Sean


--
Posted via http://dbforums.com