quick sort parallel

Nabend,

ich versuche gerade, quick sort mit mehreren Threads zu implementieren. Der Code funktioniert, alles wird richtig sortiert, leider ergeben sich keinerlei Performance-Verbesserungen im Vergleich zur normalen Version.

std::async scheint nicht das zu machen, was ich glaube. Ich habe 4 echte Kerne, aber egal wieviel threads ich mit async erstelle, im Taskmananger ist immer nur ein Kern ausgelastet und die Laufzeit ändert sich wie gesagt überhaupt nicht. Auch mit std::thread statt std::async ändert sich nichts.

Der Overhead der Threads sollt eigentlich bei der Vectorgröße keinen Einfluss haben. Ich hoffe, ich habe einfach nur irgendetwas kleines übersehen...

MinGW/gcc 4.8.1 unter Windows 7 64bit:

g++ -Wall -ansi -pedantic -O3 -march=native -std=c++11 main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <future>
#include <cstdlib>

void quick_sort(std::vector<int>::iterator first, std::vector<int>::iterator last)
{
    if(last-first>1)
    {
        //find pivot with median of three
        std::vector<int>::iterator mid(first + (last-first)/2);
        if(*first>*mid) std::swap(*first, *mid);
        if(*first>*(last-1)) std::swap(*first, *(last-1));
        if(*(last-1)>*mid) std::swap(*mid, *(last-1));

        //in-place partition
        std::vector<int>::iterator i(first-1), j(last-1);
        for(;;)
        {
            while(*(++i) < *(last-1) );
            while(*(--j) > *(last-1) );
            if(i>=j) break;
            std::swap(*i, *j);
        }
        std::swap(*i, *(last-1));

        quick_sort(first, i);
        quick_sort(i+1, last);
    }
}

void _quick_sort_parallel(std::vector<int>::iterator first,
                          std::vector<int>::iterator last,
                          unsigned remaining_threads)
{
    if(last-first>1)
    {
        //find pivot with median of three
        std::vector<int>::iterator mid(first + (last-first)/2);
        if(*first>*mid) std::swap(*first, *mid);
        if(*first>*(last-1)) std::swap(*first, *(last-1));
        if(*(last-1)>*mid) std::swap(*mid, *(last-1));

        //in-place partition
        std::vector<int>::iterator i(first-1), j(last-1);
        for(;;)
        {
            while(*(++i) < *(last-1) );
            while(*(--j) > *(last-1) );
            if(i>=j) break;
            std::swap(*i, *j);
        }
        std::swap(*i, *(last-1));

        //recursion
        if(remaining_threads)
        {
            std::future<void> thread = std::async(_quick_sort_parallel,first, i, remaining_threads-1);
            quick_sort(i+1, last);

            thread.wait();
        }
        else
        {
            quick_sort(first, i);
            quick_sort(i+1, last);
        }
    }
}

void quick_sort_parallel(std::vector<int>::iterator first, std::vector<int>::iterator last)
{
    _quick_sort_parallel(first, last, 3); //noch bis zu 3 zusaetzliche threads
}

int main()
{
    int size = 100000000;
    std::vector<int> test(size);
    std::generate(test.begin(), test.end(), [](){ return std::rand(); });

    clock_t time01 = clock();
    quick_sort_parallel(test.begin(), test.end());
    clock_t time02 = clock();

    std::cout << (1.0*(time02-time01))/CLOCKS_PER_SEC << " sec\n";
    std::cout << std::is_sorted(test.begin(), test.end()) << '\n';
}

SeppJ

Also wenn ich als lauch policy noch async angebe, dann wird (unter Linux) parallel ausgeführt (unter Linux muss man beim GCC auch noch mit -pthread übersetzen, weiß nicht, wie das unter Windows ist). Das macht aber im Endeffekt auch nur die Kerne heißer für minimalen Zeitgewinn, denn wenn ich das richtig sehe, wird der Löwenanteil der Arbeit bei dir seriell ausgeführt.

Danke, -pthread wars :).