Отвечая на другой вопрос переполнения стека ( этот ), я наткнулся на интересную подзадачу. Какой самый быстрый способ сортировки массива из 6 целых чисел?

Как вопрос очень низкого уровня:

• мы не можем предполагать, что библиотеки доступны (и сам вызов имеет свою стоимость), только простой 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. Интересно, какая специфическая оптимизация имеет этот эффект?

Комментарии к предлагаемым решениям

Сортировка вставок (Даниэль Штутцбах)

Как и ожидалось, минимизация веток действительно хорошая идея.

Сортировка сетей (Даниэль Штутцбах)

Лучше, чем сортировка вставок. Я задавался вопросом, не был ли главный эффект от избегания внешнего цикла. Я проверил развернутую сортировку вставок, чтобы проверить, и мы действительно получаем примерно одинаковые цифры (код здесь ).

Сортировка сетей (Пол Р)

Лучшее пока. Фактический код, который я использовал для тестирования, находится здесь . Пока не знаю, почему это почти в два раза быстрее, чем в другой сети сортировки. Передача параметров? Быстро макс?

Сортировка сетей 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.

обновление :

Как видно из опубликованных выше рисунков, этот эффект все еще усиливался в более поздних версиях 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 цикла. Я называю это удивительно быстро. Возможны ли другие улучшения?

Для любой оптимизации всегда лучше всего тестировать, тестировать, тестировать. Я бы попробовал хотя бы сортировку сетей и вставку сортировки. Если бы я делал ставки, я бы положил свои деньги на сортировку, основываясь на прошлом опыте.

Вы знаете что-нибудь о входных данных? Некоторые алгоритмы будут работать лучше с определенными видами данных. Например, сортировка вставкой работает лучше для отсортированных или почти отсортированных данных, поэтому она будет лучшим выбором, если вероятность почти отсортированных данных выше среднего.

Алгоритм, который вы опубликовали, похож на сортировку вставкой, но похоже, что вы свели к минимуму количество свопов за счет дополнительных сравнений. Сравнения намного дороже, чем свопы, потому что ветки могут привести к остановке конвейера команд.

Вот реализация сортировки вставкой:

static __inline__ int sort6(int *d){
        int i, j;
        for (i = 1; i < 6; i++) {
                int tmp = d[i];
                for (j = i; j >= 1 && tmp < d[j-1]; j--)
                        d[j] = d[j-1];
                d[j] = tmp;
        }
}

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

static __inline__ int sort6(int * d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
    SWAP(1, 2);
    SWAP(0, 2);
    SWAP(0, 1);
    SWAP(4, 5);
    SWAP(3, 5);
    SWAP(3, 4);
    SWAP(0, 3);
    SWAP(1, 4);
    SWAP(2, 5);
    SWAP(2, 4);
    SWAP(1, 3);
    SWAP(2, 3);
#undef SWAP
}

Вот реализация с использованием сортировки сетей :

inline void Sort2(int *p0, int *p1)
{
    const int temp = min(*p0, *p1);
    *p1 = max(*p0, *p1);
    *p0 = temp;
}

inline void Sort3(int *p0, int *p1, int *p2)
{
    Sort2(p0, p1);
    Sort2(p1, p2);
    Sort2(p0, p1);
}

inline void Sort4(int *p0, int *p1, int *p2, int *p3)
{
    Sort2(p0, p1);
    Sort2(p2, p3);
    Sort2(p0, p2);  
    Sort2(p1, p3);  
    Sort2(p1, p2);  
}

inline void Sort6(int *p0, int *p1, int *p2, int *p3, int *p4, int *p5)
{
    Sort3(p0, p1, p2);
    Sort3(p3, p4, p5);
    Sort2(p0, p3);  
    Sort2(p2, p5);  
    Sort4(p1, p2, p3, p4);  
}

Для этого вам действительно нужны очень эффективные функции без ветвей minи maxреализаций, поскольку именно к этому и сводится этот код - последовательность операций minи maxопераций (всего по 13 на каждый). Я оставляю это как упражнение для читателя.

Обратите внимание, что эта реализация легко поддается векторизации (например, SIMD - в большинстве SIMD ISA есть инструкции min / max для векторов), а также к реализациям на GPU (например, CUDA - без разветвлений нет проблем с расхождением деформации и т. Д.).

Смотрите также: Быстрая реализация алгоритма для сортировки очень маленького списка.

Поскольку это целые числа, а сравнение быстрое, почему бы не вычислить порядок ранжирования каждого из них напрямую:

inline void sort6(int *d) {
  int e[6];
  memcpy(e,d,6*sizeof(int));
  int o0 = (d[0]>d[1])+(d[0]>d[2])+(d[0]>d[3])+(d[0]>d[4])+(d[0]>d[5]);
  int o1 = (d[1]>=d[0])+(d[1]>d[2])+(d[1]>d[3])+(d[1]>d[4])+(d[1]>d[5]);
  int o2 = (d[2]>=d[0])+(d[2]>=d[1])+(d[2]>d[3])+(d[2]>d[4])+(d[2]>d[5]);
  int o3 = (d[3]>=d[0])+(d[3]>=d[1])+(d[3]>=d[2])+(d[3]>d[4])+(d[3]>d[5]);
  int o4 = (d[4]>=d[0])+(d[4]>=d[1])+(d[4]>=d[2])+(d[4]>=d[3])+(d[4]>d[5]);
  int o5 = 15-(o0+o1+o2+o3+o4);
  d[o0]=e[0]; d[o1]=e[1]; d[o2]=e[2]; d[o3]=e[3]; d[o4]=e[4]; d[o5]=e[5];
}

Похоже, я попал на вечеринку год спустя, но здесь мы идем ...

Глядя на сборку, сгенерированную gcc 4.5.2, я заметил, что загрузка и сохранение выполняются для каждого свопа, который действительно не нужен. Было бы лучше загрузить 6 значений в регистры, отсортировать их и сохранить обратно в память. Я приказал, чтобы грузы в магазинах были как можно ближе к тому месту, где регистры сначала нужны и в последний раз используются. Я также использовал SWAP-макрос Стейнара Г. Гандерсона. Обновление: я переключился на макрос SWAP Паоло Бонзини, который превращает gcc во что-то похожее на макрос Гандерсона, но gcc может лучше упорядочить инструкции, поскольку они не представлены как явная сборка.

Я использовал тот же порядок обмена, что и для сети с переупорядоченным обменом, которая указана как наиболее эффективная, хотя может быть и лучший порядок. Если я найду больше времени, я сгенерирую и протестирую несколько перестановок.

Я изменил код тестирования, чтобы рассмотреть более 4000 массивов и показать среднее число циклов, необходимых для сортировки каждого из них. На i5-650 я получаю ~ 34,1 циклов / сортировку (с использованием -O3), по сравнению с исходной переупорядоченной сеткой сортировки, получающей ~ 65,3 циклов / сортировку (с использованием -O1, бьет -O2 и -O3).

#include <stdio.h>

static inline void sort6_fast(int * d) {
#define SWAP(x,y) { int dx = x, dy = y, tmp; tmp = x = dx < dy ? dx : dy; y ^= dx ^ tmp; }
    register int x0,x1,x2,x3,x4,x5;
    x1 = d[1];
    x2 = d[2];
    SWAP(x1, x2);
    x4 = d[4];
    x5 = d[5];
    SWAP(x4, x5);
    x0 = d[0];
    SWAP(x0, x2);
    x3 = d[3];
    SWAP(x3, x5);
    SWAP(x0, x1);
    SWAP(x3, x4);
    SWAP(x1, x4);
    SWAP(x0, x3);
    d[0] = x0;
    SWAP(x2, x5);
    d[5] = x5;
    SWAP(x1, x3);
    d[1] = x1;
    SWAP(x2, x4);
    d[4] = x4;
    SWAP(x2, x3);
    d[2] = x2;
    d[3] = x3;

#undef SWAP
#undef min
#undef max
}

