Почему обработка несортированного массива такая же скорость, как и обработка отсортированного массива с помощью современных x86-64 clang?

Я обнаружил этот популярный ~ 9-летний ТАК вопрос и решил перепроверить его результаты.

Итак, у меня AMD Ryzen 9 5950X, clang ++ 10 и Linux, я скопировал код из вопроса и вот что у меня получилось:

Сортировано - 0,549702 с:

~/d/so_sorting_faster$ cat main.cpp | grep "std::sort" && clang++ -O3 main.cpp && ./a.out
    std::sort(data, data + arraySize);
0.549702
sum = 314931600000

Несортированный - 0,546554 с:

~/d/so_sorting_faster $ cat main.cpp | grep "std::sort" && clang++ -O3 main.cpp && ./a.out
    // std::sort(data, data + arraySize);
0.546554
sum = 314931600000

Я почти уверен, что тот факт, что несортированная версия оказалась быстрее на 3 мс, это просто шум, но, похоже, она больше не медленнее.

Итак, что изменилось в архитектуре процессора (чтобы он стал не на порядок медленнее)?

Вот результаты нескольких прогонов:

Unsorted: 0.543557 0.551147 0.541722 0.555599
Sorted:   0.542587 0.559719 0.53938  0.557909

На всякий случай вот мой main.cpp:

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster.
    // std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
    return 0;
}

Обновить

С большим количеством элементов (627680):

Unsorted
cat main.cpp | grep "std::sort" && clang++ -O3 main.cpp && ./a.out
    // std::sort(data, data + arraySize);
10.3814

Sorted:
cat main.cpp | grep "std::sort" && clang++ -O3 main.cpp && ./a.out
    std::sort(data, data + arraySize);
10.6885

Думаю, вопрос еще актуален - разницы почти нет.


person DimanNe    schedule 07.03.2021    source источник
comment
Вы были правы, разместив это как новый вопрос. Это не дубликат, это дополнительный вопрос, и его, безусловно, следует не публиковать в качестве ответа. Если бы вы уже знали, почему этот эффект проявляется с помощью современных инструментов, вы могли бы записать его в форме, которая работала бы как ответ на этот старый вопрос. Но ни одно из предложений @ rsjaffe не было правильным для этого конкретного случая.   -  person Peter Cordes    schedule 08.03.2021
comment
Для записи Это не дубликат Почему обработка отсортированного массива выполняется быстрее, чем обработка несортированного массива? , это продолжение. Компилятор, используемый в этом вопросе, делает другой выбор из исходного вопроса (или флаг оптимизации gcc -O3 делает код медленнее, чем -O2), и объяснение того, что компилятор сделал по-другому (вневетвленная векторизация SIMD), является ответом на этот вопрос. Сообщите мне, если это закроется; Я могу открыть заново. (Но золотые значки в 3 тегах - это все равно только один голос: P) @Mukyuu   -  person Peter Cordes    schedule 08.03.2021
comment
Ok. Таким образом, добавление -O3 является ошибкой, если вы хотите протестировать только процессор. @DimanNe Результаты по-прежнему удивляют с -O0 или -O2?   -  person jpaugh    schedule 09.03.2021
comment
@jpaugh: с -O2: отсортировано: 10,4747, несортировано: 10,4589. С -O1: отсортировано: 27,6086, несортировано: 26,7066. С -O0: отсортировано: 118,997, несортировано: 316,762.   -  person DimanNe    schedule 10.03.2021
comment
Ух ты! Думаю, даже -O1 включает оптимизацию векторизации. Это интересно!   -  person jpaugh    schedule 10.03.2021
comment
исправьте это различие godbolt.org/g/XTCozk, clang-developers.42468.n3.nabble.com/   -  person Ibrahim zawra    schedule 10.03.2021


Ответы (1)


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

В частности, clang ++ 10 с -O3 векторизует внутренний цикл. См. код на godbolt, строки 36-67 сборки. Код немного сложен, но вы точно не заметите какой-либо условной ветки в data[c] >= 128 тесте. Вместо этого он использует инструкции сравнения векторов (pcmpgtd), вывод которых представляет собой маску с единицами для совпадающих элементов и 0 для несоответствий. Последующий pand с этой маской заменяет несовпадающие элементы на 0, так что они не вносят никакого вклада при безусловном добавлении к сумме.

Примерный эквивалент C ++ будет

sum += data[c] & -(data[c] >= 128);

Код фактически сохраняет два работающих 64-битных sum для четных и нечетных элементов массива, так что их можно накапливать параллельно, а затем складывать вместе в конце цикла.

Некоторая дополнительная сложность состоит в том, чтобы позаботиться о знаковом расширении 32-битных data элементов до 64 бит; вот чего достигают такие последовательности, как pxor xmm5, xmm5 ; pcmpgtd xmm5, xmm4 ; punpckldq xmm4, xmm5. Включите -mavx2, и вы увидите на его месте более простой vpmovsxdq ymm5, xmm5.

Код также выглядит длинным, потому что цикл был развернут, обрабатывая 8 элементов data за итерацию.

person Nate Eldredge    schedule 07.03.2021
comment
Также обратите внимание, что clang по умолчанию разворачивает небольшие циклы (в отличие от GCC); если вы хотите увидеть самый простой вариант векторизации, используйте -fno-unroll-loops. godbolt.org/z/z6WYG9. (Я добавил -march=nehalem, чтобы включить SSE4, включая pmovsxdq sign-extension, чтобы сделать asm проще, чем с расширением знака вручную. Как ни странно, даже без него он все равно обрабатывает только 8 байтов за раз, не используя punpckldq + punpckhdq для использования низкого и высокие половины нагрузки + результат сравнения. Честно говоря, иногда GCC стреляет себе в ногу, не используя более узкие нагрузки, когда он должен быть широким: /) - person Peter Cordes; 08.03.2021
comment
Кроме того, вероятно, было бы лучше для стратегии clang (с SSE4.2 от -march=nehalem) использовать pmovsxdq xmm, [mem] загрузки и расширить сравнение до 64-бит, а не расширять результат сравнения. GCC выполняет 16-байтовые загрузки, как я упоминал в моем первом комментарии. С SSE4 требуется 2 перетасовки, чтобы подписать два верхних маскированных элемента (все же, вероятно, оно того стоит), а без SSE4 это чистая победа против clang, чтобы получить вдвое больше работы с каждым pcmpgtd / pand с исходными данными, и даже продление знака может делить часть работы между половинами. godbolt.org/z/nWhz3n - person Peter Cordes; 08.03.2021
comment
В любом случае, да, ответ на этот вопрос заключается в том, что он автоматически векторизуется. Как правило, компиляторы не выбирают идеальных стратегий. (Хотя GCC может быть оптимальным для SSE2 или SSE4.) - person Peter Cordes; 08.03.2021
comment
Также по теме: Флаг оптимизации gcc -O3 делает код медленнее, чем -O2 для того же кода, где безотказный (без векторизации) невыгоден для сортировки, и вам понадобится PGO (оптимизация с помощью профиля), чтобы GCC сделал оптимальный выбор: не выполнять if-преобразование, если вы используете старый GCC или компилируете с -fno-tree-vectorize. - person Peter Cordes; 08.03.2021
comment
Итак ... компилятор с годами стал лучше :) - person Michael Dorgan; 11.03.2021