22 Вопрос: Почему обработка отсортированного массива быстрее, чем обработка несортированного массива?

вопрос создан в Tue, Jun 4, 2019 12:00 AM

Вот фрагмент кода на 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);
    }
}

с похожим, но менее экстремальным результатом.

Сначала я подумал, что сортировка переносит данные в кеш, но потом я подумал, насколько это глупо, потому что массив только что сгенерирован.

  • Что происходит?
  • Почему обработка отсортированного массива быстрее, чем обработка несортированного массива? Код суммирует некоторые независимые термины, поэтому порядок не должен иметь значения.
23151
  1. Только для записи. На Windows /VS2017 /i7-6700K 4GHz нет никакой разницы между двумя версиями. Это занимает 0,6 с в обоих случаях. Если количество итераций во внешнем цикле увеличивается в 10 раз, то время выполнения увеличивается в 10 раз до 6 с в обоих случаях.
    2017-11-15 20: 45: 37Z
  2. @ user194715: любой компилятор, который использует cmov или другую реализацию без ответвлений (например, автоматическую векторизацию с pcmpgtd), будет иметь производительность, не зависящую от данных какого-либо ЦП. Но если он ветвистый, он будет зависеть от сортировки на любом процессоре с нестандартным спекулятивным выполнением. (Даже высокопроизводительные центральные процессоры используют предсказание ветвлений, чтобы избежать пузырей извлечения /декодирования на взятых ветвях; штраф за промах меньше).
    2017-12-26 07: 14: 57Z
  3. @ KyleMit это как-то связано с обоими? Я не слишком много читал об обоих
    2018-01-10 06: 26: 02Z
  4. @ mohitmun, оба этих недостатка безопасности вписываются в широкую категорию уязвимостей, классифицированных как атаки« внедрение цели ветвления »
    2018-01-10 14: 26: 37Z
  5. 22 ответа                              22                         

    Вы стали жертвой прогноза ветвления .

    Что такое прогнозирование ветвей?

    Рассмотрим железнодорожный узел:

     Изображение, показывающее железнодорожный узел Изображение от Mecanismo, с помощью Wikimedia Commons. Используется по лицензии CC-By-SA 3.0 . р>

    Теперь, ради аргумента, предположим, что это еще в 1800-х годах - до дальней связи или радиосвязи.

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

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

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

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

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

    Рассмотрим оператор if: На уровне процессора это инструкция перехода:

    Снимок экрана скомпилированного кода, содержащего оператор if

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

    Современные процессоры сложны и имеют длинные конвейеры. Таким образом, им нужно «разогреваться» и «замедляться» вечно.

    Есть ли лучший способ? Вы угадываете, в каком направлении пойдет ветка!

    • Если вы угадали, вы продолжаете выполнять.
    • Если вы угадали, вам нужно очистить конвейер и вернуться к ответвлению. Затем вы можете перезапустить другой путь.

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

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

    Итак, как бы вы стратегически предположили, чтобы минимизировать количество раз, когда поезд должен вернуться назад и пойти по другому пути? Вы смотрите на прошлую историю! Если поезд уходит в 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 ГГц

    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 ++ хак на самом деле медленнее, чем с веткой, когда данные сортируются.

    Общее правило - избегать ветвления, зависящего от данных, в критических циклах (например, в этом примере).

    Update:

    • GCC 4.6.1 с -O3 или -ftree-vectorize на x64 может генерировать условное перемещение. Таким образом, нет никакой разницы между отсортированными и несортированными данными - они оба быстрые.

    • VC ++ 2010 не может сгенерировать условные перемещения для этой ветви даже под /Ox.

    • Компилятор Intel C ++ (ICC) 11 совершает нечто чудесное. Это чередует два цикла , тем самым поднимая непредсказуемую ветвь во внешний цикл. Таким образом, он не только защищает от неправильных предсказаний, но и в два раза быстрее, чем любой другой VC ++ и GCC могут генерировать! Другими словами, ICC воспользовался тестовым циклом, чтобы победить тест ...

    • Если вы дадите компилятору Intel код без ответвлений, он просто векторизует его ... и будет так же быстро, как и с веткой (с обменом циклами).

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

        
    30295
    2019-05-27 12: 42: 11Z
    1. @ Mysticial Чтобы избежать взлома смещения, вы можете написать что-то вроде int t=-((data[c]>=128)) для генерации маски. Это тоже должно быть быстрее. Было бы интересно узнать, достаточно ли умен компилятор для вставки условного перемещения или нет.
      2012-06-27 16: 47: 51Z
    2. @ phonetagger Посмотрите на этот вопрос: stackoverflow.com/questions/11276291/… Компилятор Intel приблизился к полному избавлению от внешнего цикла.
      2012-07-10 17: 08: 39Z
    3. @ Novelocrat Только половина из них является правильной. Сдвиг 1 в знаковый бит, когда он равен нулю, действительно является UB. Это потому, что это целочисленное переполнение со знаком. Но сдвиг 1 из знака-бита - это IB. Сдвиг вправо отрицательного целого числа со знаком - IB. Вы можете перейти к аргументу, что этот C /C ++ не требует, чтобы старший бит был индикатором знака. Но детали реализации IB.
      2013-08-18 21: 04: 38Z
    4. @ Mysticial Большое спасибо за ссылку. Это выглядит многообещающе. Я пойду, хотя это. Последний запрос Извините, но, пожалуйста, не возражайте, не могли бы вы сказать мне, как вы могли бы сделать это int t = (data[c] - 128) >> 31; sum += ~t & data[c];, чтобы заменить первоначальное условие if выше?
      2014-03-08 20: 05: 22Z
    5. Грамматика во мне хочет, чтобы я подумал, что это должно читаться как "... жертва предсказания ветвления не удалась ure ", а не просто ".. . Жертва предсказания ветвления не удалась. "
      2015-06-27 11: 35: 58Z

    Прогноз ветвления.

    Для отсортированного массива условие data[c] >= 128 сначала составляет false для последовательности значений, а затем становится true для всех последующих значений. Это легко предсказать. С несортированным массивом вы платите за стоимость ветвления.

        
    3907
    2016-08-05 07: 53: 10Z
    1. Предсказание ветвлений работает лучше на отсортированных массивах по сравнению с массивами с разными шаблонами? Например, для массива - > {10, 5, 20, 10, 40, 20, ...} следующий элемент в массиве из шаблона - 80. Будет ли ускорен этот тип массива с помощью предсказания перехода, в котором следующий элемент равен 80, если образец следует? Или это обычно помогает только с отсортированными массивами?
      2014-09-23 18: 58: 12Z
    2. Таким образом, в основном все, что я обычно узнал о big-O, находится вне окна? Лучше понести стоимость сортировки, чем стоимость ветвления?
      2014-10-30 07: 51: 58Z
    3. @ AgrimPathak Это зависит. Для не слишком больших входных данных алгоритм с более высокой сложностью быстрее, чем алгоритм с более низкой сложностью, когда константы меньше для алгоритма с более высокой сложностью.Где точка безубыточности может быть трудно предсказать. Кроме того, сравните это , местность важна. Big-O важен, но это не единственный критерий эффективности.
      2014-10-30 10: 14: 12Z
    4. Когда происходит предсказание перехода? Когда язык узнает, что массив отсортирован? Я думаю о ситуации с массивом, который выглядит следующим образом: [1,2,3,4,5, ... 998,999,1000, 3, 10001, 10002]? это неясное 3 увеличит время работы? Это будет так же долго, как и несортированный массив?
      2014-11-09 13: 37: 18Z
    5. @ FilipBartuzi Предсказание ветвлений происходит в процессоре ниже уровня языка (но язык может предлагать способы сообщить компилятору о том, что вероятно, поэтому компилятор может испускать подходящий код к этому). В вашем примере отклонение 3 приведет к ошибочному прогнозированию ветвлений (для соответствующих условий, когда 3 дает результат, отличный от 1000), и, следовательно, обработка этого массива, вероятно, займет пару десятков или сотен наносекунд дольше, чем отсортированный массив, вряд ли когда-нибудь заметный. То, что стоит времени, - это высокий уровень неправильных прогнозов, одно неправильное прогнозирование на 1000 не очень много.
      2014-11-09 13: 49: 37Z

    Причина, по которой производительность резко улучшается при сортировке данных, заключается в том, что штраф за предсказание ветвления снят, как прекрасно объясняется в ответ Mysticial .

    Теперь, если мы посмотрим на код

     
    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 ГГц и режиме выпуска Visual Studio 2010 эталонный тест (формат скопирован из Mysticial):

    x86

     
    //  Branch - Random
    seconds = 8.885
    
    //  Branch - Sorted
    seconds = 1.528
    
    //  Branchless - Random
    seconds = 3.716
    
    //  Branchless - Sorted
    seconds = 3.71
    

    64

     
    //  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 выполнение инструкции делится на несколько этапов. Грубо говоря, у нас разные аппаратные средства для разных этапов. Поэтому нам не нужно ждать окончания одной инструкции, чтобы начать новую. Это называется конвейерная обработка .

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

    В случае условного перемещения выполнение команды условного перемещения делится на несколько этапов, но более ранние этапы, такие как Fetch и Decode, не зависят от результата предыдущей инструкции; только последним этапам нужен результат. Таким образом,мы ждем часть времени выполнения одной инструкции. Вот почему версия условного перемещения медленнее, чем ветвь, когда предсказание легко.

    Книга Компьютерные системы: взгляд программиста, второе издание объясняет это подробно. Вы можете проверить раздел 3.6.6 для Инструкции условного перемещения , всю главу 4 для Архитектура процессора и раздел 5.11.2 для специальной обработки для предсказания и неправильного предсказания ветвления Штрафы .

    Иногда некоторые современные компиляторы могут оптимизировать наш код для сборки с большей производительностью, иногда некоторые компиляторы не могут (рассматриваемый код использует собственный компилятор Visual Studio). Зная разницу в производительности между ветвлением и условным перемещением, когда он непредсказуем, может помочь нам написать код с лучшей производительностью, когда сценарий становится настолько сложным, что компилятор не может оптимизировать их автоматически.

        
    3144
    2019-05-27 12: 50: 22Z
    1. Нет уровня оптимизации по умолчанию, если вы не добавите -O в свои командные строки GCC. (И вы не можете иметь худший английский, чем мой;)
      2012-06-28 14: 04: 45Z
    2. Мне трудно поверить, что компилятор может оптимизировать троичный оператор лучше, чем эквивалентный оператор if. Вы показали, что GCC оптимизирует троичный оператор для условного перемещения; Вы не показали, что это не делает то же самое для оператора if. Фактически, согласно Mystical выше, GCC действительно оптимизирует оператор if для условного перемещения, что делает этот ответ совершенно неверным.
      2012-06-30 15: 29: 23Z
    3. @ WiSaGaN Код ничего не демонстрирует, потому что ваши две части кода компилируются в один и тот же машинный код. Чрезвычайно важно, чтобы люди не понимали, что выражение if в вашем примере отличается от terenary в вашем примере. Это правда, что вы признаете сходство в своем последнем абзаце, но это не стирает тот факт, что остальная часть примера вредна.
      2012-10-11 03: 12: 02Z
    4. @ WiSaGaN Мое отрицательное голосование определенно превратится в повышательное, если вы измените свой ответ, чтобы удалить вводящий в заблуждение пример -O0 и показать разницу в optimized asm в двух ваших тестах.
      2012-10-11 04: 13: 03Z
    5. @ UpAndAdam На момент тестирования VS2010 не может оптимизировать исходную ветку в условное перемещение даже при указании высокого уровня оптимизации, в то время как gcc может.
      2013-09-14 15: 18: 02Z

    Если вам интересно еще больше возможностей оптимизации этого кода, подумайте об этом:

    Начиная с оригинального цикла:

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

    С помощью обмена циклами мы можем смело изменить этот цикл на:

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

    Затем вы можете видеть, что условие if является постоянным на протяжении всего цикла i, поэтому вы можете вывести if наружу:

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

    Затем вы видите, что внутренний цикл можно свернуть в одно отдельное выражение, предполагая, что это допускает модель с плавающей запятой (например, /fp:fast)

     
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
        {
            sum += data[j] * 100000;
        }
    }
    

    Это в 100 000 раз быстрее, чем раньше.

        
    2159
    2019-05-27 12: 51: 33Z
    1. Если вы хотите обмануть, вы можете также вывести умножение за пределы цикла и выполнить sum * = 100000 после цикла.
      2012-10-11 01: 48: 01Z
    2. @ Майкл - я считаю, что этот пример на самом деле является примером оптимизация с циклическим подъемом (LIH), а НЕ замена цикла . В этом случае весь внутренний цикл не зависит от внешнего цикла и поэтому может быть выведен из внешнего цикла, после чего получается результат просто умножить на сумму более i из одной единицы = 1e5. Это не имеет никакого значения для конечного результата, но я просто хотел исправить запись, так как это такая часто посещаемая страница.
      2013-03-04 12: 59: 11Z
    3. Хотя не в простом духе обмена циклами, внутренний if в этой точке может быть преобразован в: sum += (data[j] >= 128) ? data[j] * 100000 : 0;, который компилятор может уменьшить до cmovge или эквивалентный.
      2013-05-15 11: 57: 16Z
    4. Внешний цикл должен сделать время, затрачиваемое внутренним циклом, достаточно большим для профилирования. Так почему бы вам не поменять местами. В конце концов, этот цикл все равно будет удален.
      2016-06-22 15: 45: 19Z
    5. @ saurabheights: Неверный вопрос: почему компилятор НЕ поменяет цикл. Микробенчмарки это сложно;)
      2016-12-29 13: 58: 53Z

    Несомненно, некоторые из нас будут заинтересованы в способах идентификации кода, который проблематичен для предсказателя ветвления ЦП. Инструмент Valgrind cachegrind имеет симулятор предсказания ветвлений, включаемый с помощью флага --branch-sim=yes. Выполнение этого в примерах, приведенных в этом вопросе, с числом внешних циклов, уменьшенным до 10000 и скомпилированным с g++, дает следующие результаты:

    Сортировка:

     
    ==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
    ==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
    ==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )
    

    Unsorted:

     
    ==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
    ==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
    ==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )
    

    Детализация до построчного вывода, произведенного cg_annotate, мы видим для рассматриваемого цикла:

    Сортировка:

     
              Bc    Bcm Bi Bim
          10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
               .      .  .   .      {
               .      .  .   .          // primary loop
     327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
               .      .  .   .          {
     327,680,000 10,006  0   0              if (data[c] >= 128)
               0      0  0   0                  sum += data[c];
               .      .  .   .          }
               .      .  .   .      }
    

    Unsorted:

     
              Bc         Bcm Bi Bim
          10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
               .           .  .   .      {
               .           .  .   .          // primary loop
     327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
               .           .  .   .          {
     327,680,000 164,050,007  0   0              if (data[c] >= 128)
               0           0  0   0                  sum += data[c];
               .           .  .   .          }
               .           .  .   .      }
    

    Это позволяет легко идентифицировать проблемную строку - в несортированной версии строка if (data[c] >= 128) вызывает 164 050 007 неправильно предсказанных условных переходов (Bcm) в модели предсказателя ветвления в cachegrind, тогда как в отсортированной версии она вызывает только 10 006.

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

     
    perf stat ./sumtest_sorted
    

    Сортировка:

     
     Performance counter stats for './sumtest_sorted':
    
      11808.095776 task-clock                #    0.998 CPUs utilized          
             1,062 context-switches          #    0.090 K/sec                  
                14 CPU-migrations            #    0.001 K/sec                  
               337 page-faults               #    0.029 K/sec                  
    26,487,882,764 cycles                    #    2.243 GHz                    
    41,025,654,322 instructions              #    1.55  insns per cycle        
     6,558,871,379 branches                  #  555.455 M/sec                  
           567,204 branch-misses             #    0.01% of all branches        
    
      11.827228330 seconds time elapsed
    

    Unsorted:

     
     Performance counter stats for './sumtest_unsorted':
    
      28877.954344 task-clock                #    0.998 CPUs utilized          
             2,584 context-switches          #    0.089 K/sec                  
                18 CPU-migrations            #    0.001 K/sec                  
               335 page-faults               #    0.012 K/sec                  
    65,076,127,595 cycles                    #    2.253 GHz                    
    41,032,528,741 instructions              #    0.63  insns per cycle        
     6,560,579,013 branches                  #  227.183 M/sec                  
     1,646,394,749 branch-misses             #   25.10% of all branches        
    
      28.935500947 seconds time elapsed
    

    Он также может делать аннотации исходного кода с разборкой.

     
    perf record -e branch-misses ./sumtest_unsorted
    perf annotate -d sumtest_unsorted
    
     
     Percent |      Source code & Disassembly of sumtest_unsorted
    ------------------------------------------------
    ...
             :                      sum += data[c];
        0.00 :        400a1a:       mov    -0x14(%rbp),%eax
       39.97 :        400a1d:       mov    %eax,%eax
        5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
        4.60 :        400a26:       cltq   
        0.00 :        400a28:       add    %rax,-0x30(%rbp)
    ...
    

    Подробнее см. руководство по повышению эффективности .

        
    1800
    2012-10-18 19: 20: 21Z
    1. Это страшно, в несортированном списке должна быть 50% вероятность попадания при добавлении. Каким-то образом предсказание ветвлений имеет только 25% промахов, как это может быть лучше, чем промах 50%?
      2013-12-09 04: 00: 09Z
    2. @ tall.b.lo: 25% от всех ветвей - в цикле две ветви, одна для data[c] >= 128 (что имеет промах 50%, как вы предлагаете) и один для условия цикла c < arraySize, который имеет промах ~ 0%.
      2013-12-09 04: 29: 25Z

    Я только что прочитал этот вопрос и его ответы и чувствую, что ответа не хватает.

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

    Этот подход работает в общем случае, если:

    1. это небольшая таблица, которая, вероятно, будет кэшироваться в процессоре, и
    2. вы работаете в довольно узком цикле, и /или процессор может предварительно загрузить данные.

    Ваckground и почему

    С точки зрения процессора, ваша память работает медленно. Чтобы компенсировать разницу в скорости, в ваш процессор встроена пара кешей (кеш L1 /L2). Итак, представьте, что вы делаете свои хорошие вычисления и выясните, что вам нужен кусок памяти. Процессор выполнит операцию загрузки и загрузит часть памяти в кеш, а затем использует кеш для выполнения остальных вычислений. Поскольку память относительно медленная, эта «загрузка» замедлит вашу программу.

    Как и в случае с прогнозированием переходов, он был оптимизирован в процессорах Pentium: процессор прогнозирует, что ему нужно загрузить часть данных, и пытается загрузить их в кэш, прежде чем операция действительно попадет в кэш. Как мы уже видели, предсказание ветвления иногда идет ужасно неправильно - в худшем случае вам нужно вернуться назад и фактически ожидать загрузки памяти, которая будет длиться вечно (иными словами : неудачное предсказание ветвления плохо загрузка памяти после сбоя прогнозирования ветвления просто ужасна! ).

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

    Первое, что нам нужно знать, это что такое маленький ? Хотя меньше, как правило, лучше, практическое правило заключается в том, чтобы придерживаться таблиц поиска, размер которых < = 4096 байт. В качестве верхнего предела: если ваша справочная таблица больше 64 КБ, вероятно, ее стоит пересмотреть.

    Построение таблицы

    Итак, мы выяснили, что можем создать небольшую таблицу. Следующее, что нужно сделать, это установить на место функцию поиска. Функции поиска обычно представляют собой небольшие функции, которые используют несколько основных целочисленных операций (и, или, xor, shift, add, remove и, возможно, умножение). Вы хотите, чтобы ваш ввод был переведен с помощью функции поиска в некий «уникальный ключ» в вашей таблице, который затем просто дает вам ответ на всю работу, которую вы хотели, чтобы он делал.

    В этом случае: > = 128 означает, что мы можем сохранить значение, < 128 означает, что мы избавляемся от этого. Самый простой способ сделать это - использовать 'И': если мы сохраняем это, мы И это с 7FFFFFFF; если мы хотим избавиться от него, мы И это с 0. Отметим также, что 128 - это степень 2 - так что мы можем пойти дальше и составить таблицу из 32768/128 целых чисел и заполнить ее одним нулем и множеством 7FFFFFFFF лет.

    Управляемые языки

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

    Ну, не совсем ...: -)

    Была проделана определенная работа по удалению этой ветки для управляемых языков. Например:

     
    for (int i = 0; i < array.Length; ++i)
    {
       // Use array[i]
    }
    

    В этом случае для компилятора очевидно, что граничное условие никогда не будет выполнено. По крайней мере компилятор Microsoft JIT (но я ожидаю, что Java делает подобные вещи) заметит это и вообще уберет проверку. Вау, это означает, что нет ветви. Точно так же это будет иметь дело с другими очевидными случаями.

    Если у вас возникли проблемы с поиском на управляемых языках - ключ заключается в том, чтобы добавить & 0x[something]FFF в вашу функцию поиска, чтобы сделать проверку границ предсказуемой, - и наблюдать, как она идет быстрее.

    Результат этого дела

     
    // Generate data
    int arraySize = 32768;
    int[] data = new int[arraySize];
    
    Random random = new Random(0);
    for (int c = 0; c < arraySize; ++c)
    {
        data[c] = random.Next(256);
    }
    
    /*To keep the spirit of the code intact, I'll make a separate lookup table
    (I assume we cannot modify 'data' or the number of loops)*/
    
    int[] lookup = new int[256];
    
    for (int c = 0; c < 256; ++c)
    {
        lookup[c] = (c >= 128) ? c : 0;
    }
    
    // Test
    DateTime startTime = System.DateTime.Now;
    long sum = 0;
    
    for (int i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (int j = 0; j < arraySize; ++j)
        {
            /* Here you basically want to use simple operations - so no
            random branches, but things like &, |, *, -, +, etc. are fine. */
            sum += lookup[data[j]];
        }
    }
    
    DateTime endTime = System.DateTime.Now;
    Console.WriteLine(endTime - startTime);
    Console.WriteLine("sum = " + sum);
    Console.ReadLine();
    
        
    1259
    2019-01-16 04: 47: 21Z
    1. Вы хотите обойти предсказатель ветвления, почему? Это оптимизация.
      2013-04-24 17: 50: 33Z
    2. Поскольку ни одна ветвь не лучше ветки :-) Во многих ситуациях это просто намного быстрее ... если вы оптимизируете, это определенно стоит пытаться. Они также используют его в f.ex. graphics.stanford.edu/~seander/bithacks.html
      2013-04-24 21: 57: 13Z
    3. В общем случае таблицы поиска могут быть быстрыми, но вы запускали тесты для этого конкретного условия? Вы по-прежнему будете иметь условие ветвления в своем коде, только теперь оно перемещено в часть генерации справочной таблицы. Вы все еще не получили бы свой перфоманс
      2013-12-19 21: 45: 03Z
    4. @ Зейн, если вы действительно хотите знать ... Да: 15 секунд с веткой и 10 секунд с моей версией. В любом случае, это полезная техника, которую нужно знать в любом случае.
      2013-12-20 18: 57: 29Z
    5. Почему бы не sum += lookup[data[j]], где lookup - это массив с 256 записями, первые из которых равны нулю, а последние равны индексу?
      2014-03-12 12: 17: 49Z

    Поскольку данные распределяются между 0 и 255 при сортировке массива, примерно первая половина итераций не будет входить в if-утверждение (оператор if представлен ниже).

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

    Вопрос в том, что делает вышеприведенное утверждение не выполненным в некоторых случаях, например, в случае отсортированных данных? Здесь появляется «предсказатель ветви». Предиктор ветвления - это цифровая схема, которая пытается угадать, каким образом пойдет ветвь (например, структура if-then-else), прежде чем это станет известно наверняка. Целью предиктора ветвления является улучшение потока в конвейере команд. Предсказатели ветвлений играют решающую роль в достижении высокой эффективной производительности!

    Давайте сделаем несколько тестов, чтобы лучше понять это

    Производительность выражения if зависит от того, имеет ли его состояние предсказуемый характер. Если условие всегда истинно или всегда ложно, логика предсказания ветвления в процессоре подберет шаблон. С другой стороны, если модель непредсказуема, то заявление if будет намного дороже.

    Давайте измерим производительность этого цикла при разных условиях:

     
    for (int i = 0; i < max; i++)
        if (condition)
            sum++;
    

    Вот время цикла с различными шаблонами истина-ложь:

     
    Condition                Pattern             Time (ms)
    -------------------------------------------------------
    (i & 0×80000000) == 0    T repeated          322
    
    (i & 0xffffffff) == 0    F repeated          276
    
    (i & 1) == 0             TF alternating      760
    
    (i & 3) == 0             TFFFTFFF…           513
    
    (i & 2) == 0             TTFFTTFF…           1675
    
    (i & 4) == 0             TTTTFFFFTTTTFFFF…   1275
    
    (i & 8) == 0             8T 8F 8T 8F …       752
    
    (i & 16) == 0            16T 16F 16T 16F …   490
    

    Шаблон «strong> bad » true-false может сделать утверждение в if раз в шесть раз медленнее шаблона « good »! Конечно, какой шаблон хорош, а какой плох, зависит от точных инструкций, сгенерированных компилятором, и от конкретного процессора.

    Таким образом, нет никаких сомнений относительно влияния прогноза ветвления на производительность!

        
    1129
    2019-02-27 10: 58: 32Z
    1. Вы не показываете время "случайного" паттерна TF.
      2013-02-23 02: 31: 21Z
    2. @ MooingDuck 'Потому что это не будет иметь значения - это значение может быть любым, но оно все равно будет в пределах этих порогов. Так зачем показывать случайное значение, когда вы уже знаете пределы? Хотя я согласен с тем, что вы могли бы показать один из них для полноты картины и «просто ради этого».
      2016-03-28 12: 58: 51Z
    3. @ cst1992: Сейчас его самый медленный тайминг - TTFFTTFFTTFF, который, на мой взгляд, вполне предсказуем. Случайность по своей природе непредсказуема, поэтому вполне возможно, что она будет еще медленнее и, таким образом, выходит за пределы, показанные здесь. OTOH, это может быть, что TTFFTTFF отлично попадает в патологический случай. Не могу сказать, так как он не показывал случайные сроки.
      2016-03-28 18: 27: 16Z
    4. @ MooingDuck Для человеческого глаза "TTFFTTFFTTFF" - это предсказуемая последовательность, но мы говорим здесь о поведении предиктора ветвления, встроенного в ЦП. Предиктором ветвления является не распознавание образов на уровне AI; это очень просто Когда вы просто чередуете ветви, это не очень хорошо предсказывает. В большинстве кода ветки идут одинаково почти все время; рассмотрим цикл, который выполняется тысячу раз. Ветвь в конце цикла возвращается к началу цикла 999 раз, а затем в тысячный раз происходит что-то другое. Обычно очень хорошо работает предсказатель ветвлений.
      2016-07-20 21: 07: 37Z
    5. @ steveha: я думаю, вы делаете предположения о том, как работает предиктор ветвления ЦП, и я не согласен с этой методологией. Я не знаю, насколько продвинут этот предсказатель ветвления, но мне кажется, что он гораздо более продвинут, чем вы. Вы, вероятно, правы, но измерения определенно были бы хорошими.
      2016-07-20 21: 10: 18Z

    Одним из способов избежать ошибок предсказания ветвлений является создание таблицы поиска и индексация ее с использованием данных. Стефан де Брюин обсуждал это в своем ответе.

    Но в этом случае мы знаем, что значения находятся в диапазоне [0, 255], и мы заботимся только о значениях > = 128. Это означает, что мы можем легко извлечь один бит, который скажет нам, хотим ли мы значение или нет: сдвигая данные в правые 7 бит, мы получаем 0 или 1 бит, и мы хотим добавить значение только тогда, когда у нас есть 1 бит. Давайте назовем этот бит «битом решения».

    Используя значение 0/1 бита решения в качестве индекса в массиве, мы можем создать код, который будет одинаково быстрым независимо от того, отсортированы данные или нет. Наш код всегда добавляет значение, но когда бит принятия решения равен 0, мы добавим значение туда, где нам все равно. Вот код:

     
    // Test
    clock_t start = clock();
    long long a[] = {0, 0};
    long long sum;
    
    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            int j = (data[c] >> 7);
            a[j] += data[c];
        }
    }
    
    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
    sum = a[1];
    

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

    Но в моем тестировании явная таблица поиска была немного быстрее, чем эта, вероятно, потому что индексирование в таблице поиска было немного быстрее, чем битовое смещение. Это показывает, как мой код настраивает и использует таблицу поиска (в коде «без таблиц» в коде названо lut). Вот код C ++:

     
    // Declare and then fill in the lookup table
    int lut[256];
    for (unsigned c = 0; c < 256; ++c)
        lut[c] = (c >= 128) ? c : 0;
    
    // Use the lookup table after it is built
    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            sum += lut[data[c]];
        }
    }
    

    В этом случае таблица поиска составляла всего 256 байт, поэтому она отлично помещалась в кеш, и все было быстро. Этот метод не сработает, если данные будут 24-битными значениями, а нам нужна только половина из них ... таблица поиска была бы слишком большой, чтобы быть практичной. С другой стороны, мы можем объединить два метода, показанных выше: сначала сдвинуть биты, а затем проиндексировать таблицу поиска. Для 24-битного значения, для которого нам нужно только верхнее половинное значение, мы могли бы сдвинуть данные вправо на 12 бит и оставить 12-битное значение для индекса таблицы. 12-битный индекс таблицы подразумевает таблицу из 4096 значений, что может быть полезно.

    Техника индексации в массив, вместо использования оператора if, может быть использована для определения, какой указатель использовать. Я увидел библиотеку, в которой реализованы двоичные деревья, и вместо двух именованных указателей (pLeft и pRight и т. Д.) Имел массив указателей длины 2 и использовал технику «бит решения», чтобы решить, какой из них следовать. Например, вместо:

     
    if (x < node->value)
        node = node->pLeft;
    else
        node = node->pRight;
    

    эта библиотека будет делать что-то вроде:

     
    i = (x < node->value);
    node = node->link[i];
    

    Вот ссылка на этот код: Красно-черные деревья , Вечно сбитый с толку

        
    1051
    2019-05-27 13: 08: 32Z
    1. Правильно, вы также можете просто использовать бит напрямую и умножать (data[c]>>7 - что также обсуждается где-то здесь); Я намеренно оставил это решение, но, конечно, вы правы. Небольшое примечание: практическое правило для справочных таблиц заключается в том, что если он умещается в 4 КБ (из-за кэширования), он будет работать - желательно, чтобы таблица была как можно меньше. Для управляемых языков я бы увеличил это до 64 КБ, для низкоуровневых языков, таких как C ++ и C, я бы, вероятно, пересмотрел (это только мой опыт). Начиная с typeof(int) = 4, я бы попробовал придерживаться максимум 10 бит.
      2013-07-29 12: 05: 24Z
    2. Я думаю, что индексирование со значением 0/1, вероятно, будет быстрее, чем умножение целых чисел, но я думаю, если производительность действительно критична, вы должны профилировать ее. Я согласен с тем, что маленькие таблицы поиска необходимы, чтобы избежать нагрузки на кэш, но, очевидно, если у вас больший кэш, вы можете справиться с большей таблицей поиска, поэтому 4 КБ - это скорее практическое правило, чем жесткое правило. Я думаю, что вы имели в виду sizeof(int) == 4? Это было бы верно для 32-разрядных. Мой двухлетний сотовый телефон имеет кэш-память L1 объемом 32 КБ, поэтому даже справочная таблица 4 КБ может работать, особенно если значения поиска были байтовыми, а не целыми.
      2013-07-29 22: 02: 13Z
    3. Возможно, я что-то упускаю, но в вашем методе j равен 0 или 1, почему бы вам просто не умножить свое значение на j перед его добавлением, а не использовать индексирование массива (возможно, следует умножить на 1-j, а не на j)
      2014-03-04 15: 38: 24Z
    4. @ steveha Умножение должно быть быстрее, я пытался найти его в книгах Intel, но не смог найти его ... в любом случае, сравнительный анализ также дает мне этот результат здесь.
      2014-03-18 08: 45: 05Z
    5. @ steveha P.S .: другим возможным ответом будет int c = data[j]; sum += c & -(c >> 7);, который вообще не требует умножений.
      2014-03-18 08: 52: 11Z

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

    Действительно, массив разделен на смежную зону с data < 128, а другую с data >= 128. Таким образом, вы должны найти точку разделения с помощью дихотомического поиска (с использованием Lg(arraySize) = 15 сравнений), а затем выполнить прямое накопление с этого момента.

    Что-то вроде (не проверено)

     
    int i= 0, j, k= arraySize;
    while (i < k)
    {
      j= (i + k) >> 1;
      if (data[j] >= 128)
        k= j;
      else
        i= j;
    }
    sum= 0;
    for (; i < arraySize; i++)
      sum+= data[i];
    

    или, немного более запутанный

     
    int i, k, j= (i + k) >> 1;
    for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
      j= (i + k) >> 1;
    for (sum= 0; i < arraySize; i++)
      sum+= data[i];
    

    Еще более быстрый подход, который дает приблизительное решение для обоих отсортированных или несортированных: sum= 3137536; (при условии действительно равномерного распределения, 16384 выборки с ожидаемым значением 191,5) : -) сильный>

        
    950
    2019-05-11 11: 31: 12Z
    1. sum= 3137536 - умный. Это, очевидно, не в этом вопрос. Вопрос в том, чтобы объяснить удивительные характеристики производительности. Я склонен сказать, что добавление std::partition вместо std::sort является ценным. Хотя фактический вопрос распространяется не только на синтетический тест.
      2013-07-24 16: 31: 30Z
    2. @ DeadMG: это действительно не стандартный дихотомический поиск по заданному ключу, а поиск индекса разделения; требуется одно сравнение на каждую итерацию. Но не полагайтесь на этот код, я не проверял его. Если вы заинтересованы в гарантированно правильной реализации, дайте мне знать.
      2013-07-24 20: 37: 31Z

    Вышеупомянутое поведение происходит из-за предсказания Ветви.

    Чтобы понять прогноз ветвления, сначала нужно понять конвейер инструкций :

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

    Как правило, современные процессоры имеют довольно длинные конвейеры, но для простоты давайте рассмотрим только эти 4 шага.

    1. IF - извлечь инструкцию из памяти   
    2. ID - расшифровка инструкции   
    3. EX - выполнить инструкцию   
    4. WB - запись обратно в регистр процессора

    4-этапный конвейер в целом для 2 инструкций. 4-этапный конвейер в целом

    Возвращаясь к вышеупомянутому вопросу, давайте рассмотрим следующие инструкции:

     
                            A) if (data[c] >= 128)
                                    /\
                                   /  \
                                  /    \
                            true /      \ false
                                /        \
                               /          \
                              /            \
                             /              \
                  B) sum += data[c];          C) for loop or print().
    

    Без прогнозирования перехода произойдет следующее:

    Чтобы выполнить инструкцию B или инструкцию C, процессор должен будет ждать, пока инструкция A не достигнет стадии EX в конвейере, поскольку решение перейти к инструкции B или инструкции C зависит от результата инструкции A. Таким образом, трубопровод будет выглядеть следующим образом.

    когда условие возвращает true: введите описание изображения здесь

    Когда условие возвращает false: введите описание изображения здесь

    В результате ожидания результата инструкции A,общее количество циклов ЦП, проведенных в указанном выше случае (без прогноза ветвления; как для истинного, так и для ложного), составляет 7.

    Так что же такое прогноз ветвей?

    Предиктор ветвлений попытается угадать, каким образом пойдет ветвь (структура if-then-else), прежде чем это станет известно наверняка. Он не будет ждать, пока инструкция A достигнет стадии EX конвейера, но он угадает решение и перейдет к этой инструкции (B или C в случае нашего примера).

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

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

    В коде OP в первый раз, когда условный предиктор ветвления не имеет никакой информации для обоснования предсказания, поэтому в первый раз он случайным образом выберет следующую инструкцию. Позже в цикле for он может основывать прогноз на истории. Для массива, отсортированного в порядке возрастания, есть три возможности:

    1. Все элементы меньше 128
    2. Все элементы больше 128
    3. Некоторым начальным новым элементам меньше 128, а позже оно становится больше 128

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

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

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

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

        
    774
    2018-04-10 20: 13: 26Z
    1. как две команды выполняются вместе? это делается с отдельными ядрами процессора или инструкция конвейера интегрирована в одно ядро ​​процессора?
      2017-10-11 14: 49: 42Z
    2. @ M.kazemAkhgary Все это внутри одного логического ядра. Если вам интересно, это хорошо описано, например, в Руководстве разработчика программного обеспечения Intel
      2017-11-03 07: 45: 12Z

    Официальный ответ будет от

    1. Intel - предотвращение неправильного прогнозирования стоимости филиала
    2. Intel - реорганизация филиалов и циклов Предотвратить неправильные прогнозы
    3. Научные статьи - компьютерная архитектура отраслевого прогнозирования
    4. Книги: Дж.Л. Хеннесси, Д.А. Паттерсон: Компьютерная архитектура: количественный подход
    5. Статьи в научных публикациях: Т.Ю. Да, Я.Н. Патт сделал много из них на предсказаниях ветвлений.

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

     2-битная диаграмма состояний

    Каждый элемент в исходном коде является случайным значением

     
    data[c] = std::rand() % 256;
    

    Таким образом, предсказатель сменит сторону, как удар std::rand().

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

    678
    2017-01-31 11: 39: 33Z

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

    if (likely( everything_is_ok ))
    {
        /* Do something */
    }
    

    или аналогично

     
    if (unlikely(very_improbable_condition))
    {
        /* Do something */    
    }
    

    И likely(), и unlikely() на самом деле являются макросами, которые определяются с использованием чего-то вроде __builtin_expect GCC, чтобы помочь компилятору вставить код предсказания, чтобы одобрить условие с учетом информации, предоставленной пользователем. GCC поддерживает другие встроенные функции, которые могут изменить поведение работающей программы или выдавать низкоуровневые инструкции, такие как очистка кэша и т. Д. См. эта документация , которая проходит через встроенные функции GCC.

    Обычно такого рода оптимизации в основном встречаются в приложениях реального времени или встроенных системах, где время выполнения имеет значение и имеет решающее значение. Например, если вы проверяете какое-либо условие ошибки, которое происходит только 1/10000000 раз, то почему бы не сообщить об этом компилятору? Таким образом, по умолчанию прогноз ветвления предполагает, что условие ложно.

        
    645
    2016-10-28 10: 28: 11Z

    Часто используемые логические операции в C ++ создают много веток в скомпилированной программе. Если эти ветви находятся внутри циклов и их трудно предсказать, они могут значительно замедлить выполнение. Булевы переменные хранятся в виде 8-разрядных целых чисел со значением 0 для false и 1 для true.

    Булевы переменные переопределяются в том смысле, что все операторы, которые имеют булевы переменные в качестве входных данных, проверяют, имеют ли входы любое другое значение, кроме 0 или 1, но операторы, которые имеют логические переменные в качестве выходных данных, не могут давать никакого другого значения, кроме 0 или 1. Это делает операции с булевыми переменными в качестве входных данных менее эффективными, чем необходимо. Рассмотрим пример:

     
    bool a, b, c, d;
    c = a && b;
    d = a || b;
    

    Обычно это реализуется компилятором следующим образом:

     
    bool a, b, c, d;
    if (a != 0) {
        if (b != 0) {
            c = 1;
        }
        else {
            goto CFALSE;
        }
    }
    else {
        CFALSE:
        c = 0;
    }
    if (a == 0) {
        if (b == 0) {
            d = 0;
        }
        else {
            goto DTRUE;
        }
    }
    else {
        DTRUE:
        d = 1;
    }
    

    Этот код далеко не оптимален. Ветви могут занять много времени в случае неправильных прогнозов. Булевы операции можно сделать намного более эффективными, если точно известно, что операнды не имеют других значений, кроме 0 и 1. Причина, по которой компилятор не делает такого предположения, состоит в том, что переменные могут иметь другие значения, если они неинициализированы или получены из неизвестных источников. Приведенный выше код можно оптимизировать, если a и b были инициализированы для допустимых значений или если они получены от операторов, которые выдают логический вывод. Оптимизированный код выглядит следующим образом:

     
    char a = 0, b = 1, c, d;
    c = a & b;
    d = a | b;
    

    char используется вместо bool, чтобы сделать возможным использование побитовых операторов (& и |) вместо логических операторов (&& и ||). Побитовые операторы - это одиночные инструкции, которые занимают только один такт. Оператор ИЛИ (|) работает, даже если a и b имеют значения, отличные от 0 или 1. Оператор AND (&) и оператор EXCLUSIVE OR (^) могут давать противоречивые результаты, если операнды имеют значения, отличные от 0 и 1.

    ~ нельзя использовать для НЕ. Вместо этого вы можете сделать логическое НЕ для переменной, которая известна как 0 или 1, XOR'ом присвоив ей 1:

     
    bool a, b;
    b = !a;
    

    можно оптимизировать для:

     
    char a = 0, b;
    b = a ^ 1;
    

    a && b нельзя заменить на a & b, если b - это выражение, которое не следует оценивать, если a - это false(&& не будет оценивать b, & будет). Аналогично, a || b нельзя заменить на a | b, если b является выражением, которое не следует оценивать, если a равно true.

    Использование побитовых операторов более выгодно, если операнды являются переменными, чем если операнды являются сравнениями:

     
    bool a; double x, y, z;
    a = x > y && z < 5.0;
    

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

        
    614
    2019-05-30 16: 34: 26Z

    Это точно! ...

    Прогноз ветвей замедляет работу логики из-за переключения, которое происходит в вашем коде! Как будто вы идете по прямой улице или улице с большим количеством поворотов, наверняка прямая будет сделана быстрее! ...

    Если массив отсортирован, ваше условие ложно на первом шаге: data[c] >= 128, а затем становится истинным значением для всего пути до конца улицы. Вот так вы быстрее доберетесь до конца логики. С другой стороны, при использовании несортированного массива вам нужно много переворачивать и обрабатывать, что наверняка сделает ваш код медленнее ...

    Посмотрите на изображение, которое я создал для вас ниже. Какая улица будет закончена быстрее?

     Прогноз ветвления

    Так программно, предсказание ветвления приводит к замедлению процесса ...

    В конце концов, хорошо знать, что у нас есть два вида предсказаний ветвлений, каждый из которых по-разному повлияет на ваш код:

    1. Static

    2. Dynamic

     Прогноз ветвления

      

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

         

    Для того, чтобы эффективно написать свой код, чтобы воспользоваться этими   правила, при написании операторов if-else или switch отметьте наиболее   общие случаи в первую очередь и работают постепенно до наименьшего общего.   Циклы не обязательно требуют какого-либо специального заказа кода для   статическое предсказание ветвления, как только условие итератора цикла   обычно используется.

        
    289
    2018-05-03 06: 35: 51Z

    На этот вопрос уже много раз отвечали превосходно. Тем не менее, я хотел бы обратить внимание группы на еще один интересный анализ.

    Недавно этот пример (измененный очень незначительно) также использовался для демонстрации того, как фрагмент кода может быть профилирован внутри самой программы в Windows. Попутно автор также показывает, как использовать результаты, чтобы определить, где код проводит большую часть своего времени как в отсортированном & несортированный случай. Наконец, в этой части также показано, как использовать малоизвестную функцию HAL (Уровень аппаратной абстракции), чтобы определить, насколько часто происходит неправильное предсказание ветвления в несортированном случае.

    Ссылка здесь: http://www.geoffchappell.com/studies/windows/km/Ntoskrnl /апи /бывший /профиль /demo.htm

        
    266
    2017-01-17 18: 02: 31Z
    1. Это очень интересная статья (на самом деле, я только что прочитал ее все), но как она отвечает на вопрос?
      2018-03-16 12: 47: 19Z
    2. @ PeterMortensen Я немного озадачен вашим вопросом. Например, вот одна соответствующая строка из этого фрагмента: When the input is unsorted, all the rest of the loop takes substantial time. But with sorted input, the processor is somehow able to spend not just less time in the body of the loop, meaning the buckets at offsets 0x18 and 0x1C, but vanishingly little time on the mechanism of looping. Автор пытается обсудить профилирование в контексте кода, размещенного здесь, и в процессе пытается объяснить, почему отсортированный случай намного быстрее.
      2018-03-16 15: 37: 16Z

    Как уже упоминалось другими, за этой загадкой стоит Predictor Branch .

    Я не пытаюсь что-то добавить, а объясняю концепцию по-другому. Существует краткое введение в вики, которое содержит текст и диаграмму. Мне нравится объяснение ниже, которое использует диаграмму для интуитивного создания предсказателя ветвей.

      

    В компьютерной архитектуре предсказатель ветвления является   цифровая схема, которая пытается угадать, каким образом ветвь (например,   структура if-then-else) пойдет до того, как это станет известно наверняка.   Целью предсказателя ветвления является улучшение потока в   инструкция конвейера. Предикторы ветвления играют решающую роль в   достижение высокой эффективности во многих современных конвейерных   микропроцессорные архитектуры, такие как x86.

         

    Двустороннее ветвление обычно реализуется с условным переходом   инструкция. Условный переход можно либо «не выполнить», либо продолжить.   выполнение с первой ветвью кода, которая следует сразу   после условного прыжка, или его можно «взять» и перейти к   другое место в памяти программ, где вторая ветвь кода   сохраняются. Не известно наверняка, будет ли условный переход   принято или не принято, пока условие не будет рассчитано и   условный переход прошел этап исполнения в инструкции   трубопровод (см. рис. 1).

     figure 1

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

    1. Без предсказателя ветвления.
      

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

    В примере содержатся три инструкции, а первая - это инструкция условного перехода. Последние две инструкции могут идти в конвейер, пока не будет выполнена команда условного перехода.

     без предиктора ветвления

    Для выполнения 3-х инструкций потребуется 9 тактов.

    1. Используйте Branch Predictor и не выполняйте условный переход. Давайте предположим, что прогноз не выполняет условный переход.

     введите описание изображения здесь

    Для выполнения 3-х инструкций потребуется 7 тактов.

    1. Используйте Branch Predictor и сделайте условный переход. Давайте предположим, что прогноз не выполняет условный переход.

     введите описание изображения здесь

    Для выполнения 3-х инструкций потребуется 9 тактов.

      

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

    Как видите, у нас нет причин не использовать Branch Predictor.

    Это довольно простая демонстрация, которая разъясняет основную часть Branch Predictor. Если эти картинки раздражают, пожалуйста, не стесняйтесь удалять их из ответа, и посетители также могут получить демонстрацию из BranchPredictorDemo р>     

    183
    2019-06-04 16: 20: 33Z

    Выгода от предсказания ветвлений!

    Важно понимать, что ветвьнеправильное прогнозирование не замедляет программы. Стоимость пропущенного прогноза такая же, как если бы прогноз ветвления не существовал, и вы подождали, пока оценка выражения решит, какой код запустить (дальнейшее объяснение в следующем абзаце).

     
    if (expression)
    {
        // Run 1
    } else {
        // Run 2
    }
    

    Всякий раз, когда есть оператор if-else \switch, выражение должно быть оценено, чтобы определить, какой блок должен быть выполнен. В коде сборки, сгенерированном компилятором, вставлены условные инструкции ответвления .

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

    При этом компилятор пытается предсказать результат до его фактической оценки. Он будет извлекать инструкции из блока if, и если выражение окажется верным, тогда замечательно! Мы получили время, необходимое для его оценки, и добились прогресса в коде; если нет, то мы выполняем неправильный код, конвейер сбрасывается и запускается правильный блок.

    Визуализация:

    Допустим, вам нужно выбрать маршрут 1 или маршрут 2. В ожидании вашего партнера, чтобы проверить карту, вы остановились на ## и подождали, или вы можете просто выбрать маршрут 1 и, если вам повезло (маршрут 1 правильный маршрут), значит, вам не нужно было ждать, пока ваш партнер проверит карту (вы сэкономили время, которое потребовалось бы ему, чтобы проверить карту), иначе вы просто вернетесь назад.

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

     
     O      Route 1  /-------------------------------
    /|\             /
     |  ---------##/
    / \            \
                    \
            Route 2  \--------------------------------
    
        
    172
    2018-03-16 12: 30: 45Z

    Речь идет о предсказании ветвлений. Что это?

    • Предсказатель ветвей - это одна из древних технологий повышения производительности, которая все еще находит применение в современных архитектурах. Хотя простые методы прогнозирования обеспечивают быстрый поиск и эффективность энергопотребления, они страдают от высокой степени неверного прогнозирования.

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

    • В дополнение к этому, в сложных методах прогнозирования время, затрачиваемое на прогнозирование ветвей, само по себе очень велико - в диапазоне от 2 до 5 циклов - что сопоставимо со временем выполнения фактических ветвей.

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

    На самом деле существует три вида ветвей:

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

    Обратные условные переходы - ПК изменяется на указание назад в потоке команд. Ветвление основано на некотором условии, например, переходе назад к началу цикла программы, когда тест в конце цикла указывает, что цикл должен быть выполнен снова.

    Безусловные ветви - это включает переходы, вызовы процедур и возвраты, которые не имеют особых условий. Например, команда безусловного перехода может быть закодирована на языке ассемблера как просто «jmp», и поток команд должен быть немедленно направлен в целевое местоположение, на которое указывает инструкция перехода, тогда как условный переход, который может быть закодирован как «jmpne» будет перенаправлять поток команд только в том случае, если результат сравнения двух значений в предыдущих инструкциях «сравнения» показывает, что значения не равны. (Схема сегментированной адресации, используемая архитектурой x86, добавляет дополнительную сложность, поскольку переходы могут быть «ближними» (внутри сегмента) или «дальними» (вне сегмента). Каждый тип по-разному влияет на алгоритмы прогнозирования ветвлений.) р>

    Статическое /динамическое предсказание ветвления : предсказание статического ветвления используется микропроцессором при первом обнаружении условного ветвления, а динамическое предсказание ветвления используется для последующих выполненийусловного кода ветви.

    Литература:

    116
    2018-03-16 10: 57: 23Z

    Помимо того, что предсказание ветвления может замедлить вас, у отсортированного массива есть еще одно преимущество:

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

     
     // sort backwards (higher values first), may be in some other part of the code
     std::sort(data, data + arraySize, std::greater<int>());
    
     for (unsigned c = 0; c < arraySize; ++c) {
           if (data[c] < 128) {
                  break;
           }
           sum += data[c];               
     }
    
        
    110
    2019-03-05 09: 58: 40Z
    1. Правильно, но стоимость установки для сортировки массива составляет O (N log N), поэтому преждевременное прерывание не поможет, если единственная причина, по которой вы сортируете массив должен быть в состоянии сломаться рано. Однако если у вас есть другие причины для предварительной сортировки массива, то да, это ценно.
      2018-11-06 12: 28: 29Z
    2. @ LukeHutchison хорошее наблюдение; пожалуйста, смотрите мой ответ ниже для другого дубля.
      2019-02-27 11: 47: 22Z
    3. Зависит от того, сколько раз вы сортируете данные по сравнению с тем, сколько раз вы зациклились на них. Сортировка в этом примере - просто пример, она не должна быть перед циклом
      2019-02-27 12: 23: 22Z
    4. Да, именно об этом я и говорил в своем первом комментарии :-) Вы говорите: «Прогноз ветвления будет пропущен только один раз». Но вы не учитываете пропуски ветвления O (N log N) внутри алгоритма сортировки, которые на самом деле больше, чем пропуски ветвления O (N) в несортированном случае. Таким образом, вам нужно было бы использовать всю совокупность отсортированных данных O (log N) раз для безубыточности (вероятно, на самом деле ближе к O (10 log N), в зависимости от алгоритма сортировки, например, для быстрой сортировки, из-за пропадания кэша - mergesort более кэш-когерентен, так что вам нужно приблизиться к O (2 log N) использования, чтобы достичь безубыточности.)
      2019-02-28 12: 28: 14Z
    5. Хотя одной важной оптимизацией было бы сделать только "половину быстрой сортировки", сортируя только элементы, которые меньше целевого целевого значения 127 (при условии, что все меньше, чем или равно сводная после сортировки). Как только вы достигнете точки, суммируйте элементы перед точкой. Это будет выполняться во время запуска O (N), а не O (N log N), хотя все еще будет много ошибок прогнозирования ветвлений, вероятно, порядка O (5 N) на основе чисел, которые я дал ранее, так как это половина быстрой сортировки.
      2019-02-28 12: 34: 48Z

    В ARM ветвление не требуется, поскольку каждая инструкция имеет 4-битное поле условия, которое тестируется с нулевой стоимостью. Это устраняет необходимость в коротких ветвях, и не будет никакого предсказания ветвлений. Поэтому отсортированная версия будет работать медленнее, чем несортированная версия в ARM, из-за дополнительных издержек сортировки. Внутренний цикл будет выглядеть примерно так:

     
    MOV R0, #0     // R0 = sum = 0
    MOV R1, #0     // R1 = c = 0
    ADR R2, data   // R2 = addr of data array (put this instruction outside outer loop)
    .inner_loop    // Inner loop branch label
        LDRB R3, [R2, R1]     // R3 = data[c]
        CMP R3, #128          // compare R3 to 128
        ADDGE R0, R0, R3      // if R3 >= 128, then sum += data[c] -- no branch needed!
        ADD R1, R1, #1        // c++
        CMP R1, #arraySize    // compare c to arraySize
        BLT inner_loop        // Branch to inner_loop if c < arraySize
    
        
    106
    2018-05-14 14: 01: 18Z
    1. Вы говорите, что каждый инструктажИон может быть условным? Таким образом, несколько инструкций с суффиксом GE могут выполняться последовательно, без изменения значения R3 между?
      2018-05-14 14: 04: 03Z
    2. Да, правильно, каждая инструкция может быть условной для ARM, по крайней мере, в 32- и 64-битных наборах команд. Есть выделенное 4-битное поле условия. У вас может быть несколько инструкций подряд с одним и тем же условием, но в какой-то момент, если вероятность ложного условия не пренебрежимо мала, эффективнее добавить ветвь.
      2018-05-15 17: 06: 42Z
    3. Другим нововведением в ARM является добавление суффикса инструкции S, также необязательного (почти) для всех инструкций, который, если он отсутствует, не позволяет командам изменять биты состояния (с помощью исключение из инструкции CMP, задачей которой является установка битов состояния, поэтому ей не требуется суффикс S). Это позволяет вам избегать команд CMP во многих случаях, если сравнение выполняется с нулем или аналогичным образом (например, SUBS R0, R0, # 1 установит бит Z (Ноль), когда R0 достигнет нуля). Условные выражения и суффикс S не требуют дополнительных затрат. Это довольно красивый ISA.
      2018-05-15 17: 06: 54Z
    4. Не добавляя суффикс S, вы можете иметь несколько условных инструкций подряд, не беспокоясь о том, что одна из них может изменить биты состояния, которые в противном случае могли бы иметь побочный эффект пропуская остальные условные инструкции.
      2018-05-15 17: 08: 22Z

    Сортированные массивы обрабатываются быстрее, чем несортированный массив из-за явления, называемого предсказанием ветвлений.

    Предиктор ветвления - это цифровая схема (в компьютерной архитектуре), пытающаяся предсказать, каким образом пойдет ветвь, улучшая поток в конвейере команд. Схема /компьютер предсказывает следующий шаг и выполняет его.

    Неправильный прогноз приводит к возврату к предыдущему шагу и выполнению с другим прогнозом. Если предположить, что прогноз верен, код перейдет к следующему шагу. Неправильный прогноз приводит к повторению одного и того же шага, пока не произойдет правильный прогноз.

    Ответ на ваш вопрос очень прост.

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

    Сортированный массив: прямая дорога     ____________________________________________________________________________________     - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -     TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

    Несортированный массив: изогнутая дорога

     
    ______   ________
    |     |__|
    

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

     
    ___________________________________________ Straight road
     |_________________________________________|Longer road
    

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

    Также я хочу процитировать @Simon_Weaver из комментариев:

      

    Он не делает меньше прогнозов - он делает меньше неправильных прогнозов. Это все еще нужно прогнозировать для каждого раза через цикл ...

        
    96
    2019-05-27 12: 47: 18Z
    1. "Простыми словами" - я нахожу ваше объяснение менее простым, чем у других с поездами, и гораздо менее точным, чем любой другой ответ, хотя Я не новичок. Мне очень любопытно, почему так много отрицательных отзывов, может быть, кто-то из будущих восходящих скажет мне?
      2018-07-04 13: 54: 21Z
    2. @ SinaТак как это, вероятно, действительно основано на мнении, я сам нашел, что это достаточно хорошо, чтобы высказывать его, это, конечно, не так точно, как другие примеры, вот в чем весь смысл: раздавать ответ (как мы все можем согласиться, что здесь используется предсказание ветвления) без читатели должны были найти технические объяснения, как это сделали другие (очень хорошо). И я думаю, что он сделал это достаточно хорошо.
      2018-07-09 12: 45: 50Z
    3. Он не делает меньше прогнозов - он делает меньше неправильных прогнозов. Это все еще должно предсказывать каждый раз в цикле.
      2018-07-16 01: 28: 03Z
    4. О, вы правы, мой плохой, спасибо @Simon_Weaver, я исправлю это через некоторое время, или, может быть, некоторые из вас отредактируют его, а затем я его одобрю спасибо заранее ...
      2018-07-16 05: 52: 47Z

    Допущение других ответов о том, что нужно сортировать данные, неверно.

    Следующий код сортирует не весь массив, а только его 200-элементные сегменты и, следовательно, работает быстрее всего.

    Сортировка только k-элементных срезов завершает предварительную обработку за линейное время, а не за n.log(n).

     
    #include <algorithm>
    #include <ctime>
    #include <iostream>
    
    int main() {
        int data[32768]; const int l = sizeof data / sizeof data[0];
    
        for (unsigned c = 0; c < l; ++c)
            data[c] = std::rand() % 256;
    
        // sort 200-element segments, not the whole array
        for (unsigned c = 0; c + 200 <= l; c += 200)
            std::sort(&data[c], &data[c + 200]);
    
        clock_t start = clock();
        long long sum = 0;
    
        for (unsigned i = 0; i < 100000; ++i) {
            for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }
    
        std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
        std::cout << "sum = " << sum << std::endl;
    }
    

    Это также «доказывает», что это не имеет никакого отношения к каким-либо алгоритмическим проблемам, таким как порядок сортировки, и это действительно предсказание ветвлений.

        
    17
    2019-02-28 15: 24: 59Z
    1. Я действительно не вижу, как это доказывает что-нибудь? Единственное, что вы показали, это то, что «не вся работа по сортировке всего массива занимает меньше времени, чем сортировка всего массива». Ваше утверждение, что это «также работает быстрее», очень зависит от архитектуры. Смотрите мой ответ о том, как это работает на ARM. PS вы могли бы ускорить свой код на архитектурах без ARM, поместив суммирование внутри цикла из 200 элементов, отсортировав его в обратном порядке, а затем воспользовавшись предложением Йохая Тиммера о разрыве, как только вы получите значение вне диапазона. Таким образом, каждое суммирование блока из 200 элементов может быть прекращено досрочно.
      2019-02-28 12: 18: 29Z
    2. @ LukeHutchison Это доказательство для ОП, а не для такого хорошо информированного автора, как вы. Для ОП это сводит на нет гипотезу о том, что сортировка имеет какое-либо отношение к более быстрой обработке (см. Формулировку названия вопроса). «Быстрее всего» в алгоритмическом смысле в архитектуре общего назначения - ARM - особый случай. Предложение Йохая Тиммера - это приятная оптимизация, которая не является алгоритмической в ​​смысле большого О. Кроме того, в общем, люди будут делать что-то и в истинном, и в ложном случае, чтобы взлом Йохая не применялся & скорее всего, что-то более важное, чем суммирование.
      2019-02-28 15: 21: 15Z
источник размещен Вот