Сегодня столкнулся с непонятным для меня проседанием по времени на GCC решения, которое нормально заходит под MSC++.
Есть код, в котором что-то примерно такое:
struct point{double x,y;};
vector<pair<point,long > > v;
bool cmp(pair<point, int> a,pair<point, int> b)
{
if (a.first.x>b.first.x)return true;
if (a.first.x<b.first.x)return false;
if (a.first.y>b.first.y)return true;
return false;
}
int main()
{
sort(v.begin(),v.end(),cmp);
}
Тестирование в "запуске" показало, что при отправке решения под GCC время исполнения превышает время исполнения под студией в 9-12 раз.
Если исправить типы pair<point,long > / pair<point, int> (чтобы пары по описанию точно совпадали в векторе и в сортировке, не важно, будет в обеих случаях int или long), то это ускоряет программу процентов на 30, но все равно время выполнения больше студийного в 6-8 раз.
Кто-то может объяснить мне причины такой ощутимой разницы?
UPD. Если переписать просто на вектор точек (заменить пары на сами точки), то все равно разница сохраняется.
Изменится ли что-то, если сделать
?
или так еще попробуй
А ну и причина в том, что происходит копирование объектов при передаче в функцию. а также вызов функции не инлайнится, поэтому долго получается.
Кстати по поводу inline, есть пример, в котором добавление этого слова реально даёт выигрыш при включенном O2?
в рекурсиях нехило часто помогает
Я не спорю с этим утверждением, но если это действительно так, то не мог бы кто-нибудь объяснить почему?
Ну видимо код инлайнится с некоторой глубиной, что позволяет сократить глубину рекурсии(читать кол-во вызовов функций) в эти несколько раз
У меня есть такой пример. Некоторое время назад решали Московский четвертьфинал 2009, и там была задача I, решающаяся dfs-ом огромной глубины (хотя, я чувствую, существует нормальное решение). Отправили, получили ML (он был 128 МБ), дописали inline к dfs, отправили, получили AC. Потом посмотрели: решение работало примерно в 2 раза быстрее и кушало примерно на 30 метров меньше памяти.
Если просто заинлайнить — никаких изменений.
Если изменить способ передачи в функцию, то очень заметное ускорение. Но все равно GCC далеко позади.
Для 500000 точек время выполнения было 0.45/3.5, стало 0.25/1.
Ну хорошо. Тогда предыдущие изменения + перед
cmpдобавить#pragma GCC optimize ("fast-math")Что теперь?
Без изменений.
Если есть желание что-то пробовать, менять и проверять — отослал полный исходник.
Вы не могли бы дать какую-нибудь ссыль на материал о #pragma GCC optimize. Меня интересует, какого рода optimize можно делать.) И вообще, есть ли смысл делать их вручную?
Это всего лишь механизм, как задать дополнительные
-Oили-fпараметры, если нельзя поменять строку запуска компилятора. То есть, на своём компьютере вместо этой строчки можно было бы просто дописать-ffast-mathк параметрам компилятора.http://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html#index-g_t_0040code_007boptimize_007d-function-attribute-2663
Нет, смысла особого нет, за исключением случая, когда точно знаешь, какую конкретную оптимизацию хочешь включить/выключить.
Спасибо.
Возможно, Visual Studio с оптимизациями по умолчанию догадывается, что копирование point (1) не имеет побочных эффектов и (2) не требуется. И поэтому заменил объявление
на
У меня с mingw-g++ 4.7.2 это локально дало ускорение в несколько раз.
А по-хорошему, учитывая (1) и (2), можно заинлайнить всю функцию. Но у меня g++ наотрез отказывается это делать, даже с
профайлер показывает, что функция есть. Может, кто-то подскажет, как это делается правильно?
UPD: исходник тут.
Вот исходник после всех названных выше оптимизаций.
Теперь я не могу понять, чем же мой код принципиально отличается. Потому как в примере выше — время выполнения примерно одинаковое.
А мой код под студией все равно работает в 3.5 раза быстрее.
Почему не inline bool cmp(const pair <point, int>& a, const pair <point, int>& b)? И почему это эквивалентное объявление дает ускорение небольшое ?:/
На всякий случай замечу, что
const Tдействительно должно быть эквивалентноT const. ЗаписьT const(исправил) понятнее: если слева отconstесть тип, то величину этого типа запрещается менять. Например,int const * const * xозначает, что нельзя менять ниint, ниint *, аint * *менять можно. Ну а если слева отconstничего нет, ему приходится взять следующий тип справа.У меня
constс любой стороны даёт одинаковую скорость. Возможно, случилась погрешность при измерении времени работы.Видимо, так оно и есть. У меня теперь тоже нет разницы.
Кажется, вот еще одно ускорение : stable_sort вместо sort. Видимо, дело в специфике данных.
Можно как-то более конкретно — какая здесь специфика, и в чем отличия между двумя семействами компиляторов в данных условиях? Был бы рад понять это на идейном уровне, ведь не хотелось бы наступать на эти грабли опять, как только условия немножко изменятся:)
Ну, утверждать не берусь, смотреть лень, но, видимо, в MSC++ всегда используется merge_sort, а в g++ sort() начинается с quick_sort, в то время как stable_sort также реализован на merge_sort (про g++ уверен на 95%). В случае, если изначально данные не совершенно случайные — есть частичная отсортированность, много равных элементов, стоимость swap-а очень высока — stable_sort работает быстрее, на случайных же данных quick_sort все-таки быстрее. Можно еще делать вот так: static bool cmp(pnt * a, pnt * b), тогда, если я правильно понимаю, стоимость свопа падает (и, кстати, это действительно дает еще небольшое ускорение, теперь тормозят new), но все равно stable_sort быстрее (почему?...). Вот еще ссылочка http://attractivechaos.wordpress.com/2008/08/28/comparison-of-internal-sorting-algorithms/
Спасибо:) Именно на ответ такого рода я и ждал. В свободное время надо будет поэкспериментировать — покормить ее сортированными/шафленными массивами и остальное в этом духе.
И статья интересная)
Остальным тоже спасибо, хоть я и спрашивал не "как ускорить то, что работает медленно", а "почему оно работает медленно", но тоже узнал много полезного.
Ну, утверждать не берусь, смотреть лень, но, видимо, в MSC++ всегда используется merge_sortЭто не так. Везде в современных реализациях STL в std::sort используются вариации introsort.А почему нельзя в структуре переопределить оператор сравнения? На сколько я помню так должно быстрее вроде работать.
А еще некоторые компиляторы будут ругаться, если будешь передавать значения в него не по ссылке, так что такую ошибку уже не допустишь.
Тут пары сравниваются, так что в структуре не определишь. Да, и у меня почему-то перегруженный оператор< для пар работает дольше чем функция-компаратор.
так пара сравнивает с начала первый операнд, затем второй, а при сравнении в данном случае второй вообще не затрагивается
если хочется скорости, то лучше вообще функтор делать
А чем функтор лучше простой
inline-функции с точки зрения оптимизации?а как ты инлайнить будешь указатель на функцию при компиляции?
если T это конкретный класс, то всё понятно что инлайнить, а если T указатель на функцию void (*)()?
То, что инлайнить, понятно из места вызова, ведь функция
inline, а значит, определена в том же файле.Код: http://pastie.org/7155607
Результат компиляции с
gcc -O2:_Z6test_av: movl $42, %eax ret _Z6test_bv: movl $42, %eax retзабавно, если перед вызовом sort поставить
то время выполнения становится одинаковым, то есть на GCC быстрее