Почему цикл for с многопоточностью не будет иметь такой же высокой производительности, как с однопоточным?

Question

Почему цикл for с многопоточностью не будет иметь такой же высокой производительности, как с однопоточным?

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

int main()
{
    constexpr int N = 100000;

    std::random_device rd;
    std::mt19937 mt(rd());
    std::uniform_real_distribution<double> ini(0.0, 10.0);

    // single-thread
    {
        std::vector<int> vec(N);
        for(int i = 0; i < N; ++i)
        {
            vec[i] = ini(mt);
        }

        auto start = std::chrono::system_clock::now();

        for(int i = 0; i < N; ++i)
        {
            vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
        }

        auto end = std::chrono::system_clock::now();
        auto dur = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
        std::cout << "single : " << dur << " ms."<< std::endl;
    }

    // multi-threading (Th is the number of threads)
    for(int Th : {1, 2, 4, 8, 16})
    {
        std::vector<int> vec(N);
        for(int i = 0; i < N; ++i)
        {
            vec[i] = ini(mt);
        }

        auto start = std::chrono::system_clock::now();

        std::vector<std::future<void>> fut(Th);
        for(int t = 0; t < Th; ++t)
        {
            fut[t] = std::async(std::launch::async, [t, &vec, &N, &Th]{
                for(int i = t*N / Th; i < (t + 1)*N / Th; ++i)
                {
                    vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
                }
            });
        }
        for(int t = 0; t < Th; ++t)
        {
            fut[t].get();
        }

        auto end = std::chrono::system_clock::now();
        auto dur = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
        std::cout << "Th = " << Th << " : " << dur << " ms." << std::endl;
    }

    return 0;
}

Среда исполнения:

OS : Windows 10 64-bit
Build-system : Visual Studio Community 2015
CPU : Core i5 4210U

При сборке этой программы в режиме отладки результат был, как я и ожидал:

single : 146 ms.
Th = 1 : 140 ms.
Th = 2 : 71 ms.
Th = 4 : 64 ms.
Th = 8 : 61 ms.
Th = 16 : 68 ms.

Это говорит о том, что код, не использующий std::async, справедливо имеет ту же производительность, что и код, использующий однопоточный режим, и при использовании 4 или 8 потоков я могу получить отличную производительность.

Однако в режиме Release я получил другой результат (N: 100000 -> 100000000):

single : 54 ms.
Th = 1 : 443 ms.
Th = 2 : 285 ms.
Th = 4 : 205 ms.
Th = 8 : 206 ms.
Th = 16 : 221 ms.

Мне интересно этот результат. Только для последних половинных кодов многопоточность имеет лучшую производительность, чем одиночная. Но самый быстрый - это первые полукоды, которые не используют std::async. Я знаю тот факт, что оптимизация и издержки, связанные с многопоточностью, сильно влияют на производительность. Тем не мение,

Процесс - это просто вычисление вектора, так что можно оптимизировать не в многопоточных кодах, а в однопоточных кодах?
Эта программа не содержит ничего о мьютексе, атомах и т. Д., И конфликт данных может не произойти. Я думаю, что издержки вокруг многопоточности будут относительно небольшими.
Загрузка ЦП в кодах, не использующих std::async, меньше, чем в многопоточных кодах. Эффективно ли использовать большую часть процессора?

Обновление: я пытался исследовать векторизацию. Я включил /Qvec-report:1 варианты и получил тот факт:

//vectorized (when N is large)
for(int i = 0; i < N; ++i)
{
    vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}

//not vectorized
auto lambda = [&vec, &N]{
    for(int i = 0; i < N; ++i)
    {
        vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
    }
};
lambda();

//not vectorized
std::vector<std::future<void>> fut(Th);
for(int t = 0; t < Th; ++t)
{
    fut[t] = std::async(std::launch::async, [t, &vec, &N, Th]{
        for(int i = t*N / Th; i < (t + 1)*N / Th; ++i)
        {
            vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
        }
    });
}

и время выполнения:

single (with vectorization) : 47 ms.
single (without vectorization)  : 70 ms.

Был уверен, что цикл for не был векторизован в многопоточной версии. Тем не менее, версия требует много времени и по другим причинам.

Обновление 2: я переписал for-loop в лямбда-выражении (тип A - тип B):

//Type A (the previous one)
fut[t] = std::async(std::launch::async, [t, &vec, &N, Th]{
    for(int i = t*N / Th; i < (t + 1)*N / Th; ++i)
    {
        vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
    }
});

//Type B (the new one)
fut[t] = std::async(std::launch::async, [t, &vec, &N, Th]{
    int nb = t * N / Th;
    int ne = (t + 1) * N / Th;
    for(int i = nb; i < ne; ++i)
    {
        vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
    }
});

Тип Б работал хорошо. Результат:

