dtmoore@rijnh.nl (Dave Moore) writes:

| It used to strike me as strange that valarrays have no iterators, but
| I guess that is because the standard makes some guarantees about
| aliasing (or lack of it) in valarrays.  Well, before I appreciated

Iterators destroy relationship between contained elements and their
containers. The aliasing property is easily destroyed if you pass
three iterators around instead of two valarrays.

--
                                                        Gabriel Dos Reis
                                                         gdr@cs.tamu.edu
  Texas A&M University -- Computer Science Department
 301, Bright Building -- College Station, TX 77843-3112

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

kuyper@wizard.net (James Kuyper) wrote in message news:<8b42afac.0404200832.3b9bd8d2@posting.google.com>...
> > So, my question is whether or not this program has undefined
> > behavior (nothing went obviously wrong in GCC - see above). ...

Yes .. this is what I meant in the first place .. my understanding was
not at issue I guess, only my language.

>
> Addressing your actual question: I can't quite follow your argument
> for thinking that it might have undefined behavior. What requirement
> do you think it might be violating?
>

That is kind of the problem .. I can't see anything.  However when
reading chapter 22 of TC++PL 32rd ed., I came across the following
statement in the description of std::indirect_array:

" If an index is specified twice, we have referred to an element of a
valarray twice in the same operation.  That's exactly the kind of
aliasing that valarrays do not allow, so the behavior of an
indirect_array is undefined if an index is repeated."

Furthermore, the standard says (26.3.1/2):
"The valarray array classes are defined to be free of certain forms of
aliasing, thus allowing operations on these classes to be optimized."

Not very enlightening, so I read further .. the section on assignment
operators (26.3.2.2) says:
"4 If the value of an element in the left hand side of a valarray
assignment operator depends on the value of another element in that
left hand side, the resulting behavior is undefined."

Similarly the section on computed assignment (26.3.2.6/4) says the
same thing, adding the word computed between valarray and assignment.

Finally, 26.3.2.9/2 gives the specific case for std::indirect_array.


Basically, I got worried that maybe my use of index_iterator objects
in the function whoopsie from my example was doing the same thing,
since I am using it to describe the compression of a longer valarray
into a shorter one.  On the other hand, I cannot possibly see away for
the code in that particular example to fail, even under agressive
optimization by the compiler.  (ASIDE: I tried the example at
different optimization levels, with and without strict-aliasing, and
the program always produced the same results)  However, if I was doing
assignment (the specific case covered by the standard), then certain
optimizations could perhaps cause the results to be formally
undefined. For example,

  // array1 and array2 are std::valarray<double> objects
  // index1 and index2 are std::vector<int>'s of equal length
  // and index1 contains repeated indices
  index_iterator out(index1.begin(), &array1[0]);
  index_iterator  in(index2.begin(), static_cast<const double
*>(&array2[0]));

  for ( ; in!=index2.end(); ++out, ++in)
     *out=*in;

could produce different values than expected in array1 if
loop-unrolling or order-of-evaluation optimizations are applied.

So, clearly the index_iterator I am using *can* cause trouble if used
unwisely with std::valarrays ... meaning I am "working without a net"
in some sense.  What I am more concerned about is if there are other
reasons related to aliasing why the code in my original example might
produce undefined behavior.  I can't think of any, but I certainly
don't profess to have a complete understanding of aliasing, and I
certainly don't know much about compiler design.

TIA, Dave Moore

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

It used to strike me as strange that valarrays have no iterators, but
I guess that is because the standard makes some guarantees about
aliasing (or lack of it) in valarrays.  Well, before I appreciated
this point, I wrote some code like the following (simplified to get at
the kernel of the problem):

#include <iterator>
#include <valarray>
#include <cassert>
#include <iostream>

// template to create an indexed iterator from two existing iterators:
// a random access iterator providing the data, and second iterator
// providing the indices

using std::iterator;
using std::iterator_traits;

