Najszybszy rodzaj tablicy int o stałej długości 6

401

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?

Kriss
źródło
2
Czy masz jakieś ograniczenia na ints? Na przykład, możemy założyć, że za każdym 2 x, y x-yi x+ynie spowoduje niedomiaru lub nadmiaru?
Matthieu M.,
3
Powinieneś spróbować połączyć moją sieć sortowania z 12 zamianami z bezgałęziową funkcją zamiany Paula. Jego rozwiązanie przekazuje wszystkie parametry jako osobne elementy na stosie zamiast pojedynczego wskaźnika do tablicy. To też może mieć znaczenie.
Daniel Stutzbach,
2
Zauważ, że poprawna implementacja rdtsc na 64-bitach wynika z tego, __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.
Paolo Bonzini
3
@Tyler: Jak wdrożyć to na poziomie zespołu bez oddziału?
Loren Pechtel
4
@Loren: wstawi CMP EAX, EBX; SBB EAX, EAX0 lub 0xFFFFFFFF w EAXzależności od tego, czy EAXjest odpowiednio większy czy mniejszy EBX. SBBto „odejmij z pożyczeniem”, odpowiednikiem ADC(„dodaj z przeniesieniem”); bit stanu, o którym mówisz, to bit przeniesienia. Z drugiej strony, pamiętam to ADCi SBBmiałem straszne opóźnienia i przepustowość na Pentium 4 vs. ADDi SUB, i nadal były dwa razy wolniejsze na Core CPU. Od 80386 dostępne są również instrukcje SETccwarunkowego przechowywania i CMOVccwarunkowego przenoszenia, ale są one również powolne.
j_random_hacker

Odpowiedzi:

162

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:

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

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:

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
}
Daniel Stutzbach
źródło
9
+1: fajnie, zrobiłeś to z 12 wymianami zamiast 13 w mojej ręcznie kodowanej i empirycznie wyprowadzonej powyżej sieci. Dałbym ci jeszcze +1, gdybym mógł, link do strony, która generuje dla ciebie sieci - teraz dodana do zakładek.
Paul R
9
To fantastyczny pomysł na funkcję sortowania ogólnego przeznaczenia, jeśli spodziewasz się, że większość żądań będzie tablicami małych rozmiarów. Użyj instrukcji switch w przypadkach, które chcesz zoptymalizować, korzystając z tej procedury; niech domyślna wielkość liter korzysta z funkcji sortowania biblioteki.
Mark Ransom,
5
@Mark Dobra funkcja sortowania biblioteki ma już szybką ścieżkę dla małych tablic. Wiele współczesnych bibliotek używa rekursywnego QuickSort lub MergeSort, który przełącza się na InsertionSort po rekurencji do n < SMALL_CONSTANT.
Daniel Stutzbach,
3
@ Mark Cóż, funkcja sortowania w bibliotece C wymaga określenia operacji porównania za pomocą portera funkcji. Koszt wywołania funkcji dla każdego porównania jest ogromny. Zwykle jest to wciąż najczystsza droga, ponieważ rzadko jest to krytyczna ścieżka w programie. Jeśli jednak jest to ścieżka krytyczna, naprawdę możemy sortować znacznie szybciej, jeśli wiemy, że sortujemy liczby całkowite i dokładnie 6 z nich. :)
Daniel Stutzbach,
7
@tgwh: Zamiana XOR jest prawie zawsze złym pomysłem.
Paul R
63

Oto implementacja wykorzystująca sieci sortujące :

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

