Struct of arrays

Satu kumpulan data dengan field yang sama dapat disusun di memori dengan dua tata letak yang berbeda, yaitu seluruh field satu elemen berdampingan atau setiap field menjadi array tersendiri. Topik ini membandingkan keduanya, yaitu array of structs (AoS) dengan tata letak baris dan struct of arrays (SoA) dengan tata letak kolom, kemudian memperkenalkan tipe #soa bawaan Odin beserta proc soa_zip dan soa_unzip untuk konversi di antara keduanya. Contoh yang dipakai adalah data empat sensor suhu dengan field suhu dan aktif. Setelah topik ini dibaca, pemilihan tata letak dapat dilandasi ukuran memori dan pola aksesnya, bukan sekadar kebiasaan menulis.

Dua tata letak penyimpanan: baris dan kolom#

Tata letak array of structs, atau tata letak baris, menyimpan setiap elemen sebagai satu nilai struct utuh, sehingga field-field satu elemen menempati alamat yang berdekatan. Bentuk ini adalah perilaku bawaan array biasa seperti [4]Sensor, dan kebanyakan program menuliskannya tanpa pertimbangan khusus karena bentuknya mengikuti cara data dinyatakan di dalam kode. Pada data empat sensor, memori berisi suhu dan aktif sensor pertama, disusul suhu dan aktif sensor kedua, dan seterusnya hingga elemen terakhir.

Tata letak struct of arrays, atau tata letak kolom, memecah struct yang sama menjadi array terpisah, satu array untuk setiap field. Kolom suhu berisi empat nilai f32 yang berdampingan, sedangkan kolom aktif berisi empat nilai bool yang berdampingan. Kedua tata letak memuat data yang sama persis, tetapi urutan byte di memori berbeda, sehingga biaya membacanya pun berbeda. Diagram berikut membandingkan keduanya untuk data empat sensor.

Perbedaan biayanya muncul ketika cache prosesor terlibat. Cache memindahkan memori dalam blok tetap yang disebut cache line, lazimnya sebesar 64 byte, sehingga membaca satu nilai berarti membawa satu blok penuh ke aras penyimpanan yang cepat. Apabila satu perulangan hanya membaca field suhu dari banyak sensor, tata letak baris tetap mengangkut field aktif beserta padding di dalam blok yang sama, sedangkan tata letak kolom mengangkut nilai suhu saja dan memuat lebih banyak sensor per blok. Pembacaan berurutan pada satu kolom juga memungkinkan prosesor menyiapkan data berikutnya sebelum data itu benar-benar diminta.

Tipe #soa pada array, slice, dan dynamic array#

Odin membentuk tata letak kolom melalui awalan #soa pada tipe datanya. Awalan ini ditulis di depan tipe array tetap, slice, atau dynamic array yang elemennya struct, sehingga #soa[4]Sensor, #soa[]Sensor, dan #soa[dynamic]Sensor merupakan tiga bentuk yang sah. Awalan #soa yang disebut sekilas pada modul tipe dan tata letak sesungguhnya bukan struct tag yang ditempel pada deklarasi struct, melainkan bagian dari tipe data array, slice, atau dynamic array. Akses elemennya identik dengan array biasa, tetapi Odin menambahkan akses kolom, yaitu ekspresi kolom.suhu yang membaca seluruh kolom sekaligus.

Program berikut menyusun data empat sensor yang sama dalam dua tata letak, lalu membandingkan ukuran memori dan bentuk aksesnya.

package main

import "core:fmt"

Sensor :: struct {
        suhu:  f32,
        aktif: bool,
}

Jumlah_Sensor :: 4

main :: proc() {
        // tata letak baris (AoS): seluruh field satu sensor berdampingan
        baris: [Jumlah_Sensor]Sensor
        baris[0] = Sensor{suhu = 21.5, aktif = true}
        baris[1] = Sensor{suhu = 22.0, aktif = false}
        baris[2] = Sensor{suhu = 19.5, aktif = false}
        baris[3] = Sensor{suhu = 24.0, aktif = true}

        // tata letak kolom (SoA): setiap field menjadi array tersendiri
        kolom: #soa[Jumlah_Sensor]Sensor
        kolom[0] = Sensor{suhu = 21.5, aktif = true}
        kolom[1] = Sensor{suhu = 22.0, aktif = false}
        kolom[2] = Sensor{suhu = 19.5, aktif = false}
        kolom[3] = Sensor{suhu = 24.0, aktif = true}

        fmt.println("ukuran [4]Sensor     =", size_of([Jumlah_Sensor]Sensor))
        fmt.println("ukuran #soa[4]Sensor =", size_of(#soa[Jumlah_Sensor]Sensor))

        fmt.println("baris[2]:", baris[2])
        fmt.println("kolom[2]:", kolom[2])
        fmt.println("kolom suhu :", kolom.suhu)
        fmt.println("kolom aktif:", kolom.aktif)
}

odin run main.odin -file

ukuran [4]Sensor     = 32
ukuran #soa[4]Sensor = 20
baris[2]: Sensor{suhu = 19.5, aktif = false}
kolom[2]: Sensor{suhu = 19.5, aktif = false}
kolom suhu : [21.5, 22, 19.5, 24]
kolom aktif: [true, false, false, true]

Keluaran memperlihatkan tiga hal. Pertama, kedua variabel memuat data yang sama persis, sehingga baris[2] dan kolom[2] tercetak identik. Kedua, ukuran keduanya berbeda, yaitu 32 byte untuk tata letak baris dan 20 byte untuk tata letak kolom. Selisih 12 byte berasal dari tiga byte padding pada setiap elemen [4]Sensor, yang tidak muncul pada #soa[4]Sensor karena setiap kolom tersusun rapat sesuai alignment field masing-masing. Ketiga, ekspresi kolom.suhu menghasilkan [21.5, 22, 19.5, 24], yaitu seluruh kolom suhu yang berdampingan tanpa satu pun nilai aktif di antaranya.

Konversi dengan soa_zip dan soa_unzip#

Dua tata letak itu bukan dua hal yang terpisah, karena proc bawaan soa_zip dan soa_unzip mengonversi keduanya tanpa menyalin data. soa_zip menerima beberapa slice biasa sebagai argumen bernama dan mengembalikan soa slice yang elemen-elemennya bertindak seperti struct utuh. Nama field pada hasilnya mengikuti nama argumen pemanggilan, sehingga pemanggilan dengan nama field dari Sensor menghasilkan soa slice yang elemennya dapat diperlakukan sebagai Sensor. soa_unzip melakukan kebalikannya, yaitu mengembalikan satu slice untuk setiap field.

Program berikut menyusun data sensor dari dua slice kolom, mengiterasinya, mengubah satu nilainya, lalu membongkarnya kembali menjadi kolom. Untuk jumlah data yang berubah saat program berjalan, program yang sama juga menampung soa dynamic array, yaitu #soa[dynamic]Sensor yang diperlakukan seperti dynamic array biasa, mulai dari nilai nolnya yang siap diisi melalui append hingga operasi pop, len, cap, dan delete.

package main

import "core:fmt"

Sensor :: struct {
        suhu:  f32,
        aktif: bool,
}

main :: proc() {
        // dua slice terpisah, masing-masing berperan sebagai satu kolom
        suhu := []f32{21.5, 22.0, 19.5, 24.0}
        aktif := []bool{true, false, false, true}

        // kolom menjadi soa slice yang dapat diakses per elemen
        sensor := soa_zip(suhu = suhu, aktif = aktif)
        fmt.println("soa slice:", sensor)
        fmt.println("jumlah sensor:", len(sensor))

        for s, i in sensor {
                fmt.printf("sensor %d: suhu=%.1f aktif=%v\n", i, s.suhu, s.aktif)
        }

        // perubahan melalui soa slice menyentuh slice aslinya
        sensor[1].suhu = 30.0
        fmt.println("suhu sesudah perubahan:", suhu)

        // soa slice menjadi kolom kembali
        kolom_suhu, kolom_aktif := soa_unzip(sensor)
        fmt.println("kolom suhu :", kolom_suhu)
        fmt.println("kolom aktif:", kolom_aktif)

        // soa dynamic array untuk jumlah data yang berubah
        stasiun: #soa[dynamic]Sensor
        defer delete(stasiun)
        append(&stasiun, Sensor{20.0, true})
        append(&stasiun, Sensor{20.5, true}, Sensor{21.0, false})
        fmt.println("stasiun:", stasiun)
        terakhir := pop(&stasiun)
        fmt.println("pop:", terakhir, "sisa:", len(stasiun))
}

odin run konversi.odin -file

soa slice: [{suhu = 21.5, aktif = true}, {suhu = 22, aktif = false}, {suhu = 19.5, aktif = false}, {suhu = 24, aktif = true}]
jumlah sensor: 4
sensor 0: suhu=21.5 aktif=true
sensor 1: suhu=22.0 aktif=false
sensor 2: suhu=19.5 aktif=false
sensor 3: suhu=24.0 aktif=true
suhu sesudah perubahan: [21.5, 30, 19.5, 24]
kolom suhu : [21.5, 30, 19.5, 24]
kolom aktif: [true, false, false, true]
stasiun: [Sensor{suhu = 20, aktif = true}, Sensor{suhu = 20.5, aktif = true}, Sensor{suhu = 21, aktif = false}]
pop: Sensor{suhu = 21, aktif = false} sisa: 2

Keluaran memperlihatkan perilaku yang menentukan cara kedua proc itu dipakai. Soa slice hasil soa_zip dapat diukur panjangnya, diindeks, dan diiterasi seperti slice biasa, hanya saja elemen s pada perulangan membaca fieldnya melalui kolom masing-masing. Baris suhu sesudah perubahan menjadi bukti bahwa tidak terjadi penyalinan, sebab perubahan sensor[1].suhu langsung terlihat pada slice suhu yang asli. soa_unzip pun demikian, yaitu mengembalikan slice yang menunjuk kolom yang sama, bukan salinan baru. Konversi antar tata letak dengan demikian tidak berbiaya apa pun, sehingga pilihan tata letak dapat ditunda sampai tepat sebelum data diproses.

Kapan tata letak kolom dipilih#

Tata letak kolom memberi keuntungan ketika satu perulangan memproses sebagian kecil field dari banyak elemen sekaligus. Pola semacam itu lazim pada pemantauan banyak sensor, yaitu satu tahap membaca seluruh kolom suhu, tahap lain menghitung rata-ratanya, dan tahap berikutnya menandai sensor yang tidak aktif. Karena setiap kolom tersusun rapat, satu cache line memuat lebih banyak nilai yang benar-benar dibaca, sehingga jumlah pemindahan memori untuk data yang sama turun.

Pilihan itu bukan tanpa biaya. Apabila satu langkah program hampir selalu membaca seluruh field setiap elemen, tata letak baris sudah cukup dan lebih sederhana, sedangkan tata letak kolom justru memecah satu elemen ke dua lokasi memori yang berjauhan. Memperbarui satu sensor berarti menyentuh dua array yang berbeda, dan memperbanyak field berarti memperbanyak array yang harus dikelola. Keputusan yang tepat diturunkan dari pola akses yang benar-benar terjadi pada program, bukan dari bentuk struct yang paling sering ditulis.

Keputusan semacam ini adalah inti aturan jalur ini, yaitu tata letak data sebelum perilaku. Struct beserta penyusunan array-nya dirancang lebih dahulu berdasarkan cara data dibaca dan ditulis, kemudian perilaku program mengikuti tata letak tersebut. Odin menjadikan pilihan itu bagian dari tipe datanya melalui #soa, sehingga tata letak yang dipilih dapat dinyatakan di dalam kode, diperiksa compiler, dan diukur performanya, bukan sekadar diduga cepat.

Ringkasan#

• Tata letak baris (AoS) menyimpan seluruh field satu elemen berdampingan, sedangkan tata letak kolom (SoA) menyimpan setiap field sebagai array tersendiri.
• Awalan #soa membentuk tata letak kolom untuk array tetap, slice, dan dynamic array, dengan akses elemen seperti array biasa ditambah akses kolom seperti kolom.suhu.
• soa_zip menyusun beberapa slice menjadi soa slice dan soa_unzip mengembalikannya menjadi slice per field, keduanya tanpa menyalin data.
• Tata letak kolom ramah cache apabila perulangan hanya membaca sebagian field, sedangkan tata letak baris cocok apabila seluruh field diproses bersamaan.

Referensi#

• Odin Language Overview — odin-lang.org — Bagian SOA data types mendokumentasikan tipe #soa, soa slice, soa dynamic array, soa pointer, serta proc soa_zip dan soa_unzip.
• Package Documentation — pkg.odin-lang.org — Dokumentasi paket bawaan yang dipakai contoh program, antara lain core:fmt untuk pencetakan keluaran.