-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Eric Niebler Sent: Wednesday, October 10, 2007 3:04 PM To: boost-users@lists.boost.org Subject: Re: [Boost-users] Container iteration macro that is equivalent tohandcoded iteration?

Michael Marcin wrote:

...

Erik wrote:

...

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.

I won't deny that the abstraction penalty of BOOST_FOREACH is not zero, but have either of you actually measured the overhead? I have, and I found BOOST_FOREACH to be about 5% slower than the equivalent hand-coded loop when compiler optimizations are turned on. It's really very small, and that 5% buys you a lot of expressivity. YMMV.

-- Eric Niebler Boost Consulting www.boost-consulting.com _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Where does the 5% come from? Which part of BOOST_FOREACH (which is way to advanced for me to understand) is the part that causes the most trouble with compilers? Is it the extra if statement trick that seems to be used to initialize the variable? -- John

Michael Marcin wrote:

...

Erik wrote:

...

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.

I won't deny that the abstraction penalty of BOOST_FOREACH is not zero, but have either of you actually measured the overhead? I have, and I found BOOST_FOREACH to be about 5% slower than the equivalent hand-coded loop when compiler optimizations are turned on. It's really very small, and that 5% buys you a lot of expressivity. YMMV I have not made any timings, but looked at the number of instructions in

Eric Niebler skrev: the assembly. I assume this corresponds to code size. The good news is that with g++-4.2.0 -O3 there appears to be no abstraction penalty at all. BOOST_FOREACH is equivalent to the handcoded loop and my macro. They both have 21 instructions (which appear to be equivalent; some of them are reordered and some have their parameters swapped). But with -Os it is possible to get only 20 instructions with handcoded/my macro, while BOOST_FOREACH actually gives 57 instructions (-Os giving more instructions than -O3 for ANY code looks like a compiler bug to me). And then I tried -O2 of course. handcoded/my macro yield 21 instructions while BOOST_FOREACH yields 31. With g++-4.1.2 handcoded/my macro gives the same result as with g++-4.2.0. But with BOOST_FOREACH it is another story. At -O3 BOOST_FOREACH yields as much as 28 instructions, at -O2 35 instructions and at -Os 90 instructions. So I suppose that as long as everyone uses g++-4.2.0 (or higher I i suppose but did not test) and -O3 it should be fine to use BOOST_FOREACH. Those who rely on getting small code with -Os can forget about using BOOST_FOREACH with any of those compiler versions. So it seems like the gcc people did a quite good job of optimizing this very complex hack. I suppose I will suggest that we start using BOOST_FOREACH in our project. We already use -O3 for release builds and in a few months (or maybe a year) almost everyone will have at least gcc-4.2.0. But it would be interesting if others could verify my measurements and maybe test other examples of code. I did some tests and got the exact same results for the following use of BOOST_FOREACH (and the corresponding use of my macro and a handcoded loop): ////////////////////////////////////////////////////// #include #include <vector> void f(float); struct A { void g() const; std::vector<float> const v; }; void A::g() const { BOOST_FOREACH(float i, v) f(i); } //////////////////////////////////////////////////////

I did some tests and got the exact same results for the following use of BOOST_FOREACH (and the corresponding use of my macro and a handcoded loop): ////////////////////////////////////////////////////// #include

#include <vector>

void f(float); struct A { void g() const; std::vector<float> const v; };

void A::g() const { BOOST_FOREACH(float i, v) f(i); } ///////////////////////////////////////////////////// Of course I got the exact same results with this code, because v is the first member of A, so A::v has the same address as A. When I realized

Erik skrev: this I modified the testcase: ////////////////////////////////////////////////////// #include #include <vector> void f(float); struct A { void g() const; char name[52]; std::vector<float> const v; }; void A::g() const { BOOST_FOREACH(float i, v) f(i); } ////////////////////////////////////////////////////// Unfortunately it does not look so good for BOOST_FOREACH after this modification. It will increase to 24 instructions, while the handcoded is still only 21. I created a script (attached) to test the examples systematically with different compiler versions and optimization levels. Here are the results that it gave me: Optimizations: O3 O2 Os handcoded: parameter: g++-4.2.0: 21 21 20 g++-4.1.2: 21 21 20 member: g++-4.2.0: 21 21 20 g++-4.1.2: 21 21 20 member_with_local: g++-4.2.0: 21 21 20 g++-4.1.2: 21 21 20 iterate_vector: parameter: g++-4.2.0: 21 21 20 g++-4.1.2: 21 21 20 member: g++-4.2.0: 21 21 20 g++-4.1.2: 21 21 20 member_with_local: g++-4.2.0: 21 21 20 g++-4.1.2: 21 21 20 BOOST_FOREACH: parameter: g++-4.2.0: 21 31 57 g++-4.1.2: 28 35 90 member: g++-4.2.0: 24 32 58 g++-4.1.2: 29 36 91 member_with_local: g++-4.2.0: 24 32 58 g++-4.1.2: 29 36 91 If you want to try it yourself, put the script in an empty directory and run from there; it will create some files. After running it, it may be interesting to compare the generated code, for example: diff -dU2 iterate_vector-member-g++-4.2.0-O3.s BOOST_FOREACH-member-g++-4.2.0-O3.s|kompare - #! /bin/sh ITERATIONS="0 1 2" ITERATION_NAMES=(handcoded iterate_vector BOOST_FOREACH) ITERATION_CODES=(\ " 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);" \ " #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) \\ iterate_vector_const(float, it, v) f(*it);" \ " BOOST_FOREACH(float i, v) f(i);") EXAMPLES="0 1 2" EXAMPLE_NAMES=(parameter member member_with_local) EXAMPLE_CODES=(\ " void g(const std::vector<float> & v) {" \ " struct A { void g() const; char name[52]; std::vector<float> const v; }; void A::g() const {" \ " struct A { void g() const; char name[52]; std::vector<float> const m_v; }; void A::g() const { std::vector<float> const & v = m_v; ") COMPILER_VERSIONS="4.2.0 4.1.2" OPTIMIZATOINS="3 2 s" unset TABLE_HEADER for optimization in $OPTIMIZATOINS; do TABLE_HEADER="$TABLE_HEADER O$optimization" done echo "Optimizations: $TABLE_HEADER" for iteration in $ITERATIONS; do echo ${ITERATION_NAMES[$iteration]}: for example in $EXAMPLES; do NAME=${ITERATION_NAMES[$iteration]}-${EXAMPLE_NAMES[$example]} IN=$NAME.cc rm -f $IN echo "void f(float);" >> $IN echo "#include " >> $IN echo "#include <vector>" >> $IN echo "${EXAMPLE_CODES[$example]}" >> $IN echo "${ITERATION_CODES[$iteration]}" >> $IN echo "}" >> $IN echo " ${EXAMPLE_NAMES[$example]}:" for compiler_version in $COMPILER_VERSIONS; do MESSAGE=g++-$compiler_version: for optimization in $OPTIMIZATOINS; do OUT=$NAME-g++-$compiler_version-O$optimization.s g++-$compiler_version -Wall -Wextra -O$optimization -S $IN -o $OUT MESSAGE="$MESSAGE $(egrep -v "^([ ]*\\.|_)" $OUT|wc -l)" done echo " $MESSAGE" done done done

On 10/11/07, Andrew Holden wrote:

[snip]

Do you have access to a profiler? They often surprise me when I look at a report showing what parts of my program are actually using the most processor time (or wall clock time, if that is more important to you).

Profiling is the only way to optimize. Anything else is just wizardry. Regards, -- Felipe Magno de Almeida

Erik wrote:

Andrew Holden skrev:

...

Erik wrote:

...