Naprawdę potrzebujesz bardzo wydajnych gałęzi mini maximplementacji, ponieważ do tego właśnie sprowadza się ten kod - sekwencja mini maxoperacje (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

Paul R.
źródło
1
Dla niektórych hacków dla min / maks: graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
Rubys
1
@Paul: w rzeczywistym kontekście wykorzystania CUDA jest to z pewnością najlepsza odpowiedź. Sprawdzę, czy to także (i ile) w kontekście golfa x64 i opublikuję wynik.
kriss
1
Sort3byłoby szybsze (zresztą w większości architektur), gdybyś zauważył, że (a+b+c)-(min+max)jest to liczba centralna.
Rex Kerr
1
@ Rex: Rozumiem - to wygląda dobrze. W przypadku architektur SIMD, takich jak AltiVec i SSE, byłaby to taka sama liczba cykli instrukcji (maks. I min. To instrukcje pojedynczego cyklu, takie jak dodawanie / odejmowanie), ale dla normalnego procesora skalarnego Twoja metoda wygląda lepiej.
Paul R,
2
Jeśli pozwolę GCC zoptymalizować min z instrukcji warunkowych move dostaję 33% przyspieszenie: #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.
Paolo Bonzini
45

Ponieważ są to liczby całkowite, a porównania są szybkie, dlaczego nie obliczyć bezpośrednio kolejności rang dla każdego:

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];
}
Rex Kerr
źródło
@Rex: z gcc -O1 jest poniżej 1000 cykli, dość szybko, ale wolniej niż sieć sortująca. Masz pomysł na ulepszenie kodu? Może gdybyśmy mogli uniknąć kopiowania tablicy ...
kriss
@kriss: Jest szybszy niż sieć sortująca dla mnie z -O2. Czy jest jakiś powód, dla którego -O2 nie jest w porządku, czy też jest wolniejszy dla ciebie na -O2? Może to różnica w architekturze maszyn?
Rex Kerr
1
@Rex: przepraszam, brakowało mi wzorca> vs> = od pierwszego wejrzenia. Działa w każdym przypadku.
kriss
3
@kriss: Aha. Nie jest to całkowicie zaskakujące - wokół jest wiele zmiennych, które muszą być starannie uporządkowane i buforowane w rejestrach i tak dalej.
Rex Kerr,
2
@SSpoke 0+1+2+3+4+5=15Ponieważ brakuje jednego z nich, 15 minus suma reszty daje brakujący
Glenn Teitelbaum
35

Wyglą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).

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

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.

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
Kevin Stock
źródło
Twój pomysł na zmienne rejestrowe powinien zostać zastosowany w rozwiązaniu Rex Kerr „Rank Order”. Powinno to być najszybsze, a być może wtedy -O3optymalizacja nie przyniesie efektu przeciwnego do zamierzonego.
cdunn2001
1
@ cdunn2001 Właśnie go przetestowałem, nie widzę poprawy (z wyjątkiem kilku cykli dla -O0 i -Os). Patrząc na asm, wydaje się, że gcc już zdążyło wymyślić użycie rejestrów i wyeliminować połączenie z memcpy.
Kevin Stock
Czy mógłbyś dodać prostą wersję wymiany do pakietu testowego? Myślę, że interesujące może być porównanie jej z szybką zamianą montażu zoptymalizowaną ręcznie.
kriss,
1
Twój kod nadal używa wymiany Gundersona, mój byłby #define SWAP(x,y) { int oldx = x; x = x < y ? x : y; y ^= oldx ^ x; }.
Paolo Bonzini
@Paolo Bonzini: Tak, zamierzam dodać twój test, po prostu jeszcze nie miałem czasu. Ale uniknę montażu w linii.
kriss,
15

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 charpodczas 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 ...

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

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:

void simd_sort_6(char *values);
Joe Crivello
źródło
Ciekawie byłoby porównać twoje z innymi propozycjami na poziomie asemblera. Porównywane wydajności wdrożenia nie obejmują ich. Korzystanie z SSE i tak brzmi dobrze.
kriss,
Innym obszarem przyszłych badań byłoby zastosowanie nowych instrukcji Intel AVX do tego problemu. Większe wektory 256-bitowe są wystarczająco duże, aby zmieścić 8 DWORD.
Joe Crivello,
1
Zamiast tego po pxor / pinsrd xmm4, mem, 0prostu użyj movd!
Peter Cordes,
14

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

#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"); }

i wychodzi mi to o 65% szybciej (Debian gcc 4.4.5 z -O2, amd64, Core i7).

