x86-64 Assembly - Jumlah kelipatan 3 atau 5
Saya mencoba mempelajari beberapa perakitan x86 dasar dan jadi saya mulai memecahkan masalah Project Euler. Saya mengharapkan beberapa kritik terhadap kode saya yang, semoga, mencakup efisiensi operasi atau keterbacaan / gaya kode itu sendiri. Saya akan menyediakan Makefile untuk Linux 64 bit.
Tujuan dari kode ini adalah untuk menjumlahkan semua angka dari [0, 1000) yang habis dibagi 3 atau 5.
Kode dapat dijalankan menggunakan make RUN=euler_1.
NB:
Saya sadar bahwa sebagian besar kompiler mengganti modulos dari bilangan yang diketahui dengan beberapa kombinasi movdan shruntuk menghindari pembagian integer. Misalnya, lihat utas ini .
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
Jawaban
Berikut beberapa hal yang dapat membantu Anda meningkatkan kode Anda. Ulasan lain membuat beberapa poin bagus, tetapi di sini beberapa tidak tercakup di sana.
Putuskan apakah Anda menggunakan stdlib atau tidak
The Makefiledan panggilan untuk printfkeduanya menunjukkan bahwa Anda menggunakan C library standar, yang baik-baik saja, tapi kemudian berakhir Program menggunakan syscallyang tidak. Alasannya adalah bahwa startup C standar mengatur segalanya sebelum maindipanggil dan kemudian juga menghentikannya lagi setelah mainpengembalian. Kode ini melewatkan pembongkaran dengan menggunakan syscallto mengakhiri program, yang bukan merupakan praktik yang baik. Ada dua alternatif: jangan gunakan perpustakaan C sama sekali (yaitu, tulis rutinitas pencetakan Anda sendiri ) atau biarkan pembongkaran benar-benar terjadi:
xor eax, eax ; set exit code to 0 to indicate success
ret ; return to _libc_start_main which called our main
Untuk membaca lebih lanjut tentang cara kerja startup dan pembongkaran di Linux, baca ini .
Kelola register dengan hati-hati
Salah satu hal yang dilakukan pemrogram bahasa assembly ahli (dan kompiler yang baik) adalah mengelola penggunaan register. Dalam hal ini, penggunaan akhir dari jumlah tersebut adalah untuk mencetaknya, dan untuk mencetaknya kita memerlukan nilai di rsiregister. Jadi, mengapa tidak digunakan rsisebagai pengganti r8sebagai jumlah berjalan?
Ketahui cara melakukan nol register secara efisien
Jelas, jika kita menulisnya mov r8, 0memiliki efek yang diinginkan dengan memuat nilai 0 ke dalam r8register, dan seperti catatan review lainnya, ada cara yang lebih baik untuk melakukan itu, tapi mari kita lihat lebih dalam. Kode saat ini melakukan ini:
; sum = 0
mov r8, 0
; for i in [0, 1000) {
mov rcx, 0
Itu berfungsi, tetapi mari kita lihat file daftar untuk melihat apa yang telah diubah NASM menjadi:
13 ; sum = 0
14 00000000 41B800000000 mov r8, 0
15 ; for i in [0, 1000) {
16 00000006 B900000000 mov rcx, 0
Kolom pertama hanyalah nomor baris dari file daftar, yang kedua adalah alamat dan yang ketiga adalah instruksi yang dikodekan. Jadi kita melihat bahwa kedua instruksi tersebut menggunakan 11 byte. Kami bisa lebih baik! Ulasan lain dengan benar menyebutkan xorinstruksi, jadi mari kita coba:
19 00000000 4D31C0 xor r8, r8
20 00000003 4831C9 xor rcx, rcx
Lebih baik, hanya enam byte. Kita masih bisa lebih baik. Sebagai salah satu komentar dicatat dengan benar, pada mesin 64-bit x86, jika Anda xorsetengah bagian bawah rXXregister, itu juga membersihkan bagian atas. Jadi mari kita lakukan itu:
19 00000000 4D31C0 xor r8, r8
20 00000003 31C9 xor ecx, ecx
Itu menghemat satu byte, tetapi tidak ada e8register. Bisakah kita melakukan lebih baik dengan membersihkan ecxdan kemudian menyalin nilai itu ke dalamnya r8?
14 00000000 31C9 xor ecx, ecx
20 00000002 4989C8 mov r8, rcx
Tidak, kami tidak bisa, kecuali kami juga mengikuti saran di atas dan menggunakan rsisebagai ganti r8:
19 00000000 31C9 xor ecx, ecx
20 00000002 31F6 xor esi, esi
Sekarang kita turun menjadi empat byte, dan kita tidak lagi membutuhkan mov rsi, r8instruksi yang menghemat 3 byte lagi, untuk penghematan bersih 10 byte hanya dengan dua hal itu.
Hindari divjika praktis
The divinstruksi adalah salah satu petunjuk paling lambat pada arsitektur x86_64 dan juga dapat menyebabkan pengecualian jika kita mencoba untuk membagi dengan nol. Untuk kedua alasan tersebut, seringkali lebih baik menghindari instruksi jika kita bisa. Dalam hal ini, salah satu cara untuk menghindarinya adalah dengan mencatat bahwa itu terlihat sangat mirip fizzbuzzdan menyimpan dua penghitung: satu yang menghitung mundur dari 5 dan yang lain yang menghitung mundur dari 3.
Gunakan label lokal jika memungkinkan
Jelas itu mainperlu menjadi simbol global file, tetapi for0dan if01(keduanya nama yang buruk, seperti yang telah disebutkan) tidak perlu. Di NASM, kami dapat menetapkan label lokal dengan memberi awalan label tersebut dengan satu titik, jadi alih-alih for0kami dapat menggunakan .for0. Keuntungan melakukan ini adalah kita dapat menggunakan kembali label di fungsi lain tanpa harus khawatir tentang benturan.
Hindari lompatan tanpa syarat jika memungkinkan
Prosesor x86 melakukan yang terbaik untuk mencari tahu instruksi mana yang akan dijalankan selanjutnya. Ia memiliki segala macam hal untuk mewujudkannya, termasuk cache multi-level dan prediksi cabang. Itu dilakukan untuk mencoba membuat perangkat lunak berjalan lebih cepat. Anda dapat membantunya dengan menghindari percabangan sama sekali jika memungkinkan, dan terutama dengan menghindari lompatan tanpa syarat. Dengan memikirkannya dengan hati-hati, kita sering kali dapat melakukan ini dengan menyusun ulang kode. Ini kode aslinya:
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
Kita bisa menulis ulang seperti ini:
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
if01danif0bukan nama terbesar.Alih-alih memuat ulang
r9, gunakan dua register. Biarkanr9selalu berisi 3, danr10selalu berisi 5.Kenaikan
r8di satu tempat.Menjalankan loop ke bawah (1000 ke 0), bukan ke atas, akan menghemat instruksi (
cmp).mov rdx, 0dikodekan dalam 7 byte.xor rdx, rdxjauh lebih pendek.
Semua yang dikatakan, pertimbangkan
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: Saya harap Saudara tahu bahwa masalah ini memiliki solusi aritmatika yang sangat lugas.
Beberapa catatan singkat tentang pilihan penerapan Anda, dan bagaimana saya mendekatinya:
Anda tidak memerlukan ukuran operan 64-bit karena divketika angka Anda hanya mencapai 1000, itu jauh lebih lambat daripada div r32di Intel sebelum Ice Lake: Saya menjelaskan detailnya di Tinjauan Kode lain: Memeriksa apakah suatu angka adalah bilangan prima di Majelis NASM Win64 .
(Dan secara umum untuk instruksi lain, test edx, edxakan menghemat ukuran kode di sana. Bahkan dengan angka 64-bit dan 64-bit div, i % 5akan selalu muat dalam 32 bit sehingga aman untuk mengabaikan 32 bit tinggi. Lihat Keuntungan menggunakan register / instruksi 32bit di x86-64 - ini adalah ukuran operan default untuk x86-64, tidak memerlukan awalan kode mesin apa pun. Untuk efisiensi, gunakan ini kecuali Anda benar-benar memerlukan ukuran operan 64-bit untuk instruksi khusus tersebut, dan ekstensi nol implisit ke 64 -bit tidak akan melakukan apa yang Anda butuhkan. Namun, jangan menghabiskan instruksi tambahan; ukuran operan 64-bit seringkali diperlukan, misalnya untuk peningkatan pointer.)
Tentu saja, untuk pembagian dengan konstanta waktu kompilasi, divadalah opsi lambat yang dihindari compiler sepenuhnya, alih-alih menggunakan pembalikan perkalian titik tetap. Seperti di Mengapa GCC menggunakan perkalian dengan bilangan ganjil dalam menerapkan pembagian integer? di SO, atau review kode ini .
Selain itu, Anda tidak perlu membagi sama sekali jika Anda menggunakan penghitung mundur yang Anda setel ulang ke 3 atau 5 saat mereka menekan 0 (dan / atau membuka gulungan) untuk menangani pola 3, 5, seperti FizzBuzz - lihat jawaban Stack Overflow ini di mana saya menulis tutorial besar tentang teknik semacam itu, yang tidak akan saya ulangi di sini. Tidak seperti FizzBuzz, Anda hanya ingin menghitung angka sekali meskipun itu adalah kelipatan 3 dan 5.
Anda bisa membuka gulungan hingga 15 (sehingga polanya terulang sepenuhnya) dan kode keras seperti
.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
Atau terapkan beberapa matematika dan alih-alih benar-benar melihat setiap angka, gunakan rumus bentuk tertutup untuk jumlah dari kelipatan 3 dan 5 dalam rentang 15 angka, diimbangi dengan di i * nmulsmana iawal rentang Anda, dan nmulsadalah angkanya kelipatan.
misalnya dalam [60, 75)rentang tersebut, kami memiliki 60, 63, 65, 66, 69, 70, 72. Jadi itu 8 dari 15 angka. Jadi seperti [0, 15)tapi + 8*60. Lakukan bagian 0..14 dengan tangan, atau dengan satu putaran dan ingat hasilnya. (Project Euler adalah tentang matematika dan juga pemrograman; terserah Anda seberapa banyak matematika yang ingin Anda lakukan vs. berapa banyak kekuatan kasar yang Anda ingin program Anda lakukan.)
Mudahnya, 8 kebetulan menjadi salah satu faktor skala yang didukung oleh mode pengalamatan x86, jadi kita bahkan bisa melakukannya
lea eax, [rax + rcx*8 + 0 + 3 + 5 + 6 + 9 + 10 + 12]
(3 + 5 + 6 + ... adalah ekspresi konstan sehingga assembler dapat melakukannya untuk Anda pada waktu assembler, menghasilkan [reg + reg*scale + disp8]mode pengalamatan. Sayangnya, LEA 3-komponen memiliki latensi 3-siklus pada CPU Intel, dan loop- dependensi yang dibawa akan menjadi penghambat untuk loop. Jadi sebenarnya akan lebih efisien untuk menggunakan addinstruksi terpisah .)
Dan tentu saja kita telah mereduksi ini pada dasarnya menjadi jumlah deret yang meningkat secara linier, dan dapat menerapkan rumus Gauss ( n * (n+1) / 2) untuk bentuk tertutup di seluruh rentang interval, hanya harus menangani pembersihan n%15untuk bilangan yang mendekat n. BTW, dentang tahu cara mengubah loop for sederhana sum += i;ke dalam bentuk tertutup, mengaturnya untuk menghindari luapan sementara sebelum membaginya dengan 2. (shift kanan). CppCon2017 Matt Godbolt berbicara “Apa yang Telah Dilakukan Kompiler Saya untuk Saya Akhir-akhir ini? Unbolting the Compiler Lid ” menggunakannya sebagai contoh. Lihat jugahttps://stackoverflow.com/questions/38552116/how-to-remove-noise-from-gcc-clang-assembly-output
Gunakan instruksi pemindahan bersyarat jika sesuai
Untuk memperluas diskusi dalam jawaban oleh @Edward : jika Anda dapat menggunakan instruksi pemindahan bersyarat, itu akan mengurangi jumlah percabangan dan dengan demikian membantu prosesor.
Jika Anda menggabungkan dengan saran untuk mempertahankan penghitung modulo 3 dan modulo 5 alih-alih melakukan pembagian, maka garis besar badan perulangan utama akan terlihat seperti ini (meskipun belum teruji):
%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
(Perhatikan bahwa untuk mencocokkan nilai awal 0 untuk penghitung, Anda perlu menginisialisasi mod3_regke 2 dan mod5_reg4. Jika Anda menyesuaikan untuk memulai dengan 1, sebaliknya, Anda dapat menginisialisasi keduanya ke 0 yang akan menjadi a sedikit lebih sederhana.)
Perhatikan juga bahwa menurut beberapa komentar oleh @PeterCordes, mungkin ada masalah dengan cmovmembuat dependensi ekstra yang cukup dalam loop sehingga mungkin tidak sepadan. Ini akan menjadi kasus di mana, jika Anda sangat peduli dengan kinerja, menjalankan tolok ukur pada mesin target Anda akan menjadi penting.