Bubblesort, кеши и быстродействие

Несколько интересных соображений, навеянных публикациями по dual-pivot quicksort.

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

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

Что такое пузырьковая сортировка, надеюсь, помнят все :). Проходим по массиву, сравниваем соседние элементы, меняем их местами. За 1 проход наверх “всплывает” самый легкий элемент. Потом повторяем процедуру, пока массив не будет отсортирован целиком. В качестве локальной оптимизации можно: а) после первого прохода гнать волну не до самого верха, а заканчивать чуть пониже; б) прекращать сортировку, если массив уже хороший.

Код минимальный и простейший, с учетом оптимизации (а):


#include <windows.h>
#include <iostream>

#pragma comment(lib, "winmm.lib")
static int COUNTER = 100000;

void main(void)
{
    int i, j;
    int* p = (int*)malloc(sizeof(int)*COUNTER);

    for (i=0; i<COUNTER; i++)
        p[i] = rand();

    DWORD timeStart = timeGetTime();

    for (i=0; i<COUNTER; i++)
        for (j=0; j<COUNTER - (i+1); j++)
            if (p[j] > p[j+1])
            {
                int temp = p[j];
                p[j] = p[j+1];
                p[j+1]=temp;
            }

    std::cout << "Time exe: " << timeGetTime() - timeStart << ";\n";
    free(p);
}

На моем домашнем компьютере (MSVC 2008 Release, Core 2 Duo 6700 @ 2.66 GHz) получаются следующие результаты:
16965, 16945, 16971, 16959, 16957.

Если посмостреть на волны замен, то последовательно рассматриваются следующие пары элементов (на примере из 6 элементов):
0 1; 1 2; 2 3; 3 4; 4 5; 0 1; 1 2; 2 3; 3 4; 0 1; 1 2; 2 3; 0 1; 1 2; 0 1

Что можно сделать с этим пузырьком? Вообще говоря, когда первая волна дошла до точки 2<->3, в нижней части массива можно уже запускать новую волну. Когда она тоже пройдет линию 2<->3, то можно пустить следующую. Тем самым мы добиваемся того, что операции сравнения и перестановки элементов довольно длительное время локализуются в сравнительно небольшой зоне массива:
0 1; 1 2; 0 1; 2 3; 1 2; 0 1; 3 4; 2 3; 1 2; 0 1; 4 5; 3 4; 2 3; 1 2; 0 1;

Вот пример кода, который выполняет сортировку во втором случае:


#include <windows.h>
#include <iostream>

#pragma comment(lib, "winmm.lib")
static int COUNTER = 100000;

void main(void)
{
    int i, j;
    int* p = (int*)malloc(sizeof(int)*COUNTER);

    for (i=0; i<COUNTER; i++)
        p[i] = rand();

    DWORD timeStart = timeGetTime();

    for (i=0; i<COUNTER-1; i++)
        for (j=i; j>=0; j--)
            if (p[j] > p[j+1])
            {
                int temp = p[j];
                p[j] = p[j+1];
                p[j+1]=temp;
            }
    std::cout << "Time exe: " << timeGetTime() - timeStart << ";\n";
    free(p);
}

Результаты: 5415, 5391, 5434, 5421, 5410. Или примерно в 3 раза быстрее, чем “классический” вариант пузырька. Кто не верит, можете добавить количество сравнений и количество перестановок. В обоих случаях (на дефолтном srand()) выполнено 4999950000 сравнений и сделано 2506044511 перестановок соседних элементов. Впрочем, два int64 счетчика заметно влияют на картину: первая программа заняла 22650 ms, вторая – порядка 14000 ms.

Кому совсем интересно, можно поиграться параметрами memory page size / cache page size, выполняя максимум вычислений в пределах одной страницы (чтобы минимизировать перехлест “волн”). Думаю, что можно еще подсократить время выполнения. Но это уже потребует хорошего расположения входных данных в физической памяти, что не всегда может быть осуществимо.

Да, ассемблерный код практически одинаковый. Внимательно анализируя первый вариант, кстати, я обнаружил, что компилятор еще оптимизировал цикл по i, сделав его for (i=COUNTER-1; i>=0; i–) чтобы не вычитать условие окончания цикла по j. Разница между кодом в следующем: (eax == j, edi == i):

Вариант 1:

mov edi,1869Fh (1 раз в начале цикла)
xor eax,eax (на каждом фрейме)
...
inc eax
cmp eax,edi
jl main+56h (0E21056h)
dec edi
cmp edi,0FFFFFFFFh
jg main+50h (0E21050h)

Вариант 2:

mov eax,edi (на каждом фрейме)
...
sub eax,1
jns main+50h (871050h)
inc edi
cmp edi,1869Fh
jl main+4Ah (87104Ah)

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

1. Иерархически проходилась по произвольному скелету (не обязательно бипеду).
2. Для каждой ноды:
2.1. Извлекала из кусочно-линейного анимационного сплайна текущее значение (рассчет нужного сегмента сплайна по timeCur и параметрам сегментов, линейная интерполяция floating point).
2.2. На основании полученных данных (9 floating point) рассчитывала матрицу Translate-Rotate-Scale и записывала ее в специальный массив.
2.3. В структуре объекта выставляла при помощи операции |= бит “Анимация подсчитана”.

Когда пункт 2.3 был ликвидирован (сравните его по времени вычисления с 2.1 и 2.2), прирост производительности подсистемы составил около 7 процентов. В свете трехкратного ускорения bubblesort за счет разворота цикла по j – не такая уж удивительная цифра.

  • dDIMA

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