Steinar H. Gunderson
źródło
OK, kod testowy jest słaby. Możesz to poprawić. I tak, możesz użyć kodu asemblera. Dlaczego nie przejść do końca i w pełni zakodować przy użyciu asemblera x86? Może to być nieco mniej przenośne, ale po co?
kriss,
Dzięki za zauważenie przepełnienia tablicy poprawiłem go. Inne osoby mogły tego nie zauważyć, ponieważ kliknięto link do skopiuj / wklej kod, w którym nie ma przepełnienia.
kriss
4
Właściwie nawet nie potrzebujesz asemblera; jeśli porzucisz wszystkie sprytne sztuczki, GCC rozpozna sekwencję i wstawi dla ciebie ruchy warunkowe: # zdefiniuj min (a, b) ((a <b)? a: b) # zdefiniuj max (a, b) ( (a <b)? b: a) # zdefiniować SWAP (x, y) {int a = min (d [x], d [y]); int b = max (d [x], d [y]); d [x] = a; d [y] = b; } Wydaje się być może kilka procent wolniejszy niż wbudowany wariant asm, ale trudno to powiedzieć, biorąc pod uwagę brak odpowiedniego testu porównawczego.
Steinar H. Gunderson
3
… I na koniec, jeśli twoje liczby są zmienne i nie musisz się martwić o NaN itp., GCC może przekonwertować to na instrukcje SSSE minss / maxss, co jest o ~ 25% szybsze. Morale: Porzuć sprytne sztuczki bitfiddling i pozwól kompilatorowi wykonać swoją pracę. :-)
Steinar H. Gunderson
13

Chociaż naprawdę podoba mi się makro wymiany:

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

Widzę ulepszenie (które mógłby zrobić dobry kompilator):

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

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.

phkahler
źródło
To powoduje, że cofają się, zauważ, że d [y] dostaje maksimum, czyli x ^ (wspólne podwyrażenie).
Kevin Stock
Zauważyłem to samo; Myślę, że chcesz, aby twoja implementacja była poprawna, d[x]zamiast tego x(dla tego samego y), i d[y] < d[x]dla nierówności tutaj (tak, różni się od kodu min / max).
Tyler
Próbowałem z twoją zamianą, ale lokalna optymalizacja ma negatywne skutki na większym poziomie (myślę, że wprowadza zależności). A wynik jest wolniejszy niż inne zamiany. Ale jak widać z proponowanym nowym rozwiązaniem, rzeczywiście było dużo wydajności, aby uzyskać optymalizację wymiany.
kriss,
12

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:

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

(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 (npd0 = 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:

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);

a oto sortowanie wstawek:

//#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);

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:

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

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

Paolo Bonzini
źródło
1
Mniej więcej powiązane: wysłałem raport do GCC, aby mógł wdrożyć optymalizację bezpośrednio w kompilatorze. Nie jestem pewien, czy to się stanie, ale przynajmniej możesz śledzić, jak się rozwija.
Morwenn
11

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

jheriko
źródło
1
Naprawdę interesujące. Wygląda na to, że zamiana bez rozgałęzień to zły pomysł na PPC. Może to być również efekt związany z kompilatorem. Który został użyty?
kriss
Jest to gałąź kompilatora gcc - logika min, max prawdopodobnie nie jest bez rozgałęzień - sprawdzę dezasemblację i dam ci znać, ale chyba, że ​​kompilator jest wystarczająco sprytny, w tym coś w rodzaju x <y bez if, jeśli nadal staje się gałęzią - na x86 / x64 instrukcja CMOV może tego uniknąć, ale nie ma takiej instrukcji dla stałych wartości punktów na PPC, tylko zmiennoprzecinkowe. Mogę porozmawiać o tym jutro i poinformować cię - pamiętam, że w źródle Winamp AVS było znacznie prostsze min / max bez rozgałęzień, ale iirc było tylko dla pływaków - ale może być dobrym początkiem do prawdziwie bezgałęziowego podejścia.
jheriko
4
Oto branchless min / max dla PPC z wejściami unsigned: 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.
Paolo Bonzini,
7

Zamiana XOR może być przydatna w funkcjach wymiany.

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

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.

naj
źródło
1
xor wymiany pracuje dla równych wartości, jak również ... x ^ = Y zestawy x 0, y = x ^ y liście jako y (== x) = x ^ y zestawy X do Y
jheriko
11
Kiedy to nie praca jest, kiedy xi ypunkt w tej samej lokalizacji.
hobbs
W każdym razie, gdy używane jest z sieciami sortującymi, nigdy nie wywołujemy, gdy zarówno x, jak i y wskazują tę samą lokalizację. Wciąż istnieje sposób na uniknięcie testowania, który jest większy, aby uzyskać taki sam efekt jak zamiana bez rozgałęzień. Mam pomysł, aby to osiągnąć.
kriss
5

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:

**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
Nico
źródło
4

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.

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

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.

Olof Forshell
źródło
miły. Dodam go do dłuższej wersji testsuite
kriss
3

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

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

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

gcp
źródło
zaproponuj implementację :-)
kriss
Dodano propozycję. Ciesz się błędami.
gcp
3

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.

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
}

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

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

