KAL
Menu

Iterasi ramah cache

Traversal row-major serta pemisahan field panas dan dingin.

Daftar isi

Perpindahan data antara memori utama dan cache berlangsung dalam unit tetap, sehingga cara program menyusuri data menentukan berapa banyak byte yang benar-benar terpakai. Topik ini membahas baris cache (cache line) sebagai unit transfer memori, urutan traversal pada array dua dimensi, serta pemisahan field panas dan field dingin ke struct tersendiri. Setelah topik ini dibaca, perulangan dapat disusun sehingga setiap baris cache yang ditarik dari memori terpakai penuh, dan struct dapat dipilah agar field yang sering dibaca berdampingan dalam memori.

Baris cache sebagai unit transfer memori#

CPU tidak membaca memori satu byte demi satu byte. Jalur antara memori utama dan cache beroperasi dalam potongan tetap yang disebut baris cache, dan ukuran yang lazim pada CPU saat ini adalah 64 byte. Apabila program membaca satu byte, seluruh baris cache yang memuat byte tersebut ikut dipindahkan ke cache. Transfer pertama ke sebuah baris berbiaya tinggi karena data harus datang dari memori utama, sedangkan pembacaan berikutnya pada baris yang sama cepat karena data sudah berada di cache.

Satu baris cache berukuran 64 byte menampung 16 nilai f32 atau 8 nilai f64. Program yang membaca elemen secara berurutan membagi biaya transfer ke seluruh isi baris, sehingga satu transfer melayani 16 elemen sekaligus. Sebaliknya, program yang melompat dari satu baris ke baris lain membayar satu transfer penuh untuk memakai sebagian kecil isinya. Untuk mendukung pola berurutan, CPU memiliki prefetcher, yaitu rangkaian yang mengamati aliran alamat dan menarik baris-baris berikutnya sebelum perulangan memintanya. Prefetcher hanya dapat meramal pola yang teratur, dan tata letak data di memori menentukan seberapa teratur pola alamatnya.

Traversal baris demi baris dan kolom demi kolom#

Array dua dimensi Odin tersimpan secara row-major, yaitu seluruh elemen baris pertama berdampingan, disusul baris kedua, dan seterusnya. Elemen pada baris i dan kolom j berjarak dari awal array sebagai berikut:

jarak(i,j)=(i×kolom+j)×4 byte \text{jarak}(i, j) = (i \times \text{kolom} + j) \times 4\ \text{byte}

Karena satu baris matriks dengan 1024 kolom berukuran 4096 byte, indeks \(i \times \text{kolom} + j\) bertambah satu setiap langkah pada perulangan baris, sedangkan perulangan kolom menaikkannya 1024 dalam satu langkah, sehingga alamat melompat 4096 byte. Program berikut membandingkan kedua urutan pada matriks 1024 × 1024 berisi f32. Matriks dideklarasikan sebagai variabel global agar menempati segmen data, bukan stack. Program mencetak ukuran matriks, jumlah baris cache yang memuatnya, serta jarak alamat antarelemen berturutan pada tiap urutan. Program kemudian menjumlahkan seluruh elemen dengan kedua urutan untuk membuktikan bahwa data yang dibaca sama persis.

odin main.odin 
package main

import "core:fmt"

BARIS :: 1024
KOLOM :: 1024

matriks: [BARIS][KOLOM]f32

