Array secara Mendalam

Array multidimensi di Julia disimpan sebagai satu blok memori linear dengan tata letak column-major, yakni urutan kolom demi kolom. Topik ini membahas Array{T,2} atau Matrix, akibat tata letak tersebut terhadap pengindeksan dan pemotongan (slicing), serta perbedaan antara penyalinan dengan copy dan penunjukan dengan view. Setelah topik ini dipraktikkan, posisi setiap elemen di memori dapat dihitung, dan pilihan antara menyalin data dan hanya menunjuknya dapat ditentukan secara sadar.

Tata letak column-major#

Matriks di Julia merupakan objek Array{T,2}, yaitu array dua dimensi dengan tipe elemen T, dan Matrix{Int} merupakan alias dari Array{Int,2}. Meskipun ditampilkan sebagai tabel baris dan kolom, datanya diletakkan pada memori yang bersifat linear. Aturan penempatannya disebut column-major, yaitu elemen kolom pertama menempati alamat terdepan, dilanjutkan kolom kedua, dan seterusnya. Susunan ini diwarisi dari Fortran dan berbeda dengan C yang mengurutkan per baris.

Fungsi vec mengungkap urutan memori tersebut karena mengubah array menjadi vektor dengan membaca data persis sebagaimana tersimpan, tanpa menyalin isi.

A = [11 12 13; 21 22 23]
println(A)
println(size(A))
println(vec(A))

[11 12 13; 21 22 23]
(2, 3)
[11, 21, 12, 22, 13, 23]

Keluaran vec(A) berisi 11, 21, 12, 22, 13, 23, sehingga urutan memorinya adalah seluruh kolom pertama, kemudian kolom kedua, dan seterusnya. Pola ini menjadi dasar bagi aturan pengindeksan linear pada bagian berikutnya.

Membaca elemen yang berdempetan dalam satu kolom berarti membaca alamat memori yang berurutan, dan pola akses semacam itu memanfaatkan cache secara efektif. Sebaliknya, pembacaan yang melompat antarkolom mengunjungi alamat yang berjauhan sehingga lebih lambat. Aturan sederhananya, susun perulangan sehingga indeks kolom berada pada perulangan terdalam.

Menghitung indeks linear#

Setiap elemen matriks dapat diakses melalui dua indeks, yaitu indeks kartesian A[i, j] dan indeks linear A[k] yang menunjuk langsung ke urutan memori. Untuk matriks dengan m baris, keduanya terhubung oleh rumus berikut.

Rumus tersebut dapat dibaca terbalik, yaitu indeks kartesian dihitung dari indeks linear dengan membagi k oleh m. Kata kunci end berarti indeks terakhir pada dimensi yang bersangkutan, sehingga A[end, 1] menunjuk baris terakhir pada kolom pertama.

A = [11 12 13; 21 22 23]
println(A[2, 3])
println(A[6])
println(A[end, 1])
println(A[2, end])

23
23
21
23

Berkas berikut mencetak peta lengkap indeks kartesian ke indeks linear untuk matriks 2x3 yang sama, sehingga rumusnya dapat diverifikasi untuk setiap sel.

# peta-memori.jl
# Mencetak peta indeks kartesian ke indeks linear untuk matriks 2x3.

A = [11 12 13; 21 22 23]
m, n = size(A)

println("A = ", A)
println("vec(A) = ", vec(A))
println()
println("Peta indeks (i, j) ke k = i + (j - 1) * m:")
for j in 1:n, i in 1:m
    k = i + (j - 1) * m
    println("A[", i, ", ", j, "] = A[", k, "] = ", A[i, j])
end

A = [11 12 13; 21 22 23]
vec(A) = [11, 21, 12, 22, 13, 23]

Peta indeks (i, j) ke k = i + (j - 1) * m:
A[1, 1] = A[1] = 11
A[2, 1] = A[2] = 21
A[1, 2] = A[3] = 12
A[2, 2] = A[4] = 22
A[1, 3] = A[5] = 13
A[2, 3] = A[6] = 23

Diagram berikut menggambarkan pemetaan yang sama, yaitu setiap kolom matriks 2x3 dipindahkan ke pita memori secara berurutan sesuai warna kolomnya.

Pengindeksan linear juga menjadi bahasa pertukaran dengan pustaka numerik tingkat rendah, karena fungsi BLAS dan LAPACK menerima data berupa satu blok memori dengan panjang tertentu. Prediksi posisi memori membuat pemotongan kolom seperti A[:, j] menghasilkan vektor yang elemennya berdempetan, sedangkan pemotongan baris A[i, :] mengambil elemen yang terpencar dengan jarak tetap sebesar m posisi. Kedua bentuk pemotongan itu benar secara hasil, tetapi berbeda pola akses memorinya.

Pemotongan menyalin, view menunjuk#

Ekspresi pemotongan seperti A[:, 2:3] membentuk array baru berisi salinan data yang dipotong. Array hasil berdiri sendiri, sehingga perubahan padanya tidak pernah memengaruhi matriks induknya.

A = [11 12 13; 21 22 23]
B = A[:, 2:3]
B[1, 1] = 99
println(B)
println(A)

[99 13; 22 23]
[11 12 13; 21 22 23]

Perilaku tersebut aman, tetapi mahal apabila data hanya akan dibaca. Makro @view atau fungsi view() membuat view, yaitu objek ringan yang menunjuk ke memori array induk tanpa menyalin apa pun. Karena view dan induknya berbagi data yang sama, perubahan pada view langsung terlihat oleh induknya.

A = [11 12 13; 21 22 23]
V = @view A[:, 2]
V[1] = 99
println(V)
println(A)

[99, 22]
[11 99 13; 21 22 23]

Perbedaan alokasinya dapat diukur dengan makro @allocated, yang menghitung jumlah byte yang dialokasikan oleh satu ekspresi. Pengukuran dilakukan setelah pemanasan (warm-up), yaitu setiap ekspresi dipanggil sekali terlebih dahulu agar biaya kompilasi pertama tidak ikut terhitung.

using Random

A = rand(MersenneTwister(7), 200, 200)
copy(A)
A[:, 5]
v = @view A[:, 5]

alok_copy = @allocated copy(A)
alok_view = @allocated(@view A[:, 5])

println("copy mengalokasikan ulang seluruh data: ", alok_copy > 300000)
println("view hanya menyimpan penunjuk:          ", alok_view < 100)

copy mengalokasikan ulang seluruh data: true
view hanya menyimpan penunjuk:          true

Salinan copy(A) untuk matriks 200x200 bertipe Float64 membutuhkan 320000 byte data baru, sedangkan view tidak menyentuh data sama sekali dan hanya membentuk objek penunjuk kecil. Aturan praktisnya, gunakan pemotongan biasa apabila salinan memang diinginkan, dan gunakan @view apabila data besar hanya dibaca atau ditulis sebagian.

Kedua perilaku itu saling melengkapi. Salinan membutuhkan waktu dan memori tambahan, tetapi hasilnya aman untuk diubah tanpa menyentuh data lain. View jauh lebih murah, tetapi perubahannya menjalar ke induk, dan view juga membuat data induk tetap tersimpan di memori selama view tersebut masih dirujuk. Pertimbangan keduanya menjadi rutinitas ketika array berukuran besar diproses dalam beberapa tahap.

Kesalahan umum#

Kesalahan berikut sering muncul saat pengindeksan array multidimensi dipraktikkan. Yang pertama dapat direproduksi dan ditangkap pada contoh berikut.

A = [11 12 13; 21 22 23]
try
    println(A[3, 1])
catch e
    println(typeof(e), ": indeks di luar batas matriks ", size(A))
end

BoundsError: indeks di luar batas matriks (2, 3)

• Mengira urutan memori mengikuti baris seperti pada C. Akibatnya A[3] dianggap elemen baris ketiga, padahal pada matriks 2x3 indeks linear itu menunjuk A[1, 2]. Perbaikannya dengan menghitung ulang menggunakan rumus $k = i + (j - 1) \times m$ atau memeriksa vec(A).
• Mengedit hasil pemotongan sambil mengira matriks induk ikut berubah, atau sebaliknya. Pemotongan menghasilkan salinan, sehingga sinkronisasi tidak pernah terjadi. Gunakan @view hanya apabila pembaruan pada induk memang diinginkan.
• Menyusun perulangan baris lebih dahulu pada array besar. Pembacaan yang melompati memori mengurangi efektivitas cache, sedangkan perulangan kolom lebih dahulu mengikuti urutan penyimpanan dan berjalan lebih cepat.

Ringkasan#

• Array dua dimensi disimpan linear dengan urutan column-major, dan vec(A) menampilkan urutan memori tersebut apa adanya.
• Indeks kartesian A[i, j] dan indeks linear A[k] terhubung oleh rumus $k = i + (j - 1) \times m$, dengan end menunjuk indeks terakhir suatu dimensi.
• Pemotongan seperti A[:, 2:3] menyalin data ke array baru, sedangkan @view dan view() membentuk penunjuk yang berbagi memori dengan induknya.
• @allocated setelah pemanasan menunjukkan bahwa copy mengalokasikan ulang seluruh data, sedangkan view hampir tidak mengalokasikan apa pun.

Referensi#

• Arrays — The Julia Language — Mendokumentasikan pengindeksan array, vec, view, dan fungsi pemotongan lainnya.
• Performance Tips — The Julia Language — Menjelaskan pentingnya mengakses array searah kolom serta pemakaian view untuk menghemat alokasi.