Algorithms
29 October 2009

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

Эта заметка написана по мотивам одного любопытного поста, краткий коммент её же автора к которому сподвиг меня разобраться в происходящем поподробнее. Предлагается сравнить две вариации алгоритма сортировки пузырьком. Первая из них – обычный пузырёк, с небольшой оптимизацией — внутренний цикл можно закончить немного раньше, зная, что оставшаяся часть массива уже отсортирована:
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] будет одинаковым до того, как он её достигнет. Таким образом, после нескольких итераций переход легко предсказать, чему предсказатель переходов, похоже, несказанно рад.

+143
7.8k 126
Comments 65
Top of the day