c0d3r May 30 2012 at 20:57

Сравнение скорости работы range-based for, foreach(Qt) и кое-чего из STL при подсчете суммы элементов контейнеров

4 min

8.5K

C++*

+27

Comments 25

KindDragon May 30 2012 at 22:04

Не нашел, какая использовалась версия Qt и какой компилятор C++?

Gorthauer87 May 30 2012 at 23:18

Ага немаловажным было бы сравнить скорости на разных компиляторах…
Сейчас попробую протестить gcc 4.6 и clang 3.1 из под linux x86_64
Плюс еще clang может юзать libcxx вместо libstdc++

Gorthauer87 May 30 2012 at 23:37

gcc 4-6 linux x86-64

Run test for type:F7QVectorIiEvE                                                                                                                                    
"New for" results(ms):avg:189 min:188 max:192                                                                                                                       
"Accumulate" results(ms):avg:242 min:240 max:253                                                                                                                    
"Qt foreach" results(ms):avg:237 min:237 max:238                                                                                                                    
"STL for" results(ms):avg:381 min:381 max:382                                                                                                                       
"STL for 2" results(ms):avg:240 min:240 max:241                                                                                                                     
Run test for type:FSt6vectorIiSaIiEEvE                                                                                                                              
"New for" results(ms):avg:186 min:185 max:187                                                                                                                       
"Accumulate" results(ms):avg:186 min:185 max:188                                                                                                                    
"Qt foreach" results(ms):avg:484 min:482 max:499                                                                                                                    
"STL for" results(ms):avg:187 min:186 max:188                                                                                                                       
"STL for 2" results(ms):avg:186 min:186 max:187                                                                                                                     
Run test for type:F5QListIiEvE                                                                                                                                      
"New for" results(ms):avg:299 min:298 max:316                                                                                                                       
"Accumulate" results(ms):avg:298 min:297 max:301                                                                                                                    
"Qt foreach" results(ms):avg:356 min:356 max:359                                                                                                                    
"STL for" results(ms):avg:360 min:359 max:368                                                                                                                       
"STL for 2" results(ms):avg:298 min:297 max:300

clang 3.1+libcxx

Run test for type:F7QVectorIiEvE
"New for" results(ms):avg:186 min:185 max:189
"Accumulate" results(ms):avg:187 min:186 max:190
"Qt foreach" results(ms):avg:245 min:244 max:247
"STL for" results(ms):avg:331 min:330 max:343
"STL for 2" results(ms):avg:187 min:186 max:190
Run test for type:FNSt3__16vectorIiNS_9allocatorIiEEEEvE
"New for" results(ms):avg:186 min:186 max:188
"Accumulate" results(ms):avg:186 min:186 max:189
"Qt foreach" results(ms):avg:813 min:525 max:849
"STL for" results(ms):avg:187 min:185 max:204
"STL for 2" results(ms):avg:187 min:186 max:189
Run test for type:F5QListIiEvE
"New for" results(ms):avg:298 min:298 max:301
"Accumulate" results(ms):avg:299 min:297 max:316
"Qt foreach" results(ms):avg:343 min:342 max:355
"STL for" results(ms):avg:408 min:408 max:410
"STL for 2" results(ms):avg:298 min:297 max:302

Qt5 gcc 4.6

Run test for type:F7QVectorIiEvE
"New for" results(ms):avg:241 min:240 max:243
"Accumulate" results(ms):avg:187 min:186 max:189
"Qt foreach" results(ms):avg:195 min:193 max:197
"STL for" results(ms):avg:312 min:311 max:314
"STL for 2" results(ms):avg:190 min:189 max:202
Run test for type:FSt6vectorIiSaIiEEvE
"New for" results(ms):avg:186 min:186 max:188
"Accumulate" results(ms):avg:187 min:186 max:197
"Qt foreach" results(ms):avg:485 min:483 max:502
"STL for" results(ms):avg:186 min:186 max:189
"STL for 2" results(ms):avg:187 min:186 max:201
Run test for type:F5QListIiEvE
"New for" results(ms):avg:299 min:297 max:318
"Accumulate" results(ms):avg:299 min:297 max:303
"Qt foreach" results(ms):avg:350 min:348 max:357
"STL for" results(ms):avg:385 min:378 max:398
"STL for 2" results(ms):avg:305 min:299 max:326

