Почему BOOST_FOREACH не совсем эквивалентен ручному кодированию?

Question

От boost doc,

Это приводит к почти оптимальной генерации кода; производительность BOOST_FOREACH обычно находится в пределах нескольких процентов от эквивалентного закодированного цикла .

Я предполагаю, что используя макросы и нестандартный оператор типа, мы можем генерировать точно эквивалентную. Какая особенность BOOST_FOREACH делает это не точным?

Edit:

Моя версия:

#define EACH(it,v) \ 
     for(typeof(v.begin()) it = v.begin();it != v.end(); ++it) 

//use this if you want a const_iterator from a non-const container 

    #define CONST_EACH(it,v) \ 
     typedef typeof(v) v_type; \ 
     typedef const v_type& const_type; \ 
     for(typeof(static_cast<const_type>(v).begin()) it = static_cast<const_type>(v).begin(); it != static_cast<const_type>(v).end(); ++it) 

Я пытаюсь написать версию без каких-либо накладных расходов. Это использует нестандартный typeof и дает итератору вместо value_type. Я что-то пропустил?

Answer 1

Я считаю, что некоторые из хитростей, которые BOOST_FOREACH использует для поддержки естественного синтаксиса цикла, могут генерировать лишние копии объектов.

Answer 2

Boost foreach далеко не тривиальный. с GCC 4.6:

int main() 
{ 
    std::string hello("Hello, world!"); 
    BOOST_FOREACH(char ch, hello) 
    { 
     std::cout << ch; 
    } 
    return 0; 
} 

создает много случаев зондировали с A?B:C.

int main() 
{ 
    std::string hello("Hello, world!"); 

    if (
boost::foreach_detail_::auto_any_t _foreach_col9 = 
boost::foreach_detail_::contain((hello) , (true ? 0 : 
boost::foreach_detail_::or_( 
boost::foreach_detail_::and_( 
boost::foreach_detail_::not_(
boost::foreach_detail_::is_array_(hello)) , (true ? 0 : 
boost::foreach_detail_::is_rvalue_((true ? 
boost::foreach_detail_::make_probe(hello) : (hello)), 0))) , 
boost::foreach_detail_::and_( 
boost::foreach_detail_::not_(boost_foreach_is_noncopyable( 
boost::foreach_detail_::to_ptr(hello) , boost_foreach_argument_dependent_lookup_hack_value)) , boost_foreach_is_lightweight_proxy( 
boost::foreach_detail_::to_ptr(hello) , boost_foreach_argument_dependent_lookup_hack_value)))))) {} else if (
boost::foreach_detail_::auto_any_t _foreach_cur9 = 
boost::foreach_detail_::begin(_foreach_col9 , (true ? 0 : 
boost::foreach_detail_::encode_type(hello, 
boost::foreach_detail_::is_const_(hello))) , (true ? 0 : 
boost::foreach_detail_::or_( 
boost::foreach_detail_::and_( 
boost::foreach_detail_::not_(
boost::foreach_detail_::is_array_(hello)) , (true ? 0 : 
boost::foreach_detail_::is_rvalue_((true ? 
boost::foreach_detail_::make_probe(hello) : (hello)), 0))) , 
boost::foreach_detail_::and_( 
boost::foreach_detail_::not_(boost_foreach_is_noncopyable( 
boost::foreach_detail_::to_ptr(hello) , boost_foreach_argument_dependent_lookup_hack_value)) , boost_foreach_is_lightweight_proxy( 
boost::foreach_detail_::to_ptr(hello) , boost_foreach_argument_dependent_lookup_hack_value)))))) {} else if (
boost::foreach_detail_::auto_any_t _foreach_end9 = 
boost::foreach_detail_::end(_foreach_col9 , (true ? 0 : 
boost::foreach_detail_::encode_type(hello, 
boost::foreach_detail_::is_const_(hello))) , (true ? 0 : 
boost::foreach_detail_::or_( 
boost::foreach_detail_::and_( 
boost::foreach_detail_::not_(
boost::foreach_detail_::is_array_(hello)) , (true ? 0 : 
boost::foreach_detail_::is_rvalue_((true ? 
boost::foreach_detail_::make_probe(hello) : (hello)), 0))) , 
boost::foreach_detail_::and_( 
boost::foreach_detail_::not_(boost_foreach_is_noncopyable( 
boost::foreach_detail_::to_ptr(hello) , boost_foreach_argument_dependent_lookup_hack_value)) , boost_foreach_is_lightweight_proxy( 
boost::foreach_detail_::to_ptr(hello) , boost_foreach_argument_dependent_lookup_hack_value)))))) {} else for (bool _foreach_continue9 = true; _foreach_continue9 && ! 
boost::foreach_detail_::done(_foreach_cur9 , _foreach_end9 , (true ? 0 : 
boost::foreach_detail_::encode_type(hello, 
boost::foreach_detail_::is_const_(hello)))); _foreach_continue9 ? 
boost::foreach_detail_::next(_foreach_cur9 , (true ? 0 : 
boost::foreach_detail_::encode_type(hello, 
boost::foreach_detail_::is_const_(hello)))) : (void)0) if (
boost::foreach_detail_::set_false(_foreach_continue9)) {} else for (char ch = 
boost::foreach_detail_::deref(_foreach_cur9 , (true ? 0 : 
boost::foreach_detail_::encode_type(hello, 
boost::foreach_detail_::is_const_(hello)))); !_foreach_continue9; _foreach_continue9 = true) 
    { 
     std::cout << ch; 
    } 

    return 0; 
} 