static __inline__ unsigned long long rdtsc(void)
{
    unsigned long long int x;
    __asm__ volatile ("rdtsc; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
    return x;
}

void ran_fill(int n, int *a) {
    static int seed = 76521;
    while (n--) *a++ = (seed = seed *1812433253 + 12345);
}

#define NTESTS 4096
int main() {
    int i;
    int d[6*NTESTS];
    ran_fill(6*NTESTS, d);

    unsigned long long cycles = rdtsc();
    for (i = 0; i < 6*NTESTS ; i+=6) {
        sort6_fast(d+i);
    }
    cycles = rdtsc() - cycles;
    printf("Time is %.2lf\n", (double)cycles/(double)NTESTS);

    for (i = 0; i < 6*NTESTS ; i+=6) {
        if (d[i+0] > d[i+1] || d[i+1] > d[i+2] || d[i+2] > d[i+3] || d[i+3] > d[i+4] || d[i+4] > d[i+5])
            printf("d%d : %d %d %d %d %d %d\n", i,
                    d[i+0], d[i+1], d[i+2],
                    d[i+3], d[i+4], d[i+5]);
    }
    return 0;
}

Я изменил модифицированный набор тестов, чтобы также сообщать о часах для каждого вида и запускать больше тестов (функция cmp была также обновлена ​​для обработки переполнения целых чисел), вот результаты для некоторых различных архитектур. Я попытался провести тестирование на процессоре AMD, но rdtsc не надежен на имеющейся у меня X6 1100T.

Clarkdale (i5-650)
==================
Direct call to qsort library function      635.14   575.65   581.61   577.76   521.12
Naive implementation (insertion sort)      538.30   135.36   134.89   240.62   101.23
Insertion Sort (Daniel Stutzbach)          424.48   159.85   160.76   152.01   151.92
Insertion Sort Unrolled                    339.16   125.16   125.81   129.93   123.16
Rank Order                                 184.34   106.58   54.74    93.24    94.09
Rank Order with registers                  127.45   104.65   53.79    98.05    97.95
Sorting Networks (Daniel Stutzbach)        269.77   130.56   128.15   126.70   127.30
Sorting Networks (Paul R)                  551.64   103.20   64.57    73.68    73.51
Sorting Networks 12 with Fast Swap         321.74   61.61    63.90    67.92    67.76
Sorting Networks 12 reordered Swap         318.75   60.69    65.90    70.25    70.06
Reordered Sorting Network w/ fast swap     145.91   34.17    32.66    32.22    32.18

Kentsfield (Core 2 Quad)
========================
Direct call to qsort library function      870.01   736.39   723.39   725.48   721.85
Naive implementation (insertion sort)      503.67   174.09   182.13   284.41   191.10
Insertion Sort (Daniel Stutzbach)          345.32   152.84   157.67   151.23   150.96
Insertion Sort Unrolled                    316.20   133.03   129.86   118.96   105.06
Rank Order                                 164.37   138.32   46.29    99.87    99.81
Rank Order with registers                  115.44   116.02   44.04    116.04   116.03
Sorting Networks (Daniel Stutzbach)        230.35   114.31   119.15   110.51   111.45
Sorting Networks (Paul R)                  498.94   77.24    63.98    62.17    65.67
Sorting Networks 12 with Fast Swap         315.98   59.41    58.36    60.29    55.15
Sorting Networks 12 reordered Swap         307.67   55.78    51.48    51.67    50.74
Reordered Sorting Network w/ fast swap     149.68   31.46    30.91    31.54    31.58

Sandy Bridge (i7-2600k)
=======================
Direct call to qsort library function      559.97   451.88   464.84   491.35   458.11
Naive implementation (insertion sort)      341.15   160.26   160.45   154.40   106.54
Insertion Sort (Daniel Stutzbach)          284.17   136.74   132.69   123.85   121.77
Insertion Sort Unrolled                    239.40   110.49   114.81   110.79   117.30
Rank Order                                 114.24   76.42    45.31    36.96    36.73
Rank Order with registers                  105.09   32.31    48.54    32.51    33.29
Sorting Networks (Daniel Stutzbach)        210.56   115.68   116.69   107.05   124.08
Sorting Networks (Paul R)                  364.03   66.02    61.64    45.70    44.19
Sorting Networks 12 with Fast Swap         246.97   41.36    59.03    41.66    38.98
Sorting Networks 12 reordered Swap         235.39   38.84    47.36    38.61    37.29
Reordered Sorting Network w/ fast swap     115.58   27.23    27.75    27.25    26.54

Nehalem (Xeon E5640)
====================
Direct call to qsort library function      911.62   890.88   681.80   876.03   872.89
Naive implementation (insertion sort)      457.69   236.87   127.68   388.74   175.28
Insertion Sort (Daniel Stutzbach)          317.89   279.74   147.78   247.97   245.09
Insertion Sort Unrolled                    259.63   220.60   116.55   221.66   212.93
Rank Order                                 140.62   197.04   52.10    163.66   153.63
Rank Order with registers                  84.83    96.78    50.93    109.96   54.73
Sorting Networks (Daniel Stutzbach)        214.59   220.94   118.68   120.60   116.09
Sorting Networks (Paul R)                  459.17   163.76   56.40    61.83    58.69
Sorting Networks 12 with Fast Swap         284.58   95.01    50.66    53.19    55.47
Sorting Networks 12 reordered Swap         281.20   96.72    44.15    56.38    54.57
Reordered Sorting Network w/ fast swap     128.34   50.87    26.87    27.91    28.02

Я наткнулся на этот вопрос от Google несколько дней назад, потому что мне также нужно было быстро отсортировать массив фиксированной длины из 6 целых чисел. В моем случае, однако, мои целые числа - только 8 бит (вместо 32), и у меня нет строгого требования использовать только C. Я думал, что в любом случае поделюсь своими результатами, если они кому-нибудь пригодятся ...

Я реализовал вариант сетевой сортировки в сборке, который использует SSE для максимально возможной векторизации операций сравнения и обмена. Требуется шесть «проходов», чтобы полностью отсортировать массив. Я использовал новый механизм для непосредственного преобразования результатов PCMPGTB (векторизованное сравнение) в случайные параметры для PSHUFB (векторизованный обмен), используя только PADDB (векторизованное добавление), а в некоторых случаях также инструкцию PAND (побитовое И).

Этот подход также имел побочный эффект от получения действительно выполнял функцию без ответвлений. Там нет никаких инструкций прыжка вообще.

Похоже, что эта реализация примерно на 38% быстрее, чем реализация, которая в настоящее время помечена как самая быстрая опция в вопросе («Сортировка сетей 12 с помощью простой замены»). Я изменил эту реализацию, чтобы использоватьchar элементы массива во время моего тестирования, чтобы сделать сравнение справедливым.

Следует отметить, что такой подход может применяться к любому размеру массива до 16 элементов. Я ожидаю, что относительное преимущество в скорости перед альтернативами будет увеличиваться для больших массивов.

Код написан на MASM для процессоров x86_64 с SSSE3. Функция использует «новое» соглашение о вызовах Windows x64. Вот...

PUBLIC simd_sort_6

.DATA

ALIGN 16

pass1_shuffle   OWORD   0F0E0D0C0B0A09080706040503010200h
pass1_add       OWORD   0F0E0D0C0B0A09080706050503020200h
pass2_shuffle   OWORD   0F0E0D0C0B0A09080706030405000102h
pass2_and       OWORD   00000000000000000000FE00FEFE00FEh
pass2_add       OWORD   0F0E0D0C0B0A09080706050405020102h
pass3_shuffle   OWORD   0F0E0D0C0B0A09080706020304050001h
pass3_and       OWORD   00000000000000000000FDFFFFFDFFFFh
pass3_add       OWORD   0F0E0D0C0B0A09080706050404050101h
pass4_shuffle   OWORD   0F0E0D0C0B0A09080706050100020403h
pass4_and       OWORD   0000000000000000000000FDFD00FDFDh
pass4_add       OWORD   0F0E0D0C0B0A09080706050403020403h
pass5_shuffle   OWORD   0F0E0D0C0B0A09080706050201040300h
pass5_and       OWORD 0000000000000000000000FEFEFEFE00h
pass5_add       OWORD   0F0E0D0C0B0A09080706050403040300h
pass6_shuffle   OWORD   0F0E0D0C0B0A09080706050402030100h
pass6_add       OWORD   0F0E0D0C0B0A09080706050403030100h

.CODE

simd_sort_6 PROC FRAME

    .endprolog

    ; pxor xmm4, xmm4
    ; pinsrd xmm4, dword ptr [rcx], 0
    ; pinsrb xmm4, byte ptr [rcx + 4], 4
    ; pinsrb xmm4, byte ptr [rcx + 5], 5
    ; The benchmarked 38% faster mentioned in the text was with the above slower sequence that tied up the shuffle port longer.  Same on extract
    ; avoiding pins/extrb also means we don't need SSE 4.1, but SSSE3 CPUs without SSE4.1 (e.g. Conroe/Merom) have slow pshufb.
    movd    xmm4, dword ptr [rcx]
    pinsrw  xmm4,  word ptr [rcx + 4], 2  ; word 2 = bytes 4 and 5


    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass1_shuffle]
    pcmpgtb xmm5, xmm4
    paddb xmm5, oword ptr [pass1_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass2_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass2_and]
    paddb xmm5, oword ptr [pass2_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass3_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass3_and]
    paddb xmm5, oword ptr [pass3_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass4_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass4_and]
    paddb xmm5, oword ptr [pass4_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass5_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass5_and]
    paddb xmm5, oword ptr [pass5_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass6_shuffle]
    pcmpgtb xmm5, xmm4
    paddb xmm5, oword ptr [pass6_add]
    pshufb xmm4, xmm5

    ;pextrd dword ptr [rcx], xmm4, 0    ; benchmarked with this
    ;pextrb byte ptr [rcx + 4], xmm4, 4 ; slower version
    ;pextrb byte ptr [rcx + 5], xmm4, 5
    movd   dword ptr [rcx], xmm4
    pextrw  word ptr [rcx + 4], xmm4, 2  ; x86 is little-endian, so this is the right order

    ret

