Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

    Я бы хотел предложить сообществу поучаствовать в пробном эксперименте. Суть его состоит в том, чтобы прогнать на своём компьютере программу, написанную на C++, и поделиться результатом измерения времени, которое она выдаёт, сравнивая скорость работы функций sign(x), abs(x), min(a,b) и max(a,b) в исполнении с ветвлением и без него. В статье я объясню свою мотивацию, покажу сами функции, а в конце предложу условия участия в эксперименте и его (увы) ограничения.

    Мотивация


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

    Правда, что без IF быстрее?


    Нет, это неправда. Если быть более точным, то избавление от ветвлений может как дать прирост скорости, так и усугубить ситуацию в несколько раз. Всё зависит от конкретной машины, на которой данный код будет исполняться, и от компилятора. Приведу в качестве примера свой старый компьютер Core 2 Duo E8400 @3ГГц – на нём все предложенные функции работают быстрее в варианте с IF, когда данные подаются упорядоченно и ситуация может стать обратной при хаотичной подаче (подробности ниже). Компилятор у меня VC++ 2015, опция компиляции /Ox.

    Давайте рассмотрим чуть подробнее те функции, что я предлагаю протестировать. Каждая из четырёх функций может быть написана полудюжиной вариантов, все из которых Вы можете изучить самостоятельно по ссылкам [1-7] в конце статьи. Все эти варианты я уже тестировал и выбрал для каждой функции два: классический и какой-либо без ветвлений (наилучший по моим измерениям). Если, опять же, мой эксперимент окажется удачным, я проведу похожее сравнение вообще всех известных мне вариантов [4-7].

    Для начала я ввожу свои псевдонимы для типов данных и константу для сдвига:

    typedef int32_t   i32;
    typedef uint32_t  u32;
    typedef int8_t    sign_t;
    const u32 SHIFT = 31;
    

    Знак числа – sign


    Классический вариант реализуется несложной схемой из условий:

    sign_t sign0 (i32 a) {
      if (a>0)  return +1;
      if (a<0)  return -1;
      return 0;
    }
    

    Наилучший вариант без ветвлений выглядит следующим образом:

    sign_t sign1 (i32 a) {
      return (a >> SHIFT) | ((u32)(-a) >> SHIFT);
    }
    

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

    На моём процессоре разница между этими двумя функциями весьма заметна. Я прогнал их на всех возможных числах из рабочего диапазона и первая сработала за 2,87 секунды, а вторая только за 3,97 при упорядоченной подаче чисел и 13,02 vs 1,26 при хаотичной.

    Абсолютное значение – abs


    Здесь ситуация несколько лучше. Первая функция с IF, может выглядеть, например, вот так:

    u32 abs0 (i32 a) {
      if (a<0)  return -a;
      return a;
    }
    

    А без ветвления самый лучший (на мой взгляд) вариант имеет вид:

    u32 abs1 (i32 a) {
     const i32 b = a >> SHIFT; 
     return (a+b) ^ b;
    }
    

    Время работы первой 2,29, а второй — 2,33 при упорядоченной подаче и 12,01 vs 0,81 при хаотичной. Прошу обратить внимание: программист часто не знает, что компилятор может сам сделать код без ветвлений для abs, который будет по логике полностью совпадать со вторым вариантом [3]. Таким образом, если в программе есть IF, это не значит, что после компиляции ветвление останется. Мой компилятор генерирует код с ветвлением.

    Минимум и максимум со знаком — mini и maxi


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

    i32 mini0 (i32 a, i32 b) {
      return a<b ? a:b;
    }
    i32 maxi0 (i32 a, i32 b) {
      return a>b ? a:b;
    }
    

    На самом деле (и для меня это совершенно непонятно) вот такой вариант в полтора раза быстрее:

    i32 mini0 (i32 a, i32 b) {
      return a>b ? b:a;
    }
    i32 maxi0 (i32 a, i32 b) {
      return a<b ? b:a;
    }
    

    Я обнаружил это, когда сравнивал разные варианты реализации, но конкретного ответа так и не нашёл. Когда смотрел ассемблерный листинг, то обнаружил, что разница только в порядке сравнения (a сравниваем с b, или наоборот). Подозреваю, что всё дело в микроархитектуре процессора. Аналогично, я замечал уже, что команда inc ecx работает значительно медленнее, чем lea eax, [eax+1], что тоже непонятно как можно объяснить, если не кривизной микроархитектуры.

    Вариант без ветвлений для функций минимума и максимума в моём репертуаре только один (который корректно работает для всех возможных входных данных):

    i32 mini1 (i32 a, i32 b) {
      i32 d = a-b;
      return a - (d&(~(d^((a^b)&(d^a))) >> SHIFT));
    }
    i32 maxi1 (i32 a, i32 b) {
      i32 d = a-b;
      return b + (d&(~(d^((a^b)&(d^a))) >> SHIFT));
    }
    

    Здесь разница колоссальная. Первая серия функций работает около 3,5 секунд, вторая – около 9 на последовательных данных и 2 секунды vs 6 секунд на хаотичных. Разница почти втрое в обоих случаях.

    Дело в том, что в архитектуре x86 существует команда cmovl, которая как раз позволяет компилятору создать в первом случае код без ветвлений. Таким образом, получается, что на языке Си у нас ветвление есть, а реально его нет. Программист, который любой ценой хочет избавиться от ветвлений, не всегда знает, что компилятор может сделать это лучше него, если посчитает нужным.

    Минимум и максимум без знака — minu и maxu


    Классический вариант не меняется, кроме замены i32 на u32:

    u32 minu0 (u32 a, u32 b) {
      return a>b ? b:a;
    }
    u32 maxu0 (u32 a, u32 b) {
      return a<b ? b:a;
    }
    

    Вариант без ветвлений будет основан на другой страшной формуле:

    u32 minu1 (u32 a, u32 b) {
      u32 d = a-b;
      return a - (d&~(int((~a&b)|(~(a^b)&d)) >> SHIFT));
    }
    u32 maxu1 (u32 a, u32 b) {
      u32 d = a-b;
      return b + (d&~(int((~a&b)|(~(a^b)&d)) >> SHIFT));
    }
    

    Разница по скорости ещё больше: если первый вариант работает всё так же 3,5 секунд, то второй уже 9,5 на последовательных данных и примерно 2 секунды против 6 на хаотичных.

    Суть и правила эксперимента


    Я предлагаю читателям сами проверить на своих машинах то, каков будет результат сравнения. С этой целью была написана программа (GitHub) (с учётом замечаний meduzik и ivas, даю исправленную программу — тестируем обе. В одной данные подаются последовательно, во второй — хаотично). Её нужно скомпилировать и запустить. Работать она может долго, возможно, несколько минут, имейте терпение. Прошу обязательно отключить остальные ресурсоёмкие приложения на компьютере, когда запускаете эту программу.

    Отработав, она выдаст в STDOUT таблицу (последовательная подача данных)
    sign: 2.87 vs 3.97
     abs: 2.29 vs 2.33
    mini: 3.46 vs 8.93
    maxi: 3.45 vs 9.10
    minu: 3.45 vs 9.46
    maxu: 3.45 vs 9.81
    

    В первой колонке время работы функций с IF, а во второй – без ветвлений. В STDERR будет выведено число, не обращайте на него внимания, оно для правильного понимания компилятором циклов в программе.

    Аналогичная таблица для хаотичной подачи:
    sign: 13.02 vs 1.26
     abs: 12.01 vs 0.81
    mini: 1.89 vs 5.97
    maxi: 1.93 vs 6.31
    minu: 1.89 vs 6.44
    maxu: 1.92 vs 6.70
    

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

    Сразу хочу предупредить о возможных неудачах Вашего эксперимента, за которые я прошу меня простить, но я ничего не могу с этим поделать, как не старался.
    1. Программа не скомпилируется. Это возможно, так как не все компиляторы понимают std::chrono. Ещё, возможно, я где-то вышел за пределы Стандарта языка С++. Гарантирую только, что код компилируется в Visual C++ 2015 и GCC 4.8.1 (из MinGW) в OS Windows 7 (64). Компилировал я именно 32-битовый код. Я пытался спросить у грамотных людей на SO, как сделать программу лучше, но пока не получил ответа.
    2. У Вас на машине нет знакового сдвига или отрицательные числа имеют представление не в дополнительном коде — тогда все функции будут работать неправильно.
    3. Программа будет работать не так, как должна. Это возможно. Я впервые использую chrono и мог ошибиться. До этого всегда измерял время через утилиту runexe, а в этой программе мне нужен универсальный способ, который работал бы у большинства пользователей.

    Итак, давайте вместе выясним, что в каких случаях лучше и на каком процессоре.

    Список источников


    1. Hacker's Delight
    2. Bit Twiddling Hacks
    3. Optimized abs function
    4. Функция sign(x) — определение знака переменной
    5. Функция abs(x) — абсолютное значение числа
    6. Функции min(a,b) и max(a,b) для чисел со знаком
    7. Функции min(a,b) и max(a,b) для чисел без знака


    Благодарности


    Благодарю meduzik и ivas, за то, что напомнили мне про хаотичную подачу данных, о которой я случайно забыл.

    Комментарии 144

      0
      Ответом к этому комментарию я прошу давать только таблицу времени работы.
      Укажите также процессор и компилятор с опциями. Используйте тэг «pre».
        0
        Intel Core 2 Duo E8400 @3.00GHz
        Visual C++ 2015
        Опции: /Ox
        
        sign: 2.87 vs 3.97
         abs: 2.29 vs 2.33
        mini: 3.46 vs 8.93
        maxi: 3.45 vs 9.10
        minu: 3.45 vs 9.46
        maxu: 3.45 vs 9.81
        
        • НЛО прилетело и опубликовало эту надпись здесь
            +1
            Вы точно с оптимизацией скомпилировали? -O3 например?
            • НЛО прилетело и опубликовало эту надпись здесь
            0
            Intel(R) Core(TM) i5-3450 CPU @ 3.10GHz
            g++ -std=gnu++11 BranchFreeTimeout.cpp
            gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2

            sign: 4.64 vs 3.84
            abs: 2.88 vs 5.78
            mini: 5.01 vs 14.40
            maxi: 5.08 vs 14.55
            minu: 5.07 vs 14.10
            maxu: 5.09 vs 13.63
            • НЛО прилетело и опубликовало эту надпись здесь
                0
                Intel Core i5-4690 CPU @ 3.50GHz
                gcc version 5.2.1
                g++ -std=c++11 BranchFreeTimeout.cpp
                
                sign: 2.45 vs 2.69
                 abs: 2.44 vs 4.92
                mini: 4.06 vs 11.19
                maxi: 3.86 vs 11.04
                minu: 4.15 vs 11.08
                maxu: 4.07 vs 11.10
                2147483646
                
                  0
                  Прошу простить мой косяк!

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

                  Тех, кто уже принял участие, прошу перетестировать. Далее можно, кстати, обе программы тестировать — интересно же.
                    0
                    g++ -std=gnu++11 (gcc version 4.8.4)

                    Intel® Core(TM) i7-2600 CPU @ 3.40GHz

                    sign: 4.49 vs 5.82
                    abs: 5.12 vs 6.15
                    mini: 6.30 vs 15.02
                    maxi: 5.92 vs 14.99
                    minu: 6.13 vs 14.88
                    maxu: 6.38 vs 15.30

                    Intel® Xeon® CPU E5-2620 0 @ 2.00GHz

                    sign: 7.08 vs 9.13
                    abs: 6.32 vs 9.53
                    mini: 9.59 vs 22.66
                    maxi: 9.25 vs 22.94
                    minu: 9.76 vs 22.87
                    maxu: 9.94 vs 23.15

                    clang++ -std=gnu++11 (clang version 3.4)

                    Intel® Core(TM) i7-2600 CPU @ 3.40GHz

                    sign: 3.42 vs 4.11
                    abs: 3.26 vs 4.90
                    mini: 5.55 vs 11.98
                    maxi: 6.27 vs 12.00
                    minu: 5.65 vs 12.46
                    maxu: 5.55 vs 12.38

                    Intel® Xeon® CPU E5-2620 0 @ 2.00GHz

                    sign: 5.64 vs 6.74
                    abs: 5.57 vs 8.05
                    mini: 8.39 vs 18.64
                    maxi: 9.48 vs 18.66
                    minu: 8.92 vs 19.50
                    maxu: 8.92 vs 19.33
                    • НЛО прилетело и опубликовало эту надпись здесь
                        0
                        Intel(R) Core(TM) i3-2100 CPU @ 3.10GHz
                        GCC 4.9.3-r3
                        Опции: -std=gnu++11 -O3
                        
                        sign: 11.25 vs 2.25
                         abs: 11.93 vs 1.30
                        mini: 1.22 vs 2.59
                        maxi: 1.19 vs 2.71
                        minu: 13.64 vs 3.01
                        maxu: 1.21 vs 2.54
                        
                          0
                          Intel Core 2 Duo E8400 @3.00GHz
                          Visual C++ 2015
                          Опции: /Ox

                          Последовательно
                          sign: 2.87 vs 3.97
                           abs: 2.29 vs 2.33
                          mini: 3.46 vs 8.93
                          maxi: 3.45 vs 9.10
                          minu: 3.45 vs 9.46
                          maxu: 3.45 vs 9.81

                          Хаотично
                          sign: 13.02 vs 1.26
                           abs: 12.01 vs 0.81
                          mini: 1.89 vs 5.97
                          maxi: 1.93 vs 6.31
                          minu: 1.89 vs 6.44
                          maxu: 1.92 vs 6.70

                            +1
                            Intel® Core™ i7-6700K CPU @ 4.00GHz
                            GCC 5.2.1
                            Опции: -O3 -std=gnu++11
                            
                            Старая версия:
                            
                            sign: 4.31 vs 2.76
                             abs: 2.07 vs 2.22
                            mini: 2.07 vs 4.66
                            maxi: 2.08 vs 4.23
                            minu: 2.08 vs 4.19
                            maxu: 2.14 vs 4.12
                            
                            Новая версия:
                            
                            sign: 9.87 vs 0.72
                             abs: 9.57 vs 0.39
                            mini: 0.49 vs 0.83
                            maxi: 0.48 vs 0.82
                            minu: 10.20 vs 0.74
                            maxu: 0.49 vs 0.91
                            
                            
                              +2
                              Intel® Core™ i7-6700K CPU @ 4.00GHz
                              clang 3.6.2-1
                              Опции: -O3 -std=gnu++11
                              
                              Новая версия:
                              
                              sign: 9.53 vs 0.50
                               abs: 0.12 vs 0.13
                              mini: 0.47 vs 1.87
                              maxi: 0.41 vs 1.96
                              minu: 0.91 vs 1.89
                              maxu: 0.46 vs 1.97
                              
                            • НЛО прилетело и опубликовало эту надпись здесь
                                0
                                x86_64 Intel(R) Core(TM) i7 CPU X 980 @ 3.33GHz
                                g++-5.3.0 test.cpp -std=c++11 -O3 -pipe -march=native
                                
                                sign: 11.36 vs 3.64
                                 abs: 10.53 vs 0.91
                                mini: 1.25 vs 2.83
                                maxi: 1.19 vs 2.87
                                minu: 12.99 vs 3.37
                                maxu: 1.19 vs 2.77
                                2147483646
                                
                                
                                
                                  0
                                  Raspberry Pi 3, SoC: Broadcom BCM2837, CPU: ARM Cortex-A53 @ 1.2GHz
                                  gcc version 4.9.2 (Raspbian 4.9.2-10)
                                  options: -std=gnu++11

                                  BranchFreeTimeout.cpp
                                  sign: 66.21 vs 89.49
                                  abs: 62.63 vs 78.74
                                  mini: 71.58 vs 125.39
                                  maxi: 71.58 vs 125.32
                                  minu: 68.00 vs 128.90
                                  maxu: 68.00 vs 128.90
                                  2147483646

                                  BranchFreeTimeoutNew.cpp
                                  sign: 85.91 vs 93.07
                                  abs: 81.43 vs 82.33
                                  mini: 91.29 vs 128.90
                                  maxi: 91.29 vs 128.90
                                  minu: 87.70 vs 132.48
                                  maxu: 87.70 vs 132.49
                                  2147483646
                                    0
                                    Raspberry Pi 3, SoC: Broadcom BCM2837, CPU: ARM Cortex-A53 @ 1.2GHz
                                    gcc version 4.9.2 (Raspbian 4.9.2-10)
                                    options: -std=gnu++11 -O3
                                    
                                    BranchFreeTimeout.cpp
                                    sign: 7.11 vs 7.11
                                     abs: 7.11 vs 3.52
                                    mini: 7.11 vs 10.69
                                    maxi: 3.52 vs 7.11
                                    minu: 3.52 vs 7.11
                                    maxu: 7.11 vs 7.11
                                    2147483646
                                    
                                    BranchFreeTimeoutNew.cpp
                                    sign: 22.01 vs 10.74
                                     abs: 18.80 vs 10.73
                                    mini: 10.74 vs 17.93
                                    maxi: 10.74 vs 14.33
                                    minu: 24.63 vs 7.16
                                    maxu: 10.74 vs 7.16
                                    2147483646
                                    
                                  • НЛО прилетело и опубликовало эту надпись здесь
                                      0
                                      botanic@botfang:~$ cat /proc/cpuinfo | grep -wm1 Intel
                                      model name: Intel® Core(TM) i7-4810MQ CPU @ 2.80GHz

                                      опции везде -std=c++11 -O3 -lstdc++

                                      botanic@botfang:~/source/other/fastest_algorithm$ clang -v
                                      Debian clang version 3.5.0-10 (tags/RELEASE_350/final) (based on LLVM 3.5.0)

                                      botanic@botfang:~/source/other/fastest_algorithm$ ./BranchFreeTimeout
                                      sign: -0.00 vs -0.00
                                      abs: -0.00 vs -0.00
                                      mini: -0.00 vs -0.00
                                      maxi: -0.00 vs -0.00
                                      minu: -0.00 vs -0.00
                                      maxu: -0.00 vs -0.00
                                      2147483648
                                      botanic@botfang:~/source/other/fastest_algorithm$ ./BranchFreeTimeoutNew
                                      sign: 9.63 vs 0.69
                                      abs: 0.50 vs 0.25
                                      mini: 1.03 vs 2.10
                                      maxi: 0.98 vs 2.27
                                      minu: 1.14 vs 2.16
                                      maxu: 0.87 vs 2.25
                                      2147483646

                                      botanic@botfang:~/source/other/fastest_algorithm$ gcc -v

                                      gcc version 4.9.2 (Debian 4.9.2-10)
                                      botanic@botfang:~/source/other/fastest_algorithm$ ./BranchFreeTimeout
                                      sign: 3.61 vs 1.90
                                      abs: 1.16 vs 1.23
                                      mini: 1.64 vs 2.91
                                      maxi: 1.64 vs 2.32
                                      minu: 1.86 vs 1.14
                                      maxu: 1.62 vs 1.94
                                      2147483646
                                      botanic@botfang:~/source/other/fastest_algorithm$ ./BranchFreeTimeoutNew
                                      sign: 9.85 vs 0.72
                                      abs: 9.77 vs 0.37
                                      mini: 0.60 vs 0.98
                                      maxi: 0.60 vs 0.99
                                      minu: 11.09 vs 1.02
                                      maxu: 0.62 vs 1.03
                                      2147483646

                                      вне программы кланг с -O1 (-O2 тоже был неверно понят):
                                      botanic@botfang:~/source/other/fastest_algorithm$ ./BranchFreeTimeout
                                      sign: 7.38 vs 5.86
                                      abs: 4.74 vs 5.82
                                      mini: 5.83 vs 7.06
                                      maxi: 5.84 vs 6.41
                                      minu: 5.82 vs 8.18
                                      maxu: 5.89 vs 6.99
                                      2147483646
                                        0
                                        Intel® Core(TM) i7 CPU 950 @3.07GHz 3.06GHz
                                        Windows 7 32
                                        g++ -std=c++11

                                        sign: 6.18 vs 8.08
                                        abs: 7.43 vs 12.77
                                        mini: 11.19 vs 26.56
                                        maxi: 11.30 vs 26.67
                                        minu: 13.91 vs 23.85
                                        maxu: 13.91 vs 24.64
                                          0
                                          Железо: Intel® Pentium® CPU N3530 @ 2.16GHz;
                                          Компилятор: GCC 5.3.0;
                                          Командная строка: g++ -o3 -std=gnu++11.

                                          Линейно:
                                          sign: 11.07 vs 12.50
                                           abs: 12.29 vs 18.13
                                          mini: 19.70 vs 38.46
                                          maxi: 19.57 vs 39.13
                                          minu: 19.79 vs 33.52
                                          maxu: 19.21 vs 33.88
                                          


                                          Хаотично:
                                          sign: 15.62 vs 5.06
                                           abs: 13.80 vs 2.50
                                          mini: 4.13 vs 5.95
                                          maxi: 3.89 vs 6.12
                                          minu: 17.45 vs 7.50
                                          maxu: 3.89 vs 6.50
                                          
                                            0
                                            Intel(R) Core(TM) i5-2410M CPU @2.30GHz:
                                            
                                              Clang 3.7 with Microsoft CodeGen (v140_clang_3_7):
                                                Full optimization (-O3)
                                            
                                                BranchFreeTimeoutNew.exe
                                                sign: 14.49 vs 2.41
                                                 abs: 13.55 vs 1.49
                                                mini: 2.05 vs 5.99
                                                maxi: 2.07 vs 9.88
                                                minu: 2.43 vs 6.46
                                                maxu: 2.06 vs 10.52
                                            
                                                BranchFreeTimeout.exe
                                                sign: 3.28 vs 3.66
                                                 abs: 2.36 vs 1.58
                                                mini: 3.04 vs 7.53
                                                maxi: 3.16 vs 10.84
                                                minu: 3.53 vs 7.81
                                                maxu: 3.05 vs 10.65
                                            
                                              Visual Studio 2015 (v140):
                                                Full Optimization (/Ox)
                                            
                                                BranchFreeTimeoutNew.exe
                                                sign: 15.64 vs 2.45
                                                 abs: 12.61 vs 1.49
                                                mini: 2.09 vs 6.14
                                                maxi: 2.13 vs 5.88
                                                minu: 2.41 vs 6.34
                                                maxu: 2.07 vs 6.48
                                            
                                                BranchFreeTimeout.exe
                                                sign: 3.08 vs 3.75
                                                 abs: 1.51 vs 1.50
                                                mini: 2.97 vs 7.30
                                                maxi: 2.96 vs 7.34
                                                minu: 3.52 vs 7.83
                                                maxu: 2.97 vs 8.02
                                              0

                                              То же самое для чуть более нового интела:


                                              Intel(R) Core(TM) i5-4210U CPU @ 1.70GHz:
                                              
                                                Clang 3.7 with Microsoft CodeGen (v140_clang_3_7):
                                                  Full optimization (-O3)
                                              
                                                  BranchFreeTimeoutNew.exe
                                                  sign: 17.58 vs 0.61
                                                   abs: 14.51 vs 0.24
                                                  mini: 0.41 vs 2.61
                                                  maxi: 0.35 vs 9.28
                                                  minu: 0.69 vs 2.96
                                                  maxu: 0.44 vs 8.83
                                              
                                                  BranchFreeTimeout.exe
                                                  sign: 2.94 vs 2.25
                                                   abs: 1.46 vs 1.01
                                                  mini: 1.66 vs 5.06
                                                  maxi: 2.48 vs 9.21
                                                  minu: 2.33 vs 6.16
                                                  maxu: 1.75 vs 9.43
                                              
                                                Visual Studio 2015 (v140):
                                                  Full Optimization (/Ox)
                                              
                                                  BranchFreeTimeoutNew.exe
                                                  sign: 15.54 vs 0.70
                                                   abs: 13.58 vs 0.17
                                                  mini: 0.37 vs 2.52
                                                  maxi: 0.37 vs 3.25
                                                  minu: 0.62 vs 5.21
                                                  maxu: 0.51 vs 4.88
                                              
                                                  BranchFreeTimeout.exe
                                                  sign: 3.72 vs 1.92
                                                   abs: 0.96 vs 0.86
                                                  mini: 1.65 vs 5.05
                                                  maxi: 1.49 vs 4.84
                                                  minu: 1.91 vs 6.15
                                                  maxu: 1.50 vs 5.66
                                              0
                                              Intel® Core(TM) i3-4130 CPU @ 3.40GHz
                                              g++ -std=gnu++11 BranchFreeTimeoutNew.cpp

                                              sign: 23.61 vs 1.75
                                              abs: 22.11 vs 3.52
                                              mini: 24.28 vs 10.84
                                              maxi: 24.51 vs 10.83
                                              minu: 23.90 vs 10.87
                                              maxu: 23.80 vs 10.79
                                              2147483646

                                                +1
                                                Для разнообразия, на AMD:
                                                AMD Phenom II P820 @1.80GHz
                                                Visual C++ 2015, /Ox
                                                Последовательная версия:
                                                sign: 4.81 vs 5.14
                                                 abs: 3.61 vs 2.40
                                                mini: 2.40 vs 12.01
                                                maxi: 2.40 vs 12.00
                                                minu: 2.40 vs 12.14
                                                maxu: 2.53 vs 12.73
                                                Хаотическая версия:
                                                sign: 20.19 vs -0.00
                                                 abs: 18.07 vs 0.00
                                                mini: 0.00 vs 9.60
                                                maxi: -0.00 vs 12.01
                                                minu: 0.00 vs 12.01
                                                maxu: 0.04 vs 12.01
                                                
                                                g++ 5.2.0, -std=c++11 -O3
                                                Последовательная версия:
                                                sign: 9.72 vs 9.59
                                                 abs: 7.20 vs 7.20
                                                mini: 7.20 vs 14.50
                                                maxi: 7.19 vs 9.88
                                                minu: 7.20 vs 7.20
                                                maxu: 7.20 vs 9.59
                                                Хаотическая версия:
                                                sign: 17.34 vs 2.56
                                                 abs: 16.28 vs 0.02
                                                mini: -0.00 vs 0.00
                                                maxi: 0.00 vs 3.61
                                                minu: 20.99 vs 8.91
                                                maxu: -0.00 vs 3.61
                                                

                                                Но, надо отметить, определение empty в последовательной версии некорректно: что gcc, что clang успешно сворачивают цикл с empty в константу. gcc, кстати, в неправильную константу: https://godbolt.org/g/wibi2q.
                                                  0
                                                  Вот же незадача. Даже не знаю, что делать. Volatile мне не подходит, она тупит в некоторых компиляторах, подобные пустые циклы, оказалось, тоже не подходят. Я подумаю…
                                                  0
                                                  Intel Xeon E5620
                                                  Visual C++ 2015
                                                  Опции: /Ox /arch:SSE2

                                                  Release Win32:
                                                  sign: 18.47 vs 4.68
                                                  abs: 15.53 vs 1.47
                                                  mini: 2.96 vs 8.32
                                                  maxi: 2.99 vs 7.92
                                                  minu: 3.06 vs 8.35
                                                  maxu: 2.94 vs 8.41
                                                  2147483646

                                                  Release x64:
                                                  sign: 18.56 vs 4.71
                                                  abs: 15.83 vs 1.68
                                                  mini: 3.08 vs 7.81
                                                  maxi: 3.02 vs 7.78
                                                  minu: 3.03 vs 8.32
                                                  maxu: 3.31 vs 7.61
                                                  2147483646
                                                    0
                                                    AMD FX(tm)-4300 @ 3.80GHz
                                                    gcc version 4.8.4
                                                    g++ -std=c++11 -O2 BranchFreeTimeoutNew.cpp

                                                    sign: 11.89 vs 2.16
                                                    abs: 12.05 vs 0.00
                                                    mini: -0.05 vs 2.15
                                                    maxi: -0.08 vs 1.66
                                                    minu: 12.77 vs 2.23
                                                    maxu: 0.00 vs 1.74
                                                    2147483646
                                                      0
                                                      Intel Core i7 @ 2.2 GHz (Mac)

                                                      g++ -std=c++11 BranchFreeTimeoutNew.cpp

                                                      sign: 27.91 vs 2.95
                                                      abs: 28.03 vs 4.16
                                                      mini: 32.46 vs 12.13
                                                      maxi: 32.33 vs 12.04
                                                      minu: 31.42 vs 12.93
                                                      maxu: 30.78 vs 12.90
                                                      2147483646
                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                          0

                                                          Intel® Core(TM) i7-4790 CPU @ 3.60GHz
                                                          gcc version 5.3.0 (GCC)
                                                          -std=c++11 -O3 -march=native


                                                          последовательно:


                                                          sign: 4.40 vs 2.87
                                                           abs: 2.16 vs 2.24
                                                          mini: 2.22 vs 4.85
                                                          maxi: 2.22 vs 4.43
                                                          minu: 2.22 vs 3.78
                                                          maxu: 2.58 vs 3.93
                                                          

                                                          хаотично:


                                                          sign: 9.70 vs 0.62
                                                           abs: 8.92 vs 0.27
                                                          mini: 0.46 vs 0.76
                                                          maxi: 0.46 vs 0.73
                                                          minu: 9.52 vs 0.61
                                                          maxu: 0.47 vs 0.82
                                                          
                                                            0
                                                            Никак не могу понять, почему у нескольких людей уже такие тормоза на minu с IF? Очень резко выбивается из общей картины.
                                                              +2

                                                              Исходный вариант (return a>b ? b:a;):


                                                              minu: 9.52 vs 0.61
                                                              

                                                              cmpl    %eax, %r13d
                                                              ja  .L18
                                                              addl    %r13d, %r12d

                                                              Модифицированный вариант (return b>a ? a:b;):


                                                              minu: 0.78 vs 0.64
                                                              

                                                              cmpl    %r13d, %eax
                                                              cmova   %r13d, %eax
                                                              addl    %eax, %r12d

                                                              Причуда компилятора (может если %eax является операндом не с той стороны, то шаблон для генерации cmov не срабатывает; хотя скорее тут что-то посложнее).

                                                          • НЛО прилетело и опубликовало эту надпись здесь
                                                              0
                                                              Да, это входило в мои цели тоже — мне нужно было определить, будут ли у кого-то отрицательные значения, т. к. это свидетельствует о необходимости пересмотреть методологию расчётов.
                                                                0
                                                                Для AMD такое вроде нормально, по крайней мере раньше был такой баг, исправлялось настройкой таймера в системе.
                                                                Попробуйте запустить ping 127.0.0.1 или адрес другого компьютера в локальной сети и посмотрите время ответа. Если получите отрицательное, это баг процессора.
                                                                0
                                                                Intel® Core(TM) i5-4670K CPU @ 3.40GHz
                                                                gcc (GCC) 5.3.0
                                                                Опции: -std=c++11 -O3 -DNDEBUG

                                                                Последовательно
                                                                sign: 4.64 vs 3.02
                                                                abs: 2.27 vs 2.35
                                                                mini: 2.34 vs 5.10
                                                                maxi: 2.34 vs 4.64
                                                                minu: 2.33 vs 4.54
                                                                maxu: 2.72 vs 4.47

                                                                Хаотично
                                                                sign: 10.26 vs 0.68
                                                                abs: 9.34 vs 0.33
                                                                mini: 0.55 vs 0.88
                                                                maxi: 0.55 vs 0.85
                                                                minu: 10.08 vs 0.72
                                                                maxu: 0.55 vs 0.93
                                                                  0

                                                                  Новая версия


                                                                  Intel Core i7 5500U @ 2.4GHz
                                                                  mingw-w64 x86_64-5.3.0-posix-seh-rt_v4-rev0


                                                                  Без оптимизаций:


                                                                   
                                                                  sign: 30.69 vs 2.04
                                                                  2147483646
                                                                   abs: 30.14 vs 5.40
                                                                  mini: 29.88 vs 13.06
                                                                  maxi: 30.49 vs 13.51
                                                                  minu: 29.89 vs 14.17
                                                                  maxu: 30.21 vs 14.58
                                                                  

                                                                  С оптимизациями (-fno-exceptions -fno-rtti -std=c++14 -O3 -fstrict-aliasing -flto -fomit-frame-pointer -march=native -floop-interchange -ftree-loop-distribution -floop-strip-mine -floop-block -ftree-vectorize):


                                                                   
                                                                  sign: 13.38 vs 1.40
                                                                   abs: 14.61 vs 0.50
                                                                  2147483646
                                                                  mini: 0.84 vs 1.44
                                                                  maxi: 1.14 vs 1.47
                                                                  minu: 15.34 vs 1.79
                                                                  maxu: 0.84 vs 1.80
                                                                  

                                                                  А если включить еще и -ffast-math -funroll-loops, то получается фигня


                                                                   
                                                                  2147483646
                                                                  sign: 14.54 vs -0.11
                                                                   abs: 12.93 vs -0.44
                                                                  mini: -0.39 vs 0.21
                                                                  maxi: -0.36 vs 0.53
                                                                  minu: 13.88 vs 0.61
                                                                  maxu: -0.10 vs 0.56
                                                                  
                                                                  +7
                                                                  Я как-то раз был на лекции от Интел по поводу устройства современного процессора, в контексте оптимизаций кода. Так вот, в процессорах, выпущенных в последние несколько лет, суперскалярность ого-го, может выполнять до 100 инструкций вперёд. Спекулятивно, конечно, часть из них придётся выкинуть потом. А ещё есть предсказатель переходов, в который закапывают много сил и творят чёрную магию.

                                                                  В общем, все эти блоки внутри процессора чуть ли не умнее, чем компиляторы, а они точно умнее, большинство программистов. Лезть в дебри таких оптимизаций стоит только если явно есть хотспот.
                                                                    0
                                                                    Вы правы, если говорить о настольных процессорах. Однако мне лично не очевидно, что будет на мобильных телефонах или видеокартах. Там как раз игра может стоить свеч. Суть эксперимента — проверить разные процессоры, у кого что есть. Ну и разные компиляторы между делом тоже.
                                                                      0
                                                                      Там как раз игра может стоить свеч


                                                                      Ха, неплохой каламбур получился… Именно «игра» — в основном такие оптимизации нужны разве что для геймдева.
                                                                        0
                                                                        Да нет, я бы не сказал: ) В научных вычислениях, когда попадаются задачи, занимающие миллионы часов машинного времени, такое тоже может иметь смысл.
                                                                          +1
                                                                          А зачем научные вычисления на мобильных телефонах делать… А, ой, и видеокартах. Не обратил внимание в начале, приношу свои извинения. Тогда да… На видеокартах, кстати, насколько я слышал, вообще все ветки исполняются одна за другой, а потом выбирается та, для которой условие прошло (подробнее, там когда про warp рассказывается говорится об этом).
                                                                            0
                                                                            Это мне известно, вот и интересно, насколько результат будет другим. Вообще по-хорошему для видеокарты нужно делать тесты иначе, запускать там 1 поток и делать по нему выводу — плохая идея. Нужна другая система тестирования, учитывающая её особенность.
                                                                              0
                                                                              Кстати, научные вычисления может быть полезно запускать на ARM процессорах с точки зрения экономии электроэнергии. Вместо 10 серверов x86 брать 100 на ARM, и это может оказаться дешевле/экономичнее с точки зрения электропотребления. Но это надо для каждой конкретной задачи рассматривать, экономии может и не получиться.
                                                                      +11
                                                                      Простите, но вы измеряете производительность сферического коня. На производительность алгоритмов с ветвлением огромное влияние оказывает branch prediction. У вас созданы идеальные для него условия: первые N/2 вызовов идут по одному пути, остальные — по другому. Подайте на вход случайную последовательность, и получите совершенно другие результаты.

                                                                      Для примера: rextester.com/PDBX5718. Я оставил только sign. Случайностью входа управляет макрос RANDOM.

                                                                      Данный вопрос хорошо освещен на StackOverflow: stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array
                                                                        0
                                                                        Спасибо за замечание. Если уж придираться полностью, то сам по себе способ — запускать подряд 232 раз функцию друг за другом — это тоже минус с точки зрения измерений, так как в реальных условиях всё может быть иначе.

                                                                        Исправить ситуацию можно проще: после строки 28 добавить строку
                                                                            a = 17*a+1;         \
                                                                        

                                                                        Данные будут идти хаотично. Да, разница будет.
                                                                          0
                                                                          Я исправил свою ошибку (в статье теперь ссылка на вторую программу). Хорошо, что Вы быстро появились: )
                                                                          Данный момент я знал и в точности так делал в статье про подсчёт битов, но почему-то сейчас он вылетел из головы совсем. Спасибо.
                                                                          +2
                                                                          Просто посмотрев на исходний код я могу сказать, что ваши mini, maxi, minu, maxu проиграют в скорости. Поскольку это
                                                                          i32 d = a - b;
                                                                          return a - (d&(~(d ^ ((a^b)&(d^a))) >> SHIFT));

                                                                          С его 8 операциями будет медленей чем один простой условный переход.
                                                                            +2
                                                                            Ой, вот уж не факт. Все зависит от удачного предсказания перехода. Если не угадали — сброс конвейера. А это ой как дорого.
                                                                            +5
                                                                            Ваш бенчмарк сильно зависит от работы предсказателя переходов. Попробуйте в качестве аргументов тестируемых функций передавать псевдослучайные числа вместо инкрементируемого числа и результаты будут немного другие.

                                                                            Я использовал такой генератор:
                                                                            inline unsigned int fastrand() {
                                                                            return g_seed = (214013 * g_seed + 2531011);
                                                                            }

                                                                            Табличка:
                                                                            Intel Core i7-3632QM @2.20GHz
                                                                            Visual C++ 2015
                                                                            Опции: /Ox

                                                                            sign: 19.09 vs 5.79
                                                                            abs: 16.64 vs 4.72
                                                                            mini: 11.05 vs 12.95
                                                                            maxi: 11.06 vs 13.18
                                                                            minu: 10.97 vs 13.75
                                                                            maxu: 11.07 vs 13.62
                                                                              0
                                                                              Да, об этом уже сказал meduzik, я исправил свою ошибку. Через некоторое время приведу статью в порядок (поправлю цифры). Новая версия программы в тексте статьи рядом со старой.
                                                                              0
                                                                              Intel® Core(TM) i5-4258U CPU @ 2.40GHz
                                                                              Apple LLVM version 7.3.0 (clang-703.0.29)
                                                                              Опции: -std=gnu++11

                                                                              Старая версия программы:
                                                                              sign: 2.78 vs 3.21
                                                                              abs: 3.79 vs 5.34
                                                                              mini: 6.04 vs 14.08
                                                                              maxi: 6.16 vs 13.99
                                                                              minu: 6.26 vs 13.38
                                                                              maxu: 5.87 vs 13.40

                                                                              Новая версия программы:
                                                                              sign: 33.67 vs 3.23
                                                                              abs: 30.61 vs 3.75
                                                                              mini: 31.84 vs 15.64
                                                                              maxi: 32.54 vs 13.54
                                                                              minu: 33.01 vs 13.91
                                                                              maxu: 33.41 vs 14.28
                                                                                0
                                                                                похоже термины profiling и bottleneck после этого исследования можно отправлять в историю.
                                                                                  0
                                                                                  В статью были внесены изменения: добавлена вторая версия программы с хаотичной подачей данных. Такой подход несколько меняет ситуацию для sign и abs. Можно тестировать обе версии, потому что интересно теперь и то, в каких случаях разницы не будет.
                                                                                    0
                                                                                    Тест рандомной версии на i7-3667U (mscv 2013, дефолтные настройки release):

                                                                                    sign: 13.71 vs 1.68
                                                                                    abs: 12.81 vs 0.29
                                                                                    mini: 1.11 vs 4.45
                                                                                    maxi: 1.06 vs 3.59
                                                                                    minu: 1.57 vs 4.16
                                                                                    maxu: 1.07 vs 4.28
                                                                                    2147483646


                                                                                    А теперь, внимание, снимем немного позора с min/max:
                                                                                    static i32 mini1(i32 x, i32 y) {
                                                                                        return   y ^ ((x ^ y) & -(x < y));
                                                                                    }
                                                                                    
                                                                                    static i32 maxi1(i32 x, i32 y) {
                                                                                        return x ^ ((x ^ y) & -(x < y));
                                                                                    }
                                                                                    

                                                                                    результат:
                                                                                    sign: 13.67 vs 1.66
                                                                                    abs: 13.15 vs 0.41
                                                                                    mini: 1.09 vs 2.90
                                                                                    maxi: 1.08 vs 1.89
                                                                                      0
                                                                                      В последней версии min/max используются условия. Да, эта функция быстрее, и я даже об этом писал в одной своей статье, но по условиям эксперимента соревнуются именно функция с условием и функция БЕЗ него.
                                                                                        +3
                                                                                        операторы < и > не генерят бранчинга, посмотрите генерируемый асм
                                                                                          0
                                                                                          Это я знаю, что в ряде случаев там будет линейный код. Но мы сейчас смотрим на код с позиции программиста, который не может знать, что сделает компилятор. Цель программиста — избавиться от условий, если он их видит (именно ТАК поступают те, кто фанатично избавляется от них — для них эта статья и написана). Более того, как я уже говорил, здесь просто пробный эксперимент, позже я, наверное, сделаю проверку всех существующих версий (они уже описаны в [4-7]).
                                                                                            0
                                                                                            Простите, но условия — это ключевое слово if и оператор ?, так же условия содержатся в конструкциях for и while.
                                                                                            А > и < — просто бинарные операторы.

                                                                                            Любой программист, прочитавший хотя-бы книжку K&R об этом знает.
                                                                                              –1
                                                                                              P.S.:

                                                                                              > в ряде случаев там будет линейный код

                                                                                              там во всех 100% случаев будет линейный код, на любых архитектурах, даже тех, которых пока нет, почитайте стандарт
                                                                                                0
                                                                                                Вы всё равно не о том спорите. В ряде случаев конструкции < и > могут порождать ветвление (работать как условие). Я говорю о ситуации, когда программист, видя подобную конструкцию, считает, что здесь именно условие (он не знает, что именно сгенерирует компилятор). Бинарный оператор — это не гарантия отсутствия условного перехода, об этом знает любой, кто хоть раз оптимизировал программы. Верно?
                                                                                                  0
                                                                                                  Нет, не верно, операторы < и > никогда не сгенерят бранч на x86, x86_64, IA64, ARM (включая thumb), ARM64.

                                                                                                  Вообще, в погорячился про никогда. Например, на PIC micro этот оператор сгенерит бранч. Но там и операторы + и − тоже нагенерят бранчей мама не балуй.

                                                                                                  Если программист видит оператор < или > и думает про бранч, то он, простите, дебил.
                                                                                                    0
                                                                                                    Так лучше. И не надо считать подобных программистов дебилами, потому что в отличие от перечисленных архитектур, существует масса других.
                                                                                                      0
                                                                                                      Ещё дополню: когда говорите «никогда», то следует подчеркнуть, что речь идёт о типах данных вроде int, что не превышают по разрядности разрядность кода и для которых существуют нужные инструкции в процессоре. Например, если взять Ваш код для min/max и подставить туда long long, вы увидите в листинге несколько условных переходов, хотя только что говорили, что их НИКОГДА не будет для архитектуры x86. Поэтому предлагаю не тыкать друг друга носом в Стандарт и в опыт реальной работы, а смотреть на вещи как есть. Есть не мало случаев, когда «бинарный оператор» даёт условный переход, и это не только у дебилов, у нормальных программистов тоже бывает.
                                                                                                        0
                                                                                                        Если тип данных шире машинного, то и все ваши остальные конструкции будут усыпаны бранчами.

                                                                                                        Что, операторов + − и * тоже будем бояться как огня?

                                                                                                        Вы придумали себе мнимого врага — компараторы, и с ним фанатично боретесь. Смешно же
                                                                                                          0
                                                                                                          Во-первых, Вы не правы, в этом нетрудно убедиться самостоятельно, просто скомпилировав мою версию min и max для long long — там не будет ни одного условного перехода. И не должно быть. Во-вторых, при чём тут умножение, сложение и вычитание? И там тоже не будет условных переходов, если тип данных шире регистра, в этом тоже можно легко убедиться. В-третьих, Вы считаете, что я придумал себе врага и с ним борюсь. Ошибаетесь, я как раз ни с кем не борюсь, а всего лишь предложил пробный эксперимент, по результатам которого сделаю другой. Моё мнение по поводу компараторов вы вообще нигде здесь не увидите. Вот видите, Вы уже начинаете сыпать домыслами, когда выяснилось, что Вы подходите к дискуссии по вопросу не с того краю.
                                                                                                        0
                                                                                                        .
                                                                                            –1
                                                                                            В очередной раз clang выигрывает в оптимизациях:
                                                                                            GCC vs clang
                                                                                              0
                                                                                              Кстати, раз уже тема поднялась, задам вопрос — немного оффтоп… Вот часто когда говорят про компилятор, называют его clang — видел в постах. Но clang — это ведь только frontend, а backend у него llvm. Или я ошибаюсь?.. Ещё раз приношу свои извинения за оффтоп.
                                                                                                0
                                                                                                Просто традиция. Если подходить формально, то не clang, а clang++(также как не gcc а g++), но в большинстве случаев clang построен на базе llvm-backend, так что это просто опускают. Фактически llvm объединяет группу компиляторов с общим backend, а для обозначения конкретного используется имя frontend. И, ко всему прочему, есть llvm-gcc…
                                                                                                  0
                                                                                                  Ага. Спасибо, буду знать.
                                                                                              +1

                                                                                              Все кто постит тут результаты — не забывайте включать оптимизации (-O3), иначе ваши результаты полностью бесполезны!

                                                                                                0
                                                                                                С удовольствием бы проверил код интеловским компилятором, но вот незадача: MS в последнем апдейте VS его поломало. В любом случае, ветвление в современных процессорах — совсем не тот ужас, который был лет 25 назад.

                                                                                                До сих пор приходится это объяснять студентам, которые считают ветвление дорогой операцией, ломающей конвейер. При этом эти же студенты используют pow для возведения в квадрат и злоупотребляют делением.
                                                                                                  0
                                                                                                  Ветвление — это дорогая операция, ломающая конвейр в случае ошибки предсказания. Собственно, представленные в комментариях результаты тестов это наглядно демонстрируют. Однако, стоит понимать, что все современные процессоры имеют инструкцию условного копирования (cmove), поэтому в простых случаях использование оператора ?: к ветвлению не приводит.

                                                                                                  А возведение в константную целочисленную степень, типа pow(x, 2), на современных компиляторах инлайнится в несколько умножений, поэтому ничего страшного в нем нет.
                                                                                                    0
                                                                                                    Ага, вот прямо сейчас посмотрел: компилятором VS инлайнится только возведение в степень 2.
                                                                                                    Остальные варианты — pow(x, 1), pow(x, 3), pow(x, 2.0f) — через медленные вызовы возведения в степень.
                                                                                                    В C# и того хуже: там всегда вызывается pow (проверял по времени выполнения, т.к. ассемблерный код при подключении отладчика становится другим).
                                                                                                  0
                                                                                                  Intel® Core(TM) i5-3570 CPU @ 3.40GHz
                                                                                                  Linux 3.19.0-56-generic x86_64 GNU/Linux
                                                                                                  Ubuntu 15.10
                                                                                                  gcc 5.2.1
                                                                                                  g++ -O3 -std=c++14

                                                                                                  Old:
                                                                                                  sign: 4.84 vs 5.40
                                                                                                  abs: 2.32 vs 2.44
                                                                                                  mini: 3.17 vs 5.83
                                                                                                  maxi: 3.07 vs 5.40
                                                                                                  minu: 2.98 vs 5.40
                                                                                                  maxu: 3.55 vs 5.30

                                                                                                  New:
                                                                                                  sign: 9.92 vs 3.03
                                                                                                  abs: 9.56 vs 0.17
                                                                                                  mini: 1.18 vs 1.09
                                                                                                  maxi: 1.18 vs 1.38
                                                                                                  minu: 10.31 vs 1.66
                                                                                                  maxu: 1.28 vs 1.45

                                                                                                  g++ -std=c++14

                                                                                                  Old:
                                                                                                  sign: 2.45 vs 2.28
                                                                                                  abs: 1.43 vs 3.94
                                                                                                  mini: 3.22 vs 11.44
                                                                                                  maxi: 3.23 vs 11.20
                                                                                                  minu: 3.26 vs 11.25
                                                                                                  maxu: 3.36 vs 11.24

                                                                                                  New:
                                                                                                  sign: 21.10 vs 0.76
                                                                                                  abs: 20.00 vs 2.12
                                                                                                  mini: 22.27 vs 9.19
                                                                                                  maxi: 22.19 vs 9.33
                                                                                                  minu: 22.75 vs 9.38
                                                                                                  maxu: 22.82 vs 9.46

                                                                                                  P.S.: Мне пришлось заменить `chrono::duration_cast ` на `chrono::duration_cast `, чтобы получать неотрицательные значения времени
                                                                                                    0
                                                                                                    Что на что вы заменили? Опечатка, наверное?
                                                                                                      0
                                                                                                      chrono::duration_cast <chrono::duration<double,std::ratio<1>>> вместо chrono::duration_cast <chrono::duration>
                                                                                                        0
                                                                                                        бага дурацкая какая-то, никак не могу написать duration_cast<chrono::duration_cast\<double\>>
                                                                                                    +5
                                                                                                    В первую очередь нужно смотреть в дизассемблер. На x86 есть инструкция cmov (условное присваивание), предназначенная для избавления от простых ветвлений. Плюс есть SSE инструкции вычисляющие max/min для тех случаев, где цикл может быть векторизован. На ARM практически все инструкции могут быть условными, NEON (векторные инструкции на ARM) тоже поддерживает max и min. Так что у хорошего компилятора даже в коде с if'ами не будет полноценных ветвлений.

                                                                                                    PS Для предотвращения оптимизации циклов, нужно использовать volatile. Так же советую посмотреть это видео про микробенчмарки: CppCon 2015: Chandler Carruth «Tuning C++: Benchmarks, and CPUs, and Compilers! Oh My!»
                                                                                                      –1
                                                                                                      Я вообще-то написал про cmovXX, и сообщил, что компилятор может использовать данную конструкцию при необходимости. Да, у хорошего компилятора не будет ветвлений, но я веду речь про тех программистов, кто до сих пор этого не знает. С другой стороны, как выяснилось, при хаотичном потоке данных функции без ветвлений (sign, abs) на x86 чаще выигрывают.

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

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

                                                                                                        Далее, если говорить о честном тестировании функций, то тут вообще беда — даже хаотичное тестирование в цикле не сильно полезно (в малых циклах процессор может кэшировать сразу уже раскодированные команды при первом проходе, не раскодируя их затем при остальных), так как в реальных условиях, особенно когда нужная нам функция окружена некими другими командами, всё может быть совершенно иначе. Я ищу разные варианты решения этой проблемы, но пока не нахожу. Пока прихожу к выводу, что оптимизация программ в современных процессорах — это IT-аналог гадания на кофейной гуще. Хоть что делай — мы не знаем, что с этим сделает процессор, особенно если учесть, что ряд команд он преобразует во внутренние RISC команды которые (кстати) могут оказаться с ветвлениями (хотя исходные команды были без них). И вот об этих тонкостях работы микрокоманд хотелось бы узнавать из подобных видео. О том, насколько вообще честно мы можем измерить время работы функции, чтобы это было близко к реальным условиям.
                                                                                                        0
                                                                                                        Kubuntu 15.10 x64
                                                                                                        i7-4700MQ CPU @ 2.40GHz
                                                                                                        gcc 5.2.1

                                                                                                        # g++ -std=c++11 BranchFreeTimeoutNew.cpp -o test.elf
                                                                                                        # ./test.elf
                                                                                                        sign: 24.26 vs 2.54
                                                                                                        abs: 24.49 vs 4.54
                                                                                                        mini: 26.85 vs 12.34
                                                                                                        maxi: 26.27 vs 12.45
                                                                                                        minu: 32.05 vs 12.84
                                                                                                        maxu: 31.15 vs 14.50
                                                                                                        2147483646

                                                                                                        # g++ -std=c++14 -O3 BranchFreeTimeoutNew.cpp -o test.elf
                                                                                                        # ./test.elf
                                                                                                        sign: 12.25 vs 1.09
                                                                                                        abs: 11.18 vs 0.58
                                                                                                        mini: 0.86 vs 1.21
                                                                                                        maxi: 0.85 vs 1.11
                                                                                                        minu: 11.87 vs 0.95
                                                                                                        maxu: 0.89 vs 1.20
                                                                                                        2147483646

                                                                                                          +4

                                                                                                          И ещё, для всех, если ещё не знаете — есть великолепный сервис gcc.godbolt.org, который позволяет быстро посмотреть на ассемлерный кот сгененированный разными компиляторами. Поддерживаются GCC, Clang и ICC разных версий и для разных архитектур.


                                                                                                          Вот пример (GCC 6, -O3):


                                                                                                          mini0(int, int):
                                                                                                                  cmpl    %esi, %edi
                                                                                                                  movl    %esi, %eax
                                                                                                                  cmovle  %edi, %eax
                                                                                                                  ret
                                                                                                          maxi0(int, int):
                                                                                                                  cmpl    %esi, %edi
                                                                                                                  movl    %esi, %eax
                                                                                                                  cmovge  %edi, %eax
                                                                                                                  ret
                                                                                                          mini1(int, int):
                                                                                                                  movl    %edi, %eax
                                                                                                                  movl    %edi, %edx
                                                                                                                  subl    %esi, %eax
                                                                                                                  xorl    %edi, %esi
                                                                                                                  xorl    %eax, %edx
                                                                                                                  andl    %edx, %esi
                                                                                                                  xorl    %eax, %esi
                                                                                                                  notl    %esi
                                                                                                                  sarl    $31, %esi
                                                                                                                  andl    %eax, %esi
                                                                                                                  movl    %edi, %eax
                                                                                                                  subl    %esi, %eax
                                                                                                                  ret
                                                                                                          maxi1(int, int):
                                                                                                                  movl    %edi, %edx
                                                                                                                  movl    %edi, %eax
                                                                                                                  subl    %esi, %edx
                                                                                                                  xorl    %esi, %eax
                                                                                                                  xorl    %edx, %edi
                                                                                                                  andl    %edi, %eax
                                                                                                                  xorl    %edx, %eax
                                                                                                                  notl    %eax
                                                                                                                  sarl    $31, %eax
                                                                                                                  andl    %edx, %eax
                                                                                                                  addl    %esi, %eax
                                                                                                                  ret
                                                                                                          

                                                                                                          Видно, что GCC сгенерировал cmov интсрукции, и в результате варинт с if не содержит условных переходов.

                                                                                                            +4
                                                                                                            Со всеми этими оптимизациями ветвлений надо иметь ввиду, что во многих случаях эта оптимизация не бесплатна и процессор как-бы вычисляет обе веткие ветки одновременно, т.е. иногда вычислений становится больше. А когда вычислений больше надо учитывать наличие свободных исполнительных устройств, instruction latency, зависимости по данным и т.п.
                                                                                                            Всё сводится к обычному The Third Rule of Code Optimization: Profile first
                                                                                                              –2
                                                                                                              Ветвление на современном процессоре стоит 0 тактов. В оптимистичном сценарии. Причём ничего не стоит не только сам if, но и условие внутри него. Это возможно благодаря так называемому предсказанию переходов. Но это название не более, чем маркетинговый трюк. Никакого предсказания в строгом смысле этого слова в процессоре не делается. Просто одновременно с вычислением условия на соседнем конвейере начинается выполнение той ветки, которая будет выполнена в случае true. Таким образом, к тому моменту, когда условие будет реально просчитано, первая ветка уже будет выполнена ровно на столько тактов, сколько потребовалось на вычисление условия. Конечно, если окажется, что условие равно false, то результаты выполнения первой ветки придётся отбросить и начать выполнять вторую ветку с самого начала. Но, во-первых, в компиляторе есть специальная оптимизация. Когда компилятор уверен в том, что наиболее вероятной веткой является else, он тупо переставляет ветки местами и инвертирует условие внутри if. Во-вторых, есть программист, который иногда лучше компилятора знает, какая ветка является более вероятной. Хороший программист всегда ставит наиболее вероятную ветку первой. На тот случай, если оптимизатор в компиляторе не сможет придти к однозначному выводу о необходимости оптимизации. В этом случае оптимизатор просто ничего не меняет и оставляет так, как было у программиста.
                                                                                                                +2
                                                                                                                На самом деле это неправда. Если бы стоимость была 0 тактов, то не было бы разницы между последовательным и хаотичным потоком данных.
                                                                                                                  –1
                                                                                                                  Эта разница объясняется иначе. Ветвление тут ни при чём. Это другая оптимизация, которая относится к циклам. Когда оптимизатор видит, что в коде есть цикл, в котором переменная монотонно возрастает/убывает, он переделывает код таким образом, чтобы эта переменная всегда была в регистре. И прямо в регистре он её инкрементит/декрементит, не перекладывая постоянно из регистра в память/кэш и обратно.
                                                                                                                    0
                                                                                                                    Нет, дело не в этом. Когда данные подаются хаотично (по формуле), переменная также находится в регистре, я проверял (там же она пересчитывается). Более того, я всегда вычитаю время работы самого вычисления этих данных, оставляя чистое время работы самой функции.
                                                                                                                      0
                                                                                                                      Не вижу, чтобы в программе измерялось время вычисления нового значения по формуле. Там измеряется только общее время работы всего цикла. Да это и невозможно сделать. На сам замер уйдёт несравнимо больше времени, чем на вычисление формулы.
                                                                                                                        0
                                                                                                                        Я измеряю время работы пустого цикла, который генерирует входные данные, затем полного цикла, который вместе с генерацией данных вызывает функцию. В ассемблерном листинге я убедился, что генерация происходит в регистре. Затем я вычитаю время работы полного цикла и пустого — получаю почти чисто время работы функции. А мы наблюдаем, что разница между одной и другой версией колоссальна. Версия с ветвлением может работать в несколько десятков раз медленнее, чем без ветвлений при хаотичной подаче, когда как при последовательной подаче версия с ветвлением выигрывает. Это можно объяснить только тем, что ветвление играет роль в вычислениях, особенно когда предсказатель не может надёжно предсказывать.
                                                                                                                          0
                                                                                                                          Это некорректно. Когда вы убираете из цикла вызов тестируемой функции, выполнение кода распределяется по конвейерам процессора совсем по-другому. Условие продолжения цикла (while (a != 0)) — это тоже ветвление. Процессор начинает выполнять следующую итерацию цикла ещё до того, как вычислит формулу, в надежде на то, что a действительно не будет равно нулю. В случае пустого цикла каждая следующая итерация цикла использует один дополнительный конвейер. Пока предыдущее значение a ещё не готово, на этом конвейере уже можно делать всё, что не зависит от a: 1) выбрать какие именно из блоков умножения и сложения будут использованы (и тех и других много); 2) загрузить в них обе константы (19993 и 1); 3) подготовить два временных места для размещения результатов умножения и сложения (внутренних для конвейера); 4) хрен знает что ещё (конвейер делает много такого, что не сразу приходит в голову). А когда в цикле есть ещё и функция, которая тоже зависит от a, то каждая следующая итерация задействует два дополнительных конвейера. Один делает всё то же самое, что и в случае пустого цикла, а второй параллельно начинает выполнять тестируемую функцию и делает всю возможную работу, которую можно сделать до того, как реально упрётся в отсутствие значения a, вычисленного на предыдущей итерации. Короче говоря, я хочу сказать, что замер на пустом цикле вообще никак не соотносится с замером на цикле с тестовой функцией.
                                                                                                                            0
                                                                                                                            Мы сейчас разговариваем не о способе измерения времени, а о том, что по Вашим словам стоимость ветвления равна нулю. Это не так и это нетрудно показать. Тот факт, что я не вполне корректно измеряю время работы функции мне и так хорошо известен. Но других вариантов, увы, не вижу. Этот способ хотя бы как-то коррелирует со сложностью функции.
                                                                                                                              0
                                                                                                                              Пока вам удалось показать это лишь с опорой на предположение о том, что будто бы вам удаётся измерять время работы функции в цикле отдельно от времени работы самой циклической конструкции. Это не так. Именно поэтому я и начал говорить о способе измерения времени. Я считаю, что измерить время работы настолько крохотных функций путём многократного их повторения в цикле на современном процессоре вообще невозможно. Тем более при использовании ключа -O3.
                                                                                                                                0
                                                                                                                                Да сколько можно… я не говорю нигде про отдельное измерение. Я сказал, что получаю почти чистое время работы функции в этих конкретных условиях. Это время не является точным, но оно коррелирует с реальностью. С тем, как функция будет вести себя в практических приложениях. Вы же, невнимательно прочитав мой ответ, считаете, что я делаю абсолютно точные вычисления и спорите с этой выдумкой. Не надо так.
                                                                                                                                  0
                                                                                                                                  Нигде не говорил подобного. Я отрицаю именно то, что вы на самом деле утверждаете. То, что замер не является точным, — понятно. Это само собой. Речь идёт о том, что он также не является ни чистым, ни почти чистым. Условия замера в случае «пустого» цикла и в случае цикла с функцией совершенно разные.
                                                                                                                                    0
                                                                                                                                    Попробую на пальцах объяснить.
                                                                                                                                    Есть функция f, а есть функция g. Есть цикл, внутрь которого мы встраиваем эти функции. С функцией f получаем время A, с функцией g получаем время B. Есть ещё время C, когда цикл почти пустой (там только генерация данных). Я вычисляю (A-C) и (B-C), называя это практически чистым временем работы функции. Я называют это этим словом, то есть даю название этим значениям (Вы можете называть их «грязным временем», суть это не поменяет). Эти значения разные, они показывают то, насколько одна функция быстрее или медленнее другой (можно даже не вычитать C, если угодно, но я хочу вычитать).
                                                                                                                                    Вы понимаете? Я получаю два разных числа и на основе их соотношения делаю приблизительный вывод о скорости работы функций. Этот вывод коррелирует с реальностью. Я не говорю, что данные числа отражают реальность, я говорю, что если в этом эксперименте одна функция сильно быстрее другой, то в реальности будет ТО ЖЕ САМОЕ. Это понятно? Если нет, то что именно не так?
                                                                                                                                      0
                                                                                                                                      Зачем вы всё это мне объясняете? Это всё понятно из текста программы. Проблема в другом. Не в том, что я не понимаю, что вы хотите измерить, а в том, что вы реально измеряете не то, что хотите. Понимаете? Мысленная модель вашего эксперимента не соответствует тому, как это на самом деле выполняется в процессоре с предсказанием условных переходов. В вашей модели сама циклическая конструкция никак не влияет на вызываемую внутри функцию. Вы просто вычитаете время, затраченное на цикл, из общего времени. В действительности же при выполнении в цикле таких простейших функций конструкция цикла оказывается неразделимо переплетена с самой функцией. Когда вы убираете из цикла вызов функции, процесс выполнения самой циклической конструкции меняется очень существенно. Проще говоря, вы не можете вычислить (А-С). Когда вы измеряете A, в него в качестве составляющей входит время, которое вы обозначаете как С. А когда вы пытаетесь измерить это С отдельно (чтобы вычесть его из A), у вас реально измеряется время, которое даже не С-штрих… это просто другое время — D… оно никак не связано с тем С, которое входит в А. Возможно, какая-то связь между C и D есть, но скорее всего даже разработчики процессоров не сразу скажут, какая именно и есть ли связь вообще.
                                                                                                                                        –1
                                                                                                                                        Нет, Вы по-прежнему меня не понимаете, приписывая мне своё видение эксперимента. Будет ли Вам лучше, если я скажу, что мне нужны числа A и B? А зачем они нужны — я в тексте статьи не говорил. Число C я вычитаю для более удобного определения соотношения (считайте это погрешностью). По поводу наличия или отсутствия связи между этими величинами и реальностью я имею своё мнение, основанное на моём опыте. При этом заметьте, я не спорю, что эти числа никакого отношения к реальному времени работы функции не имеют, я утверждаю лишь, что есть чёткая корреляция.
                                                                                                                                          0
                                                                                                                                          А я, основываясь на своём опыте, считаю, что такая корреляция могла бы быть лишь в том случае, если бы в процессоре не было бы оптимизации ветвлений через предсказание переходов. При этом мой опыт больше и лучше вашего. Я занимаюсь программированием только на С++ более 15 лет. А до этого писал на чистом С и ассемблере. Так что вы совершенно напрасно придаёте такое значение своему опыту в нашем с вами разговоре. По сравнению с моим он незначителен (считайте его погрешностью).
                                                                                                                                            0
                                                                                                                                            Ну началось: ) Сейчас будем выяснять, кто круче по числу лет. Наверное, Вы из тех людей, кто путает количество и качество.

                                                                                                                                            Внимательно слушаю ответ на мой вопрос ниже.
                                                                                                                                              0
                                                                                                                                              Выяснять ничего не будем. Понятно, что я круче и по числу лет и по качеству опыта. Но заметьте, не я начал делать упор на свой опыт, пытаясь что-то обосновать. Это вы начали. Я про опыт заговорил лишь для того, чтобы напомнить вам, что опыт есть не только у вас.
                                                                                                                                                0
                                                                                                                                                Вы не правы. Я сказал про свой опыт ТОЛЬКО для того чтобы показать, что в нём (в моём опыте) присутствует корреляция между моими сферическими в вакууме экспериментами и тем, как результаты опыта ложатся на реальные задачи. А Вы приняли это на свой счёт, будто бы я пытаюсь соревноваться. Нет, этого, увы, не будет: )
                                                                                                                                                  0
                                                                                                                                                  Возможно, я что-то неправильно понял. Мне показалось, что вы каким-то образом обосновываете свою правоту ссылкой на опыт. Это выглядело как заход с козырей. Естественно, я был вынужден ответить тоже козырем. Любой подобный разговор чем-то похож на преферанс, где отвечать нужно той же мастью. А из козырей у меня, к сожалению, есть только старшие карты — туз и король.
                                                                                                                                                    0
                                                                                                                                                    Нет, простите, если я, быть может, выбрал не тот оборот речи, однако когда я сказал «опыт», то это было (и мне показалось, я написал ясно), в контексте того, что мой опыт таких экспериментов даёт нужный результат в реальных расчётах. Обычно в научных, потому как оптимизацией бытовых программ я не занимаюсь. Это было сказано против Вашего тезиса о том, что будто бы мои эксперименты не имеют смысла. Хотя я-то знаю, что имеют.
                                                                                                                                      0
                                                                                                                                      На всякий случай, вынужден пояснить один философский момент из нашей жизни. В нашей жизни многие вещи определяются косвенно, так как напрямую их определить нельзя вообще никак. Так, например, учёные не могут разглядеть и замерить свойства квантовых частиц, но определяют их физику по косвенным признакам, в результате соударения их друг об друга. Получаемая физиками модель отвечает на ряд вопросов, важных для физиков. Далее, в реальных условиях человек не бегает по беговой дорожке в соответствующей одежде, однако если взять двух людей на беговой дорожке и двух людей, бегущих за троллейбусом, то и там, и там оба покажут качественно одинаковый результат (тот прибежит первым, кто лучше к этому подготовлен). В мире всё так, эксперимент есть эксперимент, и если я говорю, что мне нужны эти данные и я знаю, что с ними делать, значит на то у меня есть основания, диктуемые опытом. А кому кажется, что тут нет ВООБЩЕ никакой связи — ну значит это его мнение, пусть кажется дальше. Любой факт может иметь значение для того, кто в теме. Кто не в теме, тому это может ничего не говорить. Вот на этом можно и остановить разговор.
                                                                                                                                        0
                                                                                                                                        Он вас не слушает. Я хотел большой коммент написать про измерение сферического коня в вакууме. Но вы уже это разжевали так, что по-моему больше даже вопросов быть не может.
                                                                                                                                          0
                                                                                                                                          Вряд ли Вам это помогло бы, потому что я как раз знаю, что делаю. Не уверен, что мне необходимо это пояснять кому-либо. Или Вы считаете иначе?
                                                                                                                                  0
                                                                                                                                  Ещё Вы неверно поняли смысл пустого цикла (посмотрите всё-таки программу и мой комментарий выше внимательнее). Пустым я назвал цикл, в котором есть вычисление потока данных. То есть формула там тоже присутствует.
                                                                                                                                    0
                                                                                                                                    Это я понял. И из моего предыдущего комментария видно, что я это понял. Я назвал цикл пустым только потому, что соответствующий этому циклу тайминг у вас сохраняется в переменную empty.
                                                                                                                                      0
                                                                                                                                      В таком случае нет смысла мне сообщать, что я что-то делаю неправильно. Я же назвал условия эксперимента. Вы же спорите с тем, как Вы представляете себе этот эксперимент, а не я.
                                                                                                                        +3

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

                                                                                                                          0
                                                                                                                          Тогда измерять тем более бессмысленно. Чтобы измерения имели смысл, нужно знать логику работы с этими таблицами и учитывать её.
                                                                                                                            0
                                                                                                                            Смысл есть всегда. В данном случае мы пытаемся отыскать разницу по времени работы функций по отношению друг к другу. Наши измерения показывают эту разницу и в ней есть смысл. Или Вы хотите утверждать, что если, скажем, в наших экспериментах одна функция быстрее другой в 10 раз, то в реальных программах со случайным потоком данных может статься наоборот?
                                                                                                                              –1
                                                                                                                              Нет, они показывают не эту разницу, а какие-то неслучайные числа, которые не имеют отношения к умозрительной модели вашего эксперимента.
                                                                                                                                0
                                                                                                                                Это ещё нужно доказать, что не имеют отношения. Подобные голословные заключения здесь мало полезны.
                                                                                                                                  0
                                                                                                                                  К сожалению, всё ровно наоборот. Традиционно доказывать нужно именно соответствие модели эксперименту. Не наоборот.
                                                                                                                                    0
                                                                                                                                    Ничего подобного, я же не приводил никакой модели и не называл целей эксперимента. Цель и модель приписали мне Вы, и с ней же спорите. Если я даже попрошу Вас назвать мою умозрительную модель — Вы не сможете этого сделать. Попробуйте, если не верите.
                                                                                                                                      +1
                                                                                                                                      То, что вы не привели никакой модели эксперимента, — это не оправдание, а скорее отягчающее обстоятельство. Должны были привести, если считаете, что эта модель не следует однозначно из текста программы. Эксперимент, который не имеет никакой модели, не имеет и смысла.

                                                                                                                                      На самом деле, модель вашего эксперимента вытекает из текста программы. Когда я якобы приписал вам цель и модель, я их не выдумал, а прочитал в программе. В ней очень чётко видно, что именно вы пытаетесь измерить. И не менее чётко видно главную ошибку. Вы не учитываете наличие ветвления в точке, где проверяется условие выхода из цикла, которое очень хорошо оптимизируется предсказателем переходов путём распараллеливания цикла на несколько конвейеров. Чтобы доказать состоятельность вашей модели, просто покажите пальцем, где и как вы учитываете то, что это ветвление приведёт к совершенно разным временным параметрам в случае разного объёма параллельной работы непосредственно в теле цикла. На всякий случай скажу, что слова «совершенно разные» означают не то, что они не равны, а то, что они не коррелируют.
                                                                                                                                        0
                                                                                                                                        Ответьте, пожалуйста, на простой вопрос.
                                                                                                                                        Вот цикл, который выполняется 20 секунд:
                                                                                                                                          u32 i = 0, s = 0;
                                                                                                                                          do {
                                                                                                                                            i = 19993*i + 1;
                                                                                                                                            s += sign0 ((i32)i);
                                                                                                                                          } while (i!=0);
                                                                                                                                        

                                                                                                                                        Вот цикл, который выполняется 10 секунд:
                                                                                                                                          u32 i = 0, s = 0;
                                                                                                                                          do {
                                                                                                                                            i = 11*i + 1;
                                                                                                                                            s += sign0 ((i32)i);
                                                                                                                                          } while (i!=0);
                                                                                                                                        

                                                                                                                                        (Функции в цикле одинаковые — которые с IF из статьи).

                                                                                                                                        Вопрос такой: почему время работы разное, если принять во внимание Ваше утверждение о том, что ветвление работает 0 тактов? Мой компилятор выдаёт абсолютно идентичные листинги программ, разница только в константе, которая кладётся в регистр. В первом случае 19993, во втором — 11.

                                                                                                                                        По поводу эксперимента… Вы продолжаете заниматься приписыванием мне какой-то своей модели поведения. У меня есть цели и задачи эксперимента (а Вы сказали, что нет), я знаю, чего я хочу добиться, но я не обязан об этом сообщать. Если Вы не понимаете моих целей, то это НЕ значит, что моя методика обязана совпадать с Вашим представлением о таковой. Верно?

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

                                                                                                                                        Я внимательно слушаю Ваш ответ на простой вопрос.
                                                                                                                                          –1
                                                                                                                                          Константа разная, поэтому и время работы разное. Операция умножения выполняется за разное время, которое зависит от операндов.

                                                                                                                                          К сожалению, этот вопрос никак не связан с вашим экспериментом. (Хотя я понимаю, что вы считаете иначе.) Эти два цикла можно сравнивать, потому что их потенциальная возможность распараллеливания на несколько конвейеров одинакова. А у вас в эксперименте сравниваются два цикла с разным потенциалом к распараллеливанию. В том варианте, где есть тестируемая функция, каждая итерация потенциально может выполняться на двух конвейерах параллельно. На первый конвейер уходит вычисление нового значения a, на второй — выполнение тестируемой функции, которое от нового значения a не зависит. Грубо говоря, выполнение той функции, которую вы тестируете, происходит параллельно с вычислением нового значения по формуле. Но только тогда, когда дополнительный свободный конвейер есть. Но даже тогда когда его нет, выполнение функции необязательно происходит на том же конвейере, что и вычисление формулы. Возможно, свободный конвейер появится в середине вычисления формулы. Это абсолютно непредсказуемый процесс. А то, что он ещё и выполняется очень много раз в цикле, само по себе сделало бы его ещё более непредсказуемым, если бы это было возможно.

                                                                                                                                          Удивительно, что после столь подробных разъяснений, вы всё ещё не понимаете сути проблемы.
                                                                                                                                            0
                                                                                                                                            Обождите. Я никак в толк не возьму: что именно я не понимаю? Вы можете сформулировать конкретный тезис? Чётко и одним предложением.

                                                                                                                                            Можно ли узнать, как размер константы связан со скоростью вычисления? Константы какого размера будут давать одинаковое время умножения, если второй операнд всегда 32 бита?
                                                                                                                                              –1
                                                                                                                                              Одним предложением это вряд ли можно сформулировать. Важен не размер константы, а количество значащих разрядов, а иногда и конкретное значение. Например, умножение на 11 можно сделать вообще без умножения. В десятичной системе это часто можно сделать в уме: добавить справа ноль, умножив таким образом на 10, и прибавить к результату операнд. Для двоичной системы тоже несложно придумать алгоритм без умножения: добавить к операнду три нуля, прибавить операнд с двумя добавленными нулями и вычесть операнд. Если я смог придумать такой алгоритм за 10 секунд, то разработчики процессора скорее всего тоже додумались до такой оптимизации за много лет работы и встроили её в блок, выполняющий умножение.
                                                                                                                                                0
                                                                                                                                                Хорошо, я признаю, что здесь облажался. Сейчас проверил с константой 257, стало работать одинаково. Но эта константа довольно большая для моих целей, поэтому мой тест не показывает ни положительного, ни отрицательного результата. Зато данный результат показывает эксперимент в моём комментарии ниже.
                                                                                                                                              0
                                                                                                                                              Я продолжил свой эксперимент: загнал в массив упорядоченный набор чисел и запустил цикл с функцией sign0 (которая с IF), получил почти 16 секунд. Затем взял массив из тех же, но неупорядоченых чисел, получил 20 секунд. Затем повторил эксперимент с функцией sing1 (без IF), время работы в обоих случаях одинаково (16,8 сек). Вывод: ветвление вносит дополнительные затраты на работу программы, когда предсказатель не может надёжно предсказывать, то есть ветвление — это не 0 тактов.
                                                                                                                                                –1
                                                                                                                                                Но я и не говорил, что оно всегда 0 тактов. Мой первый коммент состоял не только из первого предложения. Фактически, уже со второго предложения начинается объяснение, почему иногда может быть не 0. Естественно, если вы будете специально запутывать предсказатель, то не 0 тактов будет чаще. Но в реальных программах входные данные, как правило, не запутаны. И значит стоимость ветвления в среднем близка к нулю. И обычно можно не беспокоиться о том, что у тебя в программе есть лишний IF, который можно было бы убрать, придумав какой-нибудь изощрённый алгоритм.
                                                                                                                                                  –1
                                                                                                                                                  К сожалению, в моей реальности это не так, иначе я вряд ли бы занимался подобными экспериментами. В одних случаях ветвление работает быстрее, в других без него быстрее. На видеокартах так вообще часто приходится делать уйму работы, чтобы вместо одно IF была сотня строк, но зато более быстрых. В таком случае, я не понял суть вашей претензии. Из двух алгоритмов я выбираю тот, который на моих сферических в вакууме тестах работает быстрее — и этот выбор я делаю на разных компьютерах с помощью сообщества, которое эти тесты запускает.
                                                                                                                                                    +1
                                                                                                                                                    Суть в том, что а) эксперимент здесь не нужен; б) эксперимент смоделирован неверно.

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

                                                                                                                                                    А смоделирован эксперимент неверно, потому что он не учитывает параллельность работы нескольких конвейеров. Вот вы говорите про видеокарты. Соответственно, про конвейеры должны знать. И хотя напрямую сравнивать видеокарты с обычными процессорами в этом смысле нельзя. В видеокартах этих конвейеров тысячи. Но и вообще никак не учитывать этот вопрос в эксперименте тоже нельзя, потому что в обычном современном процессоре конвейеров десятки. И они намного сложнее и эффективнее тех, что в видеокартах. Внутри конвейера ассемблерные инструкции могут менять последовательность своего исполнения, могут разбиваться на несколько этапов, чтобы поменять последовательность можно было хотя бы у этих отдельных этапов. Это всё вносит такую суровую неопределённость в процесс, что сама идея эксперимента, призванного исследовать в таких условиях отдельный IF, смехотворна. Это все равно, как крутить рулетку, пытаясь экспериментальным образом выявить распределение вероятности попадания шарика на определённые числа в ситуации, когда гравитация постоянно меняется и влияет на шарик в каждый момент времени непредсказуемым образом. Маленький ничтожный шарик — это IF, вклад которого в общий тайминг вы пытаетесь исследовать. А гравитация — это оптимизатор, распределяющий работу по конвейерам. Да, гравитация вроде бы не видна и кажется, что её нет. Но её влияние то, что происходит с шариком, более чем существенно.
                                                                                                                                                      –2
                                                                                                                                                      Так… ну вот, как я и говорил, Вы совершенно неверно понимаете мою мотивацию. Чтобы говорить о верности или неверности эксперимента, нужно знать мои цели. Вы их не знаете (а я их и не говорил). Далее, Вы серьезно думаете, что в какой-то программе sign, abs или минимум с максимумом будут узким местом, чтобы с ними так возиться? Вряд ли. Вообще эти функции — это последнее, что меня интересовало бы в сложной программе, где они как капля в море. Меня интересует в этом эксперименте другое, совсем другое… и я ещё даже не решил, писать статью с объяснением или нет.
                                                                                                                                                        +1
                                                                                                                                                        Ну, на это я даже не знаю, что сказать. Эксперимент совершенно точно выглядит как эксперимент по исследованию ветвлений. Понятно, что на примере каких-то конкретных функций, и что сами эти функции не имеют значения. Но предметом исследование определённо является само ветвление и его влияние на тайминг. Если это на самом деле не так, и реальная цель вашего эксперимента состоит, например, в исследовании того, сколько человек поведутся на призыв и начнут запускать бессмысленный и некорректный бенчмарк на своих машинах, то тогда у меня нет возражений по существу. Если эксперимент был социальным, то он действительно удался.
                                                                                                                                                          –1
                                                                                                                                                          Чушь несёте. Одна из косвенных целей — сравнить два алгоритма. В одном из них есть IF (в программе), в другом — нет. При этом меня совершенно не интересует, как именно будет работать (и будет ли он вообще после компиляции) условный переход. Теперь ясно? Суть: есть сферический в вакууме цикл проверки двух РАЗНЫХ (абсолютно разных) функций, мне нужно узнать время работы этих циклов минус время работы цикла, который я назвал пустым (даже если разность будет отрицательной). Зачем мне это нужно — этого я нигде не говорил. Далее, не нужно пытаться делать выводы только на основе того, как с Ваших позиций выглядит эксперимент. Очень может оказаться, что Вы многого не знаете, чтобы залезать в чужую голову и делать вид, что Вы там что-то понимаете. Я так и не понял, вашу претензию. Видимо, её нет, а Вы хотели просто что-то сказать, но не знали, что. Ещё раз: условные переходы в скомпилированном коде меня НЕ интересуют. Не интересует меня и то, как долго или быстро работает IF, где бы он ни был.
                                                                                                                                                            0
                                                                                                                                                            Ну, тогда просто согласимся на том, что обычно условный переход ничего не стоит и париться на счёт него не нужно.

                                                                                                                                                            А о чём в действительности был ваш эксперимент, вы расскажете в другой раз. И лучше кому-нибудь другому. Я уже устал от того, что вы мне постоянно пересказываете суть вашего эксперимента разными словами, каждый раз делая акцент на том, что я его неправильно понял, хотя каждый следующий пересказ лишь укрепляет мою уверенность в том, что я правильно понял суть с первого раза.
                                                                                                                                                        –2
                                                                                                                                                        Далее, если продолжить указывать Вам на логические ошибки, то можно это сделать со многих сторон. Вот одна из них: я сказал Вам, что меня интересует время работы моего цикла при вызове одной и другой функции. Вы же мне говорите, что я исследую работу IF, хотя эти два момента не связаны напрямую. Сколько уже можно приписывать мне СВОИ представления о том, что Я делаю, а не Вы?
                                                                                                                                                          +1
                                                                                                                                                          Добро пожаловать в реальность! В будущем все люди, с которыми вы будете иметь дело, только тем и будут заниматься, что приписывать вам те мысли и цели, которые, как они думают, у вас есть. Телепатов, к сожалению, нет. Но это не мешает людям думать, что они точно знают мысли других. Вам придётся как-то научиться жить с этим. И не факт, что сможете. У многих гиков это не получается и со временем они начинают не любить окружающих за то, что их никто не понимает.
                                                                                                                                                            –1
                                                                                                                                                            С чего Вы решили, что знаете, с какими людьми я буду иметь дело в будущем? Более того, класс людей, которые любят соваться в том, в чём не разобрались достаточно хорошо, очень велик и меня это не удивляет. Меня удивляет Ваша упорная настойчивость повторять мне одну и ту же мысль, которую я понял с первого раза и против которой чётко и ясно указал контраргумент, а затем повторил его 10 раз. Вот здесь в комментарии это последний раз. И то, я сделал одолжение, что так настойчиво объяснял свою позицию. Если и сейчас не понятно, то мне теперь это безразлично. Разговор окончен: )
                                                                                                                                                              +1
                                                                                                                                                              Я говорю о людях вообще. Мне не нужно знать, с какими конкретно людьми вы будете иметь дело, чтобы предсказать, какие у вас будут с ними проблемы. У всех людей есть одно общее свойство — они не телепаты. Мой прогноз основан только на этом свойстве людей.
                                                                                                                                                  +1
                                                                                                                                                  Касательно операции умножения — есть такой документик:
                                                                                                                                                  http://www.agner.org/optimize/instruction_tables.pdf

                                                                                                                                                  В современных процессорах операция умножения выполняется за константное количество тактов. А вот время выполнения деления пока что довольно долгое и зависит от значений операндов.
                                                                                                                                                    –1
                                                                                                                                                    Поздно. Он уже проверил. И у него получились разные результаты при разных значениях операндов.
                                                                                                                                                  +3
                                                                                                                                                  Время работы этих циклов отличается ровно в 2 раза, потому что тело цикла с константой 19993 исполнится 4294967296 раз, а с константой 11 — 2147483648 раз.
                                                                                                                                0
                                                                                                                                Нужно понимать что вот под капотом глубоко где-то так (вариант 2) и будет, по крайней нормальный Math-compiler именно так и сделает, но это будет работать быстрее, потому что там решили общую задачу и написали 100.000 тестов. В принципе, поэтому либы и пишутся.

                                                                                                                                Классический вариант реализуется несложной схемой из условий:

                                                                                                                                Вот такие штуки превращаются
                                                                                                                                sign_t sign0 (i32 a) {
                                                                                                                                if (a>0) return +1;
                                                                                                                                if (a<0) return -1;
                                                                                                                                return 0;
                                                                                                                                }
                                                                                                                                В вот такие штуки:
                                                                                                                                sign_t sign1 (i32 a) {
                                                                                                                                return (a >> SHIFT) | ((u32)(-a) >> SHIFT);
                                                                                                                                }
                                                                                                                                  0
                                                                                                                                  А у меня как-то так получилось…

                                                                                                                                  Intel(R) Core(TM) i3-3120M CPU @ 2.50GHz
                                                                                                                                  Ubuntu 16.10 x64
                                                                                                                                  GCC 5.3.1
                                                                                                                                  Linux xx 4.4.0-18-generic #34-Ubuntu SMP Wed Apr 6 14:01:02 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux


                                                                                                                                  Линейно:
                                                                                                                                  g++ -std=gnu++11 -O0
                                                                                                                                  sign: 6.23 vs 5.54
                                                                                                                                  abs: 4.52 vs 8.28
                                                                                                                                  mini: 7.12 vs 19.71
                                                                                                                                  maxi: 7.28 vs 19.04
                                                                                                                                  minu: 7.12 vs 18.99
                                                                                                                                  maxu: 7.12 vs 18.93
                                                                                                                                  2147483646

                                                                                                                                  g++ -std=gnu++11 -O1
                                                                                                                                  sign: 3.55 vs 3.47
                                                                                                                                  abs: 1.74 vs 2.69
                                                                                                                                  mini: 3.02 vs 6.20
                                                                                                                                  maxi: 3.02 vs 6.34
                                                                                                                                  minu: 3.04 vs 6.94
                                                                                                                                  maxu: 3.77 vs 5.98
                                                                                                                                  4294967294

                                                                                                                                  g++ -std=gnu++11 -O2
                                                                                                                                  sign: 5.47 vs 5.35
                                                                                                                                  abs: 3.52 vs 3.60
                                                                                                                                  mini: 4.52 vs 8.93
                                                                                                                                  maxi: 4.54 vs 8.19
                                                                                                                                  minu: 4.51 vs 8.02
                                                                                                                                  maxu: 5.25 vs 8.22
                                                                                                                                  4294967294

                                                                                                                                  g++ -std=gnu++11 -O3
                                                                                                                                  sign: 7.39 vs 5.23
                                                                                                                                  abs: 3.47 vs 3.52
                                                                                                                                  mini: 4.58 vs 9.00
                                                                                                                                  maxi: 4.53 vs 8.17
                                                                                                                                  minu: 4.52 vs 7.95
                                                                                                                                  maxu: 5.30 vs 8.01
                                                                                                                                  4294967294

                                                                                                                                  g++ -std=gnu++11 -Os
                                                                                                                                  sign: 5.75 vs 5.24
                                                                                                                                  abs: 3.50 vs 3.59
                                                                                                                                  mini: 4.02 vs 5.30
                                                                                                                                  maxi: 4.09 vs 5.32
                                                                                                                                  minu: 4.58 vs 3.57
                                                                                                                                  maxu: 4.05 vs 5.31
                                                                                                                                  4294967294


                                                                                                                                  Хаотично:
                                                                                                                                  g++ -std=gnu++11 -O0
                                                                                                                                  sign: 33.41 vs 3.77
                                                                                                                                  abs: 32.11 vs 5.66
                                                                                                                                  mini: 35.58 vs 16.71
                                                                                                                                  maxi: 36.27 vs 16.96
                                                                                                                                  minu: 37.68 vs 18.20
                                                                                                                                  maxu: 37.08 vs 18.38
                                                                                                                                  2147483646

                                                                                                                                  g++ -std=gnu++11 -O1
                                                                                                                                  sign: 2.06 vs 2.03
                                                                                                                                  abs: 0.67 vs 0.31
                                                                                                                                  mini: 1.79 vs 1.99
                                                                                                                                  maxi: 1.80 vs 2.68
                                                                                                                                  minu: 1.82 vs 2.23
                                                                                                                                  maxu: 1.81 vs 2.21
                                                                                                                                  2147483646

                                                                                                                                  g++ -std=gnu++11 -O2
                                                                                                                                  sign: 15.51 vs 2.05
                                                                                                                                  abs: 14.38 vs 0.37
                                                                                                                                  mini: 1.86 vs 1.72
                                                                                                                                  maxi: 1.85 vs 2.15
                                                                                                                                  minu: 15.45 vs 2.68
                                                                                                                                  maxu: 1.92 vs 2.21
                                                                                                                                  2147483646

                                                                                                                                  g++ -std=gnu++11 -O3
                                                                                                                                  sign: 15.17 vs 2.02
                                                                                                                                  abs: 14.41 vs 0.36
                                                                                                                                  mini: 1.86 vs 1.73
                                                                                                                                  maxi: 1.86 vs 2.16
                                                                                                                                  minu: 15.57 vs 2.68
                                                                                                                                  maxu: 1.95 vs 2.22
                                                                                                                                  2147483646

                                                                                                                                  g++ -std=gnu++11 -Os
                                                                                                                                  sign: 15.55 vs 1.81
                                                                                                                                  abs: 0.40 vs 0.35
                                                                                                                                  mini: 1.41 vs 1.49
                                                                                                                                  maxi: 1.37 vs 2.14
                                                                                                                                  minu: 1.71 vs 2.50
                                                                                                                                  maxu: 1.47 vs 2.14
                                                                                                                                  2147483646

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

                                                                                                                                  Самое читаемое