Самый быстрый вид массива с фиксированной длиной 6 int

Question

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

Answer 1

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

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

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

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

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
}

Answer 2

Вот реализация, использующая сортировка сетей :

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 - без ветвлениянет проблем с расхождением деформации и т. д.).

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

Answer 3

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

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];
}

Answer 4

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

Глядя на сборку, сгенерированную 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

Answer 5

Я наткнулся на этот вопрос от 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);

Answer 6

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

Тем не менее, также довольно легко улучшить решение для битовой сети; просто измените значение min / max / SWAP на

#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).

Answer 7

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

#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, и явно выводим общее подвыражение Это полностью исключает минимальные и максимальные макросы.

Answer 8

Никогда не оптимизируйте мин / макс без бенчмаркинга и просмотра фактической сборки, сгенерированной компилятором.Если я позволю 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);

Эта сортировка вставок быстрее, чем у Даниеля Штутцбаха, и особенно хороша на GPU или компьютере.с предикацией, потому что 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).

Answer 9

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

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

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

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

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

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

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

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

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

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

Answer 10

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

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

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