template <class indIter, class dataIter>
class index_iterator :
 public iterator<forward_iterator_tag,
                 typename iterator_traits <dataIter>::value_type,
                 typename iterator_traits <indIter>::difference_type,
                 typename iterator_traits <dataIter>::pointer,
                 typename iterator_traits <dataIter>::reference> {

public:
  explicit index_iterator(const indIter i, dataIter d) : ind(i),
datap(d) {}

  typename index_iterator::reference operator*() {return datap[*ind];}
  typename index_iterator::pointer operator->() {return &datap[*ind];}

  bool operator==(const index_iterator& a) const {
    return ind==a.ind && datap==a.datap;
  }
  bool operator!=(const index_iterator& a) const {
    return !(this->operator==(a));
  }
  index_iterator& operator++() {
    ++ind;
    return *this;
  }
private:
  indIter ind;
  dataIter datap;
};

class my_cont : public std::valarray<double> {
public:
  my_cont(size_t s) : std::valarray<double>(s) {}
  my_cont(const std::valarray<double>& v) : std::valarray<double>(v)
{}

  typedef const int* index_t;
  typedef index_iterator< index_t, double *> index_iter;
  typedef const double * const_iterator;

  index_iter index(index_t i) {
    return index_iter(i, &(*this)[0]);
  }
  const_iterator begin() const {return &(*this)[0];}
  const_iterator   end() const {return &(*this)[this->size()];}

  // etcetera
};

void whoopsie(const my_cont &Input, my_cont &Output) {
  // this has been greatly oversimplified .. the actual code does much
  // more in-depth range checking to protect against errors
  static const int max_index=3;
  static const int index_cnt=8;

  assert(Output.size() >  max_index);
  assert( Input.size() <= index_cnt);
  int indices[] = {0,1,1,2,3,2,1,3};

  my_cont::index_iter     OI=Output.index(indices);
  my_cont::const_iterator II=Input.begin();

  for (; II!=Input.end(); ++II, ++OI)
    *OI += *II;

  // Just to be explicit, this should produce the following result ..
  // assuming Output has been initialized with zeros before the call
  // Output[0]=Input[0];
  // Output[1]=Input[1]+Input[2]+Input[6];
  // Output[2]=Input[3]+Input[5];
  // Output[3]=Input[4]+Input[7];
}

int main() {
  double init[] = {1,2,3,4,5,6,7,8};
  using namespace std;
  my_cont A=valarray<double>(0.0, 4);
  my_cont B=valarray<double>(init, 8);

  whoopsie(B, A);
  my_cont::const_iterator I=A.begin();
  for (; I!=A.end(); ++I)
    cout << *I << ", ";
  cout << endl;
  return 0;
}

compiles with no errors or warnings under GCC 3.3
executable runs producing correct output:
1, 12, 10, 13

  So, my question is whether or not this *should* produce undefined