simd_sort_6 ENDP

END

Вы можете скомпилировать это в исполняемый объект и связать его с вашим C-проектом. Для получения инструкций о том, как сделать это в Visual Studio, вы можете прочитать эту статью . Вы можете использовать следующий прототип C для вызова функции из вашего кода C:

void simd_sort_6(char *values);

Тестовый код довольно плохой; он переполняет исходный массив (люди здесь не читают предупреждения компилятора?), printf печатает неправильные элементы, он использует .byte для rdtsc без веской причины, есть только один прогон (!), нет ничего проверяющего, что конечные результаты на самом деле правильные (поэтому очень легко «оптимизировать» что-то слегка неправильное), включенные тесты очень элементарны (без отрицательных чисел?), и ничто не мешает компилятору просто отбросить всю функцию как мертвый код.

Тем не менее, это также довольно легко улучшить в битонном сетевом решении; просто измените мин / макс / своп вещи на

#define SWAP(x,y) { int tmp; asm("mov %0, %2 ; cmp %1, %0 ; cmovg %1, %0 ; cmovg %2, %1" : "=r" (d[x]), "=r" (d[y]), "=r" (tmp) : "0" (d[x]), "1" (d[y]) : "cc"); }

и он у меня получается примерно на 65% быстрее (Debian gcc 4.4.5 с -O2, amd64, Core i7).

Хотя мне очень нравится макрос подкачки при условии:

#define min(x, y) (y ^ ((x ^ y) & -(x < y)))
#define max(x, y) (x ^ ((x ^ y) & -(x < y)))
#define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }

Я вижу улучшение (которое может сделать хороший компилятор):

#define SWAP(x,y) { int tmp = ((x ^ y) & -(y < x)); y ^= tmp; x ^= tmp; }

Мы обращаем внимание на то, как работают min и max, и явно извлекаем общее подвыражение. Это полностью исключает минимальные и максимальные макросы.

Никогда не оптимизируйте мин / макс без бенчмаркинга и просмотра фактической сборки, сгенерированной компилятором. Если я позволю GCC оптимизировать min с помощью инструкций условного перемещения, я получу ускорение на 33%:

#define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }

(280 против 420 циклов в тестовом коде). Выполнение max с?: Более или менее то же самое, почти потеряно в шуме, но вышеупомянутое немного быстрее. Этот SWAP быстрее с GCC и Clang.

Компиляторы также выполняют исключительную работу по распределению регистров и анализу псевдонимов, эффективно перемещая d [x] в локальные переменные заранее и только копируя обратно в память в конце. На самом деле, они делают это даже лучше, чем если бы вы работали полностью с локальными переменными (например,d0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5] ). Я пишу это, потому что вы предполагаете сильную оптимизацию и все же пытаетесь перехитрить компилятор на мин / макс. :)

Кстати, я пробовал Clang и GCC. Они выполняют одну и ту же оптимизацию, но из-за различий в расписании у обоих есть некоторые различия в результатах, не могу сказать, что на самом деле быстрее или медленнее. GCC быстрее в сетях сортировки, Clang в квадратичных сортировках.

Просто для полноты возможна развернутая сортировка пузырьков и вставка. Вот вид пузыря:

SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4); SWAP(4,5);
SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4);
SWAP(0,1); SWAP(1,2); SWAP(2,3);
SWAP(0,1); SWAP(1,2);
SWAP(0,1);

и вот сортировка вставки:

