Пузырьки, кэши и предсказатели переходов

    Эта заметка написана по мотивам одного любопытного поста, краткий коммент её же автора к которому сподвиг меня разобраться в происходящем поподробнее. Предлагается сравнить две вариации алгоритма сортировки пузырьком. Первая из них – обычный пузырёк, с небольшой оптимизацией — внутренний цикл можно закончить немного раньше, зная, что оставшаяся часть массива уже отсортирована:
    for (i=0; i<N; i++)
      for (j=0; j<N - (i+1); j++)
        if (a[j] > a[j+1])
          swap(a[j], a[j+1]);


    Во втором варианте внутренний цикл проходит по другой части массива, однако алгоритмически этот вариант эквивалентен первому (подробности ниже):
    for (i=0; i<N-1; i++)
        for (j=i; j>=0; j--)
            if (a[j] > a[j+1])
                swap(a[j], a[j+1]);


    Запускаем (код), например, для N=100 000 на массиве int'ов, и получаем около 30 секунд в первом случае, и меньше 10 секунд — во втором, то есть отличие в 3 раза! Откуда же тогда берётся такая разница?

    Для начала проверяем, что дело не в оптимизациях компилятора. В этом легко убедиться, сгенерировав и сравнив ассемблерные коды в обоих случаях. Либо можно отключить оптимизацию. Или же можно переписать код на ассемблере (например, используя ассемблерные вставки). В любом случае эффект сохраняется.

    Далее, как проверить, что оба варианта эквиваленты? Например, можно вывести в строку сравниваемые значения a[j], a[j+1] и соответствующее значение j, отсортировать получившийся список, а затем сравнить их построчно (конечно же, разумно это делать для небольших N). Оказывается, что списки совпадают, а значит в обоих случаях выполняются одни и те же сравнения и одни и те же присваивания, и разница заключается только в порядке выполнения этих операций.

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

    Но заметим, что в нашем случае объём данных не такой и большой – 100’000 int’ов это всего лишь 400Кб, в то время как современные процессоры обладают кэшами L2 от мегабайта и больше. Кроме того, в обоих случаях мы последовательно обращаемся к элементам массива, поэтому задержки обращения к памяти опять же амортизируются. Наконец, если уменьшать N, то всё равно наблюдается то же самое отличие в 3 раза. Поэтому, здесь кэши хоть и играют свою роль, но не являются основной причиной наблюдаемого эффекта.

    Чтобы разобраться в происходящем и проверить предыдущее утверждение, проанализируем оба варианта при помощи процессорных счётчиков. Эти счётчики подсчитывают число выполненных инструкций, обращений к кэшам, количество произошедших ветвлений, и многие другие параметры. Для снятия показаний я использовал интеловскую (пробную версию — да-да, не ждите халявы, тут вам не гугл!) VTune Performance Analyzer, но существуют и другие способы. Запускаем, выполняется анализ, и получаем на выходе (P4 Prescott, L1 16Кб, L2 2Мб, первый вариант vs. второй):

    Выполненных инструкций: 40 vs. 35 (·109)
    Промахов кэша L2: 1.1 vs. 1.8 (·109)
    Промахов кэша L1: 1.6 vs. 0.4 (·106)

    Итак, что отсюда следует? Во-первых, промахов кэша первого уровня в расчёте на инструкцию приходится очень мало, а поэтому и соответствующие задержки не так значительны. Во-вторых, промахов кэша второго уровня всё же достаточно много, но оказывается, что во втором варианте промахи случаются даже чаще, чем в первом! Результаты на других процессорах могут быть немного другие (в частности, может быть ещё кэш L3, которого нет на моём процессоре), но думаю, что общая картина останется примерно такой же.

    Итак, дело не в кэшах. Но посмотрим на дополнительные результаты анализа:

    Количество переходов (ветвлений, branches): 1.0 vs. 1.0 (·1010)
    Ошибок предсказателя переходов (mispredicted branches): 0.16 vs. 0.00009 (·1010)

    Небольшое отступление для тех, кто, как и я был до недавнего времени, не знаком с такой интересной вещью, как предсказатель переходов (branch predictor) — как ни странно, я не нашёл топиков о нём на хабре.

    Вы наверняка знаете, что современные процессоры за счёт конвейера инструкций (instruction pipeline) выполняют не одну инструкцию за другой последовательно, а сразу несколько инструкций параллельно, и затем объединяют результаты. Однако последовательность инструкций может зависеть от результатов условных переходов, как в нашем примере — в случае, если a[j]>a[j+1], то выполняется перестановка элементов, а в противном случае — нет. Тут на помощь приходит предсказатель переходов, который пытается догадаться, будет ли выполнент переход или нет, и в соответствии с этим выбираются инструкции для конвейера.

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

    Насколько же важен предсказатель переходов и его ошибки? Википедия сообщает, что на современных процессорах задержка составляет десятки тактов, что не так уж и много само по себе много (leotsarev). Однако, кроме того, отсутствие таких ошибок может означать очень хорошую выгоду, поскольку за счёт большой длины конвейера процессор может «заглянуть» на много инструкций вперёд. В этом можно убедиться при помощи следующего кода:

    for (i=0; i<T; i++)
      for (j=0; j<M; j++)
        if (p[j]) с++;


    Здесь p[] – массив, определяющий, нужно ли выполнять условный переход, или нет, а счётчик служит просто для различения этих двух событий. В случае, если все значения p[j] одинаковы, то через несколько итераций переход уже хорошо предсказуем. Если же p[j] сгенерировано некоторым, например, периодическим образом, то предсказуемость перехода будет зависеть от реализации предсказателя. Но при случайном заполнении массива предсказать следующий переход, при определённых ограничениях, нельзя. Нужно отметить, что размер массива M важен – если массив будет слишком большим, то он может плохо кэшироваться, а если слишком маленьким – то переход можно будет предсказать.

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

    Согласно приведённым выше результатам анализа, в первом варианте сортировки ошибки предсказателя происходят в 16% случаях, а во втором – в 1000 раз реже. Почему так получается? Это можно понять, рассмотрев, как происходит сортировка в обоих случаях.

    В первом случае, при небольших i внутренний цикл по j пробегает почти до конца массива, не трогая лишь отсортированный «хвост». Изначально данные в этой части массива неупорядочены, и поэтому условие a[j]>a[j+1] выполняется практически случайно. При увеличении i происходит некоторое упорядочивание элементов за счёт перестановок, но всё равно остаётся большая доля случайности (анимация). Поэтому предсказать переход достаточно сложно, что и приводит к большому числу ошибок предсказателя.

    Во втором случае, при i=0 внутренний цикл лишь сортирует a[0] и a[1], при i=1 он добавляет a[2], и так далее. Фактически, это сортировка вставками (но не бинарными) — на i-ом шаге происходит вставка элемента a[i+1] в уже отсортированный подмассив a[0..i] (анимация). Поскольку элемент вставляется с конца подмассива, то в большинстве случаев будет выполняться последовательное перемещение этого элемента до необходимой позиции в массиве, и значение условия p[j]>p[j+1] будет одинаковым до того, как он её достигнет. Таким образом, после нескольких итераций переход легко предсказать, чему предсказатель переходов, похоже, несказанно рад.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 65
    • НЛО прилетело и опубликовало эту надпись здесь
      • +5
        Так а ведь Intel C++ Compiler с версии 9.0 уже сам умеет менять вложенность циклов где надо. И еще кучу всего. :) Будущее уже совсем рядом.
        • 0
          Покажите мне хоть одну серьезную либу, где используется сортировка пузырьком %)
          • НЛО прилетело и опубликовало эту надпись здесь
            • 0
              Каждому алгоритму своё место. Чтобы отсортировать 10 элементов, использовать какую-нибудь хитрую многопоточную сортировку сродни стрельбе из пушек по комарам.
              Тут как раз удобен пузырёк — простой, маленький, не есть стек.
          • 0
            Думая, что Дядя Дима ака ddima внезапно удивится наплыву посетителей на геймдефф и свой блог :)
          • +1
            «Ага, скажет подкованный читатель» — привет от русских книг из серии «…для чайников»
            • +1
              Привет!
              ага, щас как-нибудь переформулирую.
              • 0

                -хрусть! — сказала японская лесопилка
                -АГА! — обрадовались суровые русские мужики
                (Ц)анекдот
              • 0
                А, по-моему, отличная вводная статья. Спасибо.
                • 0
                  Нет-нет! Статья отличная, стиль забавный :)
              • +6
                кстати, из этой же оперы: допустим, нужно делать разные операции над двумя независимыми списками (пусть одинаковой длины).

                Казалось бы — время работы будет одинаково в обоих случаях:
                — сделать работу за два разных цикла (правильный программистский подход)
                — объединить две операции в один цикл («говнокод»)

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

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

                А «классичекий» подход (если компилятор не перехитрит программиста), будет работать последовательно.
                • +3
                  Но «классичекий» подход легко распараллелить :)
                • 0
                  По моему, во втором варианте «предсказателю будущего» будет проще принять решение еще и потому что условие выхода из вложенного цикла — сравнение с константой (да и один свободный регист в процессе оптимизации много что дает, хотя не в таком простом случае).
                  • 0
                    Ну, там как раз компилятор малость оптимизирует. Да и это условие достаточно редко происходит.
                    • 0
                      Врятли так уж редко. Сначала цикл на две итерации. Потом 3. И т.д. А на каждую итерацию нужно сравнение…
                      • 0
                        Ой, что-то я не о том подумал. Проверка условия действительно каждую итерацию выполняется, но компилятор может это легко оптимизировать, и привести к виду, аналогичному второму варианту.
                  • +3
                    десятки тактов, что не так уж и много
                    Ни хера себе «не так уж много»! С учетом того, что за один такт процессор может исполнить более трех инструкций, если все удачно :)
                    • 0
                      Вообще мне кажется, что правильный вариант компилирования кода «if something then swap» не должен вообще иметь ветвления — есть специальные инструкции compare-and-swap как раз для таких случаев, специально, чтобы избежать перехода и накладных расходов на его предсказание.
                      В таком случае ошибки branch prediction будут очень редкими — ровно один раз за каждый выход из вложенного цикла (условный jump назад предсказывается происходящим).
                      • 0
                        Угу. На арме вот есть замечательная комманда swp{cond} ({cond} определяет условие при котором команда будет выполнятся). Сия статья заставила меня задуматся над возможным применением этой комманды :)
                        • +4
                          Что swp, что cmpxchg, предназначены для синхронизации (например для реализации мьютексов).
                          Команды обеспечивают атомарный доступ к памяти и поэтому являются очень медленными
                          • +1
                            И кстати SWP это уже устаревшая команда.
                            Вместо неё используется резервация кешстроки как в других RISC-ах
                            LDREX / STREX
                            • 0
                              Да, я чего-то затупил. CMOV вероятно.
                        • +1
                          Ну и последнее. Оптимизация должна идти сверху вниз. Т.е. сначала выбирается оптимальный алгоритм, потом с ним уже занимаемся низкоуровненвым дрочерством. Реквстирую в пост сравнение, как работает на том же механизме qsort или вставка.

                          еще можно (раз уж мы тут про дрочерство) сделать loop unrolling — замена цикла на многократное повторение тела. Опять задача та же — избавление от переходов. Если N не статично, то можно сделать так:

                          for (int i = 0; i < N / 2; i+=2)
                          {
                          do_something(i);
                          do_something(i+1);
                          }

                          if (N mod 2 <> 0)
                          {
                          do_something (N);
                          }
                          • +1
                            Попробовал для интереса переписать сортировку в один цикл, получилось вот что pastebin.com/m6c6397ca

                            Но в итоге, за счёт сложных вычислений, работает примерно в три раза медленнее обычной версии.
                            • +1
                              А, я кстати на грабли тут как раз наступил.
                              Деление по модулю — оно опасное. Если компилятор поставит idiv — то будет привет, у него latency десятки тактов. Поэтому, например
                              i=(i+1)%N;
                              может замедлить какой-нибудь простой цикл в 20 раз по сравнению с:
                              i++;
                              if (i > N)
                                i = 0;
                              • 0
                                Делите на степень двойки. :)
                                Если ваш компилятор напишет idiv при попытке поделить на константу-степень-двойки — выкиньте его.
                                • 0
                                  В принципе, не обязательно степень двойки — умный компилятор будет оптимизировать деление и на другие константы, например, вот так выглядит деление на 123456 (MSVC):
                                  mov ecx, DWORD PTR _x$[esp+8]
                                  mov eax, 142497619 ; 087e5753H
                                  imul ecx
                                  sar edx, 12 ; 0000000cH
                                  mov ecx, edx
                                  shr ecx, 31 ; 0000001fH
                                  add ecx, edx

                                  Но я говорил скорее о случае с не-константами.
                          • +3
                            Насколько я знаю, Prescott имеет длинный конвеер и ошибки предсказателя переходов для него критичны. На других процессорах, возможно, разница будет меньше. Поправьте пожалуйста, если я не прав
                          • +4
                            У вас алгоритмы не эквивалентны

                            В первом варианте:
                            проверка условия в первом цикле — N операций
                            проверка условия во втором цикле — (N^2-1)/2*3 операций

                            Во втором варианте
                            проверка условия в первом цикле — N-1 операций
                            проверка условия во втором цикле — (N^2-1)/2*1 операций

                            При большом N учитываем только старшую степень, общая сложность:
                            N^2(c+0.5) операций для второго и N^2(c+1.5) операций для первого
                            • +1
                              Что-то я не понял, откуда в первом варианте *3? Если речь о N — (i+1), то компилятор его посчитает только один раз на весь внутренний цикл.
                              • 0
                                i — переменная, выражения с переменными пересчитываются на каждом проходе, так как ее значение могло измениться в цикле
                                • 0
                                  А почему Вы так в этом уверены? Посмотрите ассемблерный код, сгенерированный компилятором при включённой оптимизации — он не только в курсе, что i в цикле не изменилось, он там такие штуки вытворяет ;)
                                  • –2
                                    Вам никогда не советовали писать код с выключенным оптимизатором компилятора?

                                    Странные вещи случаются когда пишешь кроссплатформенный код и один компилятор оптимизирует так, а другой иначе, в результате затормоз и быстро уже не поправить, так как глубоко зашит.
                                    • +4
                                      Искренне надеюсь, что мне этот совет никогда не пригодится ;)
                                      Не хотелось бы делать работу компилятора самому.
                              • +1
                                Сразу не понять вас, можно попробоватьтег возведения в степень
                              • 0
                                Мне вот тут интересно самому стало и я написал маленькую программочку, где массив заполняется случайными числами от 0 до 10и. И потом программка пробегается по массиву с условием if эл-т > некоторого порога (от 0 до 10). И мне было интересно, как производительность меняется как функция порога.
                                Вот кусочек программки:

                                for(i=0; i < 100000;i++){
                                xx[i]=1.*(10.*rand()/RAND_MAX);
                                }

                                for (i=0;i<1000;i++){
                                for(j=0;j<100000;j++){
                                if (xx[j]>val){
                                sum+=1;
                                }
                                else{
                                sum+=2;
                                }
                                }
                                }

                                И вот как производительность меняется, как функция порога(переменная val) (картинку не смог вставить):
                                val Time(sec):
                                0 6.5
                                1 8.6
                                2 10.6
                                3 12.1
                                4 12.5
                                5 12.0
                                6 10.7
                                7 8.7
                                8 6.6
                                9 4.6
                                Видно что максимальная производительность при val=0 или 10, когда все if-ы срабатывают одинаково. Также интересно, что разница в производительности (по сравнению с worst case) составила ровно 2 раза. Сам не ожидал.
                                • +1
                                  А у меня в 4-6 раз получилось, я вроде писал в статье.
                                • +2
                                  опечатка в тегах: «пердсказатель»
                                  вот :)
                                  • 0
                                    Тьфу, и правда. Спасибо!
                                  • 0
                                    ИМХО уменьшение кол-ва промахов L1 — это очень и очень серьёзно :-)
                                    Он быстрее L2 раз в 10 :-)
                                    • 0
                                      По данным отсюда:
                                      L1 — 4/12 Cycle Latency
                                      L2 — 20/20 Cycle Latency
                                      То есть всё же не в 10 раз :) А вот промах последнего кэша будет стоить раз в 10 дороже.
                                      Но в нашем случае промахов L1 банально слишком мало, чтобы это можно было заметить — меньше одного на 10 тысяч инструкций.
                                    • –4
                                      кэш, это конечно круто.
                                      но кнут нас учит тому что скорость сортровки равна n*log(n).

                                      зачем рассматривать пузырек, который имеет эффективность n^2 ???
                                      и его оптимизации, которые имеют эфффективность… n^2, но в три раза круче!
                                      • +4
                                        Видимо, потому что статья не о сортировках, а об обращении к памяти в алгоритмах вообще. В паре случаев подобные соображения помогли мне оптимизировать более чем в три раза линейные (!) алгоритмы в узких по производительности местах.

                                        К слову сказать, «логарифмические» сортировки часто обращаются к памяти в случайном порядке, что провоцирует малопредсказуемые переходы — и в самом печальном случае (хотя это, конечно, маловероятно) пузырек на плохой железке может перегнать qsort (слишком случаен, велико худшее время), heapsort (вот этот более предсказуем) и аналоги.
                                        • +2
                                          Кто-то должен был это спросить :) Пузырёк здесь просто как пример. Вы же не подумали, что мы тут пузырёк оптимизируем, правда?
                                          • –2
                                            пардон-пардон.
                                            а что делаем? ищем алгоритм, который на конкретном процессоре, конкретного производителя, при конкретных даныых дает выигрыш? зачем???
                                            • +3
                                              Ну, лично я ничего не ищу.
                                              Собственно, я напискал рассказ о причинах, почему один пример быстрее другого, при том что алгоритмически они не отличаются. И причины эти не в «конкретных процессорах» и не в данных, а в общих подходах, использующихся во всех современных процессорах, которые интересно и полезно знать.
                                              Это здорово, что Вы знаете про асимптотическую сложность различных сортировок, но есть и другие важные вещи.
                                              А что Вы пытаетесь сейчас доказать, так я вообще не понимаю. Может быть, Вы дочитали текст только до хабраката?
                                              • 0
                                                я имел ввиду, что наблюдение конечно интересное, однако трудноприменимое в реальной жизни.
                                                причины связаны и с конекретным процессором (на процессорах другой архитектуры разница будет меньше), и с данными (т.к. очень большую часть времени алгоритм просто идет по уже отсортированной части массива).
                                                я согласен, что анализ работы блоков процессора часто позволяет достичь существенного ускорения (для этого производитлями собственно выпускаются всяческие optimization guide и профайлеры, показывающие состояния кэшей, конвееров и т.п.), но, может быть, меня смутил выбор примера на котором это демонстрируется. т.е. взяли алгоритм, часть которого состоит из «пустого цикла», и взялись оптимизировать этот самый пустой цикл.
                                                • +1
                                                  Да не пытались мы ничего оптимизировать, мы просто разбирались, почему одно быстрее другого. Почему автор исходного поста сделал такую «оптимизацию» я точно не знаю — похоже, что он пытался на простом примере показать улучшение за счёт кэша, но чуть промазал :)
                                                  Я не знаю, о каких других архитектурах вы говорите, но по-моему Pentium 4, Core2Duo и аналогичные процы от АМД — такой нехилый класс процессоров (сколько процентов от всех десктопов?), и везде будет наблюдаться похожая разница за счёт длинного конвейера и предсказателя переходов. Я ведь не пытаюсь обобщить это на вообще все процессоры.
                                                  Насчёт реальной жизни — я, например, до того, как разобрался с этим, считал, что ветвление сильно бьёт по производительности. Где-то я это раньше читал. А в реальности как раз если переход хорошо предсказуем, то влияние на производительность будет минимальным. И мне это знание может помочь при написании реального кода.
                                                  • 0
                                                    хм. первую-то фразу статьи я и не заметил. :)
                                                    тогда все понятно.
                                        • +1
                                          Небольшая модификация, дающая еще процентов 30% ускорения (второй вариант, для включенной оптимизации).
                                          • 0
                                            Да, размотка цикла — молодец. Но об do вложенный в switch мозги поломать можно :)
                                            • +2
                                              -funroll-loops
                                              • +1
                                                Результаты с -funroll-loops:

                                                test1: 20.295
                                                test2: 6.9141
                                                duff_test: 5.82957
                                                ratio(1/2): 2.94
                                                ratio(1/d): 3.48
                                                ratio(2/d): 1.19
                                                

                                            • 0
                                              Ребята, вы упустили важную деталь. Производительность кешей, оптимизации процессора, аппаратные уловки — это все хорошо. Однако, сравнительный анализ тем полезнее, чем более эквивалентны сравниваемые сущности. А данном случае, это — далеко не так!

                                              Несмотря на внешние сходства и общую ассимптотику O(N2), «вставки» и «пузырек» — суть разные подходы. Для ознакомления могу отправить к матчасти (например, Р. Седжвик, «Фундаментальные алгоритмы на С++ [1-4]», часть 3: «Сортировка», стр. 264 :)). А вкратце — «пузырек» ведет себя, скорее, как сортировка «выбором», нежели «вставками». Но с меньшей эффективностью. Впрочем, производительность даже продуманных модификаций «пузырька» (например, Шейкер-сортировки) оставляет желать лучшего. Но в случае «вставок» — все наоборот. Это — очень мощный алгоритм, к которому часто прибегают (привет усомнившимся в применимости квадратичых методов!) для упорядочивания малых или почти отсортированных (с малым количеством инверсий) массивов. Естественно, при этом обычно добляют пару символов и улучшают его быстродействие еще в 1.5 раза.

                                              Напоследок, приведу несколько лемм без доказательства:
                                              1. «Вставки» производит около N2/4 сравнений и обменов в среднем случае, и около N2/2 — в худшем (это — редко).
                                              2. «Пузырек» — около N2/2 операций сравнения и обмена как в среднем, так и в худшем случаях.

                                              Вывод: прежде аппаратных оптимизаций, имеет смысл подумать о программных (алгоритмических). В случае анализа кода — все аналогично. Не смотря на это, автор — молодец :-) Интересный материал.
                                              • 0
                                                Сразу хочу сказать, что я «в теме» насчёт сложностей алгоритмов и методов сортировок, чтобы избежать излишних объяснений.

                                                Здесь забавно то, что изначально вообще речи не шло о сравнении двух разных методов сортировки, посмотрите исходный пост на который я ссылаюсь в начале — там говорится об «усовершенствованном пузырьке». А на самом деле, о том, что это метод вставок я догадался уже при написании статьи, когда думал про визуализацию исходных алгоритмов. Когда у тебя на глазах «оптимизируют» пузырёк, не сразу и догадаешься, что он вообще-то превратился в другой метод :)

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

                                                Т.е. вывод здесь как раз обратный — теоретическая сложность алгоритма не однозначно задаёт реальное время выполнения, довольно сильная разница может оказаться за счёт технических деталей платформы, и поэтому ими не следует пренебрегать. Но никто, конечно, не спорит, что эта разница, скорее всего, даёт лишь «не очень большую» константу, а в то время как алгоритмическая сложность разных методов может отличаться на порядки.
                                              • 0
                                                К сожалению, ночью я просмотрел, что ваш алгоритм «вставками» не выполняет break, находя позицию очередного элемента в отсортированном подмассиве. И делает это, соответственно, операциями полного, а не половинного обмена. В этом виде к нему применима та же оценка, что и для «пузырька». Единственная разница — полная упорядоченность данных, на которых работает 1й алгоритм, и почти полное ее отсутствие — во втором случае. Видимо, вы правы касательно оптимизаций. К слову, на моем процессоре (AMD Turion X2 1.6 mobile) первоначальный выигрыш ваших «вставок» по времени не превышал 30%, а после отключения оптимизаций компиллятора (/Od) — сократился до 15% (msvc).
                                                • 0
                                                  Всё верно, только алгоритм не «мой» :)
                                                  Неудивительно, что на разных процессорах выигрыш может быть разным (особенно Intel vs AMD) — кэши и предсказатели переходов всюду свои.
                                                  • 0
                                                    Т.к. классический алгоритм, для которого справедливы указанные оценки, выглядит чуть иначе — приходится говорить о «ваших вставках» как о реализации, приведенной вами :-)
                                                • 0
                                                  Прочитал эту статью после шума с Meltdown https://habrahabr.ru/post/346026/
                                                  Какие интересные порой связи находятся.

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