Найшвидший тип фіксованої довжини 6 int array

Відповідаючи на інше питання ( цей ), я натрапив на цікаву підзадачу. Який найшвидший спосіб сортування масиву з 6 ints?

Як питання дуже низький рівень:

  • ми не можемо припустити, що бібліотеки доступні (і сам виклик має свою вартість), тільки звичайний C
  • щоб уникнути спустошення конвеєра команд (який має дуже високу вартість), ми повинні, ймовірно, мінімізувати гілки, скачки і будь-який інший тип порушення потоку управління (наприклад, приховані за точками послідовності в > або || ).
  • приміщення обмежена, і мінімізація регістрів і використання пам'яті - проблема, в ідеалі на місці сортування, ймовірно, краще за все.

Дійсно, це питання - це свого роду гольф, метою якого є не мінімізація довжини джерела, а часу виконання. Я називаю це кодом "Zening", як використовується в назві книги Zen of Code optimization Michael Abrash і його сиквели .

Що стосується того, чому це цікаво, існує кілька шарів:

  • приклад простий і простий для розуміння і вимірювання, а не при використанні 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]);}  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
  • Вставка Сортування (Daniel Stutzbach): 142.12
  • Вставка Сортування Без розмітки: 125.47
  • Ранг: 102.26
  • Порядок ранжирування з регістрами: 58.03
  • Сортування мереж (Daniel Stutzbach): 111.68
  • Сортування мереж (Paul R): 66.36
  • Сортування мереж 12 з швидкою заміною: 58.86
  • Сортування мереж 12 переупорядочение свопів: 53.74
  • Сортувальні мережі 12 переупорядочение прості свопи: 31.54
  • Упорядкування сортувальна мережу зі швидкою заміною: 31.54
  • Упорядкування сортувальна мережу зі швидкою заміною V2: 33.63
  • Пов'язана сортування бульбашок (Paolo Bonzini): 48.85
  • Unrolled Insertion Sort (Paolo Bonzini): 75.30

Linux 64 біт, gcc 4.6.1 64 біт, Intel Core 2 Duo E8400, -O1

  • Прямий виклик функції бібліотеки qsort: 705.93
  • Наївна реалізація (сортування вставки): 135.60
  • Вставка Сортування (Daniel Stutzbach): 142.11
  • Вставка Сортування Без розмітки: 126.75
  • Ранг: 46.42
  • Порядок ранжирування з регістрами: 43.58
  • Сортування мереж (Daniel Stutzbach): 115.57
  • Сортування мереж (Paul R): 64.44
  • Сортування мереж 12 з швидкою заміною: 61.98
  • Сортування мереж 12 переупорядочение свопів: 54.67
  • Сортувальні мережі 12 переупорядочение прості свопи: 31.54
  • Упорядкування сортувальна мережу зі швидкою заміною: 31.24
  • Упорядкування сортувальна мережу зі швидкою заміною V2: 33.07
  • Введена сортування міхура (Paolo Bonzini): 45.79
  • Unrolled Insertion Sort (Паоло Бонзіні): 80.15

Я включив результати як -O1 і -O2, тому що несподівано для декількох програм O2 менше ефективніше, ніж O1. Цікаво, яка саме оптимізація має цей ефект?

Коментарі до пропонованих рішень

Вставка Сортування (Daniel Stutzbach)

Як і очікувалося, мінімізація гілок дійсно хороша ідея.

Сортування мереж (Daniel Stutzbach)

Краще, ніж сортування вставки. Я задавався питанням, чи не витікає головний ефект через відсутність зовнішнього контуру. Я спробував розгортати сортування вставки, щоб перевірити, і дійсно ми отримуємо приблизно однакові цифри (код тут ).

Сортування мереж (Paul R)

Краще досі. Фактичний код, який я використовував для тестування, тут . Поки не знаю, чому це майже в два рази швидше, ніж реалізація іншої сортувальної мережі. Передача параметрів? Швидкий макс?

Сортування мереж 12 SWAP зі швидкою заміною

Як запропонував Даніель Штуцбах, я об'єднав свою 12 сортувальну мережу для свопінгу з нерозподіленого швидкою заміною (код тут ). Це дійсно швидше, краще за все з невеликим відривом (приблизно 5%), як і слід було очікувати, використовуючи 1 менший своп.

Також цікаво зауважити, що розгалужений своп, мабуть, набагато (в 4 рази) менш ефективний, ніж простий, використовуючи if на архітектурі 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 і Rank Order, які стали послідовно в два рази швидше, ніж будь-яка інша альтернатива.

Сортування мереж 12 з переупорядочение свопом