behavior (it doesn't in GCC .. see above).  On the one hand, the
index_iterator OI in whoopsie is aliasing the elements of the
valarray<double> base object of Output, which (at least in principle)
seems to violate the standard.  For example, TC++PL section 22.4.9
indicates that the method provided in the STL for indexing
(indirect_array) has undefined behavior if an index is repeated.
However, the particular type of aliasing in my example should not
cause any problems AFAICT ... at least it is true that loop unrolling
and order of operation optimizations won't effect the result of the
code.  Also, this sort of indirection is routinely done in FORTRAN
code, where aliasing is (by definition) not possible.  What am I
missing?

  Just to provide some context, I am writing scientific code where
speed is of paramount importance ... thus I am using valarrays in the
hopes of getting some extra optimization in the compiled code.  The
my_cont class is used to store the results of relatively expensive
calculations that are tabulated at the beginning of the calculation.
Then there is a loop where these values need to be combined in a
certain, pre-known order (folding in local, dynamic data) to fill a
smaller valarray, which is the reason for the indexing array.
  Note that I do not care particularly about optimization of the
indexing operation in whoopsie (assuming it does not produce undefined
behavior) .. which I guess will not happen because of the raw pointers
used to create the iterators.  There are other places where
optimization will really be critical however.

TIA, Dave Moore

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

dtmoore@rijnh.nl (Dave Moore) writes:

> compiles with no errors or warnings under GCC 3.3
> executable runs producing correct output:
> 1, 12, 10, 13
>
>   So, my question is whether or not this *should* produce undefined
> behavior (it doesn't in GCC .. see above).

A nit: whether it produces undefined behavior depends entirely on the
standard and not at all on any particular compiler.  If the behavior
is undefined according to the standard (and I'm not saying if/whether
it is), and GCC is "behaving well", that's just the way it implements
the undefined behavior.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

dave@boost-consulting.com (David Abrahams) wrote in message news:<u7jweeng6.fsf@boost-consulting.com>...
> dtmoore@rijnh.nl (Dave Moore) writes:
>
> > compiles with no errors or warnings under GCC 3.3
> > executable runs producing correct output:
> > 1, 12, 10, 13
> >
> >   So, my question is whether or not this *should* produce undefined
> > behavior (it doesn't in GCC .. see above).
>
> A nit: whether it produces undefined behavior depends entirely on the
> standard and not at all on any particular compiler.  If the behavior
> is undefined according to the standard (and I'm not saying if/whether
> it is), and GCC is "behaving well", that's just the way it implements
> the undefined behavior.
>

Well .. my point was that, since GCC appears to give the correct
result, I remain unenlightened as to whether or not undefined behavior
is mandated by the standard.  So, if I was unclear (and I don't really
think I was), consider the parenthentical remark in my OP to be
ammended to "it doesn't necessarily in GCC ... see above".

Dave Moore

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

dtmoore@rijnh.nl (Dave Moore) wrote in message news:<306d400f.0404190013.72ddc50d@posting.google.com>...
> dave@boost-consulting.com (David Abrahams) wrote in message news:<u7jweeng6.fsf@boost-consulting.com>...
> > dtmoore@rijnh.nl (Dave Moore) writes:
> >
> > > compiles with no errors or warnings under GCC 3.3
> > > executable runs producing correct output:
> > > 1, 12, 10, 13
> > >
> > >   So, my question is whether or not this *should* produce undefined
> > > behavior (it doesn't in GCC .. see above).
> >
> > A nit: whether it produces undefined behavior depends entirely on the
> > standard and not at all on any particular compiler.  If the behavior
> > is undefined according to the standard (and I'm not saying if/whether
> > it is), and GCC is "behaving well", that's just the way it implements
> > the undefined behavior.
> >
>
> Well .. my point was that, since GCC appears to give the correct
> result, I remain unenlightened as to whether or not undefined behavior
> is mandated by the standard. ...

Those sentences reveal a world of confusion. First of all, when the
behavior is undefined, there's no such thing as an incorrect result -
every possible result is a correct one. Therefore, the fact that GCC
gives you a correct result tells you nothing about whether or not the
result you got is an example of undefined behavior. You would remain
equally unenlightened if GCC produced the result "This program has
undefined behavior!" - since GCC might be mistaken.

Secondly, it's meaningless to talk about undefined behavior being
mandated. When the behavior of a program is undefined, what that means
is that the standard mandates nothing. "mandating undefined behavior"
is as meaningless a phrase as "shining darkness" or "filling a box
with vaccuum" or "legislating anarchy", and for much the same reasons.

I think that you have the misconception that "undefined behavior"
means that some particular thing or things is supposed to happen. What
it actually means is that anything could happen - including precisely
what you expected to happen.

> ... So, if I was unclear (and I don't really
> think I was), consider the parenthentical remark in my OP to be
> ammended to "it doesn't necessarily in GCC ... see above".

That doesn't fix the problem. It implies that the behavior ceases to
be undefined just because GCC produced the result you expected.

However, you were really asking about valarrays - your confusion about
the meaning of undefined behavior is just a side issue. Your original
question needs just a minor fix:

Replace:
>  So, my question is whether or not this *should* produce undefined
> behavior (it doesn't in GCC .. see above).  ...

with:

> So, my question is whether or not this program has undefined
> behavior (nothing went obviously wrong in GCC - see above). ...

Addressing your actual question: I can't quite follow your argument
for thinking that it might have undefined behavior. What requirement
do you think it might be violating?

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]