Repozytorium można znaleźć tutaj: https://github.com/eyepatchParrot/sort6/

2 obrotami
źródło
1
Możesz użyć vmovmskpsna wektorach całkowitych (z rzutowaniem, aby zadowolić intrinsics), unikając potrzeby przesunięcia wyniku bitscan ( ffs) w prawo .
Peter Cordes,
1
Możesz warunkowo dodać 1 na podstawie cmpgtwyniku, odejmując go, zamiast maskować set1(1). np. index = _mm256_sub_epi32(index, gt)robiindex -= -1 or 0;
Peter Cordes,
1
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ż vpinsrdjest 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. vpblenddjest instrukcją pojedynczego działania, która działa na dowolnym porcie, a tasowanie wymaga portu 5 na procesorach Intel. ( agner.org/optimize ).
Peter Cordes,
1
Możesz również rozważyć wygenerowanie rotwektoró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.
Peter Cordes,
2

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 sort6wykorzystuje algorytm, sort4który korzysta z algorytmu sort3. 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ń:

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

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 sort3wykonuje następnie przewijanie sortowania z ostatnim elementem tablicy:

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

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:

  • Sortuj wszystko oprócz pierwszego i ostatniego elementu tablicy.
  • Zamień pierwszy i elementy tablicy, jeśli pierwszy jest większy niż ostatni.
  • Wstaw pierwszy element do posortowanej sekwencji od przodu, a następnie ostatni element od tyłu.

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.

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

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.

Morwenn
źródło
Te są miłe. Ponieważ rozwiązany problem ma wiele dziesięcioleci, prawdopodobnie tak stary program w języku C, że pytanie ma teraz prawie 5 lat, nie wydaje się zbyt istotne.
kriss,
Powinieneś rzucić okiem na sposób, w jaki inne odpowiedzi są w czasie. Chodzi o to, że przy tak małym zestawie danych zliczanie porównań, a nawet porównań i zamian, tak naprawdę nie mówi, jak szybki jest algorytm (w zasadzie sortowanie 6 liczb całkowitych zawsze oznacza O (1), ponieważ O (6 * 6) to O (1)). Obecnie najszybszym z wcześniej zaproponowanych rozwiązań jest natychmiastowe znalezienie pozycji każdej wartości przy użyciu dużego porównania (autor: RexKerr).
Kriss,
@kriss Czy jest teraz najszybszy? Po przeczytaniu wyników podejście do sieci sortujących było najszybsze, moje złe. Prawdą jest również to, że moje rozwiązanie pochodzi z mojej biblioteki ogólnej i że nie zawsze porównuję liczby całkowite, ani nie używam 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ę :)
Morwenn,
Rozwiązanie RexKerr (Order Rank) stało się najszybszym w architekturze X86 od czasu kompilatora gcc 4.2.3 (a od gcc 4.9 stał się prawie dwa razy szybszy niż drugi najlepszy). Jest to jednak w dużym stopniu zależne od optymalizacji kompilatora i może nie być prawdziwe w przypadku innych architektur.
kriss,
@kriss To interesujące wiedzieć. I rzeczywiście mogłem znowu więcej różnic -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 :)
Morwenn,
1

