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

Question

С boost doc ,

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

Думаю, используя макросы и нестандартный оператор typeof, мы можем сгенерировать точно такой же. Какая особенность 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

Повышение 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 2

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

Позвольте нам использовать простой тестовый пример (чтобы избежать беспорядка):

#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 3

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

Answer 4

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

Answer 5

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

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