Optimasi dan penguatan

Putaran soa, putaran alokator, dan pemrofilan pada proyek.

Daftar isi

Proyek yang sudah berjalan tetap memerlukan perbaikan, dan perbaikan itu paling aman dilakukan dalam putaran kecil yang disiplin. Topik ini memperkuat proyek simulasi populasi kelinci yang dibangun pada topik Rancang data lebih dahulu melalui tiga putaran, yaitu putaran tata letak kolom dengan #soa, putaran alokator dengan reservasi kapasitas, dan putaran pengukuran waktu sebelum serta sesudah perubahan. Setiap putaran mengubah satu hal saja, menempel angka keluaran nyata pada keputusannya, lalu berakhir dengan keputusan mempertahankan atau membatalkan perubahan tersebut. Setelah tiga putaran selesai, setiap klaim performa pada proyek memiliki angka yang dapat diaudit ulang.

Tiga putaran penguatan#

Putaran penguatan adalah siklus perbaikan yang dibatasi pada satu perubahan per putaran. Batasan ini bukan formalitas, melainkan cara menjaga penyebab selisih tetap tunggal, karena putaran yang mengubah tata letak sekaligus strategi alokasi tidak dapat diputuskan hanya dari kenaikan angkanya. Pola kerja ini sama untuk semua putaran, yaitu mengukur keadaan sebelum perubahan, menerapkan satu perubahan, mengukur keadaan sesudah dengan cara yang sama persis, lalu mencatat keputusan bersama angkanya.

Tiga putaran pada topik ini menaikkan tingkat abstraksi secara bertahap. Putaran pertama mengubah tata letak data populasi menjadi kolom dengan #soa agar perulangan pada populasi besar tidak menyeret field yang tidak dibaca. Putaran kedua mengubah strategi alokasinya dari pertumbuhan per entri menjadi reservasi kapasitas awal melalui proc bawaan reserve, dengan jumlah permintaan alokasi sebagai angka ukurannya. Putaran ketiga tidak mengubah perilaku sama sekali, melainkan membandingkan waktu traversal pada tata letak baris dan kolom menggunakan time.tick_now dan time.tick_since, sehingga keputusan tata letak pada putaran pertama diuji ulang dengan angka waktunya.

Putaran pertama: tata letak kolom dengan #soa#

Tata letak kolom dipilih ketika perulangan hanya membaca sebagian kecil field dari banyak elemen, dan populasi besar proyek kelinci memenuhi pola itu. Perulangan penuaan dan perulangan statistik hanya menyentuh field umur dan status, sedangkan nomor, jenis, dan generasi tidak dibaca sama sekali. Deklarasi populasi: #soa[dynamic]Kelinci menyatakan array dinamis yang menyimpan setiap field sebagai kolom tersendiri. Pemakaiannya tetap mirip array dinamis biasa, yaitu elemen ditambahkan melalui append dan diakses per elemen seperti populasi[i].umur, sedangkan seluruh kolom diakses langsung melalui ekspresi populasi.umur dan populasi.status.

Program berikut menerapkan tata letak itu pada simulasi lima generasi dengan populasi 50.000 entri. Isinya ditetapkan secara deterministik, yaitu umur awal i % 5 dan jenis kelamin bergantian, sehingga keluarannya tidak bergantung angka acak. Simpan berkasnya sebagai soa-kelinci.odin di dalam folder topik dan jalankan dari folder yang sama.

odin soa-kelinci.odin

package main

import "core:fmt"

Jenis_Kelamin :: enum u8 {
	Jantan,
	Betina,
}

Status_Hidup :: enum u8 {
	Hidup,
	Mati,
}

Kelinci :: struct {
	nomor:    u32,
	umur:     u8,
	jenis:    Jenis_Kelamin,
	status:   Status_Hidup,
	generasi: u8,
}

JUMLAH_POPULASI :: 50_000

// mutasi penuaan: perulangan hanya menyentuh field umur dan status,
// sedangkan nomor, jenis, dan generasi tidak dibaca sama sekali
jalankan_generasi :: proc(populasi: ^#soa[dynamic]Kelinci) -> (mati: int) {
	for i in 0 ..< len(populasi^) {
		if populasi[i].status == .Hidup {
			populasi[i].umur += 1
			if populasi[i].umur >= 5 {
				populasi[i].status = .Mati
				mati += 1
			}
		}
	}
	return
}

// statistik dibaca melalui akses kolom, bukan dengan menyusun struct utuh
hitung_statistik :: proc(populasi: #soa[]Kelinci) -> (hidup: int, jumlah_umur: i64) {
	umur := populasi.umur
	status := populasi.status
	for i in 0 ..< len(populasi) {
		if status[i] == .Hidup {
			hidup += 1
			jumlah_umur += i64(umur[i])
		}
	}
	return
}

main :: proc() {
	populasi: #soa[dynamic]Kelinci
	defer delete(populasi)

	// populasi awal berukuran besar dan isinya ditetapkan secara deterministik:
	// umur i % 5 dan jenis kelamin bergantian, sehingga satu kohort mati tiap generasi
	for i in 0 ..< JUMLAH_POPULASI {
		append(&populasi, Kelinci{
			nomor    = u32(i + 1),
			umur     = u8(i % 5),
			jenis    = Jenis_Kelamin(i % 2),
			status   = .Hidup,
			generasi = 0,
		})
	}

	fmt.printf("populasi awal: %v entri\n", len(populasi))
	for generasi in 1 ..= 5 {
		mati := jalankan_generasi(&populasi)
		hidup, jumlah_umur := hitung_statistik(populasi[:])
		fmt.printf("generasi %v: hidup %v dari %v entri, mati %v, jumlah umur hidup %v\n", generasi, hidup, len(populasi), mati, jumlah_umur)
	}
}

bash

# sumberkan lingkungan sandbox jalur odin bila belum tersedia
[ -f /home/kal/my-project/tools/env.sh ] && source /home/kal/my-project/tools/env.sh
# jalankan program dari dalam folder topik
odin run soa-kelinci.odin -file

text Keluaran

populasi awal: 50000 entri
generasi 1: hidup 40000 dari 50000 entri, mati 10000, jumlah umur hidup 100000
generasi 2: hidup 30000 dari 50000 entri, mati 10000, jumlah umur hidup 90000
generasi 3: hidup 20000 dari 50000 entri, mati 10000, jumlah umur hidup 70000
generasi 4: hidup 10000 dari 50000 entri, mati 10000, jumlah umur hidup 40000
generasi 5: hidup 0 dari 50000 entri, mati 10000, jumlah umur hidup 0

Keluaran menunjukkan populasi yang menyusut satu kohort per generasi. Umur awal berada di antara 0 dan 4, kelinci mati pada umur lima, sehingga kohort berumur 4 mati pada generasi pertama, disusul kohort berumur 3 pada generasi kedua, dan seterusnya hingga populasi habis pada generasi kelima. Nilai jumlah umur hidup turun mengikuti kohort yang tersisa, yaitu 100.000 pada generasi pertama karena empat kohort tersisa dengan umur 1 hingga 4. Yang penting bagi putaran ini bukan angka demografinya, melainkan kode yang menghasilkannya, yaitu proc mutasi membaca dan menulis melalui field per elemen, sedangkan proc statistik membaca dua kolom langsung tanpa menyusun struct utuh per elemen.

Putaran kedua: reservasi kapasitas dan pelacakan alokasi#

Tanpa reservasi, append memicu alokasi ulang setiap kali kapasitas terlampaui, yaitu blok baru dialokasikan, isi lama disalin, dan blok lama dilepas. Array dinamis #soa menyimpan seluruh kolomnya dalam satu blok, sehingga satu alokasi ulang berarti satu permintaan alokasi dan satu pelepasan. Jumlah permintaan itu terhitung secara persis menggunakan mem.Tracking_Allocator, yang membungkus alokator bawaan dan mencacah setiap permintaan pada field total_allocation_count. Program berikut mengisi populasi 50.000 entri tanpa reservasi, sehingga angka keluarannya menjadi keadaan sebelum pada putaran ini.

odin populasi-tumbuh.odin

package main

import "core:fmt"
import "core:mem"

Jenis_Kelamin :: enum u8 {
	Jantan,
	Betina,
}

Status_Hidup :: enum u8 {
	Hidup,
	Mati,
}

Kelinci :: struct {
	nomor:    u32,
	umur:     u8,
	jenis:    Jenis_Kelamin,
	status:   Status_Hidup,
	generasi: u8,
}

JUMLAH :: 50_000

isi_kelinci :: proc(i: int) -> Kelinci {
	return Kelinci{
		nomor    = u32(i + 1),
		umur     = u8(i % 5),
		jenis    = Jenis_Kelamin(i % 2),
		status   = .Hidup,
		generasi = 0,
	}
}

main :: proc() {
	ta: mem.Tracking_Allocator
	mem.tracking_allocator_init(&ta, context.allocator)
	defer mem.tracking_allocator_destroy(&ta)
	ctx_awal := context
	context.allocator = mem.tracking_allocator(&ta)
	defer context = ctx_awal

	// versi sebelum: populasi tumbuh per entri tanpa reservasi kapasitas
	populasi: #soa[dynamic]Kelinci
	for i in 0 ..< JUMLAH {
		append(&populasi, isi_kelinci(i))
	}
	defer delete(populasi)

	fmt.printf("entri  : %v, kapasitas akhir: %v\n", len(populasi), cap(populasi))
	fmt.printf("permintaan alokasi: %v\n", ta.total_allocation_count)
	fmt.printf("total byte dialokasikan: %v\n", ta.total_memory_allocated)
	fmt.printf("puncak memori hidup: %v byte\n", ta.peak_memory_allocated)
}

bash

# jalankan versi tanpa reservasi dari dalam folder topik
odin run populasi-tumbuh.odin -file

text Keluaran

entri  : 50000, kapasitas akhir: 65528
permintaan alokasi: 13
total byte dialokasikan: 1047616
puncak memori hidup: 524224 byte

Keluarannya memuat empat angka. Permintaan alokasi berjumlah 13, yaitu satu alokasi awal disusul dua belas alokasi ulang. Total byte dialokasikan mencakup seluruh blok yang pernah diminta, sedangkan puncak memori hidup hanya menghitung byte yang hidup bersamaan pada satu waktu, sehingga angkanya lebih kecil. Kapasitas akhir 65.528 dibulatkan ke atas melampaui 50.000 sesuai kebijakan pertumbuhan array dinamis.

Reservasi membalik urutannya, yaitu kapasitas penuh diminta sekali di awal sebelum satu pun entri diisi. Proc bawaan reserve(&populasi, JUMLAH) memperbesar cap tanpa mengubah len, sehingga pengisian tetap dilakukan melalui append yang tidak lagi memicu alokasi ulang. Bentuk lain yang setara adalah argumen kapasitas pada make, seperti make([dynamic]Kelinci, 0, JUMLAH) yang dipakai program kelinci pada rancangan awalnya. Program berikut mengisi populasi yang sama dengan satu reservasi di awal.

odin populasi-reservasi.odin

package main

import "core:fmt"
import "core:mem"

Jenis_Kelamin :: enum u8 {
	Jantan,
	Betina,
}

Status_Hidup :: enum u8 {
	Hidup,
	Mati,
}

Kelinci :: struct {
	nomor:    u32,
	umur:     u8,
	jenis:    Jenis_Kelamin,
	status:   Status_Hidup,
	generasi: u8,
}

JUMLAH :: 50_000

isi_kelinci :: proc(i: int) -> Kelinci {
	return Kelinci{
		nomor    = u32(i + 1),
		umur     = u8(i % 5),
		jenis    = Jenis_Kelamin(i % 2),
		status   = .Hidup,
		generasi = 0,
	}
}

main :: proc() {
	ta: mem.Tracking_Allocator
	mem.tracking_allocator_init(&ta, context.allocator)
	defer mem.tracking_allocator_destroy(&ta)
	ctx_awal := context
	context.allocator = mem.tracking_allocator(&ta)
	defer context = ctx_awal

	// versi sesudah: kapasitas penuh direservasi sekali sebelum pengisian
	populasi: #soa[dynamic]Kelinci
	reserve(&populasi, JUMLAH)
	for i in 0 ..< JUMLAH {
		append(&populasi, isi_kelinci(i))
	}
	defer delete(populasi)

	fmt.printf("entri  : %v, kapasitas akhir: %v\n", len(populasi), cap(populasi))
	fmt.printf("permintaan alokasi: %v\n", ta.total_allocation_count)
	fmt.printf("total byte dialokasikan: %v\n", ta.total_memory_allocated)
	fmt.printf("puncak memori hidup: %v byte\n", ta.peak_memory_allocated)
}

bash

# jalankan versi dengan reservasi dari dalam folder topik
odin run populasi-reservasi.odin -file

text Keluaran

entri  : 50000, kapasitas akhir: 50000
permintaan alokasi: 1
total byte dialokasikan: 400000
puncak memori hidup: 400000 byte

Perbandingan kedua keluaran menutup putaran ini. Permintaan alokasi turun dari 13 menjadi 1, total byte dialokasikan turun dari 1.047.616 menjadi 400.000, dan puncak memori hidup turun dari 524.224 menjadi 400.000 byte karena tidak ada lagi salinan blok lama yang hidup bersama blok baru. Angka-angka itu deterministik untuk program yang sama, sehingga perbaikan ini dapat diverifikasi ulang kapan pun dengan cara yang sama.

Putaran ketiga: waktu sebelum dan sesudah#

Keputusan tata letak pada putaran pertama diuji ulang dengan waktu. Yang dibandingkan adalah traversal statistik, yaitu menjumlahkan umur kelinci hidup, pada dua populasi identik berukuran 8.000.000 entri. Versi baris memakai []Kelinci, sedangkan versi kolom memakai #soa[]Kelinci dengan dua kolom yang diakses langsung. Kedua perulangan berindeks dengan pekerjaan yang sama persis, sehingga tata letak adalah satu-satunya variabelnya. Pola pengukurannya sama dengan yang dipakai pada topik Mengukur, bukan menduga, yaitu hangatkan sekali, ulangi lima belas kali, dan ambil median dengan time.tick_now serta time.tick_since.

odin ukur-tata-letak.odin

package main

import "core:fmt"
import "core:time"

Jenis_Kelamin :: enum u8 {
	Jantan,
	Betina,
}

Status_Hidup :: enum u8 {
	Hidup,
	Mati,
}

Kelinci :: struct {
	nomor:    u32,
	umur:     u8,
	jenis:    Jenis_Kelamin,
	status:   Status_Hidup,
	generasi: u8,
}

JUMLAH_UJI :: 8_000_000

// versi sebelum: tata letak baris, seluruh field satu elemen berdampingan
jumlah_baris :: proc(data: []Kelinci) -> (total: i64) {
	for i in 0 ..< len(data) {
		if data[i].status == .Hidup {
			total += i64(data[i].umur)
		}
	}
	return
}

// versi sesudah: tata letak kolom, perulangan menyentuh dua kolom saja
jumlah_kolom :: proc(data: #soa[]Kelinci) -> (total: i64) {
	umur := data.umur
	status := data.status
	for i in 0 ..< len(data) {
		if status[i] == .Hidup {
			total += i64(umur[i])
		}
	}
	return
}

// median lima belas durasi: nilai tengah setelah disalin dan diurutkan
median_15 :: proc(d: [15]time.Duration) -> time.Duration {
	a := d
	for i := 1; i < len(a); i += 1 {
		k := a[i]
		j := i - 1
		for j >= 0 && a[j] > k {
			a[j + 1] = a[j]
			j -= 1
		}
		a[j + 1] = k
	}
	return a[7]
}

// pola pengukuran: hangatkan sekali, ulangi lima belas kali, ambil median
ukur_baris :: proc(data: []Kelinci) -> time.Duration {
	jumlah_baris(data)
	d: [15]time.Duration
	for i := 0; i < 15; i += 1 {
		t := time.tick_now()
		jumlah_baris(data)
		d[i] = time.tick_since(t)
	}
	return median_15(d)
}

ukur_kolom :: proc(data: #soa[]Kelinci) -> time.Duration {
	jumlah_kolom(data)
	d: [15]time.Duration
	for i := 0; i < 15; i += 1 {
		t := time.tick_now()
		jumlah_kolom(data)
		d[i] = time.tick_since(t)
	}
	return median_15(d)
}

main :: proc() {
	// dua populasi identik: isi ditetapkan secara deterministik
	baris := make([]Kelinci, JUMLAH_UJI)
	defer delete(baris)
	kolom: #soa[dynamic]Kelinci
	defer delete(kolom)
	reserve(&kolom, JUMLAH_UJI)
	for i in 0 ..< JUMLAH_UJI {
		k := Kelinci{
			nomor    = u32(i + 1),
			umur     = u8(i % 5),
			jenis    = Jenis_Kelamin(i % 2),
			status   = Status_Hidup(i % 2),
			generasi = 0,
		}
		baris[i] = k
		append(&kolom, k)
	}

	d_baris := ukur_baris(baris)
	d_kolom := ukur_kolom(kolom[:])

	// biaya per elemen dalam nanodetik, dibulatkan ke bilangan bulat terdekat
	biaya_baris := (time.duration_nanoseconds(d_baris) + i64(JUMLAH_UJI) / 2) / i64(JUMLAH_UJI)
	biaya_kolom := (time.duration_nanoseconds(d_kolom) + i64(JUMLAH_UJI) / 2) / i64(JUMLAH_UJI)

	fmt.printf("elemen      : %d\n", JUMLAH_UJI)
	fmt.printf("total baris : %d\n", jumlah_baris(baris))
	fmt.printf("total kolom : %d\n", jumlah_kolom(kolom[:]))
	fmt.printf("biaya baris : %d ns per elemen\n", biaya_baris)
	fmt.printf("biaya kolom : %d ns per elemen\n", biaya_kolom)
}