//#define ITER(x) { if (t < d[x]) { d[x+1] = d[x]; d[x] = t; } }
//Faster on x86, probably slower on ARM or similar:
#define ITER(x) { d[x+1] ^= t < d[x] ? d[x] ^ d[x+1] : 0; d[x] = t < d[x] ? t : d[x]; }
static inline void sort6_insertion_sort_unrolled_v2(int * d){
    int t;
    t = d[1]; ITER(0);
    t = d[2]; ITER(1); ITER(0);
    t = d[3]; ITER(2); ITER(1); ITER(0);
    t = d[4]; ITER(3); ITER(2); ITER(1); ITER(0);
    t = d[5]; ITER(4); ITER(3); ITER(2); ITER(1); ITER(0);

Такая сортировка вставок выполняется быстрее, чем у Даниеля Штутцбаха, и особенно хороша для графического процессора или компьютера с предопределением, потому что ITER может быть выполнен только с 3 инструкциями (против 4 для SWAP). Например, вот t = d[2]; ITER(1); ITER(0);строка в сборке ARM:

    MOV    r6, r2
    CMP    r6, r1
    MOVLT  r2, r1
    MOVLT  r1, r6
    CMP    r6, r0
    MOVLT  r1, r0
    MOVLT  r0, r6

Для шести элементов сортировка вставки является конкурентоспособной с сетью сортировки (12 обменов против 15 итераций балансирует 4 инструкции / обмен против 3 инструкций / итерация); пузырьковый тип, конечно, медленнее. Но это не будет правдой, когда размер увеличивается, так как сортировка вставки - O (n ^ 2), а сортировка сетей - O (n log n).

Я перенес набор тестов на машину с архитектурой PPC, которую я не могу идентифицировать (не нужно было трогать код, просто увеличивать итерации теста, использовать 8 тестовых случаев, чтобы избежать загрязнения результатов модами и заменить специфичный для x86 rdtsc):

Прямой вызов функции библиотеки qsort : 101

Наивная реализация (вставка сортировки) : 299

Сортировка вставок (Даниэль Штутцбах) : 108

Развернутая сортировка вставок : 51

Сортировка сетей (Даниэль Штутцбах) : 26

Сортировка сетей (Paul R) : 85

Сортировка сетей 12 с быстрой заменой : 117

Сортировка сетей 12 переупорядочено Своп : 116

Порядок ранга : 56

Обмен XOR может быть полезен в ваших функциях обмена.

void xorSwap (int *x, int *y) {
     if (*x != *y) {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
 }

If может вызвать слишком большое расхождение в вашем коде, но если у вас есть гарантия, что все ваши целые уникальны, это может быть удобно.

С нетерпением жду возможности попробовать свои силы и учиться на этих примерах, но сначала несколько моментов из моей 1,5 ГГц PPC Powerbook G4 с 1 ГБ оперативной памяти DDR. (Я позаимствовал подобный rdtsc-подобный таймер для PPC от http://www.mcs.anl.gov/~kazutomo/rdtsc.html для таймингов.) Я запускал программу несколько раз, и абсолютные результаты менялись, но последовательно Самым быстрым тестом был «Сортировка вставки (Даниэль Штутцбах)», а «Сортировка вставки развернута» за короткую секунду.

Вот последний набор раз:

**Direct call to qsort library function** : 164
**Naive implementation (insertion sort)** : 138
**Insertion Sort (Daniel Stutzbach)**     : 85
**Insertion Sort Unrolled**               : 97
**Sorting Networks (Daniel Stutzbach)**   : 457
**Sorting Networks (Paul R)**             : 179
**Sorting Networks 12 with Fast Swap**    : 238
**Sorting Networks 12 reordered Swap**    : 236
**Rank Order**                            : 116

Вот мой вклад в эту тему: оптимизированная 1, 4-разрядная сортировка оболочки для вектора int из 6 элементов (valp), содержащего уникальные значения.

void shellsort (int *valp)
{      
  int c,a,*cp,*ip=valp,*ep=valp+5;

  c=*valp;    a=*(valp+4);if (c>a) {*valp=    a;*(valp+4)=c;}
  c=*(valp+1);a=*(valp+5);if (c>a) {*(valp+1)=a;*(valp+5)=c;}

  cp=ip;    
  do
  {
    c=*cp;
    a=*(cp+1);
    do
    {
      if (c<a) break;

      *cp=a;
      *(cp+1)=c;
      cp-=1;
      c=*cp;
    } while (cp>=valp);
    ip+=1;
    cp=ip;
  } while (ip<ep);
}

На моем ноутбуке HP dv7-3010so с двухъядерным процессором Athlon M300 @ 2 ГГц (память DDR2) он работает за 165 тактов. Это среднее значение, рассчитанное по времени для каждой уникальной последовательности (всего 6! / 720). Скомпилировано в Win32 с использованием OpenWatcom 1.8. Цикл по сути является сортировкой вставки и имеет длину 16 инструкций / 37 байт.

У меня нет 64-битной среды для компиляции.

Если сортировка вставок здесь достаточно конкурентоспособна, я бы рекомендовал попробовать сортировку оболочек. Боюсь, что 6 элементов, вероятно, слишком мало для того, чтобы быть в числе лучших, но, возможно, стоит попробовать.

Пример кода, непроверенный, отлаженный и т. Д. Вы хотите настроить последовательность inc = 4 и inc - = 3, чтобы найти оптимальный (например, попробуйте inc = 2, inc - = 1).

static __inline__ int sort6(int * d) {
    char j, i;
    int tmp;
    for (inc = 4; inc > 0; inc -= 3) {
        for (i = inc; i < 5; i++) {
            tmp = a[i];
            j = i;
            while (j >= inc && a[j - inc] > tmp) {
                a[j] = a[j - inc];
                j -= inc;
            }
            a[j] = tmp;
        }
    }
}

Я не думаю, что это победит, но если кто-то отправит вопрос о сортировке 10 элементов, кто знает ...

Согласно Википедии это может даже сочетаться с сортировочными сетями: Pratt, V (1979). Сортировка и сортировка сетей (Выдающиеся диссертации в области компьютерных наук). Garland. ISBN 0-824-04406-1

Я знаю, что я опоздал, но мне было интересно поэкспериментировать с разными решениями. Сначала я очистил эту пасту, скомпилировал ее и поместил в репозиторий. Я оставил некоторые нежелательные решения в тупик, чтобы другие не попробовали. Среди них было мое первое решение, которое пыталось гарантировать, что x1> x2 был вычислен один раз. После оптимизации он не быстрее других простых версий.

Я добавил зацикленную версию сортировки по рангу, поскольку мое собственное приложение для этого исследования предназначено для сортировки 2-8 элементов, поэтому, поскольку имеется переменное число аргументов, необходим цикл. По этой же причине я проигнорировал сетевые решения для сортировки.

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

Затем я написал вид вставки, который целиком находится в регистрах AVX. На моей машине это на 25% быстрее, чем другие типы вставок, но на 100% медленнее, чем порядок ранжирования. Я сделал это исключительно для эксперимента и не ожидал, что это будет лучше из-за разветвления в виде вставки.

static inline void sort6_insertion_sort_avx(int* d) {
    __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], 0, 0);
    __m256i index = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
    __m256i shlpermute = _mm256_setr_epi32(7, 0, 1, 2, 3, 4, 5, 6);
    __m256i sorted = _mm256_setr_epi32(d[0], INT_MAX, INT_MAX, INT_MAX,
            INT_MAX, INT_MAX, INT_MAX, INT_MAX);
    __m256i val, gt, permute;
    unsigned j;
     // 8 / 32 = 2^-2
#define ITER(I) \
        val = _mm256_permutevar8x32_epi32(src, _mm256_set1_epi32(I));\
        gt =  _mm256_cmpgt_epi32(sorted, val);\
        permute =  _mm256_blendv_epi8(index, shlpermute, gt);\
        j = ffs( _mm256_movemask_epi8(gt)) >> 2;\
        sorted = _mm256_blendv_epi8(_mm256_permutevar8x32_epi32(sorted, permute),\
                val, _mm256_cmpeq_epi32(index, _mm256_set1_epi32(j)))
    ITER(1);
    ITER(2);
    ITER(3);
    ITER(4);
    ITER(5);
    int x[8];
    _mm256_storeu_si256((__m256i*)x, sorted);
    d[0] = x[0]; d[1] = x[1]; d[2] = x[2]; d[3] = x[3]; d[4] = x[4]; d[5] = x[5];
#undef ITER
}

Затем я написал сортировку по рангу, используя AVX. Это соответствует скорости других решений рангового порядка, но не быстрее. Проблема в том, что я могу рассчитывать индексы только с помощью AVX, а затем мне нужно составить таблицу индексов. Это связано с тем, что расчеты основаны на назначении, а не на источнике. См. Преобразование из исходных индексов в целевые индексы

static inline void sort6_rank_order_avx(int* d) {
    __m256i ror = _mm256_setr_epi32(5, 0, 1, 2, 3, 4, 6, 7);
    __m256i one = _mm256_set1_epi32(1);
    __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], INT_MAX, INT_MAX);
    __m256i rot = src;
    __m256i index = _mm256_setzero_si256();
    __m256i gt, permute;
    __m256i shl = _mm256_setr_epi32(1, 2, 3, 4, 5, 6, 6, 6);
    __m256i dstIx = _mm256_setr_epi32(0,1,2,3,4,5,6,7);
    __m256i srcIx = dstIx;
    __m256i eq = one;
    __m256i rotIx = _mm256_setzero_si256();
