Blitz++, G++ и operator() - C/C++

Вопрос свой адресую, даже не к знатокам библиотеки Blitz++, и даже не к
знатокам С++, а скорее к специалистам по компиляторам, а конкретно по g++.
Понадобился мне недавно контейнер для работы с одно и двумерными массивами
нулей и единиц, а если проще то с битовым потоком одной системы связи.
Требования были примерно такие:

Естественно выбор пал на Blitz++, который удовлетворял, казалось (в соответствии
с документацией и интернет публикациями), всем требованиям. И все действительно
было здорово, пока на нем не была реализована одна из частей проекта (декодер
Витерби, если кому интересно). А точнее, пока этот декодер небыл протестирован на
производительность под двумя ОС, Linux и Windows, с компиляторами g++ 4.3.3 и
Visual C++ 2008 соответственно. Версия собранная под Linux показала более чем
шести кратный поригрыш, по сравнению с тем же самым кодом собранным под Windows
(естественно на том же самом компьютере). В обоих случаях использовались
одинаковые режимы оптимизации (проверялись -Os, -O2 и -O3 ) WTF !!!

Начали разбираться. Выяснили, что g++ отказывается оптимизировать перегруженный
в Blitz++ для класса Array оператор доступа по индексу, а именно operator(). Тесты
показали что он по производительности уступает даже std::list, не говоря уже о
std::vector, std::valarray и тем более сишным массивам. Оператор доступа по индексу
для blitz::Array уступал в производительности своему собрату из std::vector почти
в 6 раз.

Далее провели небольшое исследование по сравнению кода генерируемого компилятором
Visual C++ 2008 и g++ 4.3.3, для операторов доступа к элементам контейнера по
индексу для контейнеров blitz::Array и std::vector. И вот что получилось.

Код для blitz::Array:

  Array <int, 1> vec(size);
  for(int cnt_num=0; cnt_num < cnt; ++cnt_num)
  {
    for(int i=0; i<size; ++i)
      vec(i) = i;
  }

Код для std::vector:

  vector<int> vec(size);
  for(int cnt_num=0; cnt_num < cnt; ++cnt_num)
  {
    for(int i=0; i<size; ++i)
      vec[i] = i;
  }

WIN32 — MSVC 2008

------------ BLITZ ----------------

CPU Disasm
Address   Hex dump                    Command 
004010AF  |.    90                        NOP
004010B0  |>  33C0                   /XOR EAX,EAX
004010B2  |.    8BCF                  |MOV ECX,EDI
004010B4  |>  8901                   |/MOV DWORD PTR DS:[ECX],EAX
004010B6  |.    40                      ||INC EAX
004010B7  |.    03CA                  ||ADD ECX,EDX
004010B9  |.    3D D8000000    ||CMP EAX,0D8
004010BE  |.^ 7C F4                  |\JL SHORT 004010B4
004010C0  |.    83EE 01             |SUB ESI,1
004010C3  |.^ 75 EB                  \JNE SHORT 004010B0

------------ VECTOR ---------------

CPU Disasm
Address   Hex  dump                    Command   
00401070  |>  /33C0                   /XOR EAX,EAX
00401072  |>  |890481              |/MOV DWORD PTR DS:[EAX*4+ECX],EAX
00401075  |.    |40                      ||INC EAX
00401076  |.    |3D D8000000    ||CMP EAX,0D8
0040107B  |. ^|7C F5                 |\JL SHORT 00401072
0040107D  |.    |83EA 01            |SUB EDX,1
00401080  |.^  \75 EE                 \JNE SHORT 00401070

LINUX — GCC 4.3.3