Uważam, że twoje pytanie składa się z dwóch części.

  • Pierwszym jest określenie optymalnego algorytmu. Odbywa się to - przynajmniej w tym przypadku - przez zapętlenie każdego możliwego uporządkowania (nie ma ich zbyt wielu), co pozwala obliczyć dokładne min, maks, średnie i standardowe odchylenie porównań i zamian. Miej też drugie lub dwa przydatne.
  • Drugim jest optymalizacja algorytmu. Wiele można zrobić, aby przekonwertować przykłady kodu z podręczników na proste i uproszczone algorytmy. Jeśli zdajesz sobie sprawę, że algorytmu nie można zoptymalizować w wymaganym zakresie, spróbuj zająć drugie miejsce.

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.

Olof Forshell
źródło
Nie jestem pewien, jak zrozumieć twoją odpowiedź. Po pierwsze, wcale nie rozumiem, jaki algorytm proponujesz? I jak może być optymalne, jeśli trzeba zapętlić 720 możliwych porządków (istniejące odpowiedzi zajmują znacznie mniej niż 720 cykli). Jeśli masz losowe dane wejściowe, nie wyobrażam sobie (nawet na poziomie teoretycznym), w jaki sposób przewidywanie gałęzi może działać lepiej niż 50–50, chyba że nie przejmują się danymi wejściowymi. Również większość proponowanych już dobrych rozwiązań może już działać z danymi i kodem w pełni w pamięci podręcznej. Ale może całkowicie źle zrozumiałem twoją odpowiedź. Chcesz pokazać jakiś kod?
kriss,
Miałem na myśli to, że istnieje tylko 720 (6!) Różnych kombinacji 6 liczb całkowitych, a uruchamiając je wszystkie za pomocą algorytmów kandydujących, możesz określić wiele rzeczy, jak już wspomniałem - to część teoretyczna. Część praktyczna polega na dopracowaniu algorytmu, aby działał w jak najmniejszej liczbie cykli zegara. Moim punktem wyjścia do sortowania 6 liczb całkowitych jest 1, 4 szczelinowa skorupa. 4 odstępy torują drogę do dobrego przewidywania gałęzi w 1 odstępie.
Olof Forshell,
Shellsort 1, 4 gap dla 6! unikalne kombinacje (zaczynające się od 012345 i kończące się na 543210) będą miały najlepszy przypadek 7 porównań i 0 wymian, a najgorszy z 14 porównań i 10 wymian. Przeciętny przypadek to około 11,14 porównań i 6 wymian.
Olof Forshell,
1
Nie dostaję „regularnego losowego rozkładu” - tym, co robię, jest testowanie każdej możliwej kombinacji i określanie minimalnych / średnich / maksymalnych statystyk. Shellsort to seria rodzajów malejących przyrostów, tak że końcowy przyrost - 1 - wykonuje o wiele mniej pracy niż gdyby był wykonywany sam, jak w przypadku czystego wprowadzania. Jeśli chodzi o liczenie zegarów, mój algorytm wymaga średnio 406 cykli zegara, co obejmuje zbieranie statystyk i wykonywanie dwóch wywołań do faktycznej procedury sortowania - po jednym dla każdej przerwy. To jest na mobilnym kompilatorze Athlon M300 OpenWatcom.
Olof Forshell
1
„regularny rozkład losowy” oznacza, że ​​każda kombinacja faktycznie posortowanych danych może nie mieć jednakowego prawdopodobieństwa. Jeśli każda kombinacja nie ma jednakowego prawdopodobieństwa, statystyki są zepsute, ponieważ średnia musi wziąć pod uwagę, ile razy dany rozkład może wystąpić. W przypadku licznika czasu, jeśli wypróbujesz jakąkolwiek inną implementację tego rodzaju (linki podane powyżej) i uruchomisz ją w systemie testowym, będziemy mieli podstawę do porównania i zobaczymy, jak dobrze działa wybrany przez Ciebie.
kriss
1

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

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

