C++ STL valarrays vs. vectors

Discussion in 'C++' started by Michael Aramini, Sep 2, 2003.

  1. 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
     
    Michael Aramini, Sep 2, 2003
    #1
    1. Advertising

  2. Michael Aramini

    Cy Edmunds Guest

    "Michael Aramini" <> wrote in message
    news:SeS4b.16820$...
    > 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.

    --
    Cy
    http://home.rochester.rr.com/cyhome/
     
    Cy Edmunds, Sep 2, 2003
    #2
    1. Advertising

  3. Michael Aramini wrote:

    > 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.
     
    E. Robert Tisdale, Sep 2, 2003
    #3
  4. Michael Aramini wrote:

    > 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
    --
    My email address is valid, but changes periodically.
    To contact me please use the address from a recent posting.
     
    Kevin Goodsell, Sep 2, 2003
    #4
  5. Michael Aramini

    foo Guest

    Michael Aramini <> wrote in message news:<SeS4b.16820$>...
    > 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.
     
    foo, Sep 2, 2003
    #5
  6. > 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

    --
    Reply to:alex an.ti livingstone sp@am btinternet.com cutting the usual...
     
    {AGUT2} {H}-IWIK, Sep 2, 2003
    #6
  7. Michael Aramini

    Cy Edmunds Guest

    "{AGUT2} {H}-IWIK" <> wrote in
    message news:eek:...
    > > 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
    >
    > --
    > Reply to:alex an.ti livingstone sp@am btinternet.com cutting the usual...


    Ya never know when the gamers are gonna sneak in... lol hi
    --
    Cycho{HHR}
    http://home.rochester.rr.com/cyhome/
     
    Cy Edmunds, Sep 2, 2003
    #7
  8. Michael Aramini

    mjm Guest

    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.
     
    mjm, Sep 3, 2003
    #8
  9. Michael Aramini

    Jerry Coffin Guest

    In article <>,
    says...

    [ ... ]

    > 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.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
     
    Jerry Coffin, Sep 14, 2003
    #9
  10. Michael Aramini <> wrote in message news:<SeS4b.16820$>...
    >
    > 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>
    (e.g. in the Meyers book), and consider using deque<bool> for the bool
    case.

    > 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
     
    Sean Dettrick, Sep 14, 2003
    #10
  11. Michael Aramini

    vrambati Guest

    Originally posted by Sean Dettrick

    > Michael Aramini <> wrote in message
    > news:<SeS4b.16820$>...


    > >


    > > 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.


    >


    > 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.


    >


    > -Vijaya.


    >


    > > 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>


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


    > case.


    >


    > > 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


    --
    Posted via http://dbforums.com
     
    vrambati, Nov 3, 2003
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. tom_usenet

    Re: Returning valarrays

    tom_usenet, Jul 1, 2003, in forum: C++
    Replies:
    0
    Views:
    391
    tom_usenet
    Jul 1, 2003
  2. E. Robert Tisdale

    Re: Returning valarrays

    E. Robert Tisdale, Jul 1, 2003, in forum: C++
    Replies:
    0
    Views:
    407
    E. Robert Tisdale
    Jul 1, 2003
  3. Sebastian Thiebes

    valarrays and regular arrays

    Sebastian Thiebes, Jun 9, 2004, in forum: C++
    Replies:
    3
    Views:
    470
    Marc Schellens
    Jun 10, 2004
  4. Gerard Kramer
    Replies:
    9
    Views:
    375
    Gerard Kramer
    Jul 10, 2006
  5. Replies:
    5
    Views:
    401
    Lionel B
    Feb 23, 2007
Loading...

Share This Page