------------- BLITZ ----------------

 8048a40:    8b 45 e8                         mov    -0x18(%ebp),%eax
 8048a43:    31 d2                            xor      %edx,%edx
 8048a45:    eb 19                            jmp     8048a60 <main+0xf0>
 8048a47:    89 f6                            mov    %esi,%esi
 8048a49:    8d bc 27 00 00 00 00     lea       0x0(%edi,%eiz,1),%edi
 8048a50:    8b 45 e8                         mov    -0x18(%ebp),%eax
 8048a53:    8d b6 00 00 00 00        lea      0x0(%esi),%esi
 8048a59:    8d bc 27 00 00 00 00     lea      0x0(%edi,%eiz,1),%edi
 8048a60:    0f af c2                         imul    %edx,%eax
 8048a63:    89 14 81                         mov    %edx,(%ecx,%eax,4)
 8048a66:    83 c2 01                         add     $0x1,%edx
 8048a69:    81 fa d8 00 00 00        cmp    $0xd8,%edx
 8048a6f:    75 df                            jne      8048a50 <main+0xe0>
 8048a71:    83 c6 01                         add     $0x1,%esi
 8048a74:    81 fe 80 96 98 00        cmp    $0x989680,%esi
 8048a7a:    75 c4                            jne      8048a40 <main+0xd0>

------------------ VECTOR -----------------

 8048578:    31 d2                            xor      %edx,%edx
 804857a:    8d b6 00 00 00 00        lea      0x0(%esi),%esi
 8048580:    89 14 90                        mov    %edx,(%eax,%edx,4)
 8048583:    83 c2 01                        add      $0x1,%edx
 8048586:    81 fa d8 00 00 00         cmp    $0xd8,%edx
 804858c:    75 f2                           jne       8048580 <main+0x40>
 804858e:    83 c1 01                       add      $0x1,%ecx
 8048591:    81 f9 80 96 98 00        cmp    $0x989680,%ecx
 8048597:    75 df                           jne      8048578 <main+0x38>

Как видно из приведенного выше, оптимизатор от студии великолепно справился со
своей задачей и создал почти идентичный код для обоих контейнеров. Чего нельзя
сказать о G++, код для std::vector у него получился вполне приличный, а вот с
blitz::Array у него вышла какая-то не реальная хрень. Я не большой знаток
AT&T-шного синтаксиса, но помоему творится там какая-то муть.

Посему, хотелось бы услышать мнение общественности.

З.Ы. Форматирование асемблерного дампа так и не осилил, но очень-очень старался, так что звиняйте

_>Как видно из приведенного выше, оптимизатор от студии великолепно справился со
_>своей задачей и создал почти идентичный код для обоих контейнеров. Чего нельзя
_>сказать о G++, код для std::vector у него получился вполне приличный, а вот с
_>blitz::Array у него вышла какая-то не реальная хрень. Я не большой знаток
_>AT&T-шного синтаксиса, но помоему творится там какая-то муть.

_>Посему, хотелось бы услышать мнение общественности.

Доброго времени суток. Честно говоря, не очень понятно, что вы хотите услышать? Да, gcc сгенерил неоптимальный (мягко говоря) код для array. Например, он вычисляет адрес ячейки с использованием умножения, что иногда сравнимо по стоимости с записью в память. Ну и плюсом "лишние" вычисления адреса (аналог nop для выравнивания) в данном случае не совсем нужны, поскольку составляют примерно половину тела цикла (за исключением impul) по тактам. Как говорится, старался, но ...

Как это поправить — очевидно, посмотреть, чем отличаются array и vector для gcc. И поправить array таким образом, чтобы соответствовало.

Здравствуйте, first_slider, Вы писали:

_>LINUX — GCC 4.3.3

_>------------- BLITZ ----------------

_>

_> 8048a40:    8b 45 e8                         mov    -0x18(%ebp),%eax
_> 8048a43:    31 d2                            xor      %edx,%edx
_> 8048a45:    eb 19                            jmp     8048a60 <main+0xf0>
_> 8048a47:    89 f6                            mov    %esi,%esi
_> 8048a49:    8d bc 27 00 00 00 00     lea       0x0(%edi,%eiz,1),%edi
_> 8048a50:    8b 45 e8                         mov    -0x18(%ebp),%eax
_> 8048a53:    8d b6 00 00 00 00        lea      0x0(%esi),%esi
_> 8048a59:    8d bc 27 00 00 00 00     lea      0x0(%edi,%eiz,1),%edi
_> 8048a60:    0f af c2                         imul    %edx,%eax
_> 8048a63:    89 14 81                         mov    %edx,(%ecx,%eax,4)
_> 8048a66:    83 c2 01                         add     $0x1,%edx
_> 8048a69:    81 fa d8 00 00 00        cmp    $0xd8,%edx
_> 8048a6f:    75 df                            jne      8048a50 <main+0xe0>
_> 8048a71:    83 c6 01                         add     $0x1,%esi
_> 8048a74:    81 fe 80 96 98 00        cmp    $0x989680,%esi
_> 8048a7a:    75 c4                            jne      8048a40 <main+0xd0>
_>