f0b0s May 30 2012 at 23:51

А как же BOOST_FOREACH? Он копирования не делает и вообще устроен очень круто и правильно. Там дичайшая шаблонная магия с приенением sizeof и тернарного оператора, но учтены все возможные мелочи и работать он должен максимально быстро. За потробностями обращаться сюда: www.artima.com/cppsource/foreach.html

Balthasar May 31 2012 at 00:03

Добавил в тест BOOST_FOREACH.

Linux 32bit, gcc 4.6.3, Qt 4.8.1

"New for" results(ms): avg:100 min:97 max:108
"Accumulate" results(ms): avg:100 min:97 max:108
"Qt foreach" results(ms): avg:103 min:100 max:112
"Boost foreach" results(ms): avg:101 min:97 max:106
"STL for" results(ms): avg:130 min:126 max:151
"STL for 2" results(ms): avg:99 min:97 max:104

Run test for type: FSt6vectorIiSaIiEEvE
"New for" results(ms): avg:100 min:97 max:106
"Accumulate" results(ms): avg:98 min:95 max:104
"Qt foreach" results(ms): avg:258 min:249 max:290
"Boost foreach" results(ms): avg:100 min:97 max:107
"STL for" results(ms): avg:100 min:98 max:107
"STL for 2" results(ms): avg:99 min:97 max:108

Run test for type: F5QListIiEvE
"New for" results(ms): avg:100 min:98 max:110
"Accumulate" results(ms): avg:101 min:98 max:106
"Qt foreach" results(ms): avg:103 min:101 max:111
"Boost foreach" results(ms): avg:100 min:98 max:108
"STL for" results(ms): avg:131 min:126 max:146
"STL for 2" results(ms): avg:101 min:98 max:110

f0b0s May 31 2012 at 00:23

Ну вот, ничем не уступает range-based for. ЧТД

Gorthauer87 May 31 2012 at 00:37

Но ничем не превосходит

f0b0s May 31 2012 at 01:44

Как это — он поддерживается любым компилятором, включая очень древние версии gcc. А в студии до сих пор нет range based for, хотя на Going Native они заявили, что написали его реализацию.

Причем, она достаточно проста:
for ( TYPE x: range_expr ) {… }

заменяется на
auto&& range = range_expr; // perfect forwarding
for ( auto i = begin©, e = end©; i != e; ++i ) { // begin и end добавлены в c++11
TYPE x = *i;
…
}

По сути BOOST_FOREACH делает то же самое и поэтому выигрыша никакого быть и не может.

dzhioev May 31 2012 at 10:50

Да никто и не сомневался. Range-based for loop, вида:

for (T obj: range) { ... }

раскрывается компилятором в:

for (auto it = std::begin(range); it != std::end(range); ++it) {
    T obj = *it;
    ...
}

Это примерно то же самое, что делает BOOST_FOREACH.
Но из-за того, что BOOST_FOREACH является макросом, нельзя написать например так:

BOOST_FOREACH(std::pair<int, int> p, range) { ... }

Компилятор посчитает, что мы передаем макросу 3 аргумента, вместо 2-x.

Ramires May 31 2012 at 11:06

One way to fix this is with a typedef.

std::map<int,int> m;
typedef std::pair<int,int> pair_t;

BOOST_FOREACH(pair_t p, m) // ...

Another way to fix it is to predeclare the loop variable:

std::map<int,int> m;
std::pair<int,int> p;

BOOST_FOREACH(p, m) // ...

Из документации буста.

dzhioev May 31 2012 at 11:09