#define INC(I)\
    rot = _mm256_permutevar8x32_epi32(rot, ror);\
    gt = _mm256_cmpgt_epi32(src, rot);\
    index = _mm256_add_epi32(index, _mm256_and_si256(gt, one));\
    index = _mm256_add_epi32(index, _mm256_and_si256(eq,\
                _mm256_cmpeq_epi32(src, rot)));\
    eq = _mm256_insert_epi32(eq, 0, I)
    INC(0);
    INC(1);
    INC(2);
    INC(3);
    INC(4);
    int e[6];
    e[0] = d[0]; e[1] = d[1]; e[2] = d[2]; e[3] = d[3]; e[4] = d[4]; e[5] = d[5];
    int i[8];
    _mm256_storeu_si256((__m256i*)i, index);
    d[i[0]] = e[0]; d[i[1]] = e[1]; d[i[2]] = e[2]; d[i[3]] = e[3]; d[i[4]] = e[4]; d[i[5]] = e[5];
}

Репо можно найти здесь: https://github.com/eyepatchParrot/sort6/

Этот вопрос становится довольно старым, но на самом деле мне пришлось решать ту же проблему в наши дни: быстрые агорифмы для сортировки небольших массивов. Я подумал, что будет хорошей идеей поделиться своими знаниями. Хотя я впервые начал использовать сортировку сетей, мне, наконец, удалось найти другие алгоритмы, для которых общее число сравнений, выполненных для сортировки каждой перестановки из 6 значений, было меньше, чем с сетями сортировки, и меньше, чем с сортировкой вставками. Я не посчитал количество свопов; Я ожидал бы, что это будет примерно эквивалентно (возможно, немного выше иногда).

Алгоритм sort6использует алгоритм, sort4который использует алгоритм sort3. Вот реализация в некоторой легкой форме C ++ (оригинал является тяжелым шаблоном, чтобы он мог работать с любым итератором с произвольным доступом и любой подходящей функцией сравнения).

Сортировка 3 значений

Следующий алгоритм представляет собой развернутую сортировку вставок. Когда необходимо выполнить два обмена (6 назначений), вместо этого используются 4 назначения:

void sort3(int* array)
{
    if (array[1] < array[0]) {
        if (array[2] < array[0]) {
            if (array[2] < array[1]) {
                std::swap(array[0], array[2]);
            } else {
                int tmp = array[0];
                array[0] = array[1];
                array[1] = array[2];
                array[2] = tmp;
            }
        } else {
            std::swap(array[0], array[1]);
        }
    } else {
        if (array[2] < array[1]) {
            if (array[2] < array[0]) {
                int tmp = array[2];
                array[2] = array[1];
                array[1] = array[0];
                array[0] = tmp;
            } else {
                std::swap(array[1], array[2]);
            }
        }
    }
}

Это выглядит немного сложнее, потому что сортировка имеет более или менее одну ветвь для каждой возможной перестановки массива, используя 2 ~ 3 сравнения и не более 4 присваиваний для сортировки трех значений.

Сортировка 4 значений

Этот вызов вызывает sort3затем развернутую сортировку вставки с последним элементом массива:

void sort4(int* array)
{
    // Sort the first 3 elements
    sort3(array);

    // Insert the 4th element with insertion sort 
    if (array[3] < array[2]) {
        std::swap(array[2], array[3]);
        if (array[2] < array[1]) {
            std::swap(array[1], array[2]);
            if (array[1] < array[0]) {
                std::swap(array[0], array[1]);
            }
        }
    }
}

Этот алгоритм выполняет от 3 до 6 сравнений и не более 5 обменов. Развернуть сортировку вставкой легко, но мы будем использовать другой алгоритм для последней сортировки ...

Сортировка 6 значений

Этот использует развернутую версию того, что я назвал сортировкой с двойной вставкой . Название не настолько велико, но оно довольно наглядно, вот как оно работает:

• Сортировать все, кроме первого и последнего элементов массива.
• Поменяйте местами первое и элементы массива, если первое больше последнего.
• Вставьте первый элемент в отсортированную последовательность спереди, а затем последний элемент сзади.

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

void sort6(int* array)
{
    // Sort everything but first and last elements
    sort4(array+1);

    // Switch first and last elements if needed
    if (array[5] < array[0]) {
        std::swap(array[0], array[5]);
    }

    // Insert first element from the front
    if (array[1] < array[0]) {
        std::swap(array[0], array[1]);
        if (array[2] < array[1]) {
            std::swap(array[1], array[2]);
            if (array[3] < array[2]) {
                std::swap(array[2], array[3]);
                if (array[4] < array[3]) {
                    std::swap(array[3], array[4]);
                }
            }
        }
    }

    // Insert last element from the back
    if (array[5] < array[4]) {
        std::swap(array[4], array[5]);
        if (array[4] < array[3]) {
            std::swap(array[3], array[4]);
            if (array[3] < array[2]) {
                std::swap(array[2], array[3]);
                if (array[2] < array[1]) {
                    std::swap(array[1], array[2]);
                }
            }
        }
    }
}

Мои тесты на каждую перестановку из 6 значений показывают, что этот алгоритм всегда выполняет от 6 до 13 сравнений. Я не вычислял количество выполненных свопов, но не ожидаю, что оно будет выше 11 в худшем случае.

Я надеюсь, что это поможет, даже если этот вопрос больше не представляет реальной проблемы :)

РЕДАКТИРОВАТЬ: после того, как положить его в предоставленный тест, он будет медленнее, чем большинство интересных альтернатив. Это имеет тенденцию работать немного лучше, чем развернутая сортировка вставок, но это в значительной степени так. По сути, это не лучший тип для целых чисел, но он может быть интересен для типов с дорогой операцией сравнения.

Я считаю, что на ваш вопрос есть две части.

• Во-первых, определить оптимальный алгоритм. Это делается - по крайней мере, в этом случае - путем обхода каждого возможного порядка (их не так много), который позволяет вычислить точное минимальное, максимальное, среднее и стандартное отклонение сравнений и свопов. Имейте второе место или два удобных также.
• Второе - оптимизировать алгоритм. Многое можно сделать, чтобы преобразовать примеры из учебников в средние и простые алгоритмы. Если вы понимаете, что алгоритм не может быть оптимизирован до необходимой степени, попробуйте получить второе место.

Я бы не стал сильно волноваться по поводу опустошения конвейеров (если принять текущий x86): предсказание ветвлений прошло долгий путь. То, о чем я бы беспокоился, - это убедиться, что код и данные помещаются в одну строку кэша каждая (возможно, две для кода). Как только время выборки будет очень низким, это компенсирует любую задержку. Это также означает, что ваш внутренний цикл будет состоять из десяти инструкций или около того, что и должно быть (в моем алгоритме сортировки есть два разных внутренних цикла, они 10 инструкций / 22 байта и 9/22 длиной соответственно). Предполагая, что код не содержит никаких div-ов, вы можете быть уверены, что он будет ослепительно быстрым.

Я знаю, что это старый вопрос.

Но я просто написал другое решение, которым хочу поделиться.
Не используя ничего, кроме вложенного MIN MAX,

Это не быстро, так как использует 114 из каждого,
может уменьшить его до 75, просто так -> pastebin

Но тогда это уже не просто min max.

Что может работать, так это делать мин / макс для нескольких целых чисел одновременно с AVX

Ссылка PMINSW

#include <stdio.h>

