Odpowiadając na inne pytanie przepełnienia stosu ( to ) natknąłem się na interesujący pod-problem. Jaki jest najszybszy sposób na posortowanie tablicy 6 liczb całkowitych?
Ponieważ pytanie jest bardzo niskie:
- nie możemy zakładać, że biblioteki są dostępne (a samo połączenie ma swój koszt), tylko zwykłe C
- aby uniknąć opróżniania potoku instrukcji (co ma bardzo wysoki koszt), powinniśmy prawdopodobnie zminimalizować rozgałęzienia, skoki i wszelkie inne rodzaje przerywania przepływu sterowania (takie jak te ukryte za punktami sekwencji w
&&
lub||
). - Pokój jest ograniczony, a minimalizacja rejestrów i wykorzystanie pamięci to problem, najlepiej w miejscu sortowanie jest prawdopodobnie najlepsze.
Naprawdę to pytanie jest rodzajem golfa, w którym celem nie jest zminimalizowanie długości źródła, ale czas wykonania. Nazywam to kodem „Zeninga”, jak użyto w tytule książki Zen of Code optimization autorstwa Michaela Abrasha i jego kontynuacji .
Jeśli chodzi o to, dlaczego jest to interesujące, istnieje kilka warstw:
- przykład jest prosty i łatwy do zrozumienia i zmierzenia, nie wymaga dużej znajomości języka C.
- pokazuje efekty wyboru dobrego algorytmu dla problemu, ale także efekty kompilatora i podstawowego sprzętu.
Oto moja referencyjna (naiwna, niezoptymalizowana) implementacja i mój zestaw testowy.
#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);
}
Surowe wyniki
Ponieważ liczba wariantów staje się duża, zebrałem je wszystkie w pakiecie testowym, który można znaleźć tutaj . Rzeczywiste zastosowane testy są nieco mniej naiwne niż te pokazane powyżej, dzięki Kevin Stock. Możesz go skompilować i wykonać we własnym środowisku. Jestem bardzo zainteresowany zachowaniem różnych architektur docelowych / kompilatorów. (OK, podajcie odpowiedzi, daję +1 każdemu autorowi nowego zestawu wyników).
Dałem odpowiedź Danielowi Stutzbachowi (do gry w golfa) rok temu, ponieważ był on u źródła najszybszego rozwiązania w tym czasie (sieci sortowania).
Linux 64 bity, gcc 4.6.1 64 bity, Intel Core 2 Duo E8400, -O2
- Bezpośrednie wywołanie funkcji biblioteki qsort: 689,38
- Naiwna implementacja (sortowanie wstawek): 285,70
- Sortowanie wtrąceniowe (Daniel Stutzbach): 142.12
- Wstawianie sortowania rozwinięte: 125,47
- Ranga: 102,26
- Ranga Zamówienie z rejestrami: 58,03
- Sortowanie sieci (Daniel Stutzbach): 111,68
- Sorting Networks (Paul R): 66.36
- Sortowanie sieci 12 z funkcją Fast Swap: 58,86
- Sorting Networks 12 zmieniona kolejność Zamień: 53,74
- Sorting Networks 12 uporządkowana prosta zamiana: 31.54
- Zmieniona sieć sortowania z szybką wymianą: 31,54
- Zmieniona sieć sortowania z szybką wymianą V2: 33.63
- Sortowanie bąbelkowe (Paolo Bonzini): 48,85
- Unrolled Insertion Sort (Paolo Bonzini): 75.30
Linux 64 bity, gcc 4.6.1 64 bity, Intel Core 2 Duo E8400, -O1
- Bezpośrednie wywołanie funkcji bibliotecznej qsort: 705.93
- Naiwna implementacja (sortowanie wstawek): 135,60
- Sortowanie wtrąceniowe (Daniel Stutzbach): 142.11
- Wstawianie Sortowanie rozwinięte: 126,75
- Porządek rangi: 46,42
- Porządek z rejestrami: 43,58
- Sortowanie sieci (Daniel Stutzbach): 115,57
- Sortowanie sieci (Paul R): 64,44
- Sortowanie sieci 12 z funkcją Fast Swap: 61,98
- Sorting Networks 12 zmieniona kolejność Zamień: 54,67
- Sorting Networks 12 uporządkowana prosta zamiana: 31.54
- Zmieniona sieć sortowania z szybką wymianą: 31,24
- Zmiana kolejności sortowania w / fast swap V2: 33.07
- Sortowanie bąbelkowe (Paolo Bonzini): 45,79
- Unrolled Insertion Sort (Paolo Bonzini): 80,15
Dołączyłem zarówno wyniki -O1, jak i -O2, ponieważ zaskakująco w przypadku kilku programów O2 jest mniej wydajne niż O1. Zastanawiam się, jaką konkretną optymalizację ma ten efekt?
Komentarze do proponowanych rozwiązań
Sortowanie wtrąceniowe (Daniel Stutzbach)
Zgodnie z oczekiwaniami minimalizacja oddziałów jest rzeczywiście dobrym pomysłem.
Sorting Networks (Daniel Stutzbach)
Lepsze niż sortowanie przez wstawianie. Zastanawiałem się, czy głównym efektem nie było uniknięcie pętli zewnętrznej. Spróbowałem, sprawdzając niepoprawne wstawianie, i rzeczywiście otrzymujemy mniej więcej te same liczby (kod jest tutaj ).
Sortowanie sieci (Paul R)
Najlepsze do tej pory. Rzeczywisty kod, którego użyłem do testowania, jest tutaj . Nie wiem jeszcze, dlaczego jest prawie dwa razy szybszy niż inna implementacja sieci sortującej. Przekazywanie parametrów? Szybki maks?
Sortowanie sieci 12 SWAP z funkcją Fast Swap
Jak zasugerował Daniel Stutzbach, połączyłem jego sieć sortowania 12 swapów z bezgałęziową szybką zamianą (kod jest tutaj ). Jest rzeczywiście szybszy, najlepszy do tej pory z niewielkim marginesem (około 5%), jak można się spodziewać przy 1 zamianie mniejszej.
Interesujące jest również zauważenie, że zamiana bez rozgałęzień wydaje się znacznie (4 razy) mniej wydajna niż prosta przy użyciu architektury PPC.
Calling Library qsort
Aby podać kolejny punkt odniesienia, próbowałem również, jak sugerowano, po prostu wywołać bibliotekę qsort (kod jest tutaj ). Zgodnie z oczekiwaniami jest znacznie wolniejszy: 10 do 30 razy wolniejszy ... jak stało się to oczywiste dzięki nowemu pakietowi testowemu, głównym problemem wydaje się być początkowe obciążenie biblioteki po pierwszym wywołaniu i nie jest tak źle porównywane z innymi wersja. Jest tylko 3 do 20 razy wolniejszy na moim Linuksie. W niektórych architekturach wykorzystywanych do testów przez inne wydaje się to nawet szybsze (jestem naprawdę zaskoczony, ponieważ biblioteka qsort używa bardziej złożonego API).
Kolejność rang
Rex Kerr zaproponował inną całkowicie inną metodę: dla każdego elementu tablicy oblicz bezpośrednio jego ostateczną pozycję. Jest to wydajne, ponieważ obliczanie kolejności rang nie wymaga rozgałęzienia. Wadą tej metody jest to, że zajmuje ona trzy razy więcej pamięci niż tablica (jedna kopia tablicy i zmiennych do przechowywania zamówień rang). Wyniki wydajności są bardzo zaskakujące (i interesujące). W mojej referencyjnej architekturze z 32-bitowym systemem operacyjnym i Intel Core2 Quad E8300 liczba cykli była nieco poniżej 1000 (jak sortowanie sieci z rozgałęziającą wymianą). Ale po skompilowaniu i uruchomieniu na moim 64-bitowym pudełku (Intel Core2 Duo) działało znacznie lepiej: stało się jak dotąd najszybsze. W końcu znalazłem prawdziwy powód. Mój 32-bitowy box używa gcc 4.4.1, a mój 64bits box gcc 4.4.
aktualizacja :
Jak pokazują powyższe dane, efekt ten został jeszcze wzmocniony przez późniejsze wersje gcc, a Kolejność Ranków stała się dwa razy szybsza niż jakakolwiek inna opcja.
Sorting Networks 12 z uporządkowaną zamianą
Niesamowita wydajność propozycji Rex Kerr z gcc 4.4.3 sprawiła, że zastanawiałem się: jak program z 3-krotnie większym zużyciem pamięci może być szybszy niż bezgałęziowe sieci sortujące? Moja hipoteza była taka, że miał mniej zależności w rodzaju odczytu po zapisie, co pozwala na lepsze wykorzystanie superskalarnego harmonogramu instrukcji x86. To dało mi pomysł: zmiana kolejności zamian w celu zminimalizowania zależności odczytu po zapisie. Mówiąc prościej: kiedy musisz SWAP(1, 2); SWAP(0, 2);
poczekać na zakończenie pierwszej wymiany, zanim wykonasz drugą, ponieważ oba mają dostęp do wspólnej komórki pamięci. Gdy to zrobisz, SWAP(1, 2); SWAP(4, 5);
procesor może wykonywać oba równolegle. Wypróbowałem to i działa zgodnie z oczekiwaniami, sieci sortujące działają około 10% szybciej.
Sortowanie sieci 12 za pomocą prostej wymiany
Rok po tym, jak oryginalny post Steinar H. Gunderson zasugerował, abyśmy nie próbowali przechytrzyć kompilatora i utrzymać kod wymiany w prosty sposób. To naprawdę dobry pomysł, ponieważ wynikowy kod jest o około 40% szybszy! Zaproponował także zamianę zoptymalizowaną ręcznie przy użyciu wbudowanego kodu zestawu x86, który wciąż może oszczędzić trochę więcej cykli. Najbardziej zaskakujące (jak mówi tomy o psychologii programisty) jest to, że rok temu nikt z nich nie próbował tej wersji wymiany. Kod, którego użyłem do testowania, jest tutaj . Inni sugerowali inne sposoby napisania szybkiej zamiany w C, ale daje ona takie same wyniki jak prosta z przyzwoitym kompilatorem.
Kod „najlepszy” jest teraz następujący:
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
}
Jeśli uważamy, że nasz zestaw testowy (i tak, jest dość słaby, jego zaletą jest to, że jest krótki, prosty i łatwy do zrozumienia, co mierzymy), średnia liczba cykli wynikowego kodu dla jednego rodzaju jest mniejsza niż 40 cykli ( Wykonanych jest 6 testów). Dzięki temu każda zamiana trwa średnio 4 cykle. Nazywam to niezwykle szybko. Czy są możliwe inne ulepszenia?
x-y
ix+y
nie spowoduje niedomiaru lub nadmiaru?__asm__ volatile (".byte 0x0f, 0x31; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
że rdtsc umieszcza odpowiedź w EDX: EAX, podczas gdy GCC oczekuje jej w jednym 64-bitowym rejestrze. Możesz zobaczyć błąd kompilując w -O3. Zobacz także poniżej mój komentarz do Paula R na temat szybszego SWAP.CMP EAX, EBX; SBB EAX, EAX
0 lub 0xFFFFFFFF wEAX
zależności od tego, czyEAX
jest odpowiednio większy czy mniejszyEBX
.SBB
to „odejmij z pożyczeniem”, odpowiednikiemADC
(„dodaj z przeniesieniem”); bit stanu, o którym mówisz, to bit przeniesienia. Z drugiej strony, pamiętam toADC
iSBB
miałem straszne opóźnienia i przepustowość na Pentium 4 vs.ADD
iSUB
, i nadal były dwa razy wolniejsze na Core CPU. Od 80386 dostępne są również instrukcjeSETcc
warunkowego przechowywania iCMOVcc
warunkowego przenoszenia, ale są one również powolne.Odpowiedzi:
Dla każdej optymalizacji zawsze najlepiej jest testować, testować, testować. Spróbowałbym przynajmniej sortować sieci i sortować przez wstawianie. Gdybym obstawiał, postawiłbym pieniądze na sortowanie w oparciu o wcześniejsze doświadczenia.
Czy wiesz coś o danych wejściowych? Niektóre algorytmy działają lepiej w przypadku niektórych rodzajów danych. Na przykład sortowanie wstawiane działa lepiej na posortowanych lub prawie posortowanych danych, więc będzie lepszym wyborem, jeśli istnieje ponadprzeciętna szansa na prawie posortowane dane.
Algorytm, który opublikowałeś, jest podobny do rodzaju wstawiania, ale wygląda na to, że zminimalizowałeś liczbę zamian kosztem większej liczby porównań. Porównania są jednak znacznie droższe niż swapy, ponieważ gałęzie mogą spowodować zatrzymanie potoku instrukcji.
Oto implementacja sortowania według wstawiania:
Oto jak zbuduję sieć sortującą. Najpierw użyj tej witryny do wygenerowania minimalnego zestawu makr SWAP dla sieci o odpowiedniej długości. Podsumowanie w funkcji daje mi:
źródło
n < SMALL_CONSTANT
.Oto implementacja wykorzystująca sieci sortujące :
Naprawdę potrzebujesz bardzo wydajnych gałęzi
min
imax
implementacji, ponieważ do tego właśnie sprowadza się ten kod - sekwencjamin
imax
operacje (w sumie po 13). Zostawiam to jako ćwiczenie dla czytelnika.Zauważ, że ta implementacja z łatwością nadaje się do wektoryzacji (np. SIMD - większość SIMA ISA ma instrukcje min / max wektor), a także do implementacji GPU (np. CUDA - bez rozgałęzień nie ma problemów z rozbieżnością wypaczenia itp.).
Zobacz także: Szybka implementacja algorytmu do sortowania bardzo małej listy
źródło
Sort3
byłoby szybsze (zresztą w większości architektur), gdybyś zauważył, że(a+b+c)-(min+max)
jest to liczba centralna.#define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }
. Tutaj nie używam?: Dla d [y], ponieważ daje nieco gorszą wydajność, ale jest prawie w hałasie.Ponieważ są to liczby całkowite, a porównania są szybkie, dlaczego nie obliczyć bezpośrednio kolejności rang dla każdego:
źródło
0+1+2+3+4+5=15
Ponieważ brakuje jednego z nich, 15 minus suma reszty daje brakującyWygląda na to, że przybyłem na imprezę rok później, ale zaczynamy ...
Patrząc na zestaw wygenerowany przez gcc 4.5.2, zauważyłem, że ładunki i magazyny są wykonywane dla każdej wymiany, która tak naprawdę nie jest potrzebna. Lepiej byłoby załadować 6 wartości do rejestrów, posortować je i zapisać z powrotem w pamięci. Zamówiłem ładunki w sklepach tak blisko, jak to możliwe, tam rejestry są najpierw potrzebne i ostatnio używane. Użyłem również makra SWAP Steinina H. Gundersona. Aktualizacja: przełączyłem się na makro SWAP Paolo Bonziniego, które gcc konwertuje na coś podobnego do Gundersona, ale gcc jest w stanie lepiej zamówić instrukcje, ponieważ nie są one podane jako jawny zestaw.
Użyłem tej samej kolejności wymiany, co uporządkowana sieć wymiany, podana jako najskuteczniejsza, chociaż może być lepsza kolejność. Jeśli znajdę więcej czasu, wygeneruję i przetestuję kilka permutacji.
Zmieniłem kod testowy, aby wziąć pod uwagę ponad 4000 tablic i pokazać średnią liczbę cykli potrzebnych do posortowania każdego z nich. Na i5-650 otrzymuję ~ 34,1 cykli / sortowania (przy użyciu -O3), w porównaniu do oryginalnej uporządkowanej sieci sortującej, uzyskując ~ 65,3 cykli / sortowania (przy użyciu -O1, bitów -O2 i -O3).
Zmieniłem zmodyfikowany pakiet testowy, aby raportował także zegary według sortowania i przeprowadziłem więcej testów (zaktualizowano również funkcję cmp, aby obsługiwała również przepełnienie liczb całkowitych), oto wyniki niektórych różnych architektur. Próbowałem przetestować na procesorze AMD, ale rdtsc nie jest niezawodny na X6 1100T, który mam dostępny.
źródło
-O3
optymalizacja nie przyniesie efektu przeciwnego do zamierzonego.#define SWAP(x,y) { int oldx = x; x = x < y ? x : y; y ^= oldx ^ x; }
.Kilka dni temu natknąłem się na to pytanie od Google, ponieważ musiałem również szybko posortować tablicę o stałej liczbie 6 liczb całkowitych. Jednak w moim przypadku moje liczby całkowite to tylko 8 bitów (zamiast 32) i nie mam ścisłego wymogu używania tylko C. Myślałem, że i tak podzielę się swoimi odkryciami, na wypadek, gdyby były pomocne dla kogoś ...
Zaimplementowałem wariant sortowania sieciowego w zestawie, który używa SSE do wektoryzacji operacji porównywania i zamiany, w możliwym zakresie. Całkowite posortowanie tablicy zajmuje sześć „przebiegów”. Użyłem nowatorskiego mechanizmu do bezpośredniej konwersji wyników PCMPGTB (porównanie wektoryzowane) do parametrów losowych dla PSHUFB (zamiana wektoryzowana), używając tylko PADDB (dodawanie wektoryzowane), aw niektórych przypadkach także instrukcji PAND (bitowe AND).
Takie podejście miało również efekt uboczny polegający na uzyskaniu prawdziwie bezgałęziowej funkcji. Nie ma żadnych instrukcji skoku.
Wydaje się, że ta implementacja jest o około 38% szybsza niż implementacja, która jest obecnie oznaczona jako najszybsza opcja w pytaniu („Sorting Networks 12 with Simple Swap”). Zmodyfikowałem tę implementację, aby
char
podczas testów używała elementów tablicy, aby porównanie było uczciwe.Należy zauważyć, że takie podejście można zastosować do dowolnej wielkości tablicy do 16 elementów. Oczekuję, że przewaga prędkości względnej nad alternatywami wzrośnie dla większych tablic.
Kod jest napisany w MASM dla procesorów x86_64 z SSSE3. Funkcja korzysta z „nowej” konwencji wywoływania Windows x64. Oto jest ...
Możesz skompilować to do obiektu wykonywalnego i połączyć z projektem C. Aby uzyskać instrukcje, jak to zrobić w programie Visual Studio, możesz przeczytać ten artykuł . Możesz użyć następującego prototypu C, aby wywołać funkcję z kodu C:
źródło
pxor / pinsrd xmm4, mem, 0
prostu użyjmovd
!Kod testowy jest dość zły; przepełnia początkową tablicę (czy ludzie tutaj nie czytają ostrzeżeń kompilatora?), printf drukuje niewłaściwe elementy, używa .byte dla rdtsc bez powodu, jest tylko jeden bieg (!), nic nie sprawdza, czy wyniki końcowe są właściwie poprawne (więc bardzo łatwo „zoptymalizować” coś, co jest subtelnie złe), zawarte testy są bardzo szczątkowe (brak liczb ujemnych?) i nic nie stoi na przeszkodzie, aby kompilator po prostu odrzucił całą funkcję jako martwy kod.
To powiedziawszy, dość łatwo jest ulepszyć rozwiązanie sieci bitonicznej; po prostu zmień wartości min / max / SWAP na
i wychodzi mi to o 65% szybciej (Debian gcc 4.4.5 z -O2, amd64, Core i7).
źródło
Chociaż naprawdę podoba mi się makro wymiany:
Widzę ulepszenie (które mógłby zrobić dobry kompilator):
Przyjmujemy do wiadomości, w jaki sposób działają min i max, i jawnie wyciągamy wspólne podwyrażenie. Eliminuje to całkowicie makra min i maks.
źródło
d[x]
zamiast tegox
(dla tego samegoy
), id[y] < d[x]
dla nierówności tutaj (tak, różni się od kodu min / max).Nigdy nie optymalizuj wartości min./maks. Bez testów porównawczych i analizy rzeczywistego zestawu wygenerowanego przez kompilator. Jeśli pozwolę GCC zoptymalizować min z instrukcjami ruchu warunkowego, otrzymam 33% przyspieszenie:
(280 vs 420 cykli w kodzie testowym). Robienie maks z?: Jest mniej więcej takie samo, prawie zagubione w hałasie, ale powyższe jest nieco szybsze. Ten SWAP jest szybszy zarówno w GCC, jak i Clang.
Kompilatory wykonują również wyjątkową pracę przy alokacji rejestrów i analizie aliasów, skutecznie przenosząc d [x] do zmiennych lokalnych z góry i kopiując tylko z powrotem do pamięci na końcu. W rzeczywistości robią to nawet lepiej niż gdybyś pracował całkowicie ze zmiennymi lokalnymi (np
d0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5]
). Piszę to, ponieważ zakładasz silną optymalizację, a jednak próbujesz przechytrzyć kompilator na min / max. :)Nawiasem mówiąc, próbowałem Clang i GCC. Robią tę samą optymalizację, ale z powodu różnic w planowaniu obie mają pewne różnice w wynikach, nie mogą powiedzieć, która jest szybsza lub wolniejsza. GCC działa szybciej w sieciach sortujących, Clang w kwadratowych sortowaniach.
Dla kompletności możliwe są również rozwijane sortowanie bąbelkowe i sortowanie wstawek. Oto sortowanie bąbelkowe:
a oto sortowanie wstawek:
Ten rodzaj wstawiania jest szybszy niż Daniela Stutzbacha i jest szczególnie dobry na GPU lub komputerze z predykcją, ponieważ ITER można wykonać tylko za pomocą 3 instrukcji (w porównaniu do 4 dla SWAP). Na przykład tutaj jest
t = d[2]; ITER(1); ITER(0);
linia w zespole ARM:W przypadku sześciu elementów sortowanie wstawiane jest konkurencyjne w stosunku do sieci sortującej (12 swapów vs. 15 iteracji równoważy 4 instrukcje / swap vs. 3 instrukcje / iteracja); rodzaj bąbelków jest oczywiście wolniejszy. Ale nie będzie to prawdą, gdy rozmiar wzrośnie, ponieważ sortowanie przez wstawianie to O (n ^ 2), podczas gdy sieci sortujące to O (n log n).
źródło
Przeniesiłem pakiet testowy na maszynę o architekturze PPC, której nie mogę zidentyfikować (nie musiałem dotykać kodu, po prostu zwiększyć iteracje testu, użyć 8 przypadków testowych, aby uniknąć zanieczyszczenia wyników modami i zastąpić rdtsc specyficzne dla x86):
Bezpośrednie wywołanie funkcji bibliotecznej qsort : 101
Naiwna implementacja (sortowanie wstawek) : 299
Sortowanie wtrąceniowe (Daniel Stutzbach) : 108
Wstawianie Sortuj Nie rozwinięte : 51
Sorting Networks (Daniel Stutzbach) : 26
Sortowanie sieci (Paul R) : 85
Sortowanie sieci 12 z funkcją Fast Swap : 117
Sorting Networks 12 ponownie uporządkowany Zamień : 116
Ranga : 56
źródło
subfc r5,r4,r3; subfe r6,r6,r6; andc r6,r5,r6; add r4,r6,r4; subf r3,r6,r3
. r3 / r4 to wejścia, r5 / r6 to rejestry scratch, na wyjściu r3 otrzymuje min, a r4 maks. Powinien być odpowiednio zaplanowany ręcznie. Znalazłem go z superoptymalizatorem GNU, zaczynając od 4-instrukcji sekwencji min i max i ręcznie szukając dwóch, które można by połączyć. W przypadku podpisanych danych wejściowych można oczywiście dodać 0x80000000 do wszystkich elementów na początku i odjąć go ponownie na końcu, a następnie działać tak, jakby były niepodpisane.Zamiana XOR może być przydatna w funkcjach wymiany.
If może powodować zbyt duże rozbieżności w twoim kodzie, ale jeśli masz gwarancję, że wszystkie twoje ints są unikalne, może to być przydatne.
źródło
x
iy
punkt w tej samej lokalizacji.Nie mogę się doczekać, aby spróbować tego i wyciągnąć wnioski z tych przykładów, ale najpierw trochę czasu z mojej 1,5 GHz PPC Powerbook G4 z 1 GB pamięci RAM DDR. (Pożyczałem podobny zegar podobny do rdtsc dla PPC z http://www.mcs.anl.gov/~kazutomo/rdtsc.html dla timingu.) Uruchomiłem program kilka razy i wyniki absolutne były różne, ale konsekwentnie najszybszym testem był „Wstawianie sortowania (Daniel Stutzbach)”, a „Wstawianie sortowania rozwinięte” blisko sekundę.
Oto ostatni zestaw czasów:
źródło
Oto mój wkład w ten wątek: zoptymalizowany 1, 4 odstępowy shellsort dla 6-elementowego wektora int (valp) zawierającego unikalne wartości.
Na moim laptopie HP dv7-3010so z dwurdzeniowym Athlonem M300 @ 2 Ghz (pamięć DDR2) działa on w 165 cyklach zegara. Jest to średnia obliczona na podstawie czasu każdej unikalnej sekwencji (w sumie 6! / 720). Kompilowany do Win32 za pomocą OpenWatcom 1.8. Pętla jest zasadniczo rodzajem wstawiania i ma 16 instrukcji / 37 bajtów.
Nie mam 64-bitowego środowiska do kompilacji.
źródło
Jeśli rodzaj wstawiania jest tutaj dość konkurencyjny, poleciłbym wypróbowanie shellsorta. Obawiam się, że 6 elementów to chyba po prostu za mało, aby można je było zaliczyć do najlepszych, ale warto spróbować.
Przykładowy kod, nieprzetestowany, cofnięty itp. Chcesz dostroić sekwencję inc = 4 i inc - = 3, aby znaleźć optymalną wartość (spróbuj na przykład inc = 2, inc - = 1).
Nie sądzę, że to wygra, ale jeśli ktoś opublikuje pytanie dotyczące sortowania 10 elementów, kto wie ...
Według Wikipedii można to nawet łączyć z sieciami sortującymi: Pratt, V (1979). Sortowanie i sortowanie sieci (wybitne rozprawy z informatyki). Girlanda. ISBN 0-824-04406-1
źródło
Wiem, że się spóźniłem, ale byłem zainteresowany eksperymentowaniem z różnymi rozwiązaniami. Najpierw wyczyściłem tę pastę, zmusiłem ją do kompilacji i umieściłem w repozytorium. Zachowałem niektóre niepożądane rozwiązania jako ślepe zaułki, aby inni nie próbowali tego. Wśród nich było moje pierwsze rozwiązanie, które próbowało upewnić się, że x1> x2 zostało obliczone jeden raz. Po optymalizacji nie jest szybszy niż inne proste wersje.
Dodałem zapętloną wersję sortowania według kolejności rang, ponieważ moje własne zastosowanie w tym badaniu służy do sortowania 2-8 pozycji, więc ponieważ istnieje zmienna liczba argumentów, konieczna jest pętla. Dlatego też zignorowałem sieciowe rozwiązania sortujące.
Kod testowy nie testował poprawności obsługi duplikatów, więc mimo że wszystkie istniejące rozwiązania były poprawne, dodałem specjalny kod do kodu testowego, aby upewnić się, że duplikaty były obsługiwane poprawnie.
Następnie napisałem rodzaj wstawiania, który jest całkowicie w rejestrach AVX. Na mojej maszynie jest on o 25% szybszy niż inne rodzaje wstawiania, ale o 100% wolniejszy niż kolejność w rankingu. Zrobiłem to wyłącznie dla eksperymentu i nie spodziewałem się, że będzie to lepsze ze względu na rozgałęzienie w rodzaju wstawiania.
Następnie napisałem sortowanie według kolejności według AVX. Odpowiada to szybkości innych rozwiązań szeregowania, ale nie jest szybsze. Problem polega na tym, że mogę obliczyć indeksy tylko za pomocą AVX, a następnie muszę utworzyć tabelę indeksów. Wynika to z faktu, że obliczenia są oparte na miejscu docelowym, a nie na źródle. Zobacz Konwertowanie z indeksów źródłowych na indeksy docelowe
Repozytorium można znaleźć tutaj: https://github.com/eyepatchParrot/sort6/
źródło
vmovmskps
na wektorach całkowitych (z rzutowaniem, aby zadowolić intrinsics), unikając potrzeby przesunięcia wyniku bitscan (ffs
) w prawo .cmpgt
wyniku, odejmując go, zamiast maskowaćset1(1)
. np.index = _mm256_sub_epi32(index, gt)
robiindex -= -1 or 0;
eq = _mm256_insert_epi32(eq, 0, I)
nie jest skutecznym sposobem zerowania elementu, jeśli kompiluje się zgodnie z zapisami (szczególnie dla elementów spoza niskiej 4, ponieważvpinsrd
jest dostępny tylko z miejscem docelowym XMM; należy emulować wskaźniki wyższe niż 3). Zamiast tego_mm256_blend_epi32
(vpblendd
) z zerowanym wektorem.vpblendd
jest instrukcją pojedynczego działania, która działa na dowolnym porcie, a tasowanie wymaga portu 5 na procesorach Intel. ( agner.org/optimize ).rot
wektorów z różnymi losowymi zmianami z tego samego źródła lub przynajmniej równolegle uruchomić 2 łańcuchy dep równolegle, których używasz na przemian, zamiast jednego łańcucha dep poprzez tasowanie krzyżujące linie (opóźnienie 3 cykli). To zwiększy ILP w ramach jednego rodzaju. 2 łańcuchy dep ograniczają liczbę stałych wektorowych do rozsądnej liczby, tylko 2: 1 dla jednego obrotu i jeden dla 2 kroków obrotu łącznie.To pytanie staje się dość stare, ale w rzeczywistości musiałem rozwiązać ten sam problem w dzisiejszych czasach: szybkie agory, aby posortować małe tablice. Pomyślałem, że dobrym pomysłem byłoby podzielenie się moją wiedzą. Kiedy zacząłem od korzystania z sieci sortujących, w końcu udało mi się znaleźć inne algorytmy, dla których łączna liczba porównań przeprowadzonych w celu posortowania każdej permutacji 6 wartości była mniejsza niż w przypadku sieci sortujących i mniejsza niż w przypadku sortowania wstawianego. Nie policzyłem liczby swapów; Spodziewałbym się, że będzie to mniej więcej równoważne (czasem może nieco wyższe).
Algorytm
sort6
wykorzystuje algorytm,sort4
który korzysta z algorytmusort3
. Oto implementacja w lekkiej formie C ++ (oryginał zawiera dużo szablonów, dzięki czemu może współpracować z dowolnym iteratorem o swobodnym dostępie i dowolną odpowiednią funkcją porównywania).Sortowanie 3 wartości
Poniższy algorytm jest rozwiniętym rodzajem wstawiania. Kiedy trzeba wykonać dwie zamiany (6 przypisań), zamiast tego używa 4 przypisań:
Wygląda to nieco skomplikowane, ponieważ sortowanie ma więcej lub mniej jedną gałąź dla każdej możliwej permutacji tablicy, przy użyciu 2 ~ 3 porównań i co najwyżej 4 przypisań do posortowania trzech wartości.
Sortowanie 4 wartości
To wywołanie
sort3
wykonuje następnie przewijanie sortowania z ostatnim elementem tablicy:Algorytm wykonuje od 3 do 6 porównań i maksymalnie 5 swapów. Łatwo jest rozwinąć sortowanie wstawiane, ale dla ostatniego sortowania użyjemy innego algorytmu ...
Sortowanie 6 wartości
Ten wykorzystuje rozwiniętą wersję tego, co nazwałem sortowaniem z podwójnym wstawianiem . Nazwa nie jest świetna, ale jest dość opisowa, oto jak działa:
Po zamianie pierwszy element jest zawsze mniejszy niż ostatni, co oznacza, że podczas wstawiania ich do posortowanej sekwencji nie będzie więcej niż N porównań, aby wstawić dwa elementy w najgorszym przypadku: na przykład, jeśli pierwszy element został wstawiony w 3. pozycji, a ostatniego nie można wstawić niżej niż 4. pozycji.
Moje testy na każdej permutacji 6 wartości pokazują, że algorytmy te zawsze wykonują od 6 do 13 porównań. Nie obliczyłem liczby wykonanych swapów, ale nie spodziewam się, że w najgorszym przypadku będzie wyższa niż 11.
Mam nadzieję, że to pomoże, nawet jeśli to pytanie może już nie stanowić rzeczywistego problemu :)
EDYCJA: po umieszczeniu go w dostarczonym teście porównawczym jest wyraźnie wolniejsza niż większość interesujących alternatyw. Zwykle działa nieco lepiej niż rozwinięty rodzaj wstawiania, ale to wszystko. Zasadniczo nie jest to najlepszy rodzaj liczb całkowitych, ale może być interesujący dla typów z kosztowną operacją porównywania.
źródło
operator<
do porównania. Oprócz obiektywnej liczby porównań i swapów, odpowiednio dostosowałem też swoje algorytmy; to rozwiązanie było najszybsze ogólne, ale rzeczywiście brakowało mi rozwiązania @ RexKerr. Spróbuję :)-O3
. Wydaje mi się, że wtedy zastosuję inną strategię dla mojej biblioteki sortowania: dostarczając trzy rodzaje algorytmów, które mają albo małą liczbę porównań, małą liczbę zamian lub potencjalnie najlepszą wydajność. Przynajmniej to, co się stanie, będzie czytelne dla czytelnika. Dzięki za wgląd :)Uważam, że twoje pytanie składa się z dwóch części.
Nie martwiłbym się zbytnio opróżnianiem rurociągów (przy założeniu, że x86): przewidywanie gałęzi przeszło długą drogę. Martwi mnie to, czy kod i dane mieszczą się w jednym wierszu pamięci podręcznej (może dwa dla kodu). Tam opóźnienia pobierania są odświeżająco niskie, co zrekompensuje każde przeciągnięcie. Oznacza to również, że twoja wewnętrzna pętla będzie miała około dziesięciu instrukcji, co jest dokładnie tam, gdzie powinna być (w moim algorytmie sortowania są dwie różne wewnętrzne pętle, są to odpowiednio 10 instrukcji / 22 bajtów i 9/22 długości). Zakładając, że kod nie zawiera żadnych div, możesz być pewien, że będzie oślepiająco szybki.
źródło
Wiem, że to stare pytanie.
Ale właśnie napisałem inny rodzaj rozwiązania, którym chcę się podzielić.
Używając tylko zagnieżdżonego MIN MAX,
Nie jest szybki, ponieważ wykorzystuje 114 każdego z nich,
może zmniejszyć go do 75 po prostu tak -> pastebin
Ale to już nie jest wyłącznie min. Maks.
To, co może działać, to wykonywanie wartości min / max na wielu liczbach całkowitych za pomocą AVX
Referencje PMINSW
EDYCJA:
Rozwiązanie kolejności rangi zainspirowane przez Rexa Kerra, znacznie szybsze niż bałagan powyżej
źródło
int16_t
). Ale funkcja C twierdzi, że sortuje tablicęint
(która jest 32-bitowa we wszystkich implementacjach C obsługujących tęasm
składnię). Czy przetestowałeś go tylko z małymi dodatnimi liczbami całkowitymi, które mają tylko 0 w swoich wysokich połówkach? To zadziała ...int
Potrzebujesz SSE4.1pmin/maxsd
(d = dword). felixcloutier.com/x86/pminsd:pminsq lubpminusd
foruint32_t
.Okazało się, że przynajmniej w moim systemie, funkcje
sort6_iterator()
isort6_iterator_local()
zdefiniowano poniżej zarówno RAN co najmniej tak szybko, a często znacznie szybciej, niż wymienione powyżej aktualnego rekordzisty:W
std::vector
kodzie czasowym przekazałem tę funkcję jako iterator.Podejrzewam (na podstawie komentarzy takich jak ten i gdzie indziej), że użycie iteratorów daje g ++ pewne zapewnienia o tym, co może i nie może się stać z pamięcią, do której odwołuje się iterator, czego inaczej by nie miał i to właśnie te zapewnienia pozwalają g ++ na lepiej zoptymalizować kod sortujący (np. w przypadku wskaźników kompilator nie może być pewien, że wszystkie wskaźniki wskazują różne lokalizacje pamięci). Jeśli dobrze pamiętam, jest to również jeden z powodów, dla których tak wiele algorytmów STL, takich jak
std::sort()
, ma tak nieprzyzwoicie dobrą wydajność.Ponadto
sort6_iterator()
jest kilka razy (raz, w zależności od kontekstu, w którym funkcja nazywa) konsekwentnie przewyższyła o następującej funkcji sortowania, który kopiuje dane do zmiennych lokalnych przed ich sortowania. 1 Zwróć uwagę, że ponieważ zdefiniowano tylko 6 zmiennych lokalnych, jeśli te zmienne lokalne są prymitywami, prawdopodobnie nigdy nie są faktycznie przechowywane w pamięci RAM, a zamiast tego są przechowywane w rejestrach procesora aż do końca wywołania funkcji, co pomaga w sortowaniu działa szybko. (Pomaga to również kompilatorowi wiedzieć, że różne zmienne lokalne mają różne miejsca w pamięci).Zauważmy, że definiowanie
SWAP()
następująco kilka razy wyniki w nieco lepszej wydajności, choć przez większość czasu to skutkuje nieco gorsze wydajności lub znikomym różnicy w wydajności.Jeśli potrzebujesz tylko algorytmu sortowania, który dla prymitywnych typów danych, gcc -O3 jest niezmiennie dobry w optymalizacji, bez względu na kontekst, w którym wywołanie funkcji sortowania pojawia się w 1 , to w zależności od tego, jak przekazujesz dane wejściowe, spróbuj jednego z dwóch poniższych algorytmy:
Lub jeśli chcesz przekazać zmienne przez referencję, użyj tego (poniższa funkcja różni się od powyższej w pierwszych 5 wierszach):
Powodem użycia
register
słowa kluczowego jest to, że jest to jeden z niewielu przypadków, w których wiesz, że chcesz te wartości w rejestrach. Bezregister
tego kompilator przez większość czasu to zrozumie, ale czasem tak nie jest. Użycieregister
słowa kluczowego pomaga rozwiązać ten problem. Zwykle jednak nie używajregister
słowa kluczowego, ponieważ bardziej prawdopodobne jest spowolnienie kodu niż przyspieszenie.Zwróć też uwagę na użycie szablonów. Odbywa się to celowo, ponieważ nawet w przypadku
inline
słowa kluczowego funkcje szablonów są generalnie znacznie bardziej agresywnie zoptymalizowane przez gcc niż waniliowe funkcje C (ma to związek z gcc, który musi radzić sobie ze wskaźnikami funkcji dla funkcji waniliowych C, ale nie z funkcjami szablonu).źródło
Spróbuj posortować sortowanie „sorted sorted list”. :) Użyj dwóch tablic. Najszybszy dla małych i dużych tablic.
Jeśli kończysz, sprawdzasz tylko, gdzie wstawić. Inne większe wartości, których nie potrzebujesz porównywać (cmp = ab> 0).
W przypadku 4 cyfr można użyć systemu 4-5 cmp (~ 4,6) lub 3-6 cmp (~ 4,9). Sortowanie bąbelkowe użyj 6 cmp (6). Dużo cmp dla wolniejszego kodu dla dużych liczb.
Ten kod używa 5 cmp (nie sortuje 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);}
Główny 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
kod js
źródło
Sortuj 4 przedmioty według użycia cmp == 0. Liczba cmp wynosi ~ 4,34 (natywny FF ma ~ 4,52), ale zajmuje 3 razy więcej czasu niż scalanie list. Ale lepiej mniej operacji cmp, jeśli masz duże liczby lub duży tekst. Edycja: naprawiony błąd
Test online http://mlich.zam.slu.cz/js-sort/x-sort-x2.htm
źródło
Może jestem spóźniony na imprezę, ale przynajmniej moim wkładem jest nowe podejście.
swap
był wyższy (niezależnie od kosztucompare
)SWAP()
wstawiania dwóch elementów cykle są ścigane, potrzebując tylko jednej temp i jednej wymiany (rejestr-> rejestr) (nowy <- stary).Aktualizacja: nieco zmieniłem kod, niektóre osoby używają kompilatorów C ++ do kompilacji kodu C ...
źródło
wsort6()
funkcja ma poprawny interfejs.o1..o5
nie ma potrzeby stosowania drugieje[6]
tablicy temp . Oraz: kompilowanie kodu C na kompilatorze C ++ i obwinianie kodu?#include
. Naprawionoźródło
Cóż, jeśli jest tylko 6 elementów i możesz wykorzystać równoległość, chcesz zminimalizować rozgałęzienie warunkowe itp. Dlaczego nie generujesz wszystkich kombinacji i nie testujesz kolejności? Zaryzykowałbym, że w niektórych architekturach może być dość szybki (o ile pamięć jest wstępnie przydzielona)
źródło
Oto trzy typowe metody sortowania, które reprezentują trzy różne klasy algorytmów sortowania:
Ale sprawdź dyskusję Stefana Nelssona na temat najszybszego algorytmu sortowania? gdzie omawia rozwiązanie, które sprowadza się do
O(n log log n)
… Sprawdź jego wdrożenie w CTen algorytm sortowania półliniowego został zaprezentowany w artykule w 1995 roku:
A. Andersson, T. Hagerup, S. Nilsson i R. Raman. Sortujesz w czasie liniowym? W materiałach 27. dorocznego sympozjum ACM na temat teorii komputerów, strony 427–436, 1995.
źródło