EDYCJA:
Rozwiązanie kolejności rangi zainspirowane przez Rexa Kerra, znacznie szybsze niż bałagan powyżej

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;
}
PrincePolka
źródło
1
zawsze miło widzieć nowe rozwiązania. Wygląda na to, że możliwa jest łatwa optymalizacja. Ostatecznie może się nie różnić od sortowania sieci.
kriss
Tak, liczba MIN i MAX mogłaby zostać zmniejszona, na przykład MIN (AB, CD) powtarza się kilka razy, ale myślę, że ich zmniejszenie będzie bardzo trudne. Dodałem twoje przypadki testowe.
PrincePolka
pmin / maxsw działają na spakowanych 16-bitowych liczbach całkowitych ze znakiem ( int16_t). Ale funkcja C twierdzi, że sortuje tablicę int(która jest 32-bitowa we wszystkich implementacjach C obsługujących tę asmskł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 ... intPotrzebujesz SSE4.1 pmin/maxsd(d = dword). felixcloutier.com/x86/pminsd:pminsq lub pminusdfor uint32_t.
Peter Cordes,
1

Okazało się, że przynajmniej w moim systemie, funkcje sort6_iterator()i sort6_iterator_local()zdefiniowano poniżej zarówno RAN co najmniej tak szybko, a często znacznie szybciej, niż wymienione powyżej aktualnego rekordzisty:

#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
}

W std::vectorkodzie 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 jakstd::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).

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
}

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.

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

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:

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
}

Lub jeśli chcesz przekazać zmienne przez referencję, użyj tego (poniższa funkcja różni się od powyższej w pierwszych 5 wierszach):

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
}

Powodem użycia registersłowa kluczowego jest to, że jest to jeden z niewielu przypadków, w których wiesz, że chcesz te wartości w rejestrach. Bez registertego kompilator przez większość czasu to zrozumie, ale czasem tak nie jest. Użycie registersłowa kluczowego pomaga rozwiązać ten problem. Zwykle jednak nie używaj registersł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 inlinesł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).

  1. Podczas mierzenia czasu różnych funkcji sortujących zauważyłem, że kontekst (tj. Otaczający kod), w którym wykonano wywołanie funkcji sortującej, miał znaczący wpływ na wydajność, co prawdopodobnie wynika z wbudowania, a następnie optymalizacji funkcji. Na przykład, jeśli program był wystarczająco prosty, to zwykle nie było dużej różnicy w wydajności między przekazywaniem funkcji sortowania wskaźnika a przekazywaniem iteratora; w przeciwnym razie użycie iteratorów zwykle skutkowało zauważalnie lepszą wydajnością i nigdy (według mojego dotychczasowego doświadczenia) żadną zauważalnie gorszą wydajnością. Podejrzewam, że może tak być, ponieważ g ++ może globalnie zoptymalizować wystarczająco prosty kod.
Matthew K.
źródło
0

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

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

Piotr
źródło
0

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

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;
}
Peter
źródło
1
Przypadek użycia różni się nieco od początkowego kontekstu pytania. Przy stałej długości sortuje się szczegóły, a liczenie cmp swapów nie wystarczy. Nie zdziwiłbym się nawet, gdyby nie był to faktyczny rodzaj, który pochłaniałby czas, ale coś zupełnie innego, nazywając typof () w init. Nie wiem, jak wykonać rzeczywisty pomiar czasu za pomocą Javascript. Może z węzłem?
kriss
0

Może jestem spóźniony na imprezę, ale przynajmniej moim wkładem jest nowe podejście.

  • Kod naprawdę powinien zostać wstawiony
  • nawet jeśli są wstawione, istnieje zbyt wiele gałęzi
  • analizowana część to w zasadzie O (N (N-1)), co wydaje się OK dla N = 6
  • kod mógłby być bardziej skuteczny, gdyby kosztswap był wyższy (niezależnie od kosztu compare)
  • Ufam wbudowanym funkcjom statycznym.
  • Metoda jest związana z sortowaniem według rang
    • zamiast rang używane są względne rangi (przesunięcia).
    • suma stopni wynosi zero dla każdego cyklu w dowolnej grupie permutacji.
    • zamiast 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 ...

