VPF::Тормоза STL - Форум программистов

borisbn

Дата 7.11.2011, 02:08 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135

Здравствуйте.
Потребовалось тут недавно сделать несложную функцию, которая 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/366eb1fa8b05...cd9d50b5a3ab4e1

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

baldina

Дата 7.11.2011, 02:44 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 32
Всего: 101

три цикла содержат больше вычислений. а если массивы достаточно большие, то гораздо больше перезагрузек кэша, так что 6-7 раз вполне нормально.

Цитата(borisbn @ 7.11.2011, 02:08

)

не следует сдуру пихать алгоритмы STL во все дыры

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

volatile

Дата 7.11.2011, 03:03 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

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

вывод...

Это сообщение отредактировал(а) volatile - 7.11.2011, 11:57

boostcoder

Дата 7.11.2011, 03:14 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

volatile, отформатируй плиз строку компилятора. а то экран зашкаливает.

Добавлено через 2 минуты и 45 секунд

Цитата(borisbn @ 7.11.2011, 02:08

)

const int sz = 10000000;

увеличил в 10 раз, но для gen_version() время равно нулю. есть подозрение, что GCC вовсе вырезал тело этой функции. щас проверю..

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

boostcoder

Дата 7.11.2011, 04:00 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

так и есть. компилятор вырезал оба вызова gen_version() smile

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

подкорректировал код так:

Код


#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/022bb5fb7940...b9ff27ebeff3f95
на 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 версия почти всегда выполняется быстрее.

Это сообщение отредактировал(а) boostcoder - 7.11.2011, 04:18

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

Alexeis

Дата 7.11.2011, 07:39 (ссылка)

(нет голосов)

Загрузка ...

Амеба

Профиль
Группа: Админ
Сообщений: 11743
Регистрация: 12.10.2005
Где: Зеленоград

Репутация: 12
Всего: 459

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

--------------------

Vit вечная память.

Обсуждение действий администрации форума производятся только в этом форуме

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

borisbn

Дата 7.11.2011, 08:44 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135

Спасибо всем отписавшимся (о_О... и это при том, что я запостил в 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/ad3e28d4a554...cdfe13a7b58d551 ) и решил, что оптимизация там включена (не выводится 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 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

Цитата(borisbn @ 7.11.2011, 08:44

)

(не выводится trace для переменной result и для move-конструктора)

не понял.

Цитата(borisbn @ 7.11.2011, 08:44

)

Я просто не знал, что на LWS отключена оптимизация.

а ты на реальном PC не проверял этот код?

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

volatile

Дата 7.11.2011, 11:58 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

Цитата(boostcoder @ 7.11.2011, 03:14

)

отформатируй плиз строку компилятора. а то экран зашкаливает

Пардон, никому не хотел доставить неудобство, (кстати в моем браузере ничего не зашкаливает).

вставил переводы строк, не знаю как так у вас будет...

boostcoder

Дата 7.11.2011, 12:18 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

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

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

borisbn

Дата 7.11.2011, 12:42 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135

Цитата(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 не проверял этот код?

по голове не бить smile

неа. это в воскресенье было. дома компилятор не установлен.

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

boostcoder

Дата 7.11.2011, 12:54 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

Цитата(borisbn @ 7.11.2011, 12:42

)

неа

так у тебя в коде отступы в 4 пробела. ты что, руками на space жал? smile

ибо на 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.

позже.

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

borisbn

Дата 7.11.2011, 16:30 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135

Цитата(boostcoder @ 7.11.2011, 12:54

)

так у тебя в коде отступы в 4 пробела. ты что, руками на space жал? smile

ибо на LWS работает Tab, но отступы в 3 пробела.

гы... маленькая хитрость - при переводе строки на LWS отступ делается на 3 символа, но за курсором остаётся ещё один пробел, так что выровняться по 4 - это просто нажать вправо. А если нужно увеличить отступ, то я уже привык на LWS жать Tab, а затем пробел smile

Цитата(boostcoder @ 7.11.2011, 12:54

)

позже.

жду.

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

boostcoder

Дата 7.11.2011, 18:05 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

Цитата(borisbn @ 7.11.2011, 16:30

)

при переводе строки на LWS отступ делается на 3 символа, но за курсором остаётся ещё один пробел

в хроме нет никакого пробела. ну да ладно...

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

boostcoder

Дата 8.11.2011, 00:34 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

borisbn, на сколько я понял из того что нагуглил, для получения move semantics нужно использовать std::move(), ибо в противном случае, компилятор не сможет выбрать сам какой способ использовать, конструкцию с константной ссылкой, или все же move semantics. т.к. первое не сказывается на вызывающий код, а второе сказывается.

http://liveworkspace.org/code/ac113d3f5dab...2f0adb2ed7c57bd

а вообще, по моему вопросов появилось еще больше. нужно создать отдельную тему по поводу move semantics.

Добавлено через 2 минуты и 34 секунды

Цитата(borisbn @ 7.11.2011, 08:44

)

(не выводится trace для переменной result и для move-конструктора).

вот: http://liveworkspace.org/code/dc9fa6e85268...d5669c31c95a4a4

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

mes

Дата 8.11.2011, 23:25 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(boostcoder @ 7.11.2011, 23:34

)

на сколько я понял из того что нагуглил, для получения move semantics нужно использовать std::move(),

нет, move нужно использовать, тогда когда применение move- семантики не очевидно компилятору.. в остальных он сделает сам..

Добавлено через 2 минуты и 53 секунды

Цитата(boostcoder @ 7.11.2011, 23:34

)

конструкцию с константной ссылкой, или все же move semantics.

чего то запутанно слишком сказано.. не вижу связи..

Добавлено через 4 минуты и 1 секунду
наверно код надо смотреть, там много букв позже гляну.. или подожду обещанной новой темы..
тем более что самому хочется до конца разобраться с этим нововведением..

--------------------

http://opendots.net

Lols

Дата 9.11.2011, 00:13 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 144
Регистрация: 21.10.2011

Репутация: нет
Всего: нет

Интересно вы по...выделывались smile

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

)

boostcoder

Дата 9.11.2011, 02:19 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

Цитата(mes @ 8.11.2011, 23:25

)

чего то запутанно слишком сказано.. не вижу связи..

очень даже может быть.

Цитата(Lols @ 9.11.2011, 00:13

)

нужно было просто убрать тело функции?

кому нужно?

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

baldina

Дата 9.11.2011, 11:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 32
Всего: 101

move semantics:
http://liveworkspace.org/code/04e86bb47f39...8a75b99f156efcd

boostcoder

Дата 9.11.2011, 12:22 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110

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

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »