Pergi Tanpa Cabang

Diterbitkan: 3 Desember 2021

Sepertinya postingan saya sebelumnya berhasil dan banyak dari Anda telah mengirimkan solusi Anda sendiri melalui twitter. Sebelum saya melanjutkan untuk memilih hari lain sebagai tantangan, saya ingin melakukan sedikit tindak lanjut untuk hari 1-1.

Solusi Valentin Deleplace

Mari kita mulai dengan melihat kemenangannya larutan dari Valentin Deleplace yang mencapai hasil spektakuler 13.8 ns/op di mesin saya. Ini 6.5x lebih cepat dari milikku v3 solusi dan 23x lebih cepat dari milikku v1 🤯.

func Answer(input string) (int, error) {
	var prev int64 = -9999
	var increases int = -1

	val := int64(0)
	for p, N := 0, len(input); p < N; p++ {
		c := input(p)
		if c != '\n' {
			val = (val << 8) + int64(c)
		} else {
			if val > prev {
				increases++
			}
			prev = val
			val = 0
		}
	}
	if val > prev {
		increases++
	}
	return increases, nil
}

Saya tahu bahwa solusi saya tidak ideal, namun besarnya peningkatan masih mengejutkan saya. Jadi saya memutuskan untuk melihat lebih dekat untuk melihat bagaimana hal itu dilakukan:

Panggilan ke strings.IndexByte() telah dihentikan demi perulangan langsung pada masing-masing karakter masukan. Ini berfungsi dengan baik di sini karena rata-rata panjang garis sangat pendek (4 karakter) dan pemanggilan fungsi rakitan dari Go memiliki overhead yang tidak sepele terkait dengannya.
Tanpa diduga, isi fungsi tersebut sesuai dengan anggaran Go. Bangun dengan -gcflags="-m" jika Anda ingin memverifikasinya sendiri. Hal ini menghilangkan biaya tambahan untuk memanggil fungsi Answer di benchmark.
Perulangan input dilakukan tanpa menggunakan range pada string input yang menghindari overhead unicode.
Penguraian digit masukan secara langsung diintegrasikan ke dalam perulangan for dan menghindari pengulangan karakter tersebut dua kali.
val << 8 digunakan sebagai gantinya val*10. Ini berubah valtapi tidak merusak val > prev perbandingan.
Daripada menggunakan yang terpisah bool untuk menunjukkan apakah nilai sebelumnya telah terlihat, prev Dan increases diinisialisasi ke -9999 Dan -1 masing-masing merupakan permainan yang adil karena kami melihat para elf ragu-ragu untuk memberikan angka negatif kepada kami.
Penanganan kesalahan seperti pemeriksaan digit yang valid telah dihilangkan.

Yang terpenting, solusi Valentin jauh lebih kompak daripada solusi saya v3 dan tetap cukup mudah dibaca mengingat situasinya 👏.

Menurut pengalaman saya, optimasi kode selalu melibatkan banyak trial and error. Jadi menurut saya penting untuk menyadari bahwa ide pengoptimalan sering kali gagal dan mendiskusikan apa yang dapat kita pelajari dari kegagalan ini.

Salah satu kegagalan tersebut adalah upaya pertama saya untuk lebih mengoptimalkan solusi Valentin dengan menghilangkan cabang. Inspirasi saya untuk ini datang dari presentasi Parsing JSON Really Quickly: Lessons Learned karya Daniel Lemire serta Branchless Coding karya Matt Nakama di Go.

Saya belum pernah melakukan ini sebelumnya, jadi kode di bawah ini pasti bisa diperbaiki, tapi inilah yang saya hasilkan:

func Answer(input string) (int, error) {
	var prev int64 = -9999
	var increases int = -1

	val := int64(0)
	for p, N := 0, len(input); p < N; p++ {
		c := input(p)
		notNl := boolToInt64(c != '\n')
		increases += int((^notNl & 1) * boolToInt64(val > prev))
		prev = notNl*prev + val*(^notNl&1)
		val = notNl * ((val << 8) + int64(c))
	}
	increases += int(boolToInt64(val > prev))
	return increases, nil
}

func boolToInt64(b bool) int64 {
	return int64((*(*uint8)(unsafe.Pointer(&b))) & 1)
}

Ide intinya adalah untuk melakukan cast bool nilai-nilai ke dalam 0 atau 1 yang memungkinkan kita mengambil cabang seperti ini:

if c != '\n' {
  val = (val << 8) + int64(c)
} else {
  val = 0
}

Dan ubah menjadi ekspresi bebas cabang yang setara seperti yang ditunjukkan di bawah ini:

val = ((val << 8) + int64(c)) * boolToInt64(c != '\n')

Ini berfungsi karena kita selalu menghitung ekspresi dari cabang pertama dan kemudian mengalikannya dengan 1 jika cabang pertama harus diambil, atau 0 untuk cabang kedua sama settingnya val = 0 secara langsung.

Dan sementara boolToInt64(c != '\n') mungkin terlihat seperti mimpi buruk kompilasi, kompiler Go tampaknya mengeluarkan sesuatu yang relatif masuk akal (lihat https://godbolt.org/z/Tzr99vqr3):

CMPB    R8B, $10        ; compare c and '\n' (ASCII 10)
SETNE   "".b+5(SP)      ; store 1 on stack if c != '\n' otherwise 0
MOVBLZX "".b+5(SP), R9  ; move result from stack to register R9
ANDL    $1, R9          ; last part of int64((*(*uint8)(unsafe.Pointer(&b))) & 1

Dari sudut pandang saya, hal seperti ini akan lebih baik:

CMPB    R8B, $10        ; compare c and '\n' (ASCII 10)
SETNE   R9              ; store 1 in R9 if c != '\n' otherwise 0

Namun sayang sekali – saya tidak bisa mendapatkan kompiler untuk menghasilkan ini. Bagaimanapun, karena kita menghilangkan semua cabang, solusi kita seharusnya berjalan sangat cepat sekarang, bukan? Mari kita lihat:

$ benchstat v4-valentin.txt v5.txt 
name      old time/op  new time/op  delta
Answer-6  13.8ns ± 1%  77.1ns ± 0%  +460.24%  (p=0.008 n=5+5)

Aduh. Ternyata sedikit ilmu itu berbahaya 🤕. Awalnya saya cukup sedih dengan hal ini, karena saya telah berusaha keras untuk membuat semua kode “pintar” ini. Namun mengetahui bahwa mengelola emosi sering kali merupakan bagian tersulit – dan karena saat itu jam 3 pagi – saya memutuskan untuk mengakhirinya.

Saya akhirnya menebak-nebak masalahnya saat mengendarai sepeda keesokan harinya. Namun saya mungkin juga bisa mengetahuinya dengan melihat View -> Source output dari profil CPU yang ditunjukkan di bawah ini:

Seperti yang Anda lihat, kami menghabiskan cukup banyak waktu online 36 yang melakukan kondisi increases++ operasi.

Untuk memahami mengapa hal ini buruk, mari kita ingat data masukan yang kita gunakan:

Serta kode Valentin yang kami coba optimalkan:

if c != '\n' {
  val = (val << 8) + int64(c)
} else {
  if val > prev {
    increases++
  }
  prev = val
  val = 0
}

Seperti yang Anda lihat, semua baris memiliki 3 digit ditambah satu baris baru, sehingga peluang untuk berakhir di baris asli else blok saja 1/4. Untuk angka masukan yang lebih besar peluangnya akan lebih rendah lagi. Selain itu val > prev predikatnya harus truejadi eksekusi tanpa syarat kami increases++ operasi tidak memiliki peluang yang sangat baik untuk membuahkan hasil dalam banyak kasus.

Namun, kita tahu bahwa val > prev predikat dengan sendirinya adalah true 7 dari 10 kali, jadi mungkin kita bisa mengalahkan prediktor cabang CPU dengan membatasi diri kita hanya untuk menghilangkan cabang itu? Kode untuk ini ditunjukkan di bawah ini:

func Answer(input string) (int, error) {
	var prev int64 = -9999
	var increases int = -1

	val := int64(0)
	for p, N := 0, len(input); p < N; p++ {
		c := input(p)
		if c != '\n' {
			val = (val << 8) + int64(c)
		} else {
			increases += int(boolToInt64(val > prev))
			prev = val
			val = 0
		}
	}
	if val > prev {
		increases++
	}
	return increases, nil
}

func boolToInt64(b bool) int64 {
	return int64((*(*uint8)(unsafe.Pointer(&b))) & 1)
}

Mari kita lihat perbandingannya dengan solusi asli Valentin:

benchstat v4-valentin.txt v6.txt .txt 
name      old time/op  new time/op  delta
Answer-6  13.8ns ± 1%  12.7ns ± 2%  -7.91%  (p=0.008 n=5+5)

Luar biasa, sepertinya kita menghemat nanodetik lagi yang akan diubah oleh para elf menjadi hadiah untuk anak-anak!

Baiklah, itu saja untuk hari ini. Saya harap ini menyenangkan dan saya akan segera meluangkan waktu untuk membuat postingan tentang tantangan AoC lainnya.

Terima kasih telah membaca ini!

Lampiran: FAQ

Saya membayangkan kode bebas cabang di atas menimbulkan beberapa alis. Untuk menghindari kesalahpahaman, izinkan saya mencoba menjawab beberapa pertanyaan yang mungkin Anda miliki:

Apakah Anda merekomendasikan untuk menulis kode Go seperti ini?

Sama sekali tidak. Saya suka menggunakan munculnya kode untuk menjelajah dan belajar. Harap jangan menulis kode produksi seperti ini kecuali “Anda tahu apa yang Anda lakukan”™️. Saya pasti tidak akan menganggap diri saya termasuk dalam grup ini :).

Apakah ini akan berfungsi untuk distribusi data yang berbeda?

Mungkin tidak! Kode ini dioptimalkan untuk input sampel kecil yang digunakan oleh AoC untuk menjelaskan masalahnya.

Mengapa Anda tidak mengimplementasikan algoritma dalam perakitan saja?

Itu mungkin menyenangkan! Namun untuk kemunculan kode tahun ini, saya rasa saya hanya akan menggunakan assembly jika ada di stdlib Go.

–Felix Geisendörfer

Berlangganan blog ini melalui RSS atau E-Mail atau dapatkan pembaruan kecil dari saya melalui Twitter.

Source link

Pergi Tanpa Cabang · Felix Geisendörfer

Solusi Valentin Deleplace