main :: proc() {
	// nilai bulat agar penjumlahan tetap eksak pada kedua urutan
	for i in 0 ..< BARIS {
		for j in 0 ..< KOLOM {
			matriks[i][j] = f32((i + j) % 97)
		}
	}

	fmt.println("ukuran matriks =", size_of(type_of(matriks)), "byte")
	fmt.println("jumlah baris cache =", size_of(type_of(matriks)) / 64)
	fmt.println("langkah alamat urutan baris =", uintptr(&matriks[0][1]) - uintptr(&matriks[0][0]), "byte")
	fmt.println("langkah alamat urutan kolom =", uintptr(&matriks[1][0]) - uintptr(&matriks[0][0]), "byte")

	// penjumlahan baris demi baris: alamat naik 4 byte per langkah
	total_baris: u64
	for i in 0 ..< BARIS {
		for j in 0 ..< KOLOM {
			total_baris += u64(matriks[i][j])
		}
	}

	// penjumlahan kolom demi kolom: alamat melompat 4096 byte per langkah
	total_kolom: u64
	for j in 0 ..< KOLOM {
		for i in 0 ..< BARIS {
			total_kolom += u64(matriks[i][j])
		}
	}

	fmt.println("total urutan baris =", total_baris)
	fmt.println("total urutan kolom =", total_kolom)
}
bash 
odin run main.odin -file
text Keluaran 
ukuran matriks = 4194304 byte
jumlah baris cache = 65536
langkah alamat urutan baris = 4 byte
langkah alamat urutan kolom = 4096 byte
total urutan baris = 50340893
total urutan kolom = 50340893

Keluaran menunjukkan bahwa kedua urutan membaca data yang sama, sehingga total keduanya sama persis, tetapi jarak alamatnya berbeda jauh. Pada urutan baris, alamat bertambah 4 byte setiap langkah, sehingga satu baris cache melayani 16 elemen berurutan. Pada urutan kolom (column-major traversal), alamat melompat 4096 byte setiap langkah, sehingga setiap elemen menuntut baris cache baru dan hanya memakai 4 dari 64 byte yang dipindahkan.

Mengapa urutan traversal memengaruhi prefetcher#

Prefetcher mengenali aliran alamat yang bergerak maju dengan langkah tetap dan kecil. Pada urutan baris, langkah 4 byte membuat ramalan prefetcher tepat, sehingga baris berikutnya sudah menunggu di cache ketika perulangan memintanya dan latensi memori utama tertutupi. Pada urutan kolom, langkah 4096 byte berada di luar pola yang banyak prefetcher mampu ikuti, sebab ramalan juga umumnya dihentikan ketika melewati batas halaman 4 KB. Setiap elemen kemudian menunggu transfer baris cache penuh yang isinya hampir tidak terpakai, dan perpindahan halaman pada setiap langkah menekan TLB, cache kecil yang menyimpan terjemahan alamat halaman.

Efek itu dapat diukur langsung. Pada sandbox ini, penjumlahan dengan urutan baris selesai sekitar 5 ms per penyapuan, sedangkan urutan kolom sekitar 13 ms, dengan data dan jumlah operasi yang sama persis. Angka pasti berbeda antaramesin, tetapi kesannya konsisten karena perbedaannya berasal dari urutan akses memori, bukan dari aritmetikanya.

Pengukuran sebaiknya dilakukan pada build default seperti contoh di atas. Build dengan pengoptimalan -o:speed dapat mengubah bentuk perulangan, misalnya menjumlahkan kolom melalui instruksi vektor, sehingga selisih yang tampak mengecil meskipun pola akses memori pada kode sumber tetap sama.

Field panas dan field dingin#

Perulangan yang sama juga diuntungkan oleh susunan field di dalam struct. Field panas adalah field yang dibaca pada setiap iterasi perulangan, sedangkan field dingin hanya sesekali dibaca, misalnya saat pelaporan atau penyuntingan. Apabila keduanya menyatu dalam satu struct, setiap iterasi menarik baris cache yang memuat semuanya, padahal perulangan hanya memakai field panasnya. Biaya itu berlipat ketika struct disimpan dalam jumlah besar sebagai array.

Contoh berikut diambil dari pencatatan sensor suhu. Struct Pencatatan menyimpan waktu pembacaan, suhu, lokasi sensor, dan catatan. Perulangan panas hanya menjumlahkan suhu, yaitu satu field f32, tetapi size_of(Pencatatan) menunjukkan bahwa satu elemen menempati 48 byte. Ukuran struct dan posisi field semacam ini dapat diverifikasi dengan size_of dan offset_of, proc yang dijelaskan pada topik struct.

odin panas-dingin.odin 
package main