static __inline__ int MIN(int a, int b){
int result =a;
__asm__ ("pminsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ int MAX(int a, int b){
int result = a;
__asm__ ("pmaxsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ unsigned long long rdtsc(void){
  unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" :
  "=A" (x));
  return x;
}

#define MIN3(a, b, c) (MIN(MIN(a,b),c))
#define MIN4(a, b, c, d) (MIN(MIN(a,b),MIN(c,d)))

static __inline__ void sort6(int * in) {
  const int A=in[0], B=in[1], C=in[2], D=in[3], E=in[4], F=in[5];

  in[0] = MIN( MIN4(A,B,C,D),MIN(E,F) );

  const int
  AB = MAX(A, B),
  AC = MAX(A, C),
  AD = MAX(A, D),
  AE = MAX(A, E),
  AF = MAX(A, F),
  BC = MAX(B, C),
  BD = MAX(B, D),
  BE = MAX(B, E),
  BF = MAX(B, F),
  CD = MAX(C, D),
  CE = MAX(C, E),
  CF = MAX(C, F),
  DE = MAX(D, E),
  DF = MAX(D, F),
  EF = MAX(E, F);

  in[1] = MIN4 (
  MIN4( AB, AC, AD, AE ),
  MIN4( AF, BC, BD, BE ),
  MIN4( BF, CD, CE, CF ),
  MIN3( DE, DF, EF)
  );

  const int
  ABC = MAX(AB,C),
  ABD = MAX(AB,D),
  ABE = MAX(AB,E),
  ABF = MAX(AB,F),
  ACD = MAX(AC,D),
  ACE = MAX(AC,E),
  ACF = MAX(AC,F),
  ADE = MAX(AD,E),
  ADF = MAX(AD,F),
  AEF = MAX(AE,F),
  BCD = MAX(BC,D),
  BCE = MAX(BC,E),
  BCF = MAX(BC,F),
  BDE = MAX(BD,E),
  BDF = MAX(BD,F),
  BEF = MAX(BE,F),
  CDE = MAX(CD,E),
  CDF = MAX(CD,F),
  CEF = MAX(CE,F),
  DEF = MAX(DE,F);

  in[2] = MIN( MIN4 (
  MIN4( ABC, ABD, ABE, ABF ),
  MIN4( ACD, ACE, ACF, ADE ),
  MIN4( ADF, AEF, BCD, BCE ),
  MIN4( BCF, BDE, BDF, BEF )),
  MIN4( CDE, CDF, CEF, DEF )
  );


  const int
  ABCD = MAX(ABC,D),
  ABCE = MAX(ABC,E),
  ABCF = MAX(ABC,F),
  ABDE = MAX(ABD,E),
  ABDF = MAX(ABD,F),
  ABEF = MAX(ABE,F),
  ACDE = MAX(ACD,E),
  ACDF = MAX(ACD,F),
  ACEF = MAX(ACE,F),
  ADEF = MAX(ADE,F),
  BCDE = MAX(BCD,E),
  BCDF = MAX(BCD,F),
  BCEF = MAX(BCE,F),
  BDEF = MAX(BDE,F),
  CDEF = MAX(CDE,F);

  in[3] = MIN4 (
  MIN4( ABCD, ABCE, ABCF, ABDE ),
  MIN4( ABDF, ABEF, ACDE, ACDF ),
  MIN4( ACEF, ADEF, BCDE, BCDF ),
  MIN3( BCEF, BDEF, CDEF )
  );

  const int
  ABCDE= MAX(ABCD,E),
  ABCDF= MAX(ABCD,F),
  ABCEF= MAX(ABCE,F),
  ABDEF= MAX(ABDE,F),
  ACDEF= MAX(ACDE,F),
  BCDEF= MAX(BCDE,F);

  in[4]= MIN (
  MIN4( ABCDE, ABCDF, ABCEF, ABDEF ),
  MIN ( ACDEF, BCDEF )
  );

  in[5] = MAX(ABCDE,F);
}

int main(int argc, char ** argv) {
  int d[6][6] = {
    {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 (int i = 0; i < 6; i++) {
    sort6(d[i]);
  }
  cycles = rdtsc() - cycles;
  printf("Time is %d\n", (unsigned)cycles);

  for (int i = 0; i < 6; i++) {
    printf("d%d : %d %d %d %d %d %d\n", i,
     d[i][0], d[i][1], d[i][2],
     d[i][3], d[i][4], d[i][5]);
  }
}

РЕДАКТИРОВАТЬ:
решение порядка ранга вдохновлен Рекс Керр, гораздо быстрее, чем беспорядок выше

static void sort6(int *o) {
const int 
A=o[0],B=o[1],C=o[2],D=o[3],E=o[4],F=o[5];
const unsigned char
AB = A>B, AC = A>C, AD = A>D, AE = A>E,
          BC = B>C, BD = B>D, BE = B>E,
                    CD = C>D, CE = C>E,
                              DE = D>E,
a =          AB + AC + AD + AE + (A>F),
b = 1 - AB      + BC + BD + BE + (B>F),
c = 2 - AC - BC      + CD + CE + (C>F),
d = 3 - AD - BD - CD      + DE + (D>F),
e = 4 - AE - BE - CE - DE      + (E>F);
o[a]=A; o[b]=B; o[c]=C; o[d]=D; o[e]=E;
o[15-a-b-c-d-e]=F;
}

Я обнаружил , что по крайней мере на моей системе, функции sort6_iterator()и sort6_iterator_local()определены ниже как бегала по крайней мере так же быстро, и часто заметно быстрее, чем выше текущего рекордсмена:

#define MIN(x, y) (x<y?x:y)
#define MAX(x, y) (x<y?y:x)

template<class IterType> 
inline void sort6_iterator(IterType it) 
{
#define SWAP(x,y) { const auto a = MIN(*(it + x), *(it + y)); \
  const auto b = MAX(*(it + x), *(it + y)); \
  *(it + x) = a; *(it + 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
}

Я передал эту функцию в качестве std::vectorитератора в моем временном коде.

Я подозреваю (из комментариев, подобных этому и в других местах), что использование итераторов дает g ++ определенные гарантии того, что может и не может произойти с памятью, на которую ссылается итератор, чего в противном случае не было бы, и именно эти гарантии позволяют g ++ лучше оптимизировать код сортировки (например, с помощью указателей компилятор не может быть уверен, что все указатели указывают на разные области памяти). Если я правильно помню, это тоже часть из причин , почему так много алгоритмов STL, такие какstd::sort() , как правило , имеют такую нецензурно производительность хорошая.

Более того, sort6_iterator()в некоторых случаях (опять же, в зависимости от контекста, в котором вызывается функция) последовательно выполняется следующая функция сортировки, которая копирует данные в локальные переменные перед их сортировкой. ¹ Обратите внимание, что, поскольку определены только 6 локальных переменных, если эти локальные переменные являются примитивами, то они, скорее всего, фактически никогда не хранятся в ОЗУ, а вместо этого хранятся только в регистрах ЦП до конца вызова функции, что помогает производить такую ​​сортировку. функционировать быстро (Также помогает компилятору знать, что разные локальные переменные имеют разные места в памяти).

template<class IterType> 
inline void sort6_iterator_local(IterType it) 
{
#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
  const auto b = MAX(data##x, data##y); \
  data##x = a; data##y = b; }
//DD = Define Data
#define DD1(a)   auto data##a = *(it + a);
#define DD2(a,b) auto data##a = *(it + a), data##b = *(it + b);
//CB = Copy Back
#define CB(a) *(it + a) = data##a;

  DD2(1,2)    SWAP(1, 2)
  DD2(4,5)    SWAP(4, 5)
  DD1(0)      SWAP(0, 2)
  DD1(3)      SWAP(3, 5)
  SWAP(0, 1)  SWAP(3, 4)
  SWAP(1, 4)  SWAP(0, 3)   CB(0)
  SWAP(2, 5)  CB(5)
  SWAP(1, 3)  CB(1)
  SWAP(2, 4)  CB(4)
  SWAP(2, 3)  CB(2)        CB(3)
#undef CB
#undef DD2
#undef DD1
#undef SWAP
}

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

#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
  data##y = MAX(data##x, data##y); \
  data##x = a; }

Если вы просто хотите алгоритм сортировки, который в примитивных типах данных, gcc -O3 неизменно хорош в оптимизации, независимо от того, в каком контексте вызов функции сортировки появляется в ^1, то, в зависимости от того, как вы передаете ввод, попробуйте один из следующих двух алгоритмы:

template<class T> inline void sort6(T it) {
#define SORT2(x,y) {if(data##x>data##y){auto a=std::move(data##y);data##y=std::move(data##x);data##x=std::move(a);}}
#define DD1(a)   register auto data##a=*(it+a);
#define DD2(a,b) register auto data##a=*(it+a);register auto data##b=*(it+b);
#define CB1(a)   *(it+a)=data##a;
#define CB2(a,b) *(it+a)=data##a;*(it+b)=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(4,5) SORT2(4,5)
  DD1(0)   SORT2(0,2)
  DD1(3)   SORT2(3,5)
  SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
  SORT2(1,4) SORT2(0,3) CB1(0)
  SORT2(2,4) CB1(4)
  SORT2(1,3) CB1(1)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

Или, если вы хотите передать переменные по ссылке, используйте это (функция ниже отличается от вышеупомянутой в ее первых 5 строках):

template<class T> inline void sort6(T& e0, T& e1, T& e2, T& e3, T& e4, T& e5) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a)   register auto data##a=e##a;
#define DD2(a,b) register auto data##a=e##a;register auto data##b=e##b;
#define CB1(a)   e##a=data##a;
#define CB2(a,b) e##a=data##a;e##b=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(4,5) SORT2(4,5)
  DD1(0)   SORT2(0,2)
  DD1(3)   SORT2(3,5)
  SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
  SORT2(1,4) SORT2(0,3) CB1(0)
  SORT2(2,4) CB1(4)
  SORT2(1,3) CB1(1)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

Причина использования registerключевого слова в том, что это один из тех немногих случаев, когда вы знаете, что вам нужны эти значения в регистрах. Без registerэтого компилятор будет понимать это большую часть времени, но иногда это не так. Использование registerключевого слова помогает решить эту проблему. Обычно, однако, не используйте registerключевое слово, так как оно скорее замедлит ваш код, чем ускорит его.

Также обратите внимание на использование шаблонов. Это сделано специально, поскольку даже при использовании inlineключевого слова функции шаблонов обычно гораздо более агрессивно оптимизируются с помощью gcc, чем функции vanilla C (это связано с тем, что gcc необходимо иметь дело с указателями функций для функций vanilla C, но не с функциями шаблонов).

1. При синхронизации различных функций сортировки я заметил, что контекст (то есть окружающий код), в котором был сделан вызов функции сортировки, оказал значительное влияние на производительность, что, вероятно, связано с тем, что функция встроена и затем оптимизирована. Например, если программа была достаточно простой, то, как правило, не было большой разницы в производительности между передачей функции сортировки указатель и передача ей итератора; в противном случае использование итераторов обычно приводило к заметно лучшей производительности и никогда (по моему опыту, по крайней мере, пока) никакой заметно худшей производительности. Я подозреваю, что это может быть потому, что g ++ может глобально оптимизировать достаточно простой код.

Попробуйте "объединить отсортированный список" сортировать. :) Используйте два массива. Самый быстрый для малого и большого массива.
Если вы согласны, вы только проверяете, где вставить. Другие большие значения вам не нужно сравнивать (cmp = ab> 0).
Для 4 номеров вы можете использовать систему 4-5 cmp (~ 4.6) или 3-6 cmp (~ 4.9). Bubble sort использовать 6 cmp (6). Много cmp для больших чисел медленнее кода.
Этот код использует 5 cmp (не сортировка MSL):
if (cmp(arr[n][i+0],arr[n][i+1])>0) {swap(n,i+0,i+1);} if (cmp(arr[n][i+2],arr[n][i+3])>0) {swap(n,i+2,i+3);} if (cmp(arr[n][i+0],arr[n][i+2])>0) {swap(n,i+0,i+2);} if (cmp(arr[n][i+1],arr[n][i+3])>0) {swap(n,i+1,i+3);} if (cmp(arr[n][i+1],arr[n][i+2])>0) {swap(n,i+1,i+2);}

Принципиальный MSL 9 8 7 6 5 4 3 2 1 0 89 67 45 23 01 ... concat two sorted lists, list length = 1 6789 2345 01 ... concat two sorted lists, list length = 2 23456789 01 ... concat two sorted lists, list length = 4 0123456789 ... concat two sorted lists, list length = 8

JS код

function sortListMerge_2a(cmp)	
{
var step, stepmax, tmp, a,b,c, i,j,k, m,n, cycles;
var start = 0;
var end   = arr_count;
//var str = '';
cycles = 0;
if (end>3)
	{
	stepmax = ((end - start + 1) >> 1) << 1;
	m = 1;
	n = 2;
	for (step=1;step<stepmax;step<<=1)	//bounds 1-1, 2-2, 4-4, 8-8...
		{
		a = start;
		while (a<end)
			{
			b = a + step;
			c = a + step + step;
			b = b<end ? b : end;
			c = c<end ? c : end;
			i = a;
			j = b;
			k = i;
			while (i<b && j<c)
				{
				if (cmp(arr[m][i],arr[m][j])>0)
					{arr[n][k] = arr[m][j]; j++; k++;}
				else	{arr[n][k] = arr[m][i]; i++; k++;}
				}
			while (i<b)
				{arr[n][k] = arr[m][i]; i++; k++;
}
			while (j<c)
				{arr[n][k] = arr[m][j]; j++; k++;
}
			a = c;
			}
		tmp = m; m = n; n = tmp;
		}
	return m;
	}
else
	{
	// sort 3 items
	sort10(cmp);
	return m;
	}
}

Сортировать 4 элемента с использованием cmp == 0. Числа cmp ~ 4.34 (у родной FF ~ 4.52), но занимают в 3 раза больше времени, чем слияние списков. Но лучше меньше операций cmp, если у вас большие цифры или большой текст. Редактировать: исправлена ​​ошибка

Онлайн тест http://mlich.zam.slu.cz/js-sort/x-sort-x2.htm

function sort4DG(cmp,start,end,n) // sort 4
{
var n     = typeof(n)    !=='undefined' ? n   : 1;
var cmp   = typeof(cmp)  !=='undefined' ? cmp   : sortCompare2;
var start = typeof(start)!=='undefined' ? start : 0;
var end   = typeof(end)  !=='undefined' ? end   : arr[n].length;
var count = end - start;
var pos = -1;
var i = start;
var cc = [];
// stabilni?
cc[01] = cmp(arr[n][i+0],arr[n][i+1]);
cc[23] = cmp(arr[n][i+2],arr[n][i+3]);
if (cc[01]>0) {swap(n,i+0,i+1);}
if (cc[23]>0) {swap(n,i+2,i+3);}
cc[12] = cmp(arr[n][i+1],arr[n][i+2]);
if (!(cc[12]>0)) {return n;}
cc[02] = cc[01]==0 ? cc[12] : cmp(arr[n][i+0],arr[n][i+2]);
if (cc[02]>0)
    {
    swap(n,i+1,i+2); swap(n,i+0,i+1); // bubble last to top
    cc[13] = cc[23]==0 ? cc[12] : cmp(arr[n][i+1],arr[n][i+3]);
    if (cc[13]>0)
        {
        swap(n,i+2,i+3); swap(n,i+1,i+2); // bubble
        return n;
        }
    else    {
    cc[23] = cc[23]==0 ? cc[12] : (cc[01]==0 ? cc[30] : cmp(arr[n][i+2],arr[n][i+3]));  // new cc23 | c03 //repaired
        if (cc[23]>0)
            {
            swap(n,i+2,i+3);
            return n;
            }
        return n;
        }
    }
else    {
    if (cc[12]>0)
        {
        swap(n,i+1,i+2);
        cc[23] = cc[23]==0 ? cc[12] : cmp(arr[n][i+2],arr[n][i+3]); // new cc23
        if (cc[23]>0)
            {
            swap(n,i+2,i+3);
            return n;
            }
        return n;
        }
    else    {
        return n;
        }
    }
return n;
}

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

• Код действительно должен быть встроен
• даже если встроено, слишком много веток
• анализирующая часть в основном O (N (N-1)), которая кажется нормальной для N = 6
• код может быть более эффективным, если стоимостьswap будет выше (irt стоимость compare)
• Я верю, что статические функции встроены.
• Метод связан с сортировкой рангов
  • вместо рангов используются относительные ранги (смещения).
  • сумма рангов равна нулю для каждого цикла в любой группе перестановок.
  • вместо SWAP()двух элементов циклы преследуются, для чего требуется только одна временная замена и один (регистр-> регистр) своп (новый <- старый).

Обновление: немного изменил код, некоторые люди используют компиляторы C ++ для компиляции кода C ...

#include <stdio.h>

#if WANT_CHAR
typedef signed char Dif;
#else
typedef signed int Dif;
#endif

static int walksort (int *arr, int cnt);
static void countdifs (int *arr, Dif *dif, int cnt);
static void calcranks(int *arr, Dif *dif);

int wsort6(int *arr);

void do_print_a(char *msg, int *arr, unsigned cnt)
{
fprintf(stderr,"%s:", msg);
for (; cnt--; arr++) {
        fprintf(stderr, " %3d", *arr);
        }
fprintf(stderr,"\n");
}

void do_print_d(char *msg, Dif *arr, unsigned cnt)
{
fprintf(stderr,"%s:", msg);
for (; cnt--; arr++) {
        fprintf(stderr, " %3d", (int) *arr);
        }
fprintf(stderr,"\n");
}

static void inline countdifs (int *arr, Dif *dif, int cnt)
{
int top, bot;

for (top = 0; top < cnt; top++ ) {
        for (bot = 0; bot < top; bot++ ) {
                if (arr[top] < arr[bot]) { dif[top]--; dif[bot]++; }
                }
        }
return ;
}
        /* Copied from RexKerr ... */
static void inline calcranks(int *arr, Dif *dif){

dif[0] =     (arr[0]>arr[1])+(arr[0]>arr[2])+(arr[0]>arr[3])+(arr[0]>arr[4])+(arr[0]>arr[5]);
dif[1] = -1+ (arr[1]>=arr[0])+(arr[1]>arr[2])+(arr[1]>arr[3])+(arr[1]>arr[4])+(arr[1]>arr[5]);
dif[2] = -2+ (arr[2]>=arr[0])+(arr[2]>=arr[1])+(arr[2]>arr[3])+(arr[2]>arr[4])+(arr[2]>arr[5]);
dif[3] = -3+ (arr[3]>=arr[0])+(arr[3]>=arr[1])+(arr[3]>=arr[2])+(arr[3]>arr[4])+(arr[3]>arr[5]);
dif[4] = -4+ (arr[4]>=arr[0])+(arr[4]>=arr[1])+(arr[4]>=arr[2])+(arr[4]>=arr[3])+(arr[4]>arr[5]);
dif[5] = -(dif[0]+dif[1]+dif[2]+dif[3]+dif[4]);
}

static int walksort (int *arr, int cnt)
{
int idx, src,dst, nswap;

Dif difs[cnt];

#if WANT_REXK
calcranks(arr, difs);
#else
for (idx=0; idx < cnt; idx++) difs[idx] =0;
countdifs(arr, difs, cnt);
#endif
calcranks(arr, difs);

#define DUMP_IT 0
#if DUMP_IT
do_print_d("ISteps ", difs, cnt);
#endif

nswap = 0;
for (idx=0; idx < cnt; idx++) {
        int newval;
        int step,cyc;
        if ( !difs[idx] ) continue;
        newval = arr[idx];
        cyc = 0;
        src = idx;
        do      {
                int oldval;
                step = difs[src];
                difs[src] =0;
                dst = src + step;
                cyc += step ;
                if(dst == idx+1)idx=dst;
                oldval = arr[dst];
#if (DUMP_IT&1)
                fprintf(stderr, "[Nswap=%d] Cyc=%d Step=%2d Idx=%d  Old=%2d New=%2d #### Src=%d Dst=%d[%2d]->%2d <-- %d\n##\n"
                        , nswap, cyc, step, idx, oldval, newval
                        , src, dst, difs[dst], arr[dst]
                        , newval  );
                do_print_a("Array ", arr, cnt);
                do_print_d("Steps ", difs, cnt);
#endif

                arr[dst] = newval;
                newval = oldval;
                nswap++;
                src = dst;
                } while( cyc);
        }

return nswap;
}
/*************/
int wsort6(int *arr)
{
return walksort(arr, 6);
}

//Bruteforce compute unrolled count dumbsort(min to 0-index)
void bcudc_sort6(int* a)
{
    int t[6] = {0};
    int r1,r2;

    r1=0;
    r1 += (a[0] > a[1]);
    r1 += (a[0] > a[2]);
    r1 += (a[0] > a[3]);
    r1 += (a[0] > a[4]);
    r1 += (a[0] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[0];

    r2=0;
    r2 += (a[1] > a[0]);
    r2 += (a[1] > a[2]);
    r2 += (a[1] > a[3]);
    r2 += (a[1] > a[4]);
    r2 += (a[1] > a[5]);
    while(t[r2]){r2++;} 
    t[r2] = a[1];

    r1=0;
    r1 += (a[2] > a[0]);
    r1 += (a[2] > a[1]);
    r1 += (a[2] > a[3]);
    r1 += (a[2] > a[4]);
    r1 += (a[2] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[2];

    r2=0;
    r2 += (a[3] > a[0]);
    r2 += (a[3] > a[1]);
    r2 += (a[3] > a[2]);
    r2 += (a[3] > a[4]);
    r2 += (a[3] > a[5]);
    while(t[r2]){r2++;} 
    t[r2] = a[3];

    r1=0;
    r1 += (a[4] > a[0]);
    r1 += (a[4] > a[1]);
    r1 += (a[4] > a[2]);
    r1 += (a[4] > a[3]);
    r1 += (a[4] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[4];

    r2=0;
    r2 += (a[5] > a[0]);
    r2 += (a[5] > a[1]);
    r2 += (a[5] > a[2]);
    r2 += (a[5] > a[3]);
    r2 += (a[5] > a[4]);
    while(t[r2]){r2++;} 
    t[r2] = a[5];

    a[0]=t[0];
    a[1]=t[1];
    a[2]=t[2];
    a[3]=t[3];
    a[4]=t[4];
    a[5]=t[5];
}

static __inline__ void sort6(int* a)
{
    #define wire(x,y); t = a[x] ^ a[y] ^ ( (a[x] ^ a[y]) & -(a[x] < a[y]) ); a[x] = a[x] ^ t; a[y] = a[y] ^ t;
    register int t;

    wire( 0, 1); wire( 2, 3); wire( 4, 5);
    wire( 3, 5); wire( 0, 2); wire( 1, 4);
    wire( 4, 5); wire( 2, 3); wire( 0, 1); 
    wire( 3, 4); wire( 1, 2); 
    wire( 2, 3);

    #undef wire
}

Хорошо, если это всего 6 элементов, и вы можете использовать параллелизм, хотите минимизировать условное ветвление и т. Д. Почему вы не генерируете все комбинации и не проверяете порядок? Рискну предположить, что в некоторых архитектурах это может быть довольно быстро (при условии, что у вас предварительно выделена память)

Вот три типичных метода сортировки, которые представляют три разных класса алгоритмов сортировки:

Insertion Sort: Θ(n^2)

Heap Sort: Θ(n log n)

Count Sort: Θ(3n)

Но посмотрите обсуждение Стефаном Нельссоном самого быстрого алгоритма сортировки? где он обсуждает решение, которое сводится к O(n log log n).. проверить его реализацию в C

Этот алгоритм полулинейной сортировки был представлен в статье в 1995 году:

А. Андерссон, Т. Хагеруп, С. Нильссон и Р. Раман. Сортировка по линейному времени? В материалах 27-го ежегодного симпозиума ACM по теории вычислений, стр. 427-436, 1995.