Добрый вечер.

Ситуация следующая, есть учебно-развивающий проект, цель которого реализовать быструю сортировку в 2 и более потоков, при этом основная задача, чтобы производительность данной сортировки была не менее, чем на 50% быстрее однопоточной STL реализации sort.

Сортируем вектор, забитый 1млном случайных интов.

Алгоритм взять из умной книжки, и в однопоточном варианте к нему претензий нет, в условиях случайного заполнения массива работает в пределах до 10% медленнее std::sort, тут важно заметить, что значения меняются в небольшой диапазоне, в отличие от двухпоточного варианта, о чём напишу ниже.

Собственно, основная проблема в быстродействии функции потока, где точно сам не пойму. Узкие места - доступ к общим ресурсам, в данном случае это глобальный стек, ну и дальше посмотрите сами.

Очереди реализованы на std::stack. Логика работы следующая: есть глобальная очередь, до запуска потоков в неё помещаюся "координаты" отрезка, который нужно сортировать. Изначально это 0 и vector.size(). В целом ставится задача, чтобы в глобальной очереди, постоянно находился хотя бы 1 элемент, чтобы всегда была работа, для освободившегося потока.
Сначала проверяем пуста ли локальная и есть ли что-нибудь в глобальной очереди, если условия верны, забираем отрезок из глобальной очереди в локальную.
Далее сортируем локальную очередь до тех пор, пока в ней не будет 2+ элементов и, т.к. на данный момент глобальная очередь пуста, останавливаем сортировку, откладываем в глобальную очередь 1 отрезок, чтобы дать работу второму потоку.
После идут условия завершения работы, либо ожидания.
Работа завершается, если обе очереди пусти и все потоки, кроме данного, находятся в состоянии ожидания на переменной условия.
Либо, если очереди пусты, но есть ещё работающие потоки, поток переходит в ожидание на переменной условия.




В общем-то, эта функция работает и в 2 потока сортирует где-то на 30-40% быстрее std::sort, но иногда проскакивают результаты на 60-70% быстрее (скорость работы std::sort всегда примерно одинакова, +- 10 мс).. ну и такое положение дел говорит о том, что есть проблемы. Так как я их не вижу, прошу вас указать на них. И вообще буду рад любым советам по теме, как увеличить "скорость работы" данной функции, или же, как уменьшить использование мутексов/переменной условия и т.п.

Прикрутил таймер и потестил.. почему-то второй последующие потоки не стартуют, пока первый не закончит работу...

функция, которая запускает потоки выглядит так:



может проблема в ней и есть способ лучше поднимать потоки?

хотя это на винде под cygwin'ом.. ну бубунте вроде бы запускаются одновременно..   

Это сообщение отредактировал(а) NoviceF - 2.12.2012, 09:56

NoviceF, открой для себя библиотеку boost::thread, а конкретнее, boost::thread_group - это то, что тебе нужно.

Да с удовольствием бы, но в условиях задачи использовать именно pthread :(

Хотя, наверное, попробую сделать альтернативную реализацию на бусте..