#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);
}
wildplasser
źródło
wygląda jak bąbelkowy rodzaj. Potencjalnie dobry pretendent do najwolniejszej implementacji, ale nadal może być interesujące dowiedzieć się, czy praca nad kodem robi tak dużą różnicę. Proszę ustawić swój kod w tym samym formacie, co inne, abyśmy mogli uruchomić na nim test porównawczy.
kriss
@kriss en.wikipedia.org/wiki/Permutation_group Z pewnością nie jest to sortowanie bąbelkowe: kod wykrywa cykle w danej permutacji i przeprowadza te cykle, umieszczając każdy element na swoim ostatecznym miejscu. Ostatnia wsort6()funkcja ma poprawny interfejs.
dołącz
@joop: mój zły, naprawdę nie ma rodzaju bąbelków. Biorąc to pod uwagę w kontekście, nadal oczekuję, że kod będzie znacznie gorszy niż jakakolwiek inna bieżąca implementacja. Nawiasem mówiąc, rozwiązanie Order Order jest optymalne pod względem liczby zamian, ponieważ bezpośrednio znajduje ostateczną pozycję każdego przedmiotu. Nie jest również jasne, czy walksort działa nawet po usunięciu hipotezy, że wszystkie posortowane liczby są inne, jak tutaj. Aby przetestować kod, powinniśmy śledzić kod. Ponadto, ponieważ zwykle kompiluję na kompilatorze C ++, kod nie będzie działał, ponieważ OP nazwał zmienną „nową” (i to przerywa podświetlanie składni).
kriss
Metoda jest bardzo zbliżona do kolejności rang, tylko ostateczne zadania są wykonywane na miejscu . Poza szeregami o1..o5nie ma potrzeby stosowania drugiej e[6]tablicy temp . Oraz: kompilowanie kodu C na kompilatorze C ++ i obwinianie kodu?
dołącz
@ Greybeard: dziękuję, wcześniej dodałem spację #include. Naprawiono
Wildplasser
0
//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
}
rev Frantzelas G.
źródło
Czy na pewno działa, niezależnie od prędkości? W rodzaju bruteforce twoje pętle są wątpliwe. Wydaje mi się, że nie będą działać, jeśli mamy zero w posortowanych wartościach.
kriss,
1
Tablica t [6] jest inicjowana na 0x0. Więc nie ma znaczenia, gdzie i czy zostanie zapisany klucz wartości 0x0.
FranG
-1

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)

GClaramunt
źródło
9
Istnieje 720 zamówień, a szybkie wersje są znacznie poniżej 100 cykli. Nawet jeśli ogromna równoległość mogłaby być dźwignią, w tak małej skali czasowej koszt tworzenia i synchronizacji wątki prawdopodobnie przekroczyłyby koszt samego sortowania tablic na jednym rdzeniu.
Kevin Stock
-3

Oto trzy typowe metody sortowania, które reprezentują trzy różne klasy algorytmów sortowania:

Insertion Sort: Θ(n^2)

Heap Sort: Θ(n log n)

Count Sort: Θ(3n)

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 C

Ten 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.

Khaled A Khunaifer
źródło
8
To interesujące, ale nie na temat. Big-Θ ma na celu ukrycie stałych czynników i pokazanie trendu, gdy rozmiar problemu (n) staje się duży. Problem dotyczy w pełni ustalonego rozmiaru problemu (n = 6) i uwzględnienia stałych czynników.
kriss,
@kriss masz rację, moje porównanie jest asymptotyczne, więc praktyczne porównanie pokaże, czy w tym przypadku jest szybsze, czy nie
Khaled.K
4
Nie można dojść do wniosku, ponieważ każdy inny algorytm ukrywa inną stałą multiplikatywną K (a także stałą addytywną C). tj .: k0, c0 dla sortowania wstawiania, k1, c1 dla sortowania sterty i tak dalej. Wszystkie te stałe są w rzeczywistości różne (można by powiedzieć w termach, że każdy algorytm ma swój własny „współczynnik tarcia”), nie można stwierdzić, że algorytm jest w tym przypadku szybszy (lub jakikolwiek ustalony przypadek n).
kriss,