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 – не такая уж удивительная цифра.