_>Чего нельзя сказать о G++ ...... с
_>blitz::Array у него вышла какая-то не реальная хрень.
как раз у gcc никакой хрени нет — он сделал ровно то, что написано в коде.
а написано там следующее:

    T_numtype& restrict operator()(int i0) 
    {
        assertInRange(i0);
        return data_[i0 * stride_[0]];
    }

вот откуда imul.

соответственно, почему ms сделал лучше (потому, что у него длиннее

) :
он просто распознал что stride_[0] = 1, и умножение на единицу выкинул. кстати, там в потрохах blitz можно обнаружить в комментах, что разработчики предвидели возможность подобного (это называется constant propagation, то есть вычисление переменных при компиляции), и немножко пытались помочь компилятору (но не всем это помогло)

кстати, для msvc2005 тоже imul остался.

если прямо так уж необходимо быстрее, предлагаю (одномерный случай) грязный хак исходников blitz (blitz/array-impl.h):

    T_numtype& restrict operator()(int i0) 
    {
        assertInRange(i0);
        if(_bz_rank == 1) return data_[i0];
        return data_[i0 * stride_[0]];
    }

определить в compile-time что _bz_rank (в смысле, сколькимерный массив) и выкинуть лишнее сравнение не в пример проще чем протаскивать единичку через поля класса, поскольку он там один раз присваивается как static const int

_> Я не большой знаток AT&T-шного синтаксиса, но помоему творится там какая-то муть.
ну, умножение-то увидишь
кстати, попробуй для двумерных массивов — разница не такой большой должна быть между vc и gcc

_>Посему, хотелось бы услышать мнение общественности.
а вопрос-то в чем?

Здравствуйте, Antikrot, Вы писали:

A>а вопрос-то в чем?

Да то чот g++ неудалась constant propagation оптимизация я понимаю, а вопрос, собственно, в том, почему такая в общем-то не сложная (imho) оптимизация, таки не удалась g++, который, по слухам, является весьма не плохим оптимизирующим компилятором. Кстати, декодер, переведенный с blitz::Array на std::valarray, под Linux оказался быстрее Windows версии процентов на 10.
З.Ы. Вот думаю, стоит ли отпостится ли по этому поводу в багзиллу gcc.

Здравствуйте, first_slider, Вы писали:

_>Да то чот g++ неудалась constant propagation оптимизация я понимаю, а вопрос, собственно, в том, почему такая в общем-то не сложная (imho) оптимизация,
она тут не такая простая... там "константа" как элемент массива, стало быть наверное (не уверен) цепляются проверки на алиасинг с другими задействованными массивами/указателями, а вот это уже такой геморрой...

_>таки не удалась g++, который, по слухам, является весьма не плохим оптимизирующим компилятором.
хз, надо в логи да исходники смотреть, а у меня даже линуха под руками нет, не то что gcc

Здравствуйте, first_slider, Вы писали:

_>Как видно из приведенного выше, оптимизатор от студии великолепно справился со
_>своей задачей и создал почти идентичный код для обоих контейнеров. Чего нельзя
_>сказать о G++, код для std::vector у него получился вполне приличный, а вот с
_>blitz::Array у него вышла какая-то не реальная хрень. Я не большой знаток
_>AT&T-шного синтаксиса, но помоему творится там какая-то муть.

а код который можно было бы собрать, при наличие blitz у вас есть?

Здравствуйте, first_slider, Вы писали:

_>Посему, хотелось бы услышать мнение общественности.

М-м.. а, собственно, что Вы ожидаете услышать? Иногда gcc выдаёт код хуже, чем выдаёт VS. Но не настолько часто чтобы стоило сильно переживать об этом. Иногда, кстати, наблюдаются и обратные вещи — к примеру, у меня gcc 4.3.2 соптимизировал участок, работающий со статической константной строкой, а студия — нет. gcc обнаружил, что из всей строки реально используются только 3 символа и подставил их значения, несмотря на то, что в коде есть цикл, перебирающий символы из этой строки (пустой перебор, значения потом нигде не используются). В результате в бинарнике, выданном gcc самой строки не было, а в бинарнике от VS строка осталась.

