C ++ сортировка медленнее с потоками

Question

Я реализовал алгоритм сортировки слиянием в C ++.
Внутри алгоритмов он проверяет, больше ли размер массива, чем min_size_to_thread и является ли он: рекурсивно вызывает функцию с потоками.

Но когда я увеличиваю min_size_to_thread: что уменьшает количество используемых потоков, функция становится быстрее.Даже при переходе от 1 до 2 потоков.

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

template <typename T>
void merge_sort(T S[], int S_size, int min_size_to_thread)
{
    if (S_size < 2) return;

    // Left Sequence
    int L_size = S_size / 2;
    T* L = new T[L_size];
    for (int i = 0; i < L_size; i++)
    {
        L[i] = S[i];
    }

    // Right Sequence
    int R_size = (S_size + 1) / 2;
    T* R = new T[R_size];
    for (int i = 0; i < R_size; i++)
    {
        R[i] = S[i + L_size];
    }

    if (S_size > min_size_to_thread)
    {
        std::thread thread_left(merge_sort<T>, L, L_size, min_size_to_thread);
        std::thread thread_right(merge_sort<T>, R, R_size, min_size_to_thread);
        thread_right.join();
        thread_left.join();
    }
    else
    {
        merge_sort<T>(L, L_size, min_size_to_thread);
        merge_sort<T>(R, R_size, min_size_to_thread);
    }

    int S_iterator = 0;
    int L_iterator = 0;
    int R_iterator = 0;

    while ((L_iterator < L_size) && (R_iterator < R_size))
    {
        if (L[L_iterator] < R[R_iterator])
        {
            S[S_iterator] = L[L_iterator];
            ++L_iterator;
        }
        else
        {
            S[S_iterator] = R[R_iterator];
            ++R_iterator;
        }
        ++S_iterator;
    }

    while (L_iterator < L_size)
    {
        S[S_iterator] = L[L_iterator];
        ++L_iterator;
        ++S_iterator;
    }

    while (R_iterator < R_size)
    {
        S[S_iterator] = R[R_iterator];
        ++R_iterator;
        ++S_iterator;
    }

    delete[] L;
    delete[] R;
}

int main()
{
    const int S_size = 500000;
    unsigned char S[S_size];
    for (int i = 0; i < S_size; ++i)
    {
        S[i] = i % 255;
    }

    int min_size_to_thread;

    min_size_to_thread = 250;
    auto t1 = std::chrono::high_resolution_clock::now();
    merge_sort(S, S_size, min_size_to_thread);
    auto t2 = std::chrono::high_resolution_clock::now();
    std::cout << "size > " << min_size_to_thread << ": " << (t2 - t1) / std::chrono::milliseconds(1) << std::endl;

    for (int i = 0; i < S_size; ++i)
    {
        S[i] = i % 255;
    }

    min_size_to_thread = 500;
    t1 = std::chrono::high_resolution_clock::now();
    merge_sort(S, S_size, min_size_to_thread);
    t2 = std::chrono::high_resolution_clock::now();
    std::cout << "size > " << min_size_to_thread << ": " << (t2 - t1) / std::chrono::milliseconds(1) << std::endl;

    for (int i = 0; i < S_size; ++i)
    {
        S[i] = i % 255;
    }

    min_size_to_thread = 1000;
    t1 = std::chrono::high_resolution_clock::now();
    merge_sort(S, S_size, min_size_to_thread);
    t2 = std::chrono::high_resolution_clock::now();
    std::cout << "size > " << min_size_to_thread << ": " << (t2 - t1) / std::chrono::milliseconds(1) << std::endl;

    for (int i = 0; i < S_size; ++i)
    {
        S[i] = i % 255;
    }

    min_size_to_thread = 10000;
    t1 = std::chrono::high_resolution_clock::now();
    merge_sort(S, S_size, min_size_to_thread);
    t2 = std::chrono::high_resolution_clock::now();
    std::cout << "size > " << min_size_to_thread << ": " << (t2 - t1) / std::chrono::milliseconds(1) << std::endl;

    for (int i = 0; i < S_size; ++i)
    {
        S[i] = i % 255;
    }

    min_size_to_thread = 250000;
    t1 = std::chrono::high_resolution_clock::now();
    merge_sort(S, S_size, min_size_to_thread);
    t2 = std::chrono::high_resolution_clock::now();
    std::cout << "size > " << min_size_to_thread << ": " << (t2 - t1) / std::chrono::milliseconds(1) << std::endl;

    for (int i = 0; i < S_size; ++i)
    {
        S[i] = i % 255;
    }

    min_size_to_thread = 500000;
    t1 = std::chrono::high_resolution_clock::now();
    merge_sort(S, S_size, min_size_to_thread);
    t2 = std::chrono::high_resolution_clock::now();
    std::cout << "size > " << min_size_to_thread << ": " << (t2 - t1) / std::chrono::milliseconds(1) << std::endl;

    return 0;
}

Answer 1

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

size > 250: 169
size > 500: 85
size > 1000: 50
size > 10000: 29
size > 250000: 42
size > 500000: 89

Основываясь на снимке экрана, я понял, что вы запускаете свой код из Visual Studio. Кнопка запуска по умолчанию прикрепит отладчик к вашему исполняемому файлу и снизит производительность во время выполнения. Вместо этого нажмите Ctrl + F5 для запуска без отладчика или из меню Debug -> Start Without Debugging.

Answer 2

Я думаю, что это проблема с кэшированием. Чтобы быть точным ложное совместное использование замедляет алгоритм, потому что данные записываются на страницы, совместно используемые несколькими потоками. (Различные ядра процессоров стараются не отставать от страниц совместно используемой памяти). Если min_size_to_thread кратно размеру страницы вашего процессора, а ваш массив выровнен на странице - границы, производительность увеличивается. В этом случае страницы не будут разделены между потоками.

Я всегда ограничиваю создание потоков постоянной величиной, не имеет смысла запускать 100 потоков на четырехъядерном компьютере только для сортировки массива. Запуск нескольких потоков на одном ядре стоит из-за интенсивного переключения контекста. По моему опыту, максимальное число потоков всегда равно числу ядер, умноженному на 2. Одно ядро ​​может обрабатывать около 2 потоков без стоимость исполнения . Для четырехъядерного процессора программа должна запускать максимум 8 потоков одновременно. Это означает, что алгоритм может создать 8 подпотоков, родительский поток просто join s потоков, или создать 7 подпотоков, запустить часть алгоритма в родительском потоке и, наконец, join других 7 потоков .

Всегда в профиле, это может иметь совершенно другую причину.