Защо обработката на сортиран масив е по-бърза от обработката на несортиран масив?

Question

Още

Източник Не AMP-версия Редактиране на

Защо обработката на сортиран масив е по-бърза от обработката на несортиран масив?

Ето част от код на C++, който показва много странно поведение. По някаква странна причина сортирането на данните като по чудо прави кода почти шест пъти по-бърз:

#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;
}

Без std::sort(data, data + arraySize); кодът се изпълнява за 11,54 секунди.
Със сортираните данни кодът се изпълнява за 1,93 секунди.

Първоначално си помислих, че това може да е просто езикова или компилаторна аномалия, затова опитах с Java:

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

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

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

С подобен, но не толкова екстремен резултат.

Първата ми мисъл беше, че сортирането вкарва данните в кеша, но след това си помислих колко глупаво е това, защото масивът е току-що генериран.

Какво се случва?
Защо обработката на сортиран масив е по-бърза от обработката на несортиран масив?

Кодът сумира някои независими членове, така че редът не би трябвало да има значение.

Meraj al Maksud

Редактиран въпрос Направете октомври 2019 в 1:35

Програмиране

java c++ performance optimization branch-prediction

Направете юни 2012 в 1:51

22 изгледи

Daniel Fischer

Източник Не AMP-версия Редактиране на

Предвиждане на клона.

При сортиран масив условието data[c] >= 128 първо е фалшиво за поредица от стойности, а след това става истина за всички следващи стойности. Това е лесно да се предвиди. При несортиран масив плащате за разходите за разклоняване.

Shankar

Редактиран отговор Направете август 2016 в 7:53

3968

0

Коментари (9)

WiSaGaN

Източник Не AMP-версия Редактиране на

Причината, поради която производителността се подобрява драстично, когато данните са сортирани, е, че се премахва наказанието за предсказване на разклонения, както е обяснено прекрасно в Mysticial's answer.

Сега, ако разгледаме кода

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

можем да открием, че смисълът на този конкретен клон if... else... е да добави нещо, когато дадено условие е изпълнено. Този тип разклонение може лесно да се трансформира в условна инструкция за преместване, която би била компилирана в условна инструкция за преместване: cmovl, в система x86. Разклонението и по този начин потенциалното наказание за предсказване на разклонението се премахва.

В C, а следователно и в C++, операторът, който би се компилирал директно (без оптимизация) в инструкция за условно преместване в x86, е тройният оператор ... ? ... : .... Затова преписваме горния оператор в еквивалентен:

sum += data[c] >=128 ? data[c] : 0;

Като запазваме четимостта, можем да проверим коефициента на ускорение.

На процесор Intel Core i7-2600K @ 3,4 GHz и Visual Studio 2010 Release Mode бенчмаркът е (форматът е копиран от Mysticial):

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

Резултатът е стабилен при многократни тестове. Получаваме голямо ускорение, когато резултатът от разклонението е непредсказуем, но страдаме малко, когато е предсказуем. Всъщност, когато използваме условен ход, производителността е една и съща, независимо от модела на данните.

Сега нека'разгледаме по-отблизо, като изследваме генерираното от тях асембли x86. За по-голяма простота използваме две функции max1 и max2.

max1 използва условното разклонение if... else ...:

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2 използва тройния оператор ... ? ... : ...:

int max2(int a, int b) {
    return a > b ? a : b;
}

