kod maszynowy x86-16 (BubbleSort int8_t), 20 19 bajtów
Kod maszynowy x86-64 / 32 (JumpDownSort) 21 19 bajtów
Dziennik zmian:
Dziękuję @ ped7g za pomysł lodsb/ cmp [si],ali łącząc to ze zwiększaniem / resetowaniem wskaźnika, na który patrzyłem. Nie potrzebujemy al/ ahpozwala nam używać prawie tego samego kodu dla większych liczb całkowitych.
Nowy (ale pokrewny) algorytm, wiele zmian implementacyjnych: Bubbly SelectionSort pozwala na mniejszą implementację x86-64 bajtów lub dwordów; break-even na x86-16 (bajty lub słowa). Pozwala także uniknąć błędu rozmiaru = 1, który ma mój BubbleSort. Patrz poniżej.
Okazuje się, że mój Bubbly Selection Sort z zamianą za każdym razem, gdy znajdziesz nową min, jest już znanym algorytmem, JumpDown Sort. Jest wspomniany w Bubble Sort: An Archeological Algorytmic Analysis (tj. Jak Bubble Sort stał się popularny pomimo ssania).
Sortuje 8-bitowe liczby całkowite ze znakiem na miejscu . (Unsigned ma ten sam rozmiar kodu, wystarczy zmienić na jgea jae). Duplikaty nie stanowią problemu. Zamieniamy za pomocą 16-bitowego obrotu o 8 (z miejscem docelowym pamięci).
Sortowanie bąbelkowe wymaga wydajności , ale przeczytałem, że jest to jedna z najmniejszych możliwości implementacji w kodzie maszynowym. Wydaje się to szczególnie prawdziwe, gdy istnieją specjalne triki do zamiany sąsiednich elementów. Jest to w zasadzie jego jedyna zaleta, ale czasami (w prawdziwych systemach wbudowanych) jest to wystarczająca zaleta, aby użyć jej do bardzo krótkich list.
Pominąłem wcześniejsze zakończenie bez zamiany . Użyłem „zoptymalizowanej” pętli BubbleSort z Wikipedii, która unika oglądania ostatnich n − 1elementów podczas biegu po nraz -ty, więc licznik pętli zewnętrznej jest górną granicą dla pętli wewnętrznej.
Lista NASM ( nasm -l /dev/stdout) lub zwykłe źródło
2 address 16-bit bubblesort16_v2:
3 machine ;; inputs: pointer in ds:si, size in in cx
4 code ;; requires: DF=0 (cld)
5 bytes ;; clobbers: al, cx=0
6
7 00000000 49 dec cx ; cx = max valid index. (Inner loop stops 1 before cx, because it loads i and i+1).
8 .outer: ; do{
9 00000001 51 push cx ; cx = inner loop counter = i=max_unsorted_idx
10 .inner: ; do{
11 00000002 AC lodsb ; al = *p++
12 00000003 3804 cmp [si],al ; compare with *p (new one)
13 00000005 7D04 jge .noswap
14 00000007 C144FF08 rol word [si-1], 8 ; swap
15 .noswap:
16 0000000B E2F5 loop .inner ; } while(i < size);
17 0000000D 59 pop cx ; cx = outer loop counter
18 0000000E 29CE sub si,cx ; reset pointer to start of array
19 00000010 E2EF loop .outer ; } while(--size);
20 00000012 C3 ret
22 00000013 size = 0x13 = 19 bytes.
push / pop cxwokół wewnętrznej pętli oznacza, że działa z cx= outer_cx w dół do 0.
Zauważ, że rol r/m16, imm8nie jest to instrukcja 8086, została dodana później (186 lub 286), ale nie jest to próba kodu 8086, tylko 16-bitowy x86. Jeśli phminposuwpomoże SSE4.1 , skorzystam z niego.
Wersja 32-bitowa (wciąż działająca na 8-bitowych liczbach całkowitych, ale z 32-bitowymi wskaźnikami / licznikami) ma 20 bajtów (prefiks wielkości operandu włączony rol word [esi-1], 8)
Błąd: rozmiar = 1 jest traktowany jako rozmiar = 65536, ponieważ nic nie powstrzymuje nas przed wejściem do zewnętrznego do / while z cx = 0. (Zazwyczaj jcxzużywałbyś do tego.) Ale na szczęście 19-bajtowy Sort JumpDown ma 19 bajtów i nie ma tego problemu.
Oryginalna 20-bajtowa wersja x86-16 (bez pomysłu Ped7g). Pominięto, aby zaoszczędzić miejsce, zobacz historię edycji z opisem.
Wydajność
Częściowo zachodzące na siebie zapisywanie / przeładowanie (w rotacji miejsca docelowego w pamięci) powoduje zatrzymanie przekazywania magazynu na nowoczesnych procesorach x86 (z wyjątkiem Atomu w kolejności). Kiedy wysoka wartość rośnie w górę, to dodatkowe opóźnienie jest częścią łańcucha zależności przenoszonego przez pętlę. Przechowywanie / przeładowywanie jest w pierwszej kolejności zasysane (np. 5-cyklowe opóźnienie przekazywania do sklepu w Haswell), ale przeciągnięcie przekazywania powoduje więcej niż 13 cykli. Wykonanie poza kolejnością będzie miało problem z ukryciem tego.
Zobacz także: Przepełnienie stosu: sortowanie bąbelkowe do sortowania łańcucha dla wersji tego z podobną implementacją, ale z wczesnym wyprzedzeniem, gdy nie są potrzebne żadne zamiany. Używa xchg al, ah/ mov [si], axdo zamiany, która jest dłuższa o 1 bajt i powoduje częściowe zatrzymanie rejestru na niektórych procesorach. (Ale wciąż może być lepszy niż rotacja pamięci-dst, która musi ponownie załadować wartość). Mój komentarz zawiera kilka sugestii ...
x86-64 / x86-32 JumpDown Sort, 19 bajtów (sortuje int32_t)
Można wywoływać z C przy użyciu konwencji wywoływania Systemu x86-64 jako V
int bubblyselectionsort_int32(int dummy, int *array, int dummy, unsigned long size); (wartość zwracana = maks. (Tablica [])).
Jest to https://en.wikipedia.org/wiki/Selection_sort , ale zamiast zapamiętywać pozycję elementu min, zamień bieżącego kandydata na tablicę . Po znalezieniu min (region nieposortowany) zapisz go na końcu posortowanego regionu, tak jak normalne sortowanie selekcji. To powiększa posortowany region o jeden. (W kodzie rsiwskazuje jeden za końcem posortowanego regionu; lodsdprzesuwa go i mov [rsi-4], eaxzapisuje min w nim).
Nazwa Sortuj w dół jest używana w Sortowaniu bąbelkowym: archeologiczna analiza algorytmiczna . Wydaje mi się, że mój rodzaj jest naprawdę rodzajem skoku w górę, ponieważ wysokie elementy podskakują w górę, pozostawiając posortowane dno, a nie koniec.
Ten projekt wymiany prowadzi do tego, że nieposortowana część tablicy kończy się w większości w odwrotnej kolejności, co prowadzi do wielu zamian w późniejszym czasie. (Ponieważ zaczynasz od dużego kandydata i ciągle widzisz niższych i niższych kandydatów, więc ciągle zamieniasz się.) Nazwałem to „bąbelkowym”, mimo że przesuwa elementy w innym kierunku. Sposób, w jaki przesuwa elementy, jest również trochę podobny do odwrotnego sortowania. Aby obejrzeć go w akcji, użyj GDB display (int[12])buf, ustaw punkt przerwania w wewnętrznej loopinstrukcji i użyj c(kontynuuj). Naciśnij Return, aby powtórzyć. (Polecenie „display” powoduje, że GDB wypisuje cały stan tablicy za każdym razem, gdy osiągamy punkt przerwania).
xchgwith mem ma niejawny lockprzedrostek, co powoduje, że jest to bardzo wolne. Prawdopodobnie o rząd wielkości wolniejszy niż efektywna zamiana obciążenia / magazynu; xchg m,rto jedna na przepustowość 23c na Skylake, ale ładowanie / przechowywanie / mov z regem tmp dla wydajnej wymiany (reg, mem) może przesunąć jeden element na zegar. Może to być gorszy współczynnik na procesorze AMD, w którym loopinstrukcja jest szybka i nie spowodowałaby tak dużego ograniczenia wewnętrznej pętli, ale pominięcia gałęzi nadal będą dużym wąskim gardłem, ponieważ wymiany są powszechne (i stają się częstsze, gdy nieposortowany region staje się mniejszy ).
2 Address ;; hybrib Bubble Selection sort
3 machine bubblyselectionsort_int32: ;; working, 19 bytes. Same size for int32 or int8
4 code ;; input: pointer in rsi, count in rcx
5 bytes ;; returns: eax = max
6
7 ;dec ecx ; we avoid this by doing edi=esi *before* lodsb, so we do redundant compares
8 ; This lets us (re)enter the inner loop even for 1 element remaining.
9 .outer:
10 ; rsi pointing at the element that will receive min([rsi]..[rsi+rcx])
11 00000000 56 push rsi
12 00000001 5F pop rdi
13 ;mov edi, esi ; rdi = min-search pointer
14 00000002 AD lodsd
16 00000003 51 push rcx ; rcx = inner counter
17 .inner: ; do {
18 ; rdi points at next element to check
19 ; eax = candidate min
20 00000004 AF scasd ; cmp eax, [rdi++]
21 00000005 7E03 jle .notmin
22 00000007 8747FC xchg [rdi-4], eax ; exchange with new min.
23 .notmin:
24 0000000A E2F8 loop .inner ; } while(--inner);
26 ; swap min-position with sorted position
27 ; eax = min. If it's not [rsi-4], then [rsi-4] was exchanged into the array somewhere
28 0000000C 8946FC mov [rsi-4], eax
29 0000000F 59 pop rcx ; rcx = outer loop counter = unsorted elements left
30 00000010 E2EE loop .outer ; } while(--unsorted);
32 00000012 C3 ret
34 00000013 13 .size: db $ - bubblyselectionsort_int32
0x13 = 19 bytes long
Sam rozmiar kod int8_t: Używaj lodsb/ scasb, ALi zmienić [rsi/rdi-4]na -1. Ten sam kod maszynowy działa w trybie 32-bitowym dla elementów 8/32-bitowych. Tryb 16-bitowy dla 8/16-bitowych elementów musi zostać odbudowany ze zmienionymi przesunięciami (a 16-bitowe tryby adresowania używają innego kodowania). Ale wciąż 19 bajtów dla wszystkich.
Unika początkowej dec ecxpoprzez porównanie z elementem, który właśnie załadował przed przejściem dalej. Podczas ostatniej iteracji zewnętrznej pętli ładuje ostatni element, sprawdza, czy jest mniejszy niż on sam, a następnie jest wykonywany. To pozwala mu pracować z rozmiarem = 1, gdzie mój BubbleSort zawodzi (traktuje go jako rozmiar = 65536).
Testowałem tę wersję (w GDB) przy użyciu tego wywołującego: Wypróbuj online! . Możesz uruchomić to na TIO, ale oczywiście nie ma debugera ani drukowania. Mimo to, to, _startco go wywołuje, kończy działanie z parametrem exit-status = największy element = 99, więc widać, że działa.
[7 2 4 1] -> [4 2 3 1]. Czy lista CSV może także znajdować się w nawiasach? Ponadto określony format wejściowy jest bardzo odpowiedni dla niektórych języków, a zły dla innych. To sprawia, że parsowanie danych wejściowych stanowi dużą część dla niektórych zgłoszeń, a dla innych jest niepotrzebne.