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

From: Michael Marcin (mmarcin_at_[hidden])
Date: 2007-10-10 16:06:40

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