Unfortunately it does not look so good for BOOST_FOREACH after this modification. It will increase to 24 instructions, while the handcoded is still only 21.

Forgive me if this was answered in an earlier post, but how complex is the loop body, including the complexity of any functions it calls?

The answer is available by executing the test script in my previous post and then running the diff command that I showed in that post: The size of the loop body increases from 6 to 7 instructions and the code before the loop increases with 2 instructions.

No, that's not what Andrew asked. He was asking: in a *real* loop in your real application, wouldn't the work being done by the loop completely dwarf the loop-control overhead? In production code, how many loops do we write with such trivial bodies that the loop-control overhead makes a measurable difference?

Erik wrote:

...

Erik wrote:

...

Unfortunately it does not look so good for BOOST_FOREACH after this modification. It will increase to 24 instructions, while the handcoded is still only 21. I created a script (attached) to test the examples systematically with different compiler versions and optimization levels.

Forgive me if this was answered in an earlier post, The answer is available by executing the test script in my

Andrew Holden skrev: previous post and then running the diff command that I showed in that post: diff -dU2 iterate_vector-member-g++-4.2.0-O3.s BOOST_FOREACH-member-g++-4.2.0-O3.s|kompare -

...

but how complex is the loop body, including the complexity of any functions it calls? The size of the loop body increases from 6 to 7 instructions and the code before the loop increases with 2 instructions.

Okay. I see that the loop body contains a call to a function "f", which is not defined. Here is the code from one of the tests: //Begin BOOST_FOREACH-parameter.cc void f(float); #include #include <vector> void g(const std::vector<float> & v) { BOOST_FOREACH(float i, v) f(i); } //End BOOST_FOREACH-parameter.cc We would need to know the contents of f before we can really discuss the consequences of the extra instructions in BOOST_FOREACH. Even if f is a stub, it will still have compiler-generated prolog and epilog code, which will diminish the importance of the extra instructions you found. If f is sufficiently complex, then using BOOST_FOREACH instead of a handcrafted loop may add less than a second to a multi-hour run. It would also be useful to know the size of the vector. As the vector grows, the extra instructions outside the loop rapidly diminish in importance. I would strongly recommend getting a copy of Valgrind (or another suitable profiler for your platform) and doing some profiling runs with various combinations of "f" implementations and vector sizes. If nothing else, you can use the "time" program to measure how long your test programs run. I suspect you will find that the performance penalty for BOOST_FOREACH to be minimal, perhaps even swamped by experimental error in some tests. After that, determine for yourself if the improved expressiveness from BOOST_FOREACH is worth the (probably small) price in performance.

No we do not. The compiler does not need to know the contents of f to generate that code. Neither do we need to know the contents of f to discuss the code that the compiler generates in this case. I deliberately left f undefined so that loop efficiency can be studied in isolation.

If you don't write something the compiler could inline,I wouldn't worry about things that are on the order of a subroutine call. If you put something specific there, then the compiler has lots of options. Again, for very simple things you could inline yourself, for more complicated things, in almost every case I've written, memory access patterns dominate performance. A few cache misses can kill you. Intel had some good references, you can skim their site for recent stuff: http://www.google.com/search?hl=en&q=ia32+performance+optimization+site%3Aintel.com Anyone have a recent Intel compiler? I know in one case I had some hand written SSE code with real clever register usage specialized for a certain wavelet transform. As I recall, the naively written general c++ code executed in about the same time- I don't remember specifically why, but most of the Vtune results, IIRC, pointed to memory limits and not instruction count.

From: Erik Reply-To: boost-users@lists.boost.org To: boost-users@lists.boost.org Subject: Re: [Boost-users] Container iteration macro that is equivalent to handcoded iteration? Date: Fri, 12 Oct 2007 01:10:07 +0200

_________________________________________________________________ Make every IM count. Download Messenger and join the i’m Initiative now. It’s free. http://im.live.com/messenger/im/home/?source=TAGHM