Вопрос, наверное, из раздела для начинающих, но там вроде бы не встречал вопросов по многопоточности, поэтому пишу сюда.

Суть проблемы в следующем - задача отсортировать вектор интов с помощью 2х(!) потоков и получить заметный прирост производительности, по сравнению с однопоточным вариантом.

есть такой код

http://liveworkspace.org/code/33f03fd7f5a3...dcf521c4ea53fb2

это сортировка слиянием, выполненная, видимо, странным и неправильным образом. Там берётся вектор, делится на 2 отдельных вектора пополам, после чего каждый из 2х получившихся полувекторов отдаётся потоку для сортировки (всего 2 потока). После того, как потоки производят сортировку каждый своего вектора, эти векторы объединяются в один с помощью того же слияния. 

Проблема заключается в том, что по сравнению с однопоточной версией, производительность(ну то есть по моим представлениям это время выполнения программы) либо не меняется, либо падает.

Вопросы такой: как по-другому можно организовать "сортировку вектора в 2 потока", чтобы получить видимый прирост в производительности по сравнению с однопоточной версией.

Спасибо.

Если проверяешь на Debug-версии, то результат может быть какой угодно. Проверь на Release.
Если же проверяешь на Release, то результат тоже можно попытаться объяснить

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

на релизе скорее всего однопоточная тоже обгонит

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

А как организовать программу, чтобы был прирост при сортировке в 2 потока? 

У меня откуда-то есть предположение, что основной упор делается на то, что однопоточные приложения обрабатываются одним ядром ЦПУ, если потоков больше, должно задействоваться и второе.. Может какой-то ключ при компиляции  добавлять?   

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

почитайте для начала по ссылкам, интересно
http://habrahabr.ru/post/143055/
http://kimrgrey.livejournal.com/4775.html

еще припоминаю одну историю: был конкурс на написание одной программы. не помню, что она должна была делать, помню только что это конкурс intel на лучшую многопоточную программу.
некоторое время первое место было за программой, написанной на С++. и вот появилась программа (она и заняла 1е место), которая была производительней в 6(!) раз. Если сравнить код, программы практически идентичны, отличались парой строк (т.е. логически они делали одно и то же одинаковым способом), только потоки запускаются в другой последовательности. программа победителя выясняла, какие ядра относятся к одному процессору (а значит у них общий кэш), и на основе этого распределяла потоки.

Ещё у azesmcar в подписи интересная ссылка (не конкретно про сортировку, а вообще о многопоточности)

особенно эта http://www.data-race.com/2011/01/14/%D0%B4...B5%D0%B4%D0%B5/

Добавлено через 2 минуты и 31 секунду
Есть интересный алгоритм сортировки слиянием на основе построения бимонотонной (т.е. состоящей из двух монотонных частей) последовательности, Bitonic Merge Sort

Спасибо за комменты, буду ознакамливаться.

Умопомрачительная процедура!
Вектора миллионного размера, прямым копированием, да еще в рекурсии. 
Естественно тут не дополнительное ядро процессора нужно, а дополнительный DMA контроллер с дополнительной шиной данных (интересно такое вообще бывает?)
NoviceF,  есть же в языке константные ссылки (указатели в конце концов).
Нужно пользоваться ими, начиная уже со структур размером > разрядности платформы (т.е. > 4/8 байтов) 
А уж мегабайтные вектора передавать копированием, это самоубийство.
Хорошо, если у вас оптимизатор сам подставил ссылки (в чем я очень и очень сомневаюсь).

Вопрос был не в эффективности самого алгоритма, т.к. оба подхода и однопоточный и двухпоточный использовали одну и ту же реализацию алгоритма. Писал его не я и, честно говоря, было ещё чем заняться, кроме как оптимизацией алгоритма 


И хотелось бы покаяться перед всеми отписавшимися, т.к. вся инфа, что я писал выше получилось в результате кривой проверки, хотя о том, что она кривая я как-то не задумывался. Дело в том, что тестировал я следующим образом, сделал в одном проекте 2 срр файла, с функцией main в каждом, после чего для теста исключал из сборки первый файл, компилировал, проверял. Затем наоборот исключал 2й файл, отменял исключение первого, компилировал, проверял.. Ну и там ещё иногда использовался ключ для профилировщика gprof.

Вчера решил всётаки ради эксперимента разбить на 2 проекта.. и результат удивил.. В общем двухпоточная версия выполняется на 60-80% быстрее.. Так что извиняюсь за то, что ввёл в заблуждение.

Ну и вопрос, может у кого есть идеи, почему при первом варианте (с двумя поочередёно отключаемыми cpp файлами в одном проекте) результат был одинаковыми, хотя в сборке учавствовали файлы с разным кодом?

Это сообщение отредактировал(а) NoviceF - 7.11.2012, 08:33

Скорей всего у вас в ваших проектах разные настройки. (не только оптимизация)
Для надежности нужно в одном проекте собирать.
Т.е. первый случай как-раз более корректный.

Если кому-то еще интересно. В блоге победителя конкурса есть подробное описание

http://www.1024cores.net/home/in-russian/h...-i-ocen-bystrye