Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Тормоза STL

Автор: borisbn 7.11.2011, 02:08

Здравствуйте. Потребовалось тут недавно сделать несложную функцию, которая XOR-ит два массива, AND-ит результат с третьим и OR-ит результат в одну переменную. Короче так: Код     sum = 0;     for ( size_t i = 0; i < count; i++ )         sum |= ( data1[ i ] ^ data2[ i ] ) & mask[ i ]; потом решил немного по...вы..делываться и сделал то же самое на STL, только с тремя циклами (один на XOR, второй на AND, третий на аккумулирование). В результате код на STL работает в 6...7 раз медленнее. Подскажите, в чём я не прав. Или это - нормально, а просто не следует сдуру пихать алгоритмы STL во все дыры ? Вот код: Код using namespace std; typedef unsigned char uchar; typedef vector< uchar > uchar_v; template< class T >  struct binary_xor : std::binary_function< T, T, T > {     T operator()( const T & a, const T & b ) { return a ^ b; } }; template< class T > struct binary_and : std::binary_function< T, T, T > {     T operator()( const T & a, const T & b ) { return a & b; } }; template< class T > struct binary_or : std::binary_function< T, T, T > {     T operator()( const T & a, const T & b ) { return a | b; } }; //const int sz = 10000000; //uchar_v temp( sz ); bool stl_version( const uchar_v & data1, const uchar_v & data2, const uchar_v & mask ) {     size_t count = data1.size();     uchar_v temp( count ); // пробовал создавать "снаружи" - сильно не поменялось     std::transform( data1.begin(), data1.end(), data2.begin(), temp.begin(), binary_xor< uchar >() );     std::transform( temp.begin(), temp.end(), mask.begin(), temp.begin(), binary_and< uchar >() );     uchar sum = std::accumulate( temp.begin(), temp.end(), 0, binary_or< uchar >() );     if ( sum == 0 )         return true;     return false; } bool gen_version( const uchar_v & data1, const uchar_v & data2, const uchar_v & mask ) {     size_t count = data1.size();     uchar sum = 0;     for ( size_t i = 0; i < count; i++ )         sum |= ( data1[ i ] ^ data2[ i ] ) & mask[ i ];     if ( sum == 0 )         return true;     return false; } const int sz = 10000000; uchar_v data1( sz, 1 ); uchar_v data2( sz, 2 ); uchar_v mask( sz, 4 ); int main() { clock_t t1; clock_t t2;     t1 = clock();     gen_version( data1, data2, mask );     t2 = clock();     cout << "gen_version = " << t2 - t1 << endl;         t1 = clock();     stl_version( data1, data2, mask );     t2 = clock();     cout << "stl_version = " << t2 - t1 << endl; } http://liveworkspace.org/code/366eb1fa8b056258fcd9d50b5a3ab4e1

Автор: baldina 7.11.2011, 02:44

три цикла содержат больше вычислений. а если массивы достаточно большие, то гораздо больше перезагрузек кэша, так что 6-7 раз вполне нормально. Цитата(borisbn @  7.11.2011,  02:08 ) не следует сдуру пихать алгоритмы STL во все дыры   это не STL плохой, просто задача на 3 цикла действия естественным образом не распадается, это рождение напряженной мысли)) в крайнем случае можно было создать из Ваших трех функций общую функцию (a^b)&c и запихнуть её в accumulate. цикл был бы один и тяга к обобщениям удовлетворена.

Автор: volatile 7.11.2011, 03:03

borisbn, не поверите. Взял ваш код. Ничего не менял (код брал на liveworkspace). Скомпилял на студии 2008. Результат : Код gen_version = 62 stl_version = 62 gen_version = 62 stl_version = 62 Прогонял несколько раз. Цифры чуток менялись, но ничего кардинального. на всякий случай комм. строка (оптимизация) Код /O2 /Ob2 /Oi /Ot /Oy /GT /GL /D "WIN32"  /D "NDEBUG" /D "_CONSOLE"  /D "_MBCS" /FD /EHa /MT /Gy  /Yu"stdafx.h" /Fp"Release\vingrad.pch"  /Fo"Release\\" /Fd"Release\vc90.pdb"  /W3 /nologo /c /Zi /TP /errorReport:prompt вывод...

Автор: boostcoder 7.11.2011, 03:14

volatile, отформатируй плиз строку компилятора. а то экран зашкаливает. Добавлено через 2 минуты и 45 секунд Цитата(borisbn @  7.11.2011,  02:08 ) const int sz = 10000000; увеличил в 10 раз, но для gen_version() время равно нулю. есть подозрение, что GCC вовсе вырезал тело этой функции. щас проверю..

Автор: boostcoder 7.11.2011, 04:00

