Отвечая на другой вопрос переполнения стека ( этот ), я наткнулся на интересную подзадачу. Какой самый быстрый способ сортировки массива из 6 целых чисел?
Поскольку вопрос очень низкого уровня:
- мы не можем предполагать, что библиотеки доступны (и сам вызов имеет свою стоимость), только обычный C
- чтобы избежать опустошения конвейера команд (который имеет очень высокую высокую стоимость), нам, вероятно, следует минимизировать ветвления, скачки и любые другие виды прерывания потока управления (например, скрытые за точками последовательности в
&& ||).
- пространство ограничено, и минимизация регистров и использование памяти является проблемой, в идеале сортировка на месте, вероятно, лучше всего.
На самом деле этот вопрос - своего рода гольф, цель которого не в том, чтобы минимизировать длину источника, а во время выполнения. Я называю его «кодом Зенинга», который используется в названии книги Оптимизация Дзен кода от Майкл Абраш и продолжения .
Что интересно, есть несколько слоев:
- пример прост и легок для понимания и измерения, не требующий много навыков C
- показывает эффекты выбора хорошего алгоритма для этой проблемы, а также эффекты компилятора и базового оборудования.
Вот моя эталонная (наивная, не оптимизированная) реализация и мой набор тестов.
#include <stdio.h>
static __inline__ int sort6(int * d){
char j, i, imin;
int tmp;
for (j = 0 ; j < 5 ; j++){
imin = j;
for (i = j + 1; i < 6 ; i++){
if (d[i] < d[imin]){
imin = i;
}
}
tmp = d[j];
d[j] = d[imin];
d[imin] = tmp;
}
}
static __inline__ unsigned long long rdtsc(void)
{
unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
return x;
}
int main(int argc, char ** argv){
int i;
int d[6][5] = {
{1, 2, 3, 4, 5, 6},
{6, 5, 4, 3, 2, 1},
{100, 2, 300, 4, 500, 6},
{100, 2, 3, 4, 500, 6},
{1, 200, 3, 4, 5, 600},
{1, 1, 2, 1, 2, 1}
};
unsigned long long cycles = rdtsc();
for (i = 0; i < 6 ; i++){
sort6(d[i]);
/*
* printf("d%d : %d %d %d %d %d %d\n", i,
* d[i][0], d[i][6], d[i][7],
* d[i][8], d[i][9], d[i][10]);
*/
}
cycles = rdtsc() - cycles;
printf("Time is %d\n", (unsigned)cycles);
}
Необработанные результаты
Поскольку число вариантов становится большим, я собрал их все в наборе тестов, который можно найти здесь . Благодаря Кевину Сток, используемые тесты немного менее наивны, чем показанные выше. Вы можете скомпилировать и выполнить его в своей среде. Мне весьма интересно поведение на разных целевых архитектурах / компиляторах. (Хорошо, ребята, вставьте это в ответы, я буду +1 каждому вкладчику нового набора результатов).
Я дал ответ Даниэлю Штутцбаху (для игры в гольф) год назад, когда он был источником самого быстрого решения в то время (сортировка сетей).
Linux 64 бит, gcc 4.6.1 64 бит, Intel Core 2 Duo E8400, -O2
- Прямой вызов функции библиотеки qsort: 689,38
- Наивная реализация (вставка сортировки): 285,70
- Сортировка вставок (Даниэль Штутцбах): 142.12
- Сортировка вставок развернута: 125,47
- Порядок ранга: 102.26
- Порядок ранга с регистрами: 58.03
- Сортировка сетей (Даниэль Штутцбах): 111,68
- Сортировка сетей (Paul R): 66,36
- Сортировка сетей 12 с быстрой заменой: 58,86
- Сортировка сетей 12 переупорядочено Своп: 53,74
- Сортировка сетей 12 переупорядочено Простой обмен: 31,54
- Переупорядоченная сеть сортировки с быстрой заменой: 31,54
- Переупорядоченная сеть сортировки с быстрой заменой V2: 33,63
- Сортировка пузырьков (Паоло Бонзини): 48,85
- Развернутая сортировка вставок (Паоло Бонзини): 75,30
Linux 64 бит, gcc 4.6.1 64 бит, Intel Core 2 Duo E8400, -O1
- Прямой вызов функции библиотеки qsort: 705,93
- Наивная реализация (вставка сортировки): 135.60
- Сортировка вставок (Даниэль Штутцбах): 142,11
- Сортировка вставок развернута: 126,75
- Порядок ранга: 46.42
- Порядок ранга с регистрами: 43,58
- Сортировка сетей (Даниэль Штутцбах): 115,57
- Сортировка сетей (Paul R): 64,44
- Сортировка сетей 12 с быстрой заменой: 61,98
- Сортировка сетей 12 переупорядочено Своп: 54,67
- Сортировка сетей 12 переупорядочено Простой обмен: 31,54
- Переупорядоченная сеть сортировки с быстрой заменой: 31,24
- Переупорядоченная сеть сортировки с быстрой заменой V2: 33,07
- Сортировка пузырьков (Паоло Бонзини): 45,79
- Развернутая сортировка вставок (Паоло Бонзини): 80,15
Я включил результаты как -O1, так и -O2, потому что неожиданно для нескольких программ O2 * меньше эффективнее, чем O1. Интересно какая конкретно оптимизация имеет этот эффект?
Комментарии к предлагаемым решениям
Сортировка вставок (Даниэль Штутцбах)
Как и ожидалось, минимизация ветвей - действительно хорошая идея.
Сортировка сетей (Даниэль Штутцбах)
Лучше, чем сортировка вставок. Я задавался вопросом, не был ли главный эффект от избегания внешнего цикла. Я проверил развернутой сортировкой вставки, чтобы проверить, и мы действительно получаем примерно одинаковые цифры (код здесь ).
Сортировка сетей (Paul R)
Лучшее на данный момент. Фактический код, который я использовал для проверки: здесь . Пока не знаю, почему это почти в два раза быстрее, чем в другой сети сортировки. Передача параметров? Быстро макс?
Сортировка сетей 12 SWAP с быстрой заменой
По предложению Даниэля Штутцбаха, я объединил его сеть сортировки с 12 свопами и быстрый обмен без ответвлений (код здесь ). Это действительно быстрее, лучше всего с небольшим запасом (примерно 5%), как и следовало ожидать, используя 1 своп меньше.
Интересно также отметить, что своп без ветвей, по-видимому, намного (в 4 раза) менее эффективен, чем простой, используемый в архитектуре PPC.
Вызов библиотеки qsort
Чтобы дать еще одну контрольную точку, я также попытался, как предлагалось, просто вызвать библиотеку qsort (код здесь ). Как и ожидалось, он намного медленнее: в 10-30 раз медленнее ... как стало очевидно с новым набором тестов, основная проблема, похоже, заключается в начальной загрузке библиотеки после первого вызова, и она не так плохо сравнивается с версия. Это только в 3-20 раз медленнее в моем Linux. В некоторых архитектурах, используемых для тестирования другими, это кажется даже быстрее (я очень удивлен тем, что библиотека qsort использует более сложный API).
Порядок ранга
Рекс Керр предложил другой совершенно другой метод: для каждого элемента массива вычисляют непосредственно его конечную позицию. Это эффективно, потому что порядок вычисления не требует ветвления. Недостаток этого метода состоит в том, что он занимает в три раза больше памяти массива (одна копия массива и переменные для хранения ранговых порядков). Результаты производительности очень удивительны (и интересны). На моей эталонной архитектуре с 32-битной ОС и Intel Core2 Quad E8300 число циклов было чуть ниже 1000 (как в случае сортировки сетей с разветвленной ветвью). Но когда он был скомпилирован и выполнен на моем 64-битном компьютере (Intel Core2 Duo), он работал намного лучше: он стал самым быстрым до сих пор. Я наконец выяснил истинную причину. Мой 32-битный блок использует gcc 4.4.1 и мой 64-битный блок gcc 4.4.3, и последний, похоже, гораздо лучше оптимизирует этот конкретный код (для других предложений было очень мало различий).
обновление
Как показывают опубликованные выше рисунки, этот эффект все еще усиливался в более поздних версиях gcc, а ранговый порядок стал в два раза быстрее, чем в любой другой альтернативе.
Сортировка сетей 12 с переупорядоченным свопом
Удивительная эффективность предложения Rex Kerr с gcc 4.4.3 заставила меня задуматься: как может программа с 3-кратным увеличением использования памяти быть быстрее, чем сети с разветвленной сортировкой?Моя гипотеза состояла в том, что у него было меньше зависимостей типа чтения после записи, что позволяло лучше использовать планировщик суперскалярных команд в x86.Это дало мне идею: изменить порядок перестановок, чтобы минимизировать зависимости чтения после записи.Проще говоря: когда вы делаете SWAP(1, 2); SWAP(0, 2);, вам нужно дождаться завершения первого обмена, прежде чем выполнять второй, потому что оба имеют доступ к общей ячейке памяти.Когда вы делаете SWAP(1, 2); SWAP(4, 5);, процессор может выполнять оба параллельно.Я попробовал, и все работает как положено, сортировочные сети работают примерно на 10% быстрее.
Сортировка сетей 12 с помощью простого свопа
Через год после первоначальной публикации Стейнар Х. Гандерсон предложил, чтобы мы не пытались перехитрить компилятор и сохранить код подкачкипросто.Это действительно хорошая идея, поскольку полученный код работает примерно на 40% быстрее!Он также предложил обмен, оптимизированный вручную с использованием встроенного кода сборки x86, который может сэкономить еще несколько циклов.Самое удивительное (в нем говорится о психологии программиста), что год назад никто из бывших в употреблении не пробовал эту версию свопинга.Код, который я использовал для проверки: здесь .Другие предлагали другие способы написания быстрого свопинга на C, но он дает те же характеристики, что и простой с достойным компилятором.
«Лучший» код теперь выглядит следующим образом:
static inline void sort6_sorting_network_simple_swap(int * d){
#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x)
#define SWAP(x,y) { const int a = min(d[x], d[y]); \
const int b = max(d[x], d[y]); \
d[x] = a; d[y] = b; }
SWAP(1, 2);
SWAP(4, 5);
SWAP(0, 2);
SWAP(3, 5);
SWAP(0, 1);
SWAP(3, 4);
SWAP(1, 4);
SWAP(0, 3);
SWAP(2, 5);
SWAP(1, 3);
SWAP(2, 4);
SWAP(2, 3);
#undef SWAP
#undef min
#undef max
}
Если мы считаем, что наш набор тестов (и, да, он довольно плохой, просто преимущество в том, что он короткий, простой и легкий для понимания того, что мы измеряем), среднее число циклов полученного кода для одного вида будет ниже 40 циклов.(Выполнено 6 тестов).Это означает, что каждый своп в среднем составляет 4 цикла.Я называю это удивительно быстро.Возможны ли другие улучшения?