Это понятно. Но такой способ сводит на нет то, ради чего BOOST_FOREACH и делался – лаконичность записи.

f0b0s May 31 2012 at 17:27

А я обычно так делаю: я никогда не использую неименованные типы, например, map, у меня всегда идет typedef: FileID2StreamID.

И в форыче я пишу так: BOOST_FOREACH(const FileID2StreamID::value_type& v, m) {… }

f0b0s May 31 2012 at 17:40

Вы не совсем точно описали. У меня выше более правильно, хотя у вас более аккурано отформатировано.

Претензии две:
1) скорее всего end вычисляется все же 1 раз, хотя да, если у контейнера end выполняется не за O(1) — сам дурак
2) вы не рассматриваете случай, когда range это не переменная, а выражение. Поэтому оно предварительно сохраняется в переменную, через perfect forwarding, чтобы не городить копирование там, где выражение возвращает, например, константную ссылку.

dzhioev May 31 2012 at 17:44

Спасибо за уточнение.
Вообще, интересующиеся могут посмотреть на пункт 6.5.4 стандарта. Там много всяких нюансов.

Vass May 31 2012 at 00:42

Ну в свете нового стандарта, Qt foreach может быть и действительно не нужен,
но следует не забывать что, написан он был задолго до того.

А так кроме очевидного вылета:
std::vector на foreach, ничего шокирующего не увидел,
реализация Qt foreach никогда и не претендовала на скорость,
она просто облегчала написание не критического итеративного кода.
Если мне нужно пройтись по контейнеру, в котором гарантированно не больше сотни-другой элементов,
неужели стоит пожертвовать чистотой кода ради, нескольких микросекунд?

Другое дело, в том что надо понимать когда не стоит этим злоупотребять.

В итоге считаю, ваш вывод крайне категоричным, и не вижу ничего страшного в умеренном использовании foreach по ситуации.

Athari May 31 2012 at 01:27

Вы какого рода софт пишете? Чтобы метод прохода циклом имел значение, нужно И чтобы элементов было дофига, И чтобы тело цикла было тривиальным. Во всех остальных случаях разница пренебрежимо мала, поэтому оптимизации типа «никогда не использовать qt foreach» являются преждевременными.

-2

Qbit May 31 2012 at 02:38

Саттер рекомендует «std::make_shared(...» вместо «std::shared_ptr<T> (new T...».

UnknownGosu May 31 2012 at 10:09

Это, скорее, не столько Саттера рекомендация, сколько Лававея (мейнтейнера STL в Microsoft). Он на GoingNative 2012 рассказывал, что применил там оптимизацию, избавившись от 1 лишней аллокации.
А по стандарту поведение двух этих вариантов не обязано отличаться.

Qbit May 31 2012 at 10:14

habrahabr.ru/post/144905/#comment_4868656

f0b0s May 31 2012 at 17:45

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

Qbit May 31 2012 at 10:14

> Это, скорее, не столько Саттера рекомендация, сколько Лававея (мейнтейнера STL в Microsoft).

Да, STL — клёвый чувак (здесь «STL» — инициалы упомянутого мейнтейнера STL'я). Было бы неплохо, если бы он книжку накатал.

ncix Jun 6 2012 at 10:52

разный временной масштаб графиков вводит в заблуждение.

ncix Jun 6 2012 at 10:56

Qt foreach удобен но внутри сделан странно. Зачем-то делается копия контейнера вместо обхода по итераторам. Что приводит к забавным курьезам: например у меня был кастомный QList указателей с удалением объектов в деструкторе. Так вот из-за копирования в foreach всё это естественно падало по выходе из цикла (по указателям объекты убивались).

Gorthauer87 Jun 13 2012 at 15:15

Ну так же в современном программировании на С++ прямо сказано, что наследоваться от неполиморфных классов — это та ещё глупость.

ncix Jun 14 2012 at 13:53

Согласен, наследование в данном случае было ошибкой. Тем не менее поведение foreach нельзя назвать предсказуемым.

Show the best of all time