Блог

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

Мой код выглядит следующим образом:

 #include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

void troca (int *v, int i, int j);
int partition (int *v, int ini, int fim);
void quicksort (int *v, int ini, int fim, int size);

typedef struct {
    int ini, mid, fim;
} thread_arg;

int size;
int *v;

void *thread_func(void* arg){
    thread_arg *a = arg;
    quicksort(v, a->ini, a->mid, a->fim);
    printf("done inn");
    return NULL;
}

int main()
{
    // initializations
    scanf("%d", amp;size);
    v = malloc(size * sizeof(int));

    // read array
    for (int i = 0; i < size;   i)
        scanf("%d", amp;v[i]);

    // arguments
    thread_arg argument1, argument2;
    int mid = partition(v, 0, size-1);

    argument1.ini = 0;
    argument1.mid = mid-1;
    argument1.fim = size;

    argument2.ini = mid;
    argument2.mid = size-1;
    argument2.fim = size;

    pthread_t thread1, thread2;    

    // thread and execution
    pthread_create(amp;thread1, NULL, thread_func, amp;argument1);
    printf("done out 1n");
    pthread_create(amp;thread2, NULL, thread_func, amp;argument2);
    printf("done out 2n");

    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);

    free(v);

    return 0;
}

void quicksort (int *v, int ini, int fim, int size){
    if (ini >= fim)
        return;
    int meio = partition(v, ini, fim);
    quicksort(v, ini, meio-1, size);
    quicksort(v, meio 1, fim, size);
}

int partition (int *v, int ini, int fim){
    int i = ini-1, j = ini;
    troca(v, (ini fim)/2, fim);
    int pivo = v[fim];

    for (; j < fim;   j)
    {
        if (v[j] <= pivo)
        {
            i  ;
            troca(v, i, j);
        }
    }
    troca(v, i 1, fim);
    return i 1; //indice do pivo;
}


void troca (int *v, int i, int j){
    int aux = v[i];
    v[i] = v[j];
    v[j] = aux;
    return;
}
 

Выполнение работает и сортируется отлично, оно генерирует 2 новых независимых потока, которые сортируют половинки массива каждый. Проблема в том, что он не делает это одновременно. Запуск программы с вводом 100 миллионов случайных чисел:

 done out 1
done out 2
done in
done in

real    0m47,464s
user    0m50,686s
sys     0m0,452s
 

Но для появления первых 3 строк требуется около 25 секунд, а для последней — ~ 25, что указывает на то, что второй поток ожидает запуска первого.

В htop консоли кажется, что в какой-то момент оба выполняются одновременно (это подтверждается тем фактом, что эта программа работает немного быстрее, чем моя обычная)

Наконец, я понимаю, что небезопасно работать одновременно с такого рода данными, но в этом примере сортировки все должно быть в порядке.

Вы несправедливо распределяете работу между потоками. Чтобы увидеть это, измените свой код следующим образом:

     // thread and execution
    pthread_create(amp;thread1, NULL, thread_func, amp;argument1);
    printf("done out 1 (%d)n", argument1.mid - argument1.ini   1);
    pthread_create(amp;thread2, NULL, thread_func, amp;argument2);
    printf("done out 2 (%d)n", argument2.mid - argument2.ini   1);
 

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

Например, вот несколько запусков с использованием случайных данных:

выполнено 1 (66474145)
выполнено 2 (33525855)

выполнено 1 (21794872)
выполнено 2 (78205128)

выполнено 1 (67867800)
выполнено 2 (32132200)

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

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

Чтобы доказать это, я добавил unsigned long* аргумент quicksort и заставил его увеличивать значение, на которое ссылается указанный указатель при каждом вызове (по сути, подсчитывая количество вызовов каждого потока quicksort ), и я запустил его с 10M (не 100M) случайными значениями. Количество потоков 1 составило 3 851 991, а количество потоков 2 составило 9 693 697. Конечно, могут быть небольшие различия между двумя подсчетами из-за случайности при генерации списка. Но разница составляет почти в 3 раза, что гораздо более значительно, чем вы могли ожидать от небольших случайных изменений.