так и есть. компилятор вырезал оба вызова gen_version()   раньше я уже подымал подобный вопрос. мало того что gen_version() является http://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html, так ты еще и возвращаемое значение не проверяешь. поэтому компилятор вполне логично предположил, что функцию можно запросто вырезать. и ведь он не ошибся, все равно никто до сих пор не заметил что она пропала.   подкорректировал код так: Код #include <vector> #include <algorithm> #include <functional> #include <numeric> #include <cassert> #include <ctime> #include <iostream> using namespace std; typedef unsigned char uchar; typedef vector< uchar > uchar_v; template< class T > struct binary_xor : std::binary_function< T, T, T > {     T operator()( const T a, const T b ) const { return a ^ b; } }; template< class T > struct binary_and : std::binary_function< T, T, T > {     T operator()( const T a, const T b ) const { return a & b; } }; template< class T > struct binary_or : std::binary_function< T, T, T > {     T operator()( const T a, const T b ) const { return a | b; } }; //const int sz = 10000000; //uchar_v temp( sz ); bool stl_version( const uchar_v & data1, const uchar_v & data2, const uchar_v & mask ) {     size_t count = data1.size();     uchar_v temp( count ); // пробовал создавать "снаружи" - сильно не поменялось     std::transform( data1.begin(), data1.end(), data2.begin(), temp.begin(), binary_xor< uchar >() );     std::transform( temp.begin(), temp.end(), mask.begin(), temp.begin(), binary_and< uchar >() );     uchar sum = std::accumulate( temp.begin(), temp.end(), 0, binary_or< uchar >() );     return ( sum == 0 ); } bool gen_version( const uchar_v & data1, const uchar_v & data2, const uchar_v & mask ) {     size_t count = data1.size();     uchar sum = 0;     for ( size_t i = 0; i < count; i++ )     {         sum |= ( data1[ i ] ^ data2[ i ] ) & mask[ i ];     }     return ( sum == 0 ); } const int sz = 10000000; uchar_v data1( sz, 1 ); uchar_v data2( sz, 2 ); uchar_v mask( sz, 4 ); int main() {    clock_t t1;    clock_t t2;     t1 = clock();     assert(gen_version( data1, data2, mask ));     t2 = clock();     cout << "gen_version = " << t2 - t1 << endl;     t1 = clock();     assert(stl_version( data1, data2, mask ));     t2 = clock();     cout << "stl_version = " << t2 - t1 << endl;     t1 = clock();     assert(gen_version( data1, data2, mask ));     t2 = clock();     cout << "gen_version = " << t2 - t1 << endl;     t1 = clock();     assert(stl_version( data1, data2, mask ));     t2 = clock();     cout << "stl_version = " << t2 - t1 << endl; } http://liveworkspace.org/code/022bb5fb7940d6dacb9ff27ebeff3f95 на LWS оптимизация отключена, поэтому такие огромные расхождения. вот мои результаты. gcc-4.5.2, linux.  Цитата gen_version = 782 stl_version = 765 gen_version = 657 stl_version = 781 gen_version = 656 stl_version = 593 gen_version = 797 stl_version = 562 gen_version = 718 stl_version = 594 gen_version = 797 stl_version = 547 gen_version = 672 stl_version = 657 gen_version = 719 stl_version = 641 gen_version = 719 stl_version = 687 gen_version = 687 stl_version = 672 gen_version = 703 stl_version = 594 gen_version = 797 stl_version = 594 gen_version = 625 stl_version = 609 gen_version = 843 stl_version = 594 странно то, что STL версия почти всегда выполняется быстрее.

Автор: Alexeis 7.11.2011, 07:39

Фишка STL в том, что он дебаговой версии много чего проверяет, что делает отладку более простой, а код безопаснее, тогда как в релизе получается, как правило, тоже что и при использовании простого массива.

Автор: borisbn 7.11.2011, 08:44