Есть так много возможных типов вещей, которые вы, возможно, захотите перевернуть. В C++ 11 все эти фокусы больше не требуется, так как вы можете петлю над почти все с

for(auto const &a: something){ .. } 

или

for(auto a=begin(something);a!=end(something);++i){ .. } 

Answer 3

Если вы вручную код вашей петли, вы можете воспользоваться известно вы (но не обязательно компилятор или boost_foreach) свойства ваших итераторов и диапазонов. Таким образом, вы, вероятно, можете сделать лучше.

Он также в значительной степени зависит от возможности обнаружения определенных свойств классов во время компиляции, и если он не может (то есть, компилятор не может поддерживать используемые им механизмы шаблонов), он должен отложить это до времени выполнения. Это, очевидно, не так эффективно, как результаты, которые вы получите с помощью ручного кодирования (где вы, скорее всего, просто знаете).

Answer 4

Почему бы не спросить ваш любимый компилятор?

Давайте использовать простой тестовый случай (чтобы избежать помех):

#include <cstring> 
#include <cstdio> 

#include <boost/foreach.hpp> 

char const* HelloWorld = "Hello, world!\n"; 

void simplefor() { 
    for(char const* it = HelloWorld, *end = HelloWorld + strlen(HelloWorld); 
     it != end; 
     ++it) 
    { 
    printf("%c", *it); 
    } 
} 

void foreach() { 
    BOOST_FOREACH(char ch, HelloWorld) 
    { 
    printf("%c", ch); 
    } 
} 

С помощью этих команд мы извлекаем LLVM IR:

~/projects$ clang++ -O2 -c -I/usr/lib/Boost/1-39-0-1/include/ test.cpp -emit-llvm 
~/projects$ llvm-dis test.o -show-annotations 

что дает для простой:

define void @_Z9simpleforv() nounwind uwtable { 
    %1 = load i8** @HelloWorld, align 8, !tbaa !0 ; [#uses=3 type=i8*] 
    %2 = tail call i64 @strlen(i8* %1) nounwind readonly ; [#uses=2 type=i64] 
    %3 = getelementptr inbounds i8* %1, i64 %2  ; [#uses=1 type=i8*] 
    %4 = icmp eq i64 %2, 0       ; [#uses=1 type=i1] 
    br i1 %4, label %._crit_edge, label %.lr.ph 

.lr.ph:           ; preds = %.lr.ph, %0 
    %it.01 = phi i8* [ %7, %.lr.ph ], [ %1, %0 ] ; [#uses=2 type=i8*] 
    %5 = load i8* %it.01, align 1, !tbaa !1   ; [#uses=1 type=i8] 
    %6 = sext i8 %5 to i32       ; [#uses=1 type=i32] 
    %putchar = tail call i32 @putchar(i32 %6) nounwind ; [#uses=0 type=i32] 
    %7 = getelementptr inbounds i8* %it.01, i64 1 ; [#uses=2 type=i8*] 
    %8 = icmp eq i8* %7, %3       ; [#uses=1 type=i1] 
    br i1 %8, label %._crit_edge, label %.lr.ph 

._crit_edge:          ; preds = %.lr.ph, %0 
    ret void 
} 

и за BOOST_FOREACH:

; [#uses=0] 
define void @_Z7foreachv() nounwind uwtable { 
    %1 = load i8** @HelloWorld, align 8, !tbaa !0 ; [#uses=1 type=i8*] 
    br label %2 

; <label>:2          ; preds = %.preheader, %0 
    %.in = phi i8* [ %6, %.preheader ], [ %1, %0 ] ; [#uses=2 type=i8*] 
    %3 = load i8* %.in, align 1, !tbaa !1   ; [#uses=2 type=i8] 
    %4 = icmp eq i8 %3, 0       ; [#uses=1 type=i1] 
    br i1 %4, label %.critedge, label %.preheader 

.preheader:          ; preds = %2 
    %5 = sext i8 %3 to i32       ; [#uses=1 type=i32] 
    %putchar = tail call i32 @putchar(i32 %5) nounwind ; [#uses=0 type=i32] 
    %6 = getelementptr inbounds i8* %.in, i64 1  ; [#uses=1 type=i8*] 
    br label %2 

.critedge:          ; preds = %2 
    ret void 
} 

Я могу сказать, что для простого случая есть больше инструкций, но меньше ветвей (по одной на итерацию вместо двух), но мне трудно было бы прикрепить производительность оттуда.

Но, конечно ... это уже не имеет значения! Радуйся C++ 11:

void bestfor() { 
    for(char const ch: HelloWorld) { 
    printf("%c", ch); 
    } 
} 

Answer 5

Я думаю, что это в основном из-за ступенчатости: при использовании (константные) ссылки, компилятор имеет больше времени на выяснение того, что некоторые переменные не псевдоним, и генерирует меньше оптимальный код.