Параллельная быстрая сортировка: рекурсия с использованием Boost Bind?

Question

Я работаю над параллельной быстрой сортировкой, потоки - первая попытка. Версия без резьбы сортируется правильно, а с резьбой - нет (не удивительно). Что мне показалось интересным, так это когда я удалил потоки, но сохранил вызовы boost :: bind, он все еще не работает. Если boost :: bind не то, что я хочу, пожалуйста, предложите предложение. Казалось, что Bind - это самый простой (или единственный) способ заставить мою функцию работать с потоками наддува.

void Quicksort( fVec &Array, const int Left, const int Right )
{
    if( Right <= Left )
        return;

    int pivot = Left;
    const int pivotNewIndex = Partition( Array, Left, Right, pivot );

    // These function calls make it work fine
    //Quicksort( Array, Left, pivotNewIndex - 1 );
    //Quicksort( Array, pivotNewIndex + 1, Right );

    // boost::bind calls only swaps one element, doesn't actually sort
    boost::bind( &Quicksort, Array, Left, pivotNewIndex - 1 )();
    boost::bind( &Quicksort, Array, pivotNewIndex + 1, Right )();

    // threaded version that doesn't work, same as above
    //boost::thread threadA( boost::bind( &Quicksort, Array, Left, pivotNewIndex - 1 ) );
    //threadA.join();
    //boost::thread threadB( boost::bind( &Quicksort, Array, pivotNewIndex + 1, Right ) );
    //threadB.join();
}

Answer 1

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

boost::bind( &Quicksort, Array, Left, pivotNewIndex - 1 )();
boost::bind( &Quicksort, Array, pivotNewIndex + 1, Right )();

Я предполагаю, что первый аргумент состоит в том, что все портит. Я думаю, что bind требует, чтобы аргументы были копируемыми, а ссылки на самом деле не таковы; вероятно, это создание копии и передача ссылки на нее, поэтому ничего не меняется. Попробуйте:

boost::bind( &Quicksort, boost::ref(Array), Left, pivotNewIndex - 1 )();
boost::bind( &Quicksort, boost::ref(Array), pivotNewIndex + 1, Right )();

Было бы полезно узнать, что такое fVec и почему вы не передаете указатель на массив того, что вы сортируете.

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

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