single (vectorized) : 44 ms.
single (invectorized) : 77 ms.
--
Th = 1 (Type A) : 435 ms.
Th = 2 (Type A) : 278 ms.
Th = 4 (Type A) : 219 ms.
Th = 8 (Type A) : 212 ms.
--
Th = 1 (Type B) : 112 ms.
Th = 2 (Type B) : 74 ms.
Th = 4 (Type B) : 60 ms.
Th = 8 (Type B) : 61 ms.

Результат типа B понятен (многопоточные коды будут работать быстрее, чем однопоточные векторизованные коды, и не так быстро, как векторизованные коды). С другой стороны, тип A кажется эквивалентным типу B (только с использованием временных переменных), но они показывают разную производительность. Два типа могут рассматриваться как генерирующие разные ассемблерные коды.

Обновление 3: я мог бы найти фактор, который замедлял многопоточный цикл for. Это деление в состоянии for, Это однопоточный тест:

//ver 1 (ordinary)
fut[t] = std::async(std::launch::async, [&vec, &N]{
    for(int i = 0; i < N; ++i)
    {
        vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
    }
});

//ver 2 (introducing a futile variable Q)
int Q = 1;
fut[t] = std::async(std::launch::async, [&vec, &N, Q]{
    for(int i = 0; i < N / Q; ++i)
    {
        vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
    }
});

//ver 3 (using a temporary variable)
int Q = 1;
fut[t] = std::async(std::launch::async, [&vec, &N, Q]{
    int end = N / Q;
    for(int i = 0; i < end; ++i)
    {
        vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
    }
});

//ver 4 (using a raw value)
fut[t] = std::async(std::launch::async, [&vec]{
    for(int i = 0; i < 100000000; ++i)
    {
        vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
    }
});

И время работы:

ver 1 : 132 ms.
ver 2 : 391 ms.
ver 3 : 47 ms.
ver 4 : 43 ms.

Вер 3 и 4 были хорошо оптимизированы, а вер 1 был не таким большим, потому что я думаю, что компилятор не мог поймать N как неизменный, хотя N был constexpr, Я думаю, что версия 2 была очень медленной по той же причине. Компилятор не понимал, что N и Q не будут меняться. Итак, состояние i < N / Q потребуются тяжелые ассемблерные коды, которые замедляют цикл for.

6

c++ multithreading performance c++11 stdasync

Источник

user5988875 27 фев '16 в 05:29

1 ответ

Решение

Другие вопросы по тегам c++ multithreading performance c++11 stdasync

user5128211 27 фев '16 в 11:36 2016-02-27 11:36 · Accepted Answer · 2016-02-27 11:36

Когда вы запускаете однопоточный, ваш единственный поток имеет vec в кешах, как вы только что создали его из Mt. И он будет продолжать потоковую передачу через кэши, поскольку это единственный пользователь всех уровней кэша.
Я не думаю, что здесь происходит большая векторизация, иначе у вас будет меньше времени. Хотя я могу ошибаться, поскольку пропускная способность памяти является ключевым моментом здесь. Ты смотрел на асм?

Любые другие темы должны были бы получить оперативную память. Само по себе это не является большой проблемой в вашем случае, так как это один процессор, поэтому L3 используется совместно, а набор данных в любом случае больше, чем L3.
НО, несколько потоков, борющихся за L3, плохо. Я думаю, что это главный фактор здесь.
Вы запускаете слишком много потоков. Вы должны запустить столько потоков, сколько у вас ядер, чтобы платить меньше за переключение контекста и засорение кэша.
HT полезен, когда потоки 2 hw имеют достаточно "дыр" в конвейерах (здесь не так), BP (здесь не так) и в использовании кеша (сильный пример здесь -> см. #1).
Я на самом деле удивлен>2 темы не ухудшились намного больше --- в настоящее время процессоры потрясающие!
Время запуска потока и сроки меньше, чем предсказуемо. Если вы хотите большей предсказуемости, запускайте потоки постоянно и используйте дешевую сигнализацию, чтобы запустить их и уведомить, что они сделаны.

РЕДАКТИРОВАТЬ: ответы на конкретные вопросы

Процесс - это просто вычисление вектора, так что можно оптимизировать не в многопоточных кодах, а в однопоточных кодах?

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

C = 16; // try other C values?
for(int i=nb; i<ne; i+=C) {
  for(int j=0; j<C; j++)
    vec[i+j] = ...; // that's === vec[i] <<= 2;
}
// need to do the remainder....

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

Эта программа не содержит ничего о мьютексе, атомах и т. Д., И конфликт данных может не возникнуть. Я думаю, что издержки вокруг многопоточности будут относительно небольшими.

Правда. За исключением того, что потоки могут начинаться в свое время. Особенно на Windows и особенно если их много.

Загрузка ЦП в кодах, не использующих std:: async, меньше, чем в многопоточных кодах. Эффективно ли использовать большую часть процессора?

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