Дивовижна ефективність пропозиції Rex Kerr з gcc 4.4.3 змусило мене задуматися: як могла б програма з 3-кратним споживанням пам'яті швидше, ніж з використанням безконтактної технології сортувальні мережі? Моя гіпотеза полягала в тому, що у неї було менше залежностей виду, що читається після запису, що дозволяє краще використовувати суперскалярний планувальник команд x86. Це дало мені уявлення: переупорядочить свопи, щоб звести до мінімуму кількість записів після залежностей записи. Простіше кажучи: коли ви робите SWAP(1, 2); SWAP(0, 2); SWAP(1, 2); SWAP(0, 2); , Вам потрібно дочекатися завершення першого свопу перед виконанням другого, тому що обидва доступу до загальної комірці пам'яті. Коли ви виконуєте SWAP(1, 2); SWAP(4, 5); SWAP(1, 2); SWAP(4, 5); , Процесор може виконувати обидва паралельно. Я спробував, і він працює так, як очікувалося, сортувальні мережі працюють на 10% швидше.

Сортування мереж 12 з простою заміною

Через рік після початкового повідомлення Steinar H. Gunderson припустив, що ми не повинні намагатися перехитрити компілятор і тримати код свопу простим. Це дійсно хороша ідея, оскільки отриманий код приблизно на 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 циклу. Я називаю це дивно швидко. Чи можливі інші поліпшення?

368
07 мая '10 в 10:24 2010-05-07 10:24 заданий kriss 07 травня '10 о 10:24 2010-05-07 10:24
@ 23 відповідей

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

Чи знаєте ви що-небудь про вхідних даних? Деякі алгоритми будуть працювати краще з деякими видами даних. Наприклад, сортування вставки краще виконується для відсортованих або майже відсортованих даних, тому це буде кращий вибір, якщо є ймовірність перевищення в порівнянні із середнім значенням майже відсортованих даних.

Опублікований вами алгоритм схожий на сортування вставки, але схоже, що ви мінімізували кількість свопів за рахунок більшої кількості порівнянь. Однак порівняння набагато дорожче, ніж свопи, оскільки гілки можуть привести до зупинки конвеєра команд.

Тут виконується реалізація сортування вставки:

 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 } 
152
07 мая '10 в 18:02 2010-05-07 18:02 відповідь дан Daniel Stutzbach 07 травня '10 о 18:02 2010-05-07 18:02

Тут реалізація з використанням сортувальних мереж :

 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 з них). Я залишаю це як вправу для читача.

border=0

Зверніть увагу, що ця реалізація легко піддається векторизації (наприклад, SIMD - більшість SIMD ISAs мають векторні інструкції min / max), а також до реалізацій графічного процесора (наприклад, CUDA - бездисковий відсутність проблем з деформацією warp і т.д.).

Див. Також: Швидка реалізація алгоритму для сортування дуже малого списку

59
07 мая '10 в 10:37 2010-05-07 10:37 відповідь дан Paul R 07 травня '10 о 10:37 2010-05-07 10:37

Так як це цілі числа, а порівняння - швидкі, чому б не обчислити порядок рангів кожного з них:

 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]; } 
40
08 мая '10 в 2:19 2010-05-08 02:19 відповідь дан Rex Kerr 08 травня '10 в 2:19 2010-05-08 2:19

Схоже, я потрапив на вечірку в кінці року, але тут ми йдемо ...

Дивлячись на збірку, що згенерувала gcc 4.5.2, я помітив, що навантаження і магазини виконуються для кожного свопу, що дійсно не потрібно. Було б краще завантажити 6 значень в регістри, впорядкувати їх і зберегти їх назад в пам'ять. Я наказав, щоб навантаження в магазинах були якомога ближче до того, щоб регістри були спочатку необхідні і використовувалися в останній раз. Я також використав SWAP-макрос Steinar H. Gunderson. Оновлення: я переключився на макрос SWAP Paolo Bonzini, який gcc конвертує в щось схоже на Gunderson, але 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 
35
24 авг. відповідь дан Kevin Stock 24 Серпня. 2011-08-24 18:29 '11 о 18:29 2011-08-24 18:29

Тест-код досить поганий; він переповнює вихідний масив (не читають люди тут попередження компілятора?), 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).

14
24 авг. відповідь дан Steinar H. Gunderson 24 Серпня. 2011-08-24 19:10 '11 о 19:10 2011-08-24 19:10

Я натрапив на це питання з Google кілька днів тому, тому що мені також довелося швидко впорядкувати масив фіксованої довжини з 6 цілих чисел. У моєму випадку, однак, мої цілі числа складають всього 8 біт (замість 32), і у мене немає строгого вимоги використовувати тільки C. Я думав, що буду ділитися своїми результатами так чи інакше, в разі, якщо вони можуть бути корисні комусь то ...

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