Спасибо всем отписавшимся (о_О... и это при том, что я запостил в 3 часа ночи МСК) Цитата(baldina @  7.11.2011,  02:44 ) можно было создать из Ваших трех функций общую функцию (a^b)&c и запихнуть её в accumulate для этого нужно создать структуру, в которую записать a, b и c, и сделать вектор этих структур, а мне это архинеудобно Цитата(boostcoder @  7.11.2011,  04:00 ) на LWS оптимизация отключена, поэтому такие огромные расхождения. хммм. не знал, что отключена... сорри за оффтоп, но как-то экспериментировал с move semantics на LWS ( http://liveworkspace.org/code/ad3e28d4a5542510bcdfe13a7b58d551 ) и решил, что оптимизация там включена (не выводится trace для переменной result и для move-конструктора). Цитата(boostcoder @  7.11.2011,  04:00 ) странно то, что STL версия почти всегда выполняется быстрее. думаю, это из-за того, что в general-версии вызывается operator[], а в STL-версии - просто ++iter. Цитата(Alexeis @  7.11.2011,  07:39 ) Фишка STL в том, что он дебаговой версии много чего проверяет Ну, это понятно. Я просто не знал, что на LWS отключена оптимизация. Всем ещё раз спасибо. Закрываю.

Автор: boostcoder 7.11.2011, 11:08

Цитата(borisbn @  7.11.2011,  08:44 ) (не выводится trace для переменной result и для move-конструктора) не понял. Цитата(borisbn @  7.11.2011,  08:44 ) Я просто не знал, что на LWS отключена оптимизация. а ты на реальном PC не проверял этот код?

Автор: volatile 7.11.2011, 11:58

Цитата(boostcoder @  7.11.2011,  03:14 ) отформатируй плиз строку компилятора. а то экран зашкаливает Пардон, никому не хотел доставить неудобство, (кстати в моем браузере ничего не зашкаливает). вставил переводы строк, не знаю как так у вас будет...

Автор: boostcoder 7.11.2011, 12:18

volatile, спасибо. все гут.

Автор: borisbn 7.11.2011, 12:42

Цитата(boostcoder @  7.11.2011,  11:08 ) не понял. в Str operator+( const Str & other ) const; создаётся переменная Str result; так вот, судя по выводу, её конструктор/деструктор не вызывается. Смотри: в main() создаётся 3 переменных (x, y и z) плюс одна переменная result в операторе +, а выводится в cout trace всего из 3-х деструкторов и 3 варианта this. Цитата(boostcoder @  7.11.2011,  11:08 ) а ты на реальном PC не проверял этот код? по голове не бить   неа. это в воскресенье было. дома компилятор не установлен.

Автор: boostcoder 7.11.2011, 12:54

Цитата(borisbn @  7.11.2011,  12:42 ) неа так у тебя в коде отступы в 4 пробела. ты что, руками на space жал?   ибо на LWS работает Tab, но отступы в 3 пробела. Цитата(borisbn @  7.11.2011,  12:42 ) в Str operator+( const Str & other ) const; создаётся переменная Str result; так вот, судя по выводу, её конструктор/деструктор не вызывается. Смотри: в main() создаётся 3 переменных (x, y и z) плюс одна переменная result в операторе +, а выводится в cout trace всего из 3-х деструкторов и 3 варианта this. позже.

Автор: borisbn 7.11.2011, 16:30

Цитата(boostcoder @  7.11.2011,  12:54 ) так у тебя в коде отступы в 4 пробела. ты что, руками на space жал?     ибо на LWS работает Tab, но отступы в 3 пробела. гы... маленькая хитрость - при переводе строки на LWS отступ делается на 3 символа, но за курсором остаётся ещё один пробел, так что выровняться по 4 - это просто нажать вправо. А если нужно увеличить отступ, то я уже привык на LWS жать Tab, а затем пробел    Цитата(boostcoder @  7.11.2011,  12:54 ) позже. жду.

Автор: boostcoder 7.11.2011, 18:05

Цитата(borisbn @  7.11.2011,  16:30 ) при переводе строки на LWS отступ делается на 3 символа, но за курсором остаётся ещё один пробел в хроме нет никакого пробела. ну да ладно...

Автор: boostcoder 8.11.2011, 00:34

borisbn, на сколько я понял из того что нагуглил, для получения move semantics нужно использовать http://en.cppreference.com/w/cpp/utility/move, ибо в противном случае, компилятор не сможет выбрать сам какой способ использовать, конструкцию с константной ссылкой, или все же move semantics. т.к. первое не сказывается на вызывающий код, а второе сказывается. http://liveworkspace.org/code/ac113d3f5dab62ac92f0adb2ed7c57bd а вообще, по моему вопросов появилось еще больше. нужно создать отдельную тему по поводу move semantics. Добавлено через 2 минуты и 34 секунды Цитата(borisbn @  7.11.2011,  08:44 ) (не выводится trace для переменной result и для move-конструктора). вот: http://liveworkspace.org/code/dc9fa6e852685d617d5669c31c95a4a4

Автор: mes 8.11.2011, 23:25

Цитата(boostcoder @  7.11.2011,  23:34 )  на сколько я понял из того что нагуглил, для получения move semantics нужно использовать std::move(), нет, move нужно использовать, тогда когда  применение move- семантики не очевидно компилятору.. в остальных он сделает сам.. Добавлено через 2 минуты и 53 секунды Цитата(boostcoder @  7.11.2011,  23:34 ) конструкцию с константной ссылкой, или все же move semantics.    чего то запутанно слишком сказано.. не вижу связи.. Добавлено через 4 минуты и 1 секунду наверно код надо смотреть, там много букв позже гляну.. или подожду обещанной новой темы..  тем более что самому хочется до конца разобраться с этим нововведением..

Автор: Lols 9.11.2011, 00:13

Интересно вы по...выделывались  Я так понимаю, что нужно было просто убрать тело функции? (за ненадобностью )

Автор: boostcoder 9.11.2011, 02:19

Цитата(mes @  8.11.2011,  23:25 ) чего то запутанно слишком сказано.. не вижу связи.. очень даже может быть. Цитата(Lols @  9.11.2011,  00:13 ) нужно было просто убрать тело функции? кому нужно?

Автор: baldina 9.11.2011, 11:29

move semantics: http://liveworkspace.org/code/04e86bb47f39ea5ab8a75b99f156efcd

Автор: boostcoder 9.11.2011, 12:22

baldina, это-то я хорошо понимаю. мне была не понятна ситуация с деструкторами перемещенных объектов. читать тут: http://forum.vingrad.ru/forum/topic-341389.html

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)