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

10 Oct 2007

...
-----Original Message-----
From: John Femiani
Sent: Wednesday, October 10, 2007 3:16 PM
To: 'boost-users@lists.boost.org'
Subject: RE: [Boost-users] Container iteration macro that is
equivalent
tohandcoded iteration?
...
-----Original Message-----
From: boost-users-bounces@lists.boost.org [mailto:boost-users-
bounces@lists.boost.org] On Behalf Of Michael Marcin
Sent: Wednesday, October 10, 2007 1:07 PM
To: boost-users@lists.boost.org
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 
#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::const_iterator       current;
\
          std::vector::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
...
$ 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
loop:
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@lists.boost.org
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

    