x86-64 Assembly - Suma wielokrotności 3 lub 5
Próbuję nauczyć się podstaw asemblacji x86, więc zacząłem rozwiązywać problemy Projektu Euler. Liczyłem na jakąś krytykę mojego kodu, która, miejmy nadzieję, obejmuje albo wydajność operacji, albo czytelność / styl samego kodu. Dostarczę Makefile dla 64-bitowego Linuksa.
Celem kodu jest zsumowanie wszystkich liczb z przedziału [0, 1000), które można podzielić przez 3 lub 5.
Kod można uruchomić za pomocą make RUN=euler_1.
Uwaga:
Zdaję sobie sprawę, że większość kompilatorów zastępuje modulos znanych liczb jakąś kombinacją movi shraby uniknąć dzielenia liczb całkowitych. Na przykład zobacz ten wątek .
Makefile
.PHONY: clean
all: $(RUN).elf ./$^
%.elf: %.o
ld $^ -o $@ -lc -e main -dynamic-linker /lib64/ld-linux-x86-64.so.2
%.o: %.asm
nasm -f elf64 $^
clean:
rm -f *.o *.elf
euler_1.asm
extern printf
global main
section .data
fmt: db "%d", 0x0a, 0
section .text
;; main - Calculate the sum of all numbers between [0, 1000) that are divisible
;; by 3 or 5.
;; sum : R8
main:
; sum = 0
mov r8, 0
; for i in [0, 1000) {
mov rcx, 0
for0:
; if i % 3 == 0 or i % 5 == 0 {
; i % 3 == 0
mov rax, rcx
mov rdx, 0
mov r9, 3
div r9
test rdx, rdx
jne if01
; sum = sum + i
add r8, rcx
jmp if0
if01:
; i % 5 == 0
mov rax, rcx
mov rdx, 0
mov r9, 5
div r9
test rdx, rdx
jne if0
; sum = sum + i
add r8, rcx
jmp if0
; }
if0:
inc rcx
cmp rcx, 1000
jl for0
; }
; printf("%d", sum)
lea rdi, [rel fmt]
mov rsi, r8
mov rax, 0
call printf
; sys_exit(0)
mov rdi, 0
mov rax, 60
syscall
Odpowiedzi
Oto kilka rzeczy, które mogą pomóc w ulepszeniu kodu. Druga recenzja zawierała kilka dobrych punktów, ale niektóre nie zostały tam omówione.
Zdecyduj, czy używasz stdlib, czy nie
MakefileI wywołanie printfzarówno wskazują, że używasz standardowej biblioteki C, która jest w porządku, ale wtedy zakończone jest przy użyciu programu syscall, który nie jest. Powodem jest to, że standardowy start C ustawia rzeczy przed mainwywołaniem, a następnie ponownie je rozbija po mainpowrocie. Ten kod pomija rozłączanie, zamiast tego używać syscalldo zakończenia programu, co nie jest dobrą praktyką. Istnieją dwie alternatywy: albo w ogóle nie używaj biblioteki C (to znaczy napisz własną procedurę drukowania ), albo pozwól, aby porzucenie faktycznie nastąpiło:
xor eax, eax ; set exit code to 0 to indicate success
ret ; return to _libc_start_main which called our main
Aby dowiedzieć się więcej o tym, jak działa uruchamianie i usuwanie w systemie Linux, przeczytaj to .
Zarządzaj rejestrami ostrożnie
Jedną z rzeczy, które robią doświadczeni programiści asemblerowi (i dobrzy kompilatorzy), jest zarządzanie użyciem rejestrów. W tym przypadku ostatecznym zastosowaniem sumy jest wydrukowanie jej, a do wydrukowania potrzebujemy wartości w rsirejestrze. Dlaczego więc nie użyć rsizamiast r8sumy bieżącej?
Dowiedz się, jak skutecznie wyzerować rejestr
Oczywiście, jeśli napiszemy mov r8, 0, ma to pożądany efekt w postaci załadowania wartości 0 do r8rejestru, a jak zauważają inni recenzenci, są lepsze sposoby, aby to zrobić, ale spójrzmy głębiej. Kod obecnie robi to:
; sum = 0
mov r8, 0
; for i in [0, 1000) {
mov rcx, 0
To działa, ale spójrzmy na plik z listą, aby zobaczyć, w jaki sposób NASM go zmienił:
13 ; sum = 0
14 00000000 41B800000000 mov r8, 0
15 ; for i in [0, 1000) {
16 00000006 B900000000 mov rcx, 0
Pierwsza kolumna to tylko numer wiersza pliku listy, druga to adres, a trzecia to zakodowana instrukcja. Widzimy więc, że te dwie instrukcje używają 11 bajtów. Możemy zrobić lepiej! Druga recenzja poprawnie zawierała xorinstrukcję, więc spróbujmy:
19 00000000 4D31C0 xor r8, r8
20 00000003 4831C9 xor rcx, rcx
Lepiej, tylko sześć bajtów. Możemy jeszcze lepiej. Jak słusznie zauważono w jednym z komentarzy, na 64-bitowej maszynie x86, jeśli znajdujesz się xorw dolnej połowie rXXrejestru, czyści również górną połowę. Więc zróbmy to:
19 00000000 4D31C0 xor r8, r8
20 00000003 31C9 xor ecx, ecx
To zaoszczędziło jeden bajt, ale nie ma e8rejestru. Czy możemy zrobić to lepiej, usuwając, ecxa następnie kopiując tę wartość do r8?
14 00000000 31C9 xor ecx, ecx
20 00000002 4989C8 mov r8, rcx
Nie, nie możemy, chyba że zastosujemy się również do powyższych porad i rsizamiast r8:
19 00000000 31C9 xor ecx, ecx
20 00000002 31F6 xor esi, esi
Teraz mamy cztery bajty i nie potrzebujemy już mov rsi, r8instrukcji, która oszczędza nam kolejne 3 bajty, co daje oszczędności netto w wysokości 10 bajtów przy tych dwóch rzeczach.
Unikaj, divjeśli jest to praktyczne
divInstrukcja jest jednym z najwolniejszych instrukcji na architekturze x86_64, a także może spowodować wyjątek, jeśli staramy się dzielić przez zero. Z obu tych powodów często lepiej jest unikać instrukcji, jeśli możemy. W tym przypadku jednym ze sposobów uniknięcia tego jest zauważenie, że wygląda bardzo podobnie fizzbuzzi zachowanie dwóch liczników: jednego odliczającego od 5, a drugiego odliczającego od 3.
Tam, gdzie to możliwe, używaj lokalnych etykiet
Oczywiste jest, że mainmusi to być globalny symbol pliku, ale for0i if01(obie słabe nazwy, jak już wspomniano) nie muszą nim być. W NASM możemy wyznaczyć lokalne etykiety , poprzedzając te etykiety pojedynczą kropką, więc zamiast tego for0możemy użyć .for0. Zaletą takiego rozwiązania jest to, że możemy ponownie użyć etykiety w innej funkcji bez martwienia się o kolizję.
Unikaj bezwarunkowych skoków tam, gdzie to możliwe
Procesor x86 robi wszystko, co w jego mocy, aby dowiedzieć się, która instrukcja zostanie wykonana jako następna. Ma wiele rzeczy do wykonania, w tym wielopoziomowe buforowanie i przewidywanie gałęzi. Robi to, aby spróbować przyspieszyć działanie oprogramowania. Możesz temu pomóc, unikając w ogóle rozgałęziania się, jeśli jest to praktyczne, a zwłaszcza unikając bezwarunkowych skoków. Zastanawiając się nad tym, często możemy to zrobić, przebudowując kod. Oto oryginalny kod:
test rdx, rdx
jne if01
; sum = sum + i
add rsi, rcx
jmp if0
if01:
; i % 5 == 0
mov rax, rcx
mov rdx, 0
mov r9, 5
div r9
test rdx, rdx
jne if0
; sum = sum + i
add rsi, rcx
jmp if0
; }
if0:
inc rcx
cmp rcx, 1000
jl for0
Możemy przepisać to w ten sposób:
test rdx, rdx
je .accumulate
; i % 5 == 0
mov rax, rcx
mov rdx, 0
mov r9, 5
div r9
test rdx, rdx
jne .next
.accumulate:
; sum = sum + i
add rsi, rcx
; }
.next:
inc rcx
cmp rcx, 1000
jl .for0
if01iif0nie są największymi nazwiskami.Zamiast przeładowywać
r9, użyj dwóch rejestrów. Niechr9zawsze zawiera 3 ir10zawsze zawiera 5.Przyrost
r8w jednym miejscu.Uruchomienie pętli w dół (1000 do 0) zamiast w górę oszczędza instrukcję (
cmp).mov rdx, 0jest zakodowany w 7 bajtach.xor rdx, rdxjest znacznie krótszy.
Wszystko to powiedziawszy, rozważ
main:
mov r8, 0
mov r9, 3
mov r10, 5
; for i in (1000, 0]
mov rcx, 999
for0:
mov rax, rcx
xor rdx, rdx
div r9
test rdx, rdx
jeq accumulate
mov rax, rcx
xor rdx, rdx
div r10
test rdx, rdx
jne next
accumulate:
add r8, rcx
next:
dec rcx
jne for0
PS: Mam nadzieję, że wiesz, że ten problem ma bardzo proste rozwiązanie arytmetyczne.
Kilka krótkich uwag na temat wyborów dotyczących implementacji i sposobu, w jaki do tego podchodzę:
Nie potrzebujesz 64-bitowego rozmiaru operandu, divgdy twoje liczby dochodzą do 1000, to znacznie wolniej niż div r32na Intelu przed Ice Lake: wyjaśniłem szczegóły w innym przeglądzie kodu: Sprawdzanie, czy liczba jest pierwsza w zestawie NASM Win64 .
(I ogólnie w przypadku innych instrukcji test edx, edxzapisałby tam rozmiar kodu. Nawet w przypadku liczb 64-bitowych i 64-bitowych div, i % 5zawsze mieści się w 32 bitach, więc można bezpiecznie zignorować wysokie 32. Zobacz Zalety korzystania z 32-bitowych rejestrów / instrukcji w x86-64 - jest to domyślny rozmiar operandu dla x86-64, nie wymagający żadnych prefiksów kodu maszynowego.Aby zwiększyć wydajność, używaj go, chyba że faktycznie potrzebujesz 64-bitowego rozmiaru operandu dla tej konkretnej instrukcji i niejawnego rozszerzenia zerowego do 64 -bit nie zrobi tego, czego potrzebujesz. Nie wydawaj jednak dodatkowych instrukcji; 64-bitowy rozmiar argumentu jest często potrzebny, np. do zwiększania wskaźnika).
Oczywiście w przypadku dzielenia przez stałe czasu kompilacji divjest to powolna opcja, której kompilatory całkowicie unikają, zamiast tego używają odwrotności multiplikatywnej o stałym punkcie. Jak w Dlaczego GCC używa mnożenia przez dziwną liczbę przy implementacji dzielenia liczb całkowitych? na SO, czyli ten przegląd kodu .
Ponadto nie musisz w ogóle dzielić, jeśli używasz liczników w dół, które resetujesz do 3 lub 5, gdy trafią 0 (i / lub rozwijają się), aby obsłużyć wzór 3, 5, jak FizzBuzz - zobacz tę odpowiedź na przepełnienie stosu gdzie napisałem duży tutorial o takich technikach, których nie będę tutaj powtarzał. W przeciwieństwie do FizzBuzz, chcesz policzyć liczbę tylko raz, nawet jeśli jest to wielokrotność 3 i 5.
Możesz po prostu rozwinąć o 15 (więc wzór w pełni się powtarza) i na stałe zakodować coś takiego
.unroll15_loop:
; lets say ECX=60 for example
add eax, ecx ; += 60
lea eax, [rax + rcx + 3] ; += 63
lea eax, [rax + rcx + 5] ; += 65
lea eax, [rax + rcx + 6] ; += 66
...
add ecx, 15
cmp ecx, 1000-15
jbe .unroll15_loop
; handle the last not full group of 15 numbers
Lub zastosuj trochę matematyki i zamiast faktycznie patrzeć na każdą liczbę, użyj formuły zamkniętej na sumę wielokrotności 3 i 5 w 15-liczbowym zakresie, przesuniętą o to, i * nmulsgdzie ijest początek zakresu i nmulsjest liczbą wielokrotności.
np. w [60, 75)przedziale mamy 60, 63, 65, 66, 69, 70, 72. To jest 8 z 15 liczb. Więc jak to jest [0, 15)ale + 8*60. Albo wykonaj część 0..14 ręcznie lub z pętlą i zapamiętaj wynik. (Projekt Euler dotyczy zarówno matematyki, jak i programowania; to od Ciebie zależy, ile matematyki chcesz robić w porównaniu z tym, ile brutalnej siły chcesz wykonać w swoim programie).
Dogodnie, 8 jest jednym ze współczynników skalowania obsługiwanych przez tryby adresowania x86, więc możemy nawet zrobić
lea eax, [rax + rcx*8 + 0 + 3 + 5 + 6 + 9 + 10 + 12]
(3 + 5 + 6 + ... jest wyrażeniem stałym, więc asembler może zrobić to za Ciebie w czasie asemblacji, tworząc [reg + reg*scale + disp8]tryb adresowania. Niestety, ten 3-składnikowy LEA ma 3-cyklowe opóźnienie na procesorach Intela, a pętla- zależność przenoszona będzie wąskim gardłem dla pętli. Dlatego w rzeczywistości bardziej wydajne byłoby użycie oddzielnej addinstrukcji).
I oczywiście zredukowaliśmy to w zasadzie do sumy liniowo rosnących szeregów i moglibyśmy zastosować wzór Gaussa ( n * (n+1) / 2) do postaci zamkniętej w całym zakresie przedziałów, po prostu musielibyśmy zająć się czyszczeniem n%15dla zbliżających się liczb n. Przy okazji, clang wie, jak zamienić prostą pętlę for sum += i;w zamkniętą formę, układając ją tak, aby uniknąć przepełnienia tymczasowego przed podzieleniem przez 2. (przesunięcie w prawo). Wykład Matta Godbolta na temat CppCon2017 „Co ostatnio zrobił dla mnie mój kompilator? Unbolting the Compiler's Lid ” używa tego jako przykładu. Zobacz teżhttps://stackoverflow.com/questions/38552116/how-to-remove-noise-from-gcc-clang-assembly-output
Tam, gdzie to konieczne, użyj instrukcji warunkowego ruchu
Aby rozszerzyć dyskusję w odpowiedzi przez @Edward : jeśli możesz użyć instrukcji warunkowego ruchu, to jeszcze bardziej zmniejszy ilość rozgałęzień, a tym samym pomoże procesorowi.
Jeśli połączysz się z sugestią utrzymania liczników modulo 3 i modulo 5 zamiast wykonywania dzielenia, wówczas zarys głównej pętli może wyglądać następująco (chociaż nie przetestowano):
%define mod3_reg r8
%define mod5_reg r9
%define zero_reg r10
%define count_reg rcx
%define accum_reg rsi
%define addend_reg rdi
%define limit 1000
...
mainloop:
xor addend_reg, addend_reg
inc mod3_reg
cmp mod3_reg, 3
cmove addend_reg, count_reg
cmove mod3_reg, zero_reg
inc mod5_reg
cmp mod5_reg, 5
cmove addend_reg, count_reg
cmove mod5_reg, zero_reg
add accum_reg, addend_reg
inc count_reg
cmp count_reg, limit
jl mainloop
(Zwróć uwagę, że aby dopasować początkową wartość 0 dla licznika, musisz zainicjować mod3_reg2 i mod5_reg4. Z drugiej strony, jeśli dostosujesz się do rozpoczęcia od 1, możesz zainicjować oba na 0, co byłoby nieco prostsze.)
Zwróć również uwagę, że według niektórych komentarzy @PeterCordes mogą wystąpić problemy z cmovutworzeniem wystarczającej liczby dodatkowych zależności w pętli, które mogą nie okazać się tego warte. Byłby to przypadek, w którym, jeśli bardzo zależy Ci na wydajności, wykonanie testu porównawczego na komputerze docelowym byłoby ważne.