import "core:fmt"

JUMLAH :: 1_000_000

// field panas (suhu) dan field dingin (waktu, lokasi, catatan) menyatu
Pencatatan :: struct {
	waktu:   u64,
	suhu:    f32,
	lokasi:  string,
	catatan: string,
}

// field dingin dipindahkan ke struct tersendiri
Rincian :: struct {
	waktu:   u64,
	lokasi:  string,
	catatan: string,
}

main :: proc() {
	fmt.println("Pencatatan: ukuran =", size_of(Pencatatan), "byte")
	fmt.println("offset suhu =", offset_of(Pencatatan, suhu), "offset lokasi =", offset_of(Pencatatan, lokasi))
	fmt.println("Rincian: ukuran =", size_of(Rincian), "byte")

	menyatu := make([]Pencatatan, JUMLAH)
	suhu := make([]f32, JUMLAH)
	rincian := make([]Rincian, JUMLAH)
	for i in 0 ..< JUMLAH {
		menyatu[i].suhu = f32(i % 100)
		suhu[i] = f32(i % 100)
		rincian[i].waktu = u64(i)
	}

	// penyapuan panas pada tata letak menyatu
	total_menyatu: u64
	for i in 0 ..< JUMLAH {
		total_menyatu += u64(menyatu[i].suhu)
	}

	// penyapuan panas pada tata letak terpisah
	total_terpisah: u64
	for i in 0 ..< JUMLAH {
		total_terpisah += u64(suhu[i])
	}

	fmt.println("total suhu menyatu  =", total_menyatu)
	fmt.println("total suhu terpisah =", total_terpisah)
	fmt.println("byte per penyapuan menyatu  =", size_of(Pencatatan) * JUMLAH)
	fmt.println("byte per penyapuan terpisah =", size_of(f32) * JUMLAH)

	delete(menyatu)
	delete(suhu)
	delete(rincian)
}
bash 
odin run panas-dingin.odin -file
text Keluaran 
Pencatatan: ukuran = 48 byte
offset suhu = 8 offset lokasi = 16
Rincian: ukuran = 40 byte
total suhu menyatu  = 49500000
total suhu terpisah = 49500000
byte per penyapuan menyatu  = 48000000
byte per penyapuan terpisah = 4000000

Keluaran memperlihatkan pemisahannya. Field panas suhu dipindahkan ke array f32 tersendiri, sedangkan field dingin membentuk struct Rincian yang arraynya tidak pernah disentuh perulangan panas. Total yang dihitung sama persis pada kedua tata letak, tetapi byte per penyapuan turun dari 48.000.000 byte menjadi 4.000.000 byte, karena perulangan panas hanya menarik baris cache yang memuat field yang ia pakai.

Pengukuran pada sandbox ini mencatat penyapuan menyatu sekitar 5 ms dan penyapuan terpisah sekitar 4 ms pada build default. Selisihnya tampak kecil karena kedua array baru saja ditulis, sehingga sebagian masih berada di cache. Pola yang lebih nyata muncul pada program berumur panjang, ketika array rincian yang besar tidak lagi muat di cache dan perulangan panas tidak pernah menariknya.

Ringkasan#

  • Memori dipindahkan ke cache dalam baris cache 64 byte, sehingga pembacaan berurutan membagi satu transfer ke 16 nilai f32, sedangkan akses melompat membayar transfer penuh untuk sebagian kecil isinya.
  • Array dua dimensi Odin tersimpan row-major, sehingga perulangan baris lalu kolom menghasilkan alamat yang bertambah secara tetap dan mudah diramal prefetcher, sedangkan urutan kolom melompat 4096 byte per langkah.
  • Field yang dibaca setiap iterasi sebaiknya dipisah dari field yang jarang dibaca, karena perulangan panas pada tata letak terpisah menyapu jauh lebih sedikit byte.
  • size_of dan offset_of dari topik struct digunakan untuk memverifikasi ukuran struct dan posisi field sebelum pemisahan dilakukan.

Referensi#