Но это фигня.. вот то, что меня сейчас реально беспокоит — то, что в 2005-й студии компиляция иногда просто тупо виснет на многопроцессорной машине.

И по ssh компиляция в 2005-й студии не работает.

Здравствуйте, first_slider, Вы писали:

_>Далее провели небольшое исследование по сравнению кода генерируемого компилятором
_>Visual C++ 2008 и g++ 4.3.3, для операторов доступа к элементам контейнера по
_>индексу для контейнеров blitz::Array и std::vector. И вот что получилось.

А как насчет boost::array и boost::multi_array?
интересно посмотреть на результаты

Очень рекомендую попробовать перескочить на boost::ublas, если есть такая возможность.

Здравствуйте, minorlogic, Вы писали:

M>Очень рекомендую попробовать перескочить на boost::ublas, если есть такая возможность.

Я рассматривал uBlas как одного из претендентов, однако по нескольким несколько соображениям от него отказался:
1. мне совершенно не нужен BLAS, мне нужен только удобный контейнер;
2. синтаксически uBlas это полный ужас, одна только реализация концепции срезов (slice и range) чего стоит;
3. да и выдирать его из boost-а как-то лениво.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, first_slider, Вы писали:

_>>Как видно из приведенного выше, оптимизатор от студии великолепно справился со
_>>своей задачей и создал почти идентичный код для обоих контейнеров. Чего нельзя
_>>сказать о G++, код для std::vector у него получился вполне приличный, а вот с
_>>blitz::Array у него вышла какая-то не реальная хрень. Я не большой знаток
_>>AT&T-шного синтаксиса, но помоему творится там какая-то муть.

А>а код который можно было бы собрать, при наличие blitz у вас есть?

Эммм, не очень понял суть вопроса, можно подробнее?

Здравствуйте, jazzer, Вы писали:

J>Здравствуйте, first_slider, Вы писали:

_>>Далее провели небольшое исследование по сравнению кода генерируемого компилятором
_>>Visual C++ 2008 и g++ 4.3.3, для операторов доступа к элементам контейнера по
_>>индексу для контейнеров blitz::Array и std::vector. И вот что получилось.

J>А как насчет boost::array и boost::multi_array?
J>интересно посмотреть на результаты

boost::array отвергнут изначально, по причине своей статичности, и даже не рассматривался. boost::multi_array отвергнут как обладатель чудовищного синтаксиса и кривой (неполноценной и неудобной — IMHO) реализации концепций срезов (slice) и видов (view).

Здравствуйте, first_slider, Вы писали:

_>Здравствуйте, minorlogic, Вы писали:

M>>Очень рекомендую попробовать перескочить на boost::ublas, если есть такая возможность.

_>Я рассматривал uBlas как одного из претендентов, однако по нескольким несколько соображениям от него отказался:
_>1. мне совершенно не нужен BLAS, мне нужен только удобный контейнер;

Blitz тащит намного больше функциональности и кода чем boost::ublas.

_>2. синтаксически uBlas это полный ужас, одна только реализация концепции срезов (slice и range) чего стоит;
Попробуем сравнить

   template <typename TElementType>
   blitz::Array<TElementType, 1> diag(blitz::Array<TElementType, 2>& mat)
   {
      int minSize = mat.rows() < mat.cols() ? mat.rows() : mat.cols();
      blitz::Array<TElementType, 1> vecRepresentation(mat.data(), blitz::shape(mat.size()), blitz::neverDeleteData);
      return vecRepresentation(blitz::Range(0, (minSize-1)*(mat.cols()+1), mat.cols()+1));
   }


   template< class E >
   boost::numeric::ublas::matrix_vector_slice< E >
   diag( boost::numeric::ublas::matrix_expression<E> &mat )
   {
      typedef boost::numeric::ublas::matrix_vector_slice< E >   matrix_slice;
      typedef boost::numeric::ublas::slice                      slice;

      E::size_type minSize = mat().size1() < mat().size2() ? mat().size1() : mat().size2();
      return matrix_slice ( mat(), slice (0, 1, minSize), slice (0, 1, minSize));
   }

