Re: [Boost-users] Container iteration macro that is equivalent tohandcoded iteration?

From: John Femiani (JOHN.FEMIANI_at_[hidden])
Date: 2007-10-10 18:15:46

> -----Original Message-----
> From: boost-users-bounces_at_[hidden] [mailto:boost-users-
> bounces_at_[hidden]] On Behalf Of Michael Marcin
> Sent: Wednesday, October 10, 2007 1:07 PM
> To: boost-users_at_[hidden]
> Subject: Re: [Boost-users] Container iteration macro that is
equivalent
> tohandcoded iteration?
> 
> Erik wrote:
> > I have a lot of handcoded loops that look something like this:
> >
>
////////////////////////////////////////////////////////////////////////
//
> ////
> > #include <vector>
> >
> > void f(float);
> > void g(std::vector<float> const & v) {
> >     std::vector<float>::const_iterator const v_end = v.end();
> >     for (std::vector<float>::const_iterator it = v.begin(); it !=
v_end;
> ++it)
> >         f(*it);
> > }
> >
>
////////////////////////////////////////////////////////////////////////
//
> ////
> >
> > I need to replace it with something equivalent but simpler. I tried
> > BOOST_FOREACH (from boost-1.34):
> >
>
////////////////////////////////////////////////////////////////////////
//
> ////
> > #include <boost/foreach.hpp>
> >
> > #include <vector>
> >
> > void f(float);
> > void g(std::vector<float> const & v) {
> >    BOOST_FOREACH(float i, v)
> >       f(i);
> > }
> >
>
////////////////////////////////////////////////////////////////////////
//
> ////
> >
> > But when I compared the assembly output of this with that of the
> > handcoded version I discovered that the boost version is more
> > complicated, so I tried to create something better myself, with the
> > requirement that the generated code is not allowed to be any more
> > complicated than that of the handcoded loop. The following is the
best I
> > could think of right now:
> >
>
////////////////////////////////////////////////////////////////////////
//
> ////
> > #define iterate_vector_const(value_type, it, v)
\
> >    for
\
> >       (struct {
\
> >           std::vector<value_type>::const_iterator       current;
\
> >           std::vector<value_type>::const_iterator const end;
\
> >           value_type const & operator*() {return *current;}
\
> >        } it = {v.begin(), v.end()};
\
> >        it.current != it.end;
\
> >        ++it.current)
\
> >
> > #include <vector>
> >
> > void f(float);
> > void g(std::vector<float> const & v) {
> >    iterate_vector_const(float, it, v)
> >       f(*it);
> > }
> >
>
////////////////////////////////////////////////////////////////////////
//
> ////
> >
> > I looked at the difference between my macro and the handcoded loop:
> > $ diff -U2 iteration-handcoded-g++-4.2.0-O3.S
iteration-iterate_vector-
> g++-4.2.0-O3.S
> > --- iteration-handcoded-g++-4.2.0-O3.S  2007-10-07
19:38:56.000000000
> +0200
> > +++ iteration-iterate_vector-g++-4.2.0-O3.S     2007-10-07
> > 20:00:53.000000000 +0200
> > @@ -1,3 +1,3 @@
> > -       .file   "iteration-handcoded.cc"
> > +       .file   "iteration-iterate_vector.cc"
> >         .text
> >         .align 2
> > @@ -18,7 +18,7 @@
> >  .LCFI4:
> >         movl    8(%ebp), %eax
> > -       movl    4(%eax), %esi
> >         movl    (%eax), %ebx
> > -       cmpl    %ebx, %esi
> > +       movl    4(%eax), %esi
> > +       cmpl    %esi, %ebx
> >         je      .L4
> >         .p2align 4,,7
> >
> >>From this I conclude that my macro is as good as a handcoded loop.
> > (Although I of course wonder why the compiler chose to move "movl
> > 4(%eax), %esi" further down and swap the parameters of cmpl from
"%ebx,
> > %esi" to "%esi, %ebx".)
> >
> > But my macro is not as versatile as BOOST_FOREACH. Is there any way
to
> > improve it? In particular, is it possible get rid of the macro
parameter
> > value_type? Is it possible to make it work with other containers
than
> > vectors, as long as they define const_iterator/iterator, begin, end
and
> > value_type? Something like this maybe:
> >
>
////////////////////////////////////////////////////////////////////////
//
> ////
> > #define iterate_container_const(it, v)
\
> >    for
\
> >       (struct {
\
> >           typeof(v)::const_iterator       current;
\
> >           typeof(v)::const_iterator const end;
\
> >           typeof(v)::value_type const & operator*() {return
*current;} \
> >        } it = {v.begin(), v.end()};
\
> >        it.current != it.v_end;
\
> >        ++it.current)
\
> >
> > #include <vector>
> >
> > void f(float);
> > void g(std::vector<float> const & v, std::list<float> const & l) {
> >    iterate_containter_const(it, v)
> >       f(*it);
> >    iterate_containter_const(it, l)
> >       f(*it);
> > }
> >
>
////////////////////////////////////////////////////////////////////////
//
> ////
> >
> > Or is it possible to configure BOOST_FOREACH to be as efficient as
my
> macro?
> 
> I don't know but that is a good question.
> 
> I considered using BOOST_FOREACH until I checked its generated
output...
> which was worse than std::for_each with a boost::bind which was worse
> than std::for_each with a hand coded functor which was worse than a
hand
> coded for loop like yours above.
> 
> - Michael Marcin
> 
> p.s. Compilers make me sad
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users

I think you will need to pass SOME type unless you are comfortable with
BOOST_AUTO or BOOST_TYPEOF. I think the problem is on some compilers
they require each type to be 'registered'.

Maybe if you use a NEXT macro as well things will work out, because you
can put multiple braces in the next macro.

#define FOREACH(X, COL, COLT) \
{ \
    COLT& __col__ = (COL); \
    for (iterator_type<COLT>::type __i__ = begin(__col__); \
          __i__ != end(__col__);\
          ++__i__) \
    { \
        X = *__i__; \
        { 

#define NEXT() \
        }\
    }\
}

I haven't tried this, but it seems like one could do:

#define FOREACH(X, COL) \
{ \
    BOOST_TYPEOF(COL)& __col__ = (COL); \
    BOOST_AUTO(__cur__, boost::begin(__col__));    
    BOOST_AUTO(__end__, boost::end(__col__));
    for (; __cur__ != __end__; ++__cur__) \
    { \
        X = *__cur__; \
        { 

#define NEXT() \
        }\
    }\
}

Then you could use it like:

vector<int> vec;

FOREACH(int x, vec){

   //do something with x

}NEXT();

Or if BOOST_AUTO doesn't work it is

vector<int> vec; //vector<int> does not have a comma in the type name!

FOREACH(int x, vec, vector<int>) {

   //do something with x

}NEXT();

I have no idea how well BOOST_AUTO will work though. You would also need
a TPL version I think.

IN my own code I have a special concern because I deal with half_edge
structures where begin()==end() and I need to do a bottom testing loop.
In these cases I made iteration macros for each container: I.e.

MY_FOREACH_VERTEX_EDGE(e, vertex){
   //e is an edge iterator
}MY_NEXT_VERTEX_EDGE()

I found that to be readable. I did not use BGL stuff because I did not
know how to deal with begin() == end().

-- John