Hi Everybody,

there's a thread running on comp.lang.c++.moderated about STL algorithms
where someone used IMHO incorrectly std::accumulate and std::transform.
While looking for evidence supporting my statements, I found that the
requirements on binary_op for both std::accumulate and std::transform
have been radically changed in the current draft. The current standard says:

  std::accumulate: binary_op shall not cause side effects.

  std::transform: binary_op shall not have any side effects.

These, in particular, disallow binary_op to have a state. However, the
usage of the term side effect has been removed from the current draft,
which says, instead:

  std::accumulate: In the range [first,last], binary_op shall neither
modify elements nor invalidate iterators or subranges.

  std::transform: binary_op shall not invalidate iterators or subranges,
or modify elements in the ranges [first1 ,last1 ], [first2 ,first2 +
(last1 - first1 )], and [result ,result + (last1 - first1 )].

Notice that this new wording allows binary_op to keep a state. I
remember I read somewhere that one of the original intents of
disallowing side effects was to allow possible parallel implementations
of the algorithms and/or optimizations involving reordering. In the case
of std::accumulate there is probably no actual gain from such kind of
optimizations, because each step needs the result of the previous step
anyway, but std::transform might benefit from that.

However, with the new wording, any such optimization is impossible. For
example, in the cited thread, someone used std::transform with a
binary_op that kept the number of times the operator has been invoked
and used it to compute the result. Such an operator would violate the
requirements in the current standard but not those in the draft. Such
operator can work correctly only if the transform operation is performed
in the correct order.

If parallelism/reordering is being ruled out, then why not going further
and specify that the operation must be performed in the right order?
There is already a precedent for that, namely std::for_each, so why not
std::transform?

Am I missing something?

Regards,

Ganesh

---
[ 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.comeaucomputing.com/csc/faq.html                      ]

On Wed, 20 Sep 2006 23:05:20 GMT, AlbertoBarbati@libero.it (Alberto
Ganesh Barbati) wrote:

>Hi Everybody,
>
>there's a thread running on comp.lang.c++.moderated about STL algorithms
>where someone used IMHO incorrectly std::accumulate and std::transform.

To add another remark about std::accumulate where it probably will get
more attention than in a separate thread: any reason why it is
specified in terms of + instead of +=?

--
Gennaro Prota

---
[ 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.comeaucomputing.com/csc/faq.html                      ]

Alberto Ganesh Barbati wrote:

> there's a thread running on comp.lang.c++.moderated about STL
> algorithms where someone used IMHO incorrectly std::accumulate
> and std::transform.  While looking for evidence supporting my
> statements, I found that the requirements on binary_op for
> both std::accumulate and std::transform have been radically
> changed in the current draft. The current standard says:

>   std::accumulate: binary_op shall not cause side effects.

>   std::transform: binary_op shall not have any side effects.

> These, in particular, disallow binary_op to have a state.

You mean mutable state, of course.

> However, the usage of the term side effect has been removed
> from the current draft, which says, instead:

>   std::accumulate: In the range [first,last], binary_op shall neither
> modify elements nor invalidate iterators or subranges.

>   std::transform: binary_op shall not invalidate iterators or subranges,
> or modify elements in the ranges [first1 ,last1 ], [first2 ,first2 +
> (last1 - first1 )], and [result ,result + (last1 - first1 )].

> Notice that this new wording allows binary_op to keep a state.
> I remember I read somewhere that one of the original intents
> of disallowing side effects was to allow possible parallel
> implementations of the algorithms and/or optimizations
> involving reordering. In the case of std::accumulate there is
> probably no actual gain from such kind of optimizations,
> because each step needs the result of the previous step
> anyway, but std::transform might benefit from that.

It's forbidden, and always has been, in the case of
std::accumulate, and always has been, since the "effects" state
that the traversal will be in order.

> However, with the new wording, any such optimization is
> impossible. For example, in the cited thread, someone used
> std::transform with a binary_op that kept the number of times
> the operator has been invoked and used it to compute the
> result.

Where does it say that traversal will be in order for transform?
If your code counts on in-order traversal, it has undefined
behavior unless the standard guarantees in order traversal.  (In
the case of an instantiation using an input iterator, this is
perhaps an open question, since input iterators don't really
allow any other kind of traversal.)

There is another problem involving state, however: none of the
algorithms concerned make any guarantees concerning when and how
often the binary_op will be copied.  Presumably, an
implementation which copies it new directly from the argument
each time, and uses the copy, is also legal.  In which case,
mutable state can only be used through indirection.  (I had
wondered in the past whether this wasn't an oversight,
particularly with regards to the functional object in for_each,
but the note in    25/9 of the current draft makes it clear that
this is intentional.)

> Such an operator would violate the requirements in the current
> standard but not those in the draft. Such operator can work
> correctly only if the transform operation is performed in the
> correct order.

If an operator violates the requirements of the standard, you
have undefined behavior.  In order to give a correct result, it
must not only not violate the requirements of the standard, it
must not depend on guarantees not given in the standard.  In the
case of transform, for example, it must not depend on an in
order traversal.  Doing so does not cause undefined behavior,
but it does mean that the result is not specified.

> If parallelism/reordering is being ruled out, then why not
> going further and specify that the operation must be performed
> in the right order?  There is already a precedent for that,
> namely std::for_each, so why not std::transform?

Probably because it isn't considered important for transform.
The "normal" use of the algorithm should not depend on an in
order traversal, and IMHO it is preferable to allow potential
optimizations of the normal use, rather than ban them because of
some rare or exotic uses.

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ 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.comeaucomputing.com/csc/faq.html                      ]

"kanze" <kanze@gabi-soft.fr> wrote in message
news:1158833677.289931.105020@e3g2000cwe.googlegroups.com...

>
> There is another problem involving state, however: none of the
> algorithms concerned make any guarantees concerning when and how
> often the binary_op will be copied.  Presumably, an

You can use an object which is essentially a proxy to a shared state so the
copies all reference the same state. However you captured the essence of the
issue when you mentioned order traversal. This is the trap that Herb Sutter
set and which I fell into quite publically a long time ago in one of his
GotW's (which I now call gotcha's!).

Regards, John.


---
[ 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.comeaucomputing.com/csc/faq.html                      ]