На машина x86-64, `GCC -S`` генерира асемблито по-долу.

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2 използва много по-малко код благодарение на използването на инструкцията cmovge. Но истинската печалба е, че max2 не включва скокове на разклонение, jmp, които биха имали значително наказание за производителността, ако предсказаният резултат не е верен.

И така, защо условният ход се представя по-добре?

В един типичен процесор x86 изпълнението на една инструкция е разделено на няколко етапа. Приблизително имаме различен хардуер за работа с различните етапи. Така че не е необходимо да чакаме една инструкция да приключи, за да започнем нова. Това се нарича pipelining.

В случай на разклонение следващата инструкция се определя от предходната, така че не можем да направим pipelining. Трябва или да изчакаме, или да предвидим.

В случай на условно преместване изпълнението на условната инструкция за преместване е разделено на няколко етапа, но по-ранните етапи като Fetch и Decode не зависят от резултата на предишната инструкция; само последните етапи се нуждаят от резултата. По този начин изчакваме част от времето за изпълнение на една инструкция'. Ето защо версията с условен ход е по-бавна от разклонението, когато предсказването е лесно.

В книгата Computer Systems: A Programmer's Perspective, second edition това е обяснено подробно. Можете да проверите раздел 3.6.6 за Инструкции за условно преместване, цялата глава 4 за Архитектура на процесора и раздел 5.11.2 за специално разглеждане на Предоставяне на разклонението и наказания за неправилно предвиждане.

Понякога някои съвременни компилатори могат да оптимизират нашия код на асемблер с по-добра производителност, а понякога някои компилатори не могат (въпросният код използва родния компилатор на Visual Studio'). Познаването на разликата в производителността между разклонение и условен ход при непредсказуемост може да ни помогне да напишем код с по-добра производителност, когато сценарият стане толкова сложен, че компилаторът не може да ги оптимизира автоматично.

Peter Mortensen

Редактиран отговор Направете май 2019 в 12:50

3212

0

Коментари (9)

Mysticial · Accepted Answer · 2012-06-27T13:56:42+00:00

Вие сте жертва на провал на branch prediction.

Какво е предвиждане на клонове?

Да разгледаме един железопътен възел: ![Изображение, показващо железопътен възел](//i.stack.imgur.com/muxnt.jpg) Image by Mecanismo, via Wikimedia Commons. Използвано под лиценза CC-By-SA 3.0. Сега, в името на аргументацията, да предположим, че това е в далечната 1800 г. - преди комуникацията на дълги разстояния или радиовръзката. Вие сте оператор на прелез и чувате, че идва влак. Нямате представа в коя посока трябва да се движи той. Спирате влака, за да попитате машиниста коя посока иска да избере. И след това настройвате стрелката по подходящ начин. Влаковете са тежки и имат голяма инерция. Затова им отнема цяла вечност да потеглят и да намалят скоростта си. Има ли по-добър начин? Отгатнете в коя посока ще се движи влакът!

Ако сте познали правилно, влакът продължава да се движи.
Ако сте познали грешно, капитанът ще спре, ще се върне назад и ще ви извика да завъртите ключа. След това той може да тръгне отново по другия път. Ако всеки път отгатвате правилно, влакът никога няма да спира.
Ако грешите твърде често, влакът ще прекарва много време в спиране, връщане назад и рестартиране.

Разгледайте if-изречението: На ниво процесор то е инструкция за разклоняване: ![Екранна снимка на компилиран код, съдържащ инструкция if](//i.stack.imgur.com/pyfwC.png) Вие сте процесор и виждате разклонение. Нямате представа накъде ще тръгне. Какво ще направите? Спирате изпълнението и изчаквате, докато предишните инструкции приключат. След това продължавате по правилния път. Съвременните процесори са сложни и имат дълги конвейери. Затова им отнема цяла вечност да "загреят" и "забавят". Има ли по-добър начин? Отгатнете в коя посока ще тръгне клонът!
Ако сте познали правилно, продължавате изпълнението.
Ако сте познали погрешно, трябва да промиете тръбопровода и да се върнете към клона. След това можете да започнете отново по другия път. Ако всеки път отгатвате правилно, изпълнението никога няма да се налага да спира.
Ако грешите твърде често, ще прекарате много време в спиране, връщане назад и рестартиране.

Това е предсказване на разклонения. Признавам, че това'не е най-добрата аналогия, тъй като влакът би могъл просто да сигнализира за посоката с флагче. Но в компютрите процесорът не знае в коя посока ще тръгне даден клон до последния момент. Така че как стратегически бихте предположили, за да сведете до минимум броя на случаите, в които влакът трябва да се върне назад и да тръгне по другия път? Поглеждате към предишната история! Ако влакът отива наляво в 99% от случаите, тогава предполагате наляво. Ако влакът се движи последователно, тогава редувате предположенията си. Ако влакът върви по един път на всеки три пъти, предполагате едно и също... С други думи, опитвате се да идентифицирате модел и да го следвате. Това е приблизително начинът, по който работят клоновите прогнози. Повечето приложения имат добре поддържани клонове. Така че съвременните предсказвачи на разклонения обикновено постигат >90 % успеваемост. Но когато се сблъскат с непредсказуеми разклонения без разпознаваеми модели, предсказателите на разклонения са практически безполезни. Допълнително четене: статия в Уикипедия.

Както бе подсказано по-горе, виновникът е тази if-заявка:

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

Забележете, че данните са равномерно разпределени между 0 и 255. Когато данните са сортирани, приблизително първата половина от итерациите няма да влезе в if-заявлението. След това всички те ще влязат в if-изречението. Това е много благоприятно за предсказващия клон, тъй като клонът последователно преминава в една и съща посока много пъти. Дори обикновен насищащ брояч ще предскаже правилно разклонението, с изключение на няколкото итерации, след като то смени посоката си. Бърза визуализация:

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

Когато обаче данните са напълно случайни, предсказателят на разклонения се оказва безполезен, защото не може да предсказва случайни данни. По този начин вероятно ще има около 50 % грешно предсказване (не по-добро от случайното отгатване).

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

И така, какво може да се направи? Ако компилаторът не'е в състояние да оптимизира разклонението в условен ход, можете да опитате някои хакове, ако сте готови да пожертвате четливостта в полза на производителността. Заменете:

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

с:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

Това елиминира разклонението и го замества с някои битови операции. (Имайте предвид, че този хак не е строго еквивалентен на оригиналната if-заявка. Но в този случай тя е валидна за всички входни стойности на data[].) Образец: Core i7 920 @ 3,5 GHz C++ - Visual Studio 2010 - версия x64

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - NetBeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

Наблюдения:

С клона: Има огромна разлика между сортираните и несортираните данни.
При Hack: Няма разлика между сортираните и несортираните данни.
В случая със C++ хакването всъщност е малко по-бавно, отколкото с клона, когато данните са сортирани. Общото правило е да се избягва разклоняването, зависещо от данните, в критични цикли (като в този пример).

Актуализация:
GCC 4.6.1 с -O3 или -ftree-vectorize на x64 е в състояние да генерира условен ход. Така че няма разлика между сортираните и несортираните данни - и двете са бързи.
VC++ 2010 не е в състояние да генерира условни ходове за този клон дори под /Ox.
Intel C++ Compiler (ICC) 11 прави нещо чудотворно. Той разменя двата цикъла, като по този начин вдига непредсказуемия клон към външния цикъл. Така че той не само е имунизиран срещу грешните прогнози, но и е два пъти по-бърз от всичко, което VC++ и GCC могат да генерират! С други думи, ICC се възползва от тестовия цикъл, за да победи еталона...
Ако дадете на компилатора на Intel кода без разклонения, той просто го векторизира... и е също толкова бърз, колкото и с разклонението (с размяна на цикъла). Това показва, че дори зрелите съвременни компилатори могат да варират значително в способността си да оптимизират кода...

Защо обработката на сортиран масив е по-бърза от обработката на несортиран масив?

Вие сте жертва на провал на branch prediction.

Какво е предвиждане на клонове?

Както бе подсказано по-горе, виновникът е тази if-заявка: