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

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

> -----Original Message-----
> From: John Femiani
> Sent: Wednesday, October 10, 2007 3:16 PM
> To: 'boost-users_at_[hidden]'
> Subject: RE: [Boost-users] Container iteration macro that is
equivalent
> tohandcoded iteration?
> 
> 
> > -----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

That is, unless you can understand the magic that makes BOOST_FOREACH
work. :)

-- John