Russian Qt Forum

Добрый день

Навеяно этим http://www.prog.org.ru/topic_26946_0.html (http://www.prog.org.ru/topic_26946_0.html), но там мои попытки завязать содержательный разговор не имели успеха :)  Типа "ну вот есть средства (Concurrent, QThread) - вот ими и пользуйся". Наверное подразумевается что если уж выучил средства по букварю, то все самой получится. Но вот чего-то у меня не выходит :) Псевдокод задачи

C++ (Qt)
void Merge(int *A, int first, int last)
{
  // что-то делаем с массивом
}
 
void MergeSort(int *A, int first, int last)
{
  MergeSort(A, first, (first+last)/2); //сортировка левой части
  MergeSort(A, (first+last)/2+1, last); //сортировка правой части
  Merge(A, first, last); //слияние двух частей
}
 
void main()
{
  ...
  MergeSort(A, 1, n); 
  ...
}
 

Как же будем "разпоточивать"? Да, и давайте по-взрослому: число созданных потоков не должно превышать число ядер

Спасибо

В простом случае, нет нужды распоточивать рекурсию.
Например, можно запустить две нитки, каждой дать по половине массива. Дождаться их завершения и объединить их в запускающей нитке. Или запустить четыре и дать каждой по четверти массива.

Ну четыре надо сначала получить. А две - это всего 2 ядра, а сейчас 8 - пройденный этап, да и 16 никого не удивить. Да и даже 2 - как запускать-то? (в смысле куда встроить код запуска).

По поводу смысла: начиная так метров со 100 данных - он появляется очень быстро 

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

Раскидать это можно и на 8 ядер. Например, в запускаемый создаём две нитки, внутри себя они создают ещё две рабочих.

Добрался до компьютера:

C++ (Qt)
int main()
{
    ...
 
    std::thread th1( std::bind( &MergeSort, A, first, (first+last)/2 ) );
    std::thread th2( std::bind( &MergeSort, A, (first+last)/2+1, last ) );
    th1.join();
    th2.join();
    Merge( A, first, last );
}
 

Да, красиво с bind. Но все-таки это hard-coded для 2 ниток. Да, можно для 4, но все равно решение остается hard-coded. И предлагаю не частить, а послушать что люди скажут. Поэтому беру паузу  :)

Такое легко можно сделать для любого количества ниток. Главное требование, что это количество делилось на 2, но для этого алгоритма это вполне адекватное требование.
Реальных ниток будет больше, на каждую пару +1

Эта задача аналогична распараллеливанию transform из этой темы http://www.prog.org.ru/topic_25963_15.html (http://www.prog.org.ru/topic_25963_15.html)
Где вместо std::transform нужно поставить MergeSort)

В том-то и дело что нет, в данном случае число задач неизвестно заранее.

Вам это ничего (никого) не напоминает? :) "Прошу исполнить"

А вы про что/кого?

Не вопрос.

Ловите:

C++ (Qt)
void sort( int *A, int first, int last, unsigned int numthread )
{
        assert( A );
        assert( first < last );
 
        if( numthread )
        {
                thread th1( bind( &sort, A, first, (first+last)/2, numthread - 1 ) );
                thread th2( bind( &sort, A, (first+last)/2+1, last, numthread - 1 ) );
                th1.join();
                th2.join();
        }
        else
        {
                thread th1( bind( &mergeSort, A, first, (first+last)/2 ) );
                thread th2( bind( &mergeSort, A, (first+last)/2+1, last ) );
                th1.join();
                th2.join();
        }
        merge( A, first, last );
}
 

numthread - это необходимое количество квадратов пар потоков.

Можно сделать красивей, но мне пока лень. :)

Ааа.. понятненько)

Ну так old уже предложил вариант)
Думаю, что ещё можно эту рекурсию в компил тайме раскрутить.. (через мета шаблонную магию)

Это (может быть) помогло бы девушке сдать лабу, но не более того. Формально да, все нитки запущены, но ведь они толкаются и ждут друг друга. Производительность/КПД такой реализации ужасна.

Да, и UI кто-то всегда должен сопли подтирать, нечего там всем рассиживаться на join.

Что за глупости? Никто там не толкается. Опять вас понесло в голословные утверждения про производительность и КПД? :)
Всю основную работу делает заданное количество ниток рекурсивно. Дополнительные нити ждут их и процессор не едят. Если начнете думать, то и с UI все будет в порядке.

Это реализация сделанная на коленке за несколько минут, можно избавиться от объединяющих ниток, но нужно писать дополнительный код. Мне лень, да и не даст это особого прироста.

Так что очень ждем от вас "профессиональную" реализацию и будем сравнивать. :)