valarray <vallaray<T> > efficiency

Discussion in 'C++' started by john, Jan 3, 2008.

  1. john

    john Guest

    Hi, in TC++PL 3 on pages 674-675 it is mentioned:


    "Maybe your first idea for a two-dimensional vector was something like this:

    class Matrix {
    valarray< valarray<double> >v;
    public:
    // ...
    };

    This would also work (22.9[10]). However, it is not easy to match
    efficiency and compatibility required by high performance computations
    without dropping to the lower and more conventional level represented by
    valarray plus slices".


    However since 1998 much time has passed, and I wonder if the current
    compiler implementations allow valarray<valarray<T> > to be equally
    efficient (or more) than using a valarray with slices/slice_arrays.
    john, Jan 3, 2008
    #1
    1. Advertising

  2. john

    kwikius Guest

    On Jan 3, 3:03 pm, john <> wrote:
    > Hi, in TC++PL 3 on pages 674-675 it is mentioned:
    >
    > "Maybe your first idea for a two-dimensional vector was something like this:
    >
    > class Matrix {
    >       valarray< valarray<double> >v;
    > public:
    >        // ...
    >
    > };
    >
    > This would also work (22.9[10]). However, it is not easy to match
    > efficiency and compatibility required by high performance computations
    > without dropping to the lower and more conventional level represented by
    > valarray plus slices".
    >
    > However since 1998 much time has passed, and I wonder if the current
    > compiler implementations allow valarray<valarray<T> > to be equally
    > efficient (or more) than using a valarray with slices/slice_arrays.


    My 2p's worth.. FWIW

    Because a valarray is not a compile time fixed size it must? use heap
    allocation, hence a matrix as view of list approach will likely only
    require one allocation, whereas matrix as sequence of sequence will
    require multiple allocations.

    I believe even now that compilers find it difficult to do much
    optimisation on heap pointers( even wary of stack pointers and
    anything complicated in references), so it probably makes sense to use
    as few pointers as possible, then the compiler only needs to deal with
    a single offset.

    Anyway its an interesting issue :)

    regards
    Andy Little
    kwikius, Jan 3, 2008
    #2
    1. Advertising

  3. kwikius wrote:
    >
    > My 2p's worth.. FWIW
    >
    > Because a valarray is not a compile time fixed size it must? use heap
    > allocation, hence a matrix as view of list approach will likely only
    > require one allocation, whereas matrix as sequence of sequence will
    > require multiple allocations.
    >
    > I believe even now that compilers find it difficult to do much
    > optimisation on heap pointers( even wary of stack pointers and
    > anything complicated in references), so it probably makes sense to use
    > as few pointers as possible, then the compiler only needs to deal with
    > a single offset.
    >
    > Anyway its an interesting issue :)



    Given that TC++PL3 was written before the change in the standard that
    *requires* that vectors, valarrays, etc are implemented as continuous
    sequences,wouldn't the following be more efficient or at least the same
    efficient as the usage of valarrays and slices/slice_arrays to
    "simulate" a 2-dimensional matrix?


    #include <iostream>
    #include <valarray>



    int main()
    {
    using namespace std;

    valarray<int> vi(1, 10);

    int (*p)[5]= reinterpret_cast<int (*)[5]> (&vi[0]);

    for (size_t i= 0; i< 2; ++i)
    for(size_t j=0; j<5; ++j)
    cout<< p[j]<<" ";

    cout<< endl;

    }


    Here p behaves a s a 2-dimensional matrix, that is a 2x5 matrix.
    Ioannis Vranos, Jan 3, 2008
    #3
  4. Ioannis Vranos wrote:
    > kwikius wrote:
    >>
    >> My 2p's worth.. FWIW
    >>
    >> Because a valarray is not a compile time fixed size it must? use heap
    >> allocation, hence a matrix as view of list approach will likely only
    >> require one allocation, whereas matrix as sequence of sequence will
    >> require multiple allocations.
    >>
    >> I believe even now that compilers find it difficult to do much
    >> optimisation on heap pointers( even wary of stack pointers and
    >> anything complicated in references), so it probably makes sense to
    >> use as few pointers as possible, then the compiler only needs to
    >> deal with a single offset.
    >>
    >> Anyway its an interesting issue :)

    >
    >
    > Given that TC++PL3 was written before the change in the standard that
    > *requires* that vectors, valarrays, etc are implemented as continuous
    > sequences,wouldn't the following be more efficient or at least the
    > same efficient as the usage of valarrays and slices/slice_arrays to
    > "simulate" a 2-dimensional matrix?



    Given that 'reinterpret_cast' is not supposed to be used that way,
    the following has undefined behaviour. Aside from that...

    >
    >
    > #include <iostream>
    > #include <valarray>
    >
    >
    >
    > int main()
    > {
    > using namespace std;
    >
    > valarray<int> vi(1, 10);
    >
    > int (*p)[5]= reinterpret_cast<int (*)[5]> (&vi[0]);
    >
    > for (size_t i= 0; i< 2; ++i)
    > for(size_t j=0; j<5; ++j)
    > cout<< p[j]<<" ";
    >
    > cout<< endl;
    >
    > }
    >
    >
    > Here p behaves a s a 2-dimensional matrix, that is a 2x5 matrix.


    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Jan 3, 2008
    #4
  5. Victor Bazarov wrote:
    >
    > Given that 'reinterpret_cast' is not supposed to be used that way,



    Apart from the approach:

    static_cast<int (*)[5]> ( static_cast<void *> (&vi[0]) );


    why reinterpret_cast "is not supposed to be used that way"?
    Ioannis Vranos, Jan 3, 2008
    #5
  6. Ioannis Vranos wrote:
    > Victor Bazarov wrote:
    >>
    >> Given that 'reinterpret_cast' is not supposed to be used that way,

    >
    >
    > Apart from the approach:
    >
    > static_cast<int (*)[5]> ( static_cast<void *> (&vi[0]) );
    >
    >
    > why reinterpret_cast "is not supposed to be used that way"?


    If you reinterpret_cast one object pointer into another object
    pointer, the Standard only specifies that the resulting pointer
    can be converted back to the original type. Please see Standard,
    [expr.reinterpret.cast]/7. Whatever you think you can do with
    the pointer, is not in the langauge specification, literally.

    As to the two consequitive static_cast operations, the result
    of those is also unspecified, since you're not converting the
    result of static_cast<void*> back to the original type. See
    [expr.static.cast].

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Jan 3, 2008
    #6
  7. john

    kwikius Guest

    On Jan 3, 4:49 pm, Ioannis Vranos <> wrote:
    > kwikius wrote:
    >
    > > My 2p's worth.. FWIW

    >
    > > Because a valarray is not a compile time fixed size it must? use heap
    > > allocation, hence a matrix as view of list approach will likely only
    > > require one allocation, whereas matrix as sequence of sequence will
    > > require multiple allocations.

    >
    > > I believe even now that compilers find it difficult to do much
    > > optimisation on heap pointers( even wary of stack pointers and
    > > anything complicated in references), so it probably makes sense to use
    > > as few pointers as possible, then the compiler only needs to deal with
    > > a single offset.

    >
    > > Anyway its an interesting issue :)

    >
    > Given that TC++PL3 was written before the change in the standard that
    > *requires* that vectors, valarrays, etc are implemented as continuous
    > sequences,wouldn't the following be more efficient or at least the same
    > efficient as the usage of valarrays and slices/slice_arrays to
    > "simulate" a 2-dimensional matrix?


    The more interesting question to me is how necessary runtime
    resizability of matrices is. Because if they are not resizeable then
    there is no need to allocate from the heap and valarray is unnecessary
    (you can simple use a wrapped c-style array), in which case the
    compiler has much better opportunities for optimisation.

    And N.B some might call an e.g array of 3dpoints a matrix where I
    would see it as an array of matrices where 1 dimension is equal to 1
    dependent on the local convention.

    regards
    Andy Little
    kwikius, Jan 3, 2008
    #7
  8. On 2008-01-03 16:03, john wrote:
    > Hi, in TC++PL 3 on pages 674-675 it is mentioned:
    >
    >
    > "Maybe your first idea for a two-dimensional vector was something like this:
    >
    > class Matrix {
    > valarray< valarray<double> >v;
    > public:
    > // ...
    > };
    >
    > This would also work (22.9[10]). However, it is not easy to match
    > efficiency and compatibility required by high performance computations
    > without dropping to the lower and more conventional level represented by
    > valarray plus slices".
    >
    >
    > However since 1998 much time has passed, and I wonder if the current
    > compiler implementations allow valarray<valarray<T> > to be equally
    > efficient (or more) than using a valarray with slices/slice_arrays.


    For various reasons valarray never became what it was meant to be, and
    few people use it. Since few use it the library writers have not
    bothered much with it so I would not be surprised if the code is more or
    less the same as it was back in 1998. And even if they had it would
    still not be able to match the efficiency of slices since a valarray of
    valarrays adds an additional layer of indirection.

    --
    Erik Wikström
    Erik Wikström, Jan 3, 2008
    #8
  9. Victor Bazarov wrote:
    > Ioannis Vranos wrote:
    >> Victor Bazarov wrote:
    >>> Given that 'reinterpret_cast' is not supposed to be used that way,

    >>
    >> Apart from the approach:
    >>
    >> static_cast<int (*)[5]> ( static_cast<void *> (&vi[0]) );
    >>
    >>
    >> why reinterpret_cast "is not supposed to be used that way"?

    >
    > If you reinterpret_cast one object pointer into another object
    > pointer, the Standard only specifies that the resulting pointer
    > can be converted back to the original type. Please see Standard,
    > [expr.reinterpret.cast]/7. Whatever you think you can do with
    > the pointer, is not in the langauge specification, literally.



    There, it is mentioned:

    "A pointer to an object can be explicitly converted to a pointer to an
    object of different type. 65)".

    "65) The types may have different cv-qualifiers, subject to the overall
    restriction that a reinterpret_cast cannot cast away const-
    ness".



    >
    > As to the two consequitive static_cast operations, the result
    > of those is also unspecified, since you're not converting the
    > result of static_cast<void*> back to the original type. See
    > [expr.static.cast].



    Yes, I think in the standard, conversions from "pointer to object" to
    "pointer to an array of n objects" is not explicitly mentioned, but I
    think there isn't any decent implementation where it does not work
    whenever the pointed object is member of an array (sequence).

    Actually I have the feeling the guarantee exists in the standard and is
    probably "buried" in some clause. :)


    So we have

    int main()
    {


    int array[5]= {0};

    int *p= &array[0];

    int (*q)[5]= reinterpret_cast<int (*)[5]> (p);
    }



    Shouldn't the last always work?
    Ioannis Vranos, Jan 3, 2008
    #9
  10. kwikius wrote:
    >
    >> Given that TC++PL3 was written before the change in the standard that
    >> *requires* that vectors, valarrays, etc are implemented as continuous
    >> sequences,wouldn't the following be more efficient or at least the same
    >> efficient as the usage of valarrays and slices/slice_arrays to
    >> "simulate" a 2-dimensional matrix?

    >
    > The more interesting question to me is how necessary runtime
    > resizability of matrices is. Because if they are not resizeable then
    > there is no need to allocate from the heap and valarray is unnecessary
    > (you can simple use a wrapped c-style array), in which case the
    > compiler has much better opportunities for optimisation.



    valarray is not a typical container in terms of implementation. It is
    intended to be heavily optimised, and it can use raw storage from
    anywhere or something else AFAIK.
    Ioannis Vranos, Jan 3, 2008
    #10
  11. Erik Wikström wrote:
    > On 2008-01-03 16:03, john wrote:
    >> Hi, in TC++PL 3 on pages 674-675 it is mentioned:
    >>
    >>
    >> "Maybe your first idea for a two-dimensional vector was something like this:
    >>
    >> class Matrix {
    >> valarray< valarray<double> >v;
    >> public:
    >> // ...
    >> };
    >>
    >> This would also work (22.9[10]). However, it is not easy to match
    >> efficiency and compatibility required by high performance computations
    >> without dropping to the lower and more conventional level represented by
    >> valarray plus slices".
    >>
    >>
    >> However since 1998 much time has passed, and I wonder if the current
    >> compiler implementations allow valarray<valarray<T> > to be equally
    >> efficient (or more) than using a valarray with slices/slice_arrays.

    >
    > For various reasons valarray never became what it was meant to be, and
    > few people use it. Since few use it the library writers have not
    > bothered much with it so I would not be surprised if the code is more or
    > less the same as it was back in 1998. And even if they had it would
    > still not be able to match the efficiency of slices since a valarray of
    > valarrays adds an additional layer of indirection.




    How about using "pointer to array" pointing to a member of a valarray as
    I mentioned in another post in the thread instead of slices, to
    simulate a matrix?
    Ioannis Vranos, Jan 3, 2008
    #11
  12. Ioannis Vranos wrote:
    > Victor Bazarov wrote:
    >> Ioannis Vranos wrote:
    >>> Victor Bazarov wrote:
    >>>> Given that 'reinterpret_cast' is not supposed to be used that way,
    >>>
    >>> Apart from the approach:
    >>>
    >>> static_cast<int (*)[5]> ( static_cast<void *> (&vi[0]) );
    >>>
    >>>
    >>> why reinterpret_cast "is not supposed to be used that way"?

    >>
    >> If you reinterpret_cast one object pointer into another object
    >> pointer, the Standard only specifies that the resulting pointer
    >> can be converted back to the original type. Please see Standard,
    >> [expr.reinterpret.cast]/7. Whatever you think you can do with
    >> the pointer, is not in the langauge specification, literally.

    >
    >
    > There, it is mentioned:
    >
    > "A pointer to an object can be explicitly converted to a pointer to an
    > object of different type. 65)".
    >
    > "65) The types may have different cv-qualifiers, subject to the
    > overall restriction that a reinterpret_cast cannot cast away const-
    > ness".
    >
    >
    >
    >>
    >> As to the two consequitive static_cast operations, the result
    >> of those is also unspecified, since you're not converting the
    >> result of static_cast<void*> back to the original type. See
    >> [expr.static.cast].

    >
    >
    > Yes, I think in the standard, conversions from "pointer to object" to
    > "pointer to an array of n objects" is not explicitly mentioned, but I
    > think there isn't any decent implementation where it does not work
    > whenever the pointed object is member of an array (sequence).
    >
    > Actually I have the feeling the guarantee exists in the standard and
    > is probably "buried" in some clause. :)


    Find it; everybody will be grateful.

    > [..]


    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Jan 3, 2008
    #12
  13. On 2008-01-03 22:39, Ioannis Vranos wrote:
    > Erik Wikström wrote:
    >> On 2008-01-03 16:03, john wrote:
    >>> Hi, in TC++PL 3 on pages 674-675 it is mentioned:
    >>>
    >>>
    >>> "Maybe your first idea for a two-dimensional vector was something like this:
    >>>
    >>> class Matrix {
    >>> valarray< valarray<double> >v;
    >>> public:
    >>> // ...
    >>> };
    >>>
    >>> This would also work (22.9[10]). However, it is not easy to match
    >>> efficiency and compatibility required by high performance computations
    >>> without dropping to the lower and more conventional level represented by
    >>> valarray plus slices".
    >>>
    >>>
    >>> However since 1998 much time has passed, and I wonder if the current
    >>> compiler implementations allow valarray<valarray<T> > to be equally
    >>> efficient (or more) than using a valarray with slices/slice_arrays.

    >>
    >> For various reasons valarray never became what it was meant to be, and
    >> few people use it. Since few use it the library writers have not
    >> bothered much with it so I would not be surprised if the code is more or
    >> less the same as it was back in 1998. And even if they had it would
    >> still not be able to match the efficiency of slices since a valarray of
    >> valarrays adds an additional layer of indirection.

    >
    >
    >
    > How about using "pointer to array" pointing to a member of a valarray as
    > I mentioned in another post in the thread instead of slices, to
    > simulate a matrix?


    If you want a matrix there are a number of libraries out there, or you
    can write your own. In the end it usually ends up with a contiguous
    piece of memory that is somehow divided into rown/columns and some
    simple arithmetic is used to get the correct element. Besides, these
    kinds of optimisations usually have a smaller impact than expected in
    real world applications where operations are usually performed on the
    whole matrix and where the real costs comes from creation of
    temporaries. That is why expression templates are used by all libraries
    aiming for high performance.

    --
    Erik Wikström
    Erik Wikström, Jan 3, 2008
    #13
  14. On 2008-01-03 22:36, Ioannis Vranos wrote:
    > kwikius wrote:
    >>
    >>> Given that TC++PL3 was written before the change in the standard that
    >>> *requires* that vectors, valarrays, etc are implemented as continuous
    >>> sequences,wouldn't the following be more efficient or at least the same
    >>> efficient as the usage of valarrays and slices/slice_arrays to
    >>> "simulate" a 2-dimensional matrix?

    >>
    >> The more interesting question to me is how necessary runtime
    >> resizability of matrices is. Because if they are not resizeable then
    >> there is no need to allocate from the heap and valarray is unnecessary
    >> (you can simple use a wrapped c-style array), in which case the
    >> compiler has much better opportunities for optimisation.

    >
    >
    > valarray is not a typical container in terms of implementation. It is
    > intended to be heavily optimised, and it can use raw storage from
    > anywhere or something else AFAIK.


    That was the intention, however, as I mentioned elsethread, that is not
    the case. I do not know of any high-performance applications (and I
    doubt that they exist) where valarrays are used. My understanding is
    that valarray is designed to allow for optimisations (such as utilising
    SIMD instructions), but no implementation have made those optimisations.

    --
    Erik Wikström
    Erik Wikström, Jan 4, 2008
    #14
  15. Erik Wikström wrote:
    >
    >> valarray is not a typical container in terms of implementation. It is
    >> intended to be heavily optimised, and it can use raw storage from
    >> anywhere or something else AFAIK.

    >
    > That was the intention, however, as I mentioned elsethread, that is not
    > the case. I do not know of any high-performance applications (and I
    > doubt that they exist) where valarrays are used. My understanding is
    > that valarray is designed to allow for optimisations (such as utilising
    > SIMD instructions), but no implementation have made those optimisations.



    So, what kind of container is used for high performance C++ computing
    instead? Those template math libraries on the web?
    Ioannis Vranos, Jan 4, 2008
    #15
  16. john

    kwikius Guest

    On Jan 3, 9:36 pm, Ioannis Vranos <> wrote:
    > kwikius wrote:
    >
    > >> Given that TC++PL3 was written before the change in the standard that
    > >> *requires* that vectors, valarrays, etc are implemented as continuous
    > >> sequences,wouldn't the following be more efficient or at least the same
    > >> efficient as the usage of valarrays and slices/slice_arrays to
    > >> "simulate" a 2-dimensional matrix?

    >
    > > The more interesting question to me is how necessary runtime
    > > resizability of matrices is. Because if they are not resizeable then
    > > there is no need to allocate from the heap and valarray is unnecessary
    > > (you can simple use a wrapped c-style array), in which case the
    > > compiler has much better opportunities for optimisation.

    >
    > valarray is not a typical container in terms of implementation. It is
    > intended to be heavily optimised, and it can use raw storage from
    > anywhere or something else AFAIK.


    In practise I reckon you will find that implementation of valarray
    uses "new" to allocate, after all if this cool allocation mechanism
    exists , you might as well use it for new too..

    regards
    Andy Little
    kwikius, Jan 4, 2008
    #16
  17. On 2008-01-04 01:16, Ioannis Vranos wrote:
    > Erik Wikström wrote:
    >>
    >>> valarray is not a typical container in terms of implementation. It is
    >>> intended to be heavily optimised, and it can use raw storage from
    >>> anywhere or something else AFAIK.

    >>
    >> That was the intention, however, as I mentioned elsethread, that is not
    >> the case. I do not know of any high-performance applications (and I
    >> doubt that they exist) where valarrays are used. My understanding is
    >> that valarray is designed to allow for optimisations (such as utilising
    >> SIMD instructions), but no implementation have made those optimisations.

    >
    >
    > So, what kind of container is used for high performance C++ computing
    > instead? Those template math libraries on the web?


    For a non-sparse NxM matrix of type double I would assume that they
    simply allocate an array of N*M elements. But I have not looked under
    the hood on any of them.

    --
    Erik Wikström
    Erik Wikström, Jan 4, 2008
    #17
  18. Victor Bazarov wrote:
    >
    > Ioannis Vranos wrote:
    >
    >> There, it is mentioned:
    >>
    >> "A pointer to an object can be explicitly converted to a pointer to an
    >> object of different type. 65)".
    >>
    >> "65) The types may have different cv-qualifiers, subject to the
    >> overall restriction that a reinterpret_cast cannot cast away const-
    >> ness".

    > [...]
    >> Actually I have the feeling the guarantee exists in the standard and
    >> is probably "buried" in some clause. :)

    >
    > Find it; everybody will be grateful.



    I think the above quotation from the standard is sufficient.
    Ioannis Vranos, Jan 4, 2008
    #18
  19. Ioannis Vranos wrote:
    > Victor Bazarov wrote:
    >>
    >> Ioannis Vranos wrote:
    >>
    >>> There, it is mentioned:
    >>>
    >>> "A pointer to an object can be explicitly converted to a pointer to
    >>> an object of different type. 65)".
    >>>
    >>> "65) The types may have different cv-qualifiers, subject to the
    >>> overall restriction that a reinterpret_cast cannot cast away const-
    >>> ness".

    >> [...]
    >>> Actually I have the feeling the guarantee exists in the standard and
    >>> is probably "buried" in some clause. :)

    >>
    >> Find it; everybody will be grateful.

    >
    >
    > I think the above quotation from the standard is sufficient.


    No, it's not. You conveniently omitted the rest of the paragraph
    7, following the "type. 65)". Read it. The result of such conversion
    is unspecified. That means no guarantees are given. Where you get
    your "feeling the guarantee exists", I cannot imagine. If you find it
    elsewhere, do post about it. Until you do, the guarantee that you
    speak of does NOT exist, and that is expressed in the second sentence
    of the paragraph 7 of [expr.reinterpret.cast].

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Jan 4, 2008
    #19
  20. Victor Bazarov wrote:
    >
    > No, it's not. You conveniently omitted the rest of the paragraph
    > 7, following the "type. 65)". Read it. The result of such conversion
    > is unspecified. That means no guarantees are given. Where you get
    > your "feeling the guarantee exists", I cannot imagine. If you find it
    > elsewhere, do post about it. Until you do, the guarantee that you
    > speak of does NOT exist, and that is expressed in the second sentence
    > of the paragraph 7 of [expr.reinterpret.cast].



    Doesn't the standard mention that all kinds of automatic storage/heap
    arrays are stored in a sequence?
    Ioannis Vranos, Jan 4, 2008
    #20
    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. Glen Low
    Replies:
    3
    Views:
    968
    Glen Low
    Jun 26, 2003
  2. Marc Schellens

    Re: valarray resize

    Marc Schellens, Jul 29, 2003, in forum: C++
    Replies:
    5
    Views:
    1,271
    Marc Schellens
    Jul 30, 2003
  3. =?ISO-8859-1?Q?Christian_Brechb=FChler?=

    Enhancing valarray with "normal" arithmetic operators

    =?ISO-8859-1?Q?Christian_Brechb=FChler?=, Sep 12, 2003, in forum: C++
    Replies:
    6
    Views:
    945
    =?ISO-8859-1?Q?Christian_Brechb=FChler?=
    Sep 14, 2003
  4. Jim West

    const and valarray reference

    Jim West, Oct 23, 2003, in forum: C++
    Replies:
    4
    Views:
    1,124
    Victor Bazarov
    Oct 24, 2003
  5. Jim West
    Replies:
    2
    Views:
    486
    Jim West
    Dec 23, 2003
Loading...

Share This Page