bash

# jalankan program pengukuran dari dalam folder topik
odin run ukur-tata-letak.odin -file

text Keluaran

elemen      : 8000000
total baris : 8000000
total kolom : 8000000
biaya baris : 5 ns per elemen
biaya kolom : 4 ns per elemen

Dua baris total menjadi pemeriksaan kebenaran, karena kedua versi wajib menghasilkan jumlah yang sama sebelum angka waktunya dibaca. Dua baris biaya menunjukkan 5 nanodetik per elemen pada tata letak baris berbanding 4 nanodetik per elemen pada tata letak kolom. Durasi medianya tidak dicetak oleh program karena berubah-ubah antareksekusi, tetapi angkanya dapat dinyatakan di sini, yaitu pada eksekusi penulisan topik ini median baris tercatat sekitar 37 ms dan median kolom sekitar 35 ms. Biaya per elemen yang dibulatkan justru stabil pada kedua angka tersebut di seluruh eksekusi, sehingga kedua baris biaya itulah yang dipakai sebagai dasar keputusan.

Selisihnya kecil tetapi arahnya konsisten, dan penyebabnya sesuai dengan jumlah byte yang dilintasi. Perulangan kolom membaca dua kolom berukuran 8 MB masing-masing, sedangkan perulangan baris membaca seluruh array utuh berukuran 64 MB, sehingga byte yang berpindah dari memori hanya seperempat dari versi baris. Timer tidak dapat memastikan seberapa besar peran cache dalam selisih tersebut, dan itulah wilayah pemrofilan cache-miss yang menggunakan alat seperti perf. Keputusan putaran ini sederhana, yaitu perubahan tata letak dipertahankan karena angkanya mendukung, dan rancangan tidak diubah lebih jauh karena kebutuhan proyek sudah terlayani.

Etika optimasi#

Etika optimasi pada jalur ini dirangkum menjadi tiga kebiasaan yang saling menopang. Kebiasaan pertama adalah mengukur sebelum dan sesudah, karena perubahan yang tidak disertai kedua angka tersebut tidak dapat dinilai dampaknya. Kebiasaan kedua adalah membuat klaim yang selalu terukur, yaitu setiap pernyataan tentang kecepatan atau pemakaian memori menyebut kondisinya, meliputi jumlah entri dan konfigurasi build yang dipakai. Kebiasaan ketiga adalah berhenti saat cukup, yaitu optimasi berakhir ketika kebutuhan proyek sudah terlayani dan setiap tambahan perubahan mulai dibayar dengan kerumitan, bukan dengan kecepatan.

Ketiga kebiasaan itu juga menentukan apa yang dilakukan ketika angka tidak mendukung. Perubahan yang angka ukurnya memburuk atau netral dibatalkan, dan pembatalan itu bukan kegagalan, melainkan bagian dari putaran itu sendiri. Apabila selisih terlihat tetapi penyebabnya belum jelas, pemrofilan dilakukan lebih dahulu sebelum perubahan berikutnya, karena timer hanya menjawab berapa besar selisihnya. Dengan disiplin tersebut, proyek yang diperkuat selalu berada pada keadaan yang angkanya dapat dipertahankan di hadapan pengukuran ulang.

Ringkasan#

Penguatan proyek dijalankan sebagai putaran satu perubahan, dengan pengukuran sebelum dan sesudah sebagai dasar keputusan mempertahankan atau membatalkan.
Deklarasi #soa[dynamic]Kelinci menyimpan setiap field sebagai kolom, sehingga perulangan penuaan dan statistik pada populasi 50.000 entri hanya menyentuh kolom yang benar-benar dibaca.
Reservasi melalui reserve(&populasi, 50000) menurunkan permintaan alokasi dari 13 menjadi 1, dengan total byte dari 1.047.616 menjadi 400.000 dan puncak memori hidup dari 524.224 menjadi 400.000 byte.
Pengukuran waktu dengan time.tick_now dan time.tick_since menunjukkan biaya traversal 5 ns per elemen pada tata letak baris berbanding 4 ns pada tata letak kolom, dan keputusannya dicatat bersama angka tersebut.

Referensi#

Overview — Odin Documentation — Dokumentasi resmi bagian dynamic arrays dan SOA data types yang mencakup proc reserve, append, serta tipe #soa.
package time — pkg.odin-lang.org — Dokumentasi time.tick_now, time.tick_since, dan time.Duration yang dipakai pada putaran ketiga.
package mem — pkg.odin-lang.org — Dokumentasi Tracking_Allocator beserta field pencacah alokasi yang dipakai pada putaran kedua.