Огромной разницы не вижу. Плюс есть функции "project" для упрощения синтаксиса.

_>3. да и выдирать его из boost-а как-то лениво.

Это уже вопрос политики и техники, выдирать не выдирать.

Из минусов Blitz, основной это неправильная семантика копирования и владения , например нельзя blitz::Array делать членом класса или помещать в стандартные контейнеры.

Здравствуйте, first_slider, Вы писали:

_>2. синтаксически uBlas это полный ужас, одна только реализация концепции срезов (slice и range) чего стоит;

Приведите пример срезов на том и другом , может я смогу помочь ?

Здравствуйте, first_slider, Вы писали:

_>Здравствуйте, Аноним, Вы писали:

А>>Здравствуйте, first_slider, Вы писали:

_>>>Как видно из приведенного выше, оптимизатор от студии великолепно справился со
_>>>своей задачей и создал почти идентичный код для обоих контейнеров. Чего нельзя
_>>>сказать о G++, код для std::vector у него получился вполне приличный, а вот с
_>>>blitz::Array у него вышла какая-то не реальная хрень. Я не большой знаток
_>>>AT&T-шного синтаксиса, но помоему творится там какая-то муть.

А>>а код который можно было бы собрать, при наличие blitz у вас есть?

_>Эммм, не очень понял суть вопроса, можно подробнее?

имеется ввиду готовый cpp файл, в котором уже есть нужные include, хорошо еще был бы main,
чтобы поместить это в багзилу gcc и разработчики gcc могли бы легко воспроизвести эту проблему

Здравствуйте, first_slider, Вы писали:

_>Здравствуйте, jazzer, Вы писали:

J>>Здравствуйте, first_slider, Вы писали:

_>>>Далее провели небольшое исследование по сравнению кода генерируемого компилятором
_>>>Visual C++ 2008 и g++ 4.3.3, для операторов доступа к элементам контейнера по
_>>>индексу для контейнеров blitz::Array и std::vector. И вот что получилось.

J>>А как насчет boost::array и boost::multi_array?
J>>интересно посмотреть на результаты

_>boost::array отвергнут изначально, по причине своей статичности, и даже не рассматривался. boost::multi_array отвергнут как обладатель чудовищного синтаксиса и кривой (неполноценной и неудобной — IMHO) реализации концепций срезов (slice) и видов (view).

Да я не про Ваш проект (я понятия не имею, что Вам нужно, поэтому далек от раздачи советов), а про оптимизатор.
У Вас же есть уже код, который меряет скорость вектора и блица — вот я и прошу этим же (условно) кодом замерить boost::array и boost::multi_array и выложить результаты.
Чтоб, так сказать, было полноценное сравнение оптимизатора на популярных плюсовых библиотеках.

ПС. а что не так с синтаксисом, срезами и вьюхами?
Вроде, синтаксис стандартный, array[i][j][k]

Я до сих пор столкнулся только с одним неудобством: внутренний тип reference в общем случае — не ссылка, что ломает кое-какой код, но, опять же, это обходится очень легко. Но иначе, наверное, сделать многомерную индексацию и не получится.

	От:	first_slider
	Дата:	11.04.09 19:59
	Оценка:

От:	Andrew S	http://alchemy-lab.com
Дата:	11.04.09 21:51
Оценка:

	От:	Antikrot
	Дата:	11.04.09 22:44
	Оценка:

	От:	first_slider
	Дата:	12.04.09 08:11
	Оценка:

	От:	Antikrot
	Дата:	12.04.09 12:28
	Оценка:

От:	artem_korneev	https://www.linkedin.com/in/artemkorneev/
Дата:	13.04.09 10:21
Оценка:

От:	jazzer	Skype: enerjazzer
Дата:	13.04.09 13:15
Оценка:

	От:	minorlogic
	Дата:	14.04.09 10:59
	Оценка:

	От:	minorlogic
	Дата:	14.04.09 11:07
	Оценка:

	От:	Аноним
	Дата:	14.04.09 12:24
	Оценка: