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

Question

От повышения док,

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

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

Редактировать:

Моя версия:

    #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) свойствами ваших итераторов и диапазонов. Так что вы, вероятно, можете сделать лучше.

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