Jump to content

SoA vs AoS

From Haidhi Wiki

Array of Structures (AoS) dan Structure of Arrays (SoA) adalah dua cara menyusun (me-layout) data di memori. Keduanya menyimpan informasi yang sama persis, tapi urutan byte-nya di RAM berbeda. Di dunia HPC, perbedaan "sepele" ini bisa berdampak besar ke performa — sering kali 2x sampai 8x lipat — karena berhubungan langsung dengan cara kerja cache, SIMD/vektorisasi, dan memory coalescing di GPU.

Prinsip utamanya satu kalimat: susun data mengikuti pola aksesnya, bukan mengikuti "kerapian" konsep OOP. Ini adalah ide inti dari data-oriented design.

Analogi Sederhana

Bayangkan sekolah dengan 1.000 siswa, dan tiap siswa punya data: nama, nilai Matematika, nilai Fisika, nilai Kimia.

  • AoS = satu map arsip per siswa. Map si Budi berisi lengkap: nama Budi, nilai Mat Budi, nilai Fisika Budi, nilai Kimia Budi.
  • SoA = satu buku besar per jenis data. Ada buku khusus "Nilai Matematika seluruh siswa", buku "Nilai Fisika seluruh siswa", dst.

Sekarang tugasnya: hitung rata-rata nilai Matematika seluruh sekolah.

  • Dengan AoS: kamu harus buka 1.000 map satu per satu, ambil selembar nilai Matematika, dan sisanya (nama, Fisika, Kimia) ikut terangkat dari rak padahal tidak dipakai. Boros tenaga.
  • Dengan SoA: tinggal ambil satu buku "Nilai Matematika", baca dari atas ke bawah. Selesai.

CPU bekerja persis seperti ini. Setiap kali CPU mengambil data dari RAM, dia tidak mengambil 1 byte, melainkan satu boks penuh yang disebut cache line (umumnya 64 byte). Kalau isi boks itu kebanyakan data yang tidak dipakai, bandwidth memori terbuang percuma.

Array of Structures (AoS)

Ini gaya yang paling natural kalau kita terbiasa OOP: definisikan satu struct untuk satu objek, lalu buat array dari struct itu. 

struct Particle {
    float x, y, z;   // posisi
    float mass;      // massa
};                   // total: 16 byte per partikel

Particle p[N];       // <-- Array of Structures

// Contoh: jumlahkan semua koordinat x
float sum = 0.0f;
for (int i = 0; i < N; ++i)
    sum += p[i].x;   // tiap iterasi "loncat" 16 byte

Layout di Memori

Semua field satu partikel berdempetan, lalu disusul partikel berikutnya: 

Alamat memori bertambah ke kanan --->

+----+----+----+----+----+----+----+----+----+----+----+----+
| x0 | y0 | z0 | m0 | x1 | y1 | z1 | m1 | x2 | y2 | z2 | m2 | ...
+----+----+----+----+----+----+----+----+----+----+----+----+
 \_____Partikel 0______/ \_____Partikel 1______/ \__Partikel 2 ...

Structure of Arrays (SoA)

Kebalikannya: satu array terpisah untuk tiap field. 

struct Particles {
    float x[N];
    float y[N];
    float z[N];
    float mass[N];
};                   // <-- Structure of Arrays

Particles p;

// Contoh: jumlahkan semua koordinat x
float sum = 0.0f;
for (int i = 0; i < N; ++i)
    sum += p.x[i];   // akses 100% berurutan (contiguous)

Layout di Memori

x[]    : +----+----+----+----+----+----+
         | x0 | x1 | x2 | x3 | x4 | x5 | ...
         +----+----+----+----+----+----+

y[]    : +----+----+----+----+----+----+
         | y0 | y1 | y2 | y3 | y4 | y5 | ...
         +----+----+----+----+----+----+

z[]    : | z0 | z1 | z2 | ...
mass[] : | m0 | m1 | m2 | ...

Kenapa Ini Penting di HPC

1. Efisiensi Cache Line

Cache line modern = 64 byte = muat 16 buah float. Perhatikan apa yang terjadi kalau loop kita hanya butuh field x: 

Kasus AoS -- 1 cache line (64 byte) berisi 4 partikel utuh:

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| x0 | y0 | z0 | m0 | x1 | y1 | z1 | m1 | x2 | y2 | z2 | m2 | x3 | y3 | z3 | m3 |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
  ^^                  ^^                  ^^                  ^^
dipakai             dipakai             dipakai             dipakai

Hanya 4 dari 16 float yang dipakai  -->  efisiensi bandwidth 25%
(75% data yang diangkut dari RAM dibuang sia-sia)


Kasus SoA -- 1 cache line berisi 16 nilai x sekaligus:

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| x0 | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 |x10 |x11 |x12 |x13 |x14 |x15 |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
 ^^^^ semua 16 float dipakai  -->  efisiensi bandwidth 100%

Karena mayoritas kernel HPC bersifat memory-bound (bottleneck-nya di bandwidth memori, bukan di ALU), efisiensi cache line ini langsung menentukan performa akhir.

2. Vektorisasi (SIMD)

Instruksi SIMD (SSE = 4 float, AVX2 = 8 float, AVX-512 = 16 float) paling senang kalau datanya berurutan rapat di memori — cukup satu instruksi load untuk mengisi satu register penuh. 

SoA + AVX2 (register 256-bit = 8 float):

memori x[] :  | x0 | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
                |    |    |    |    |    |    |    |
                v    v    v    v    v    v    v    v      <- 1 instruksi
register   :  | x0 | x1 | x2 | x3 | x4 | x5 | x6 | x7 |      (vmovups)


AoS + AVX2:

memori     :  | x0 | y0 | z0 | m0 | x1 | y1 | z1 | m1 | ...
                |                   |
                +--- perlu gather / banyak shuffle ---+
                     (lambat, boros instruksi)

Efek praktisnya: compiler (GCC/Clang/ICC) jauh lebih gampang melakukan auto-vectorization pada loop SoA. Loop AoS sering gagal divektorisasi, atau divektorisasi dengan instruksi gather yang mahal.

3. GPU: Coalesced Memory Access

Di GPU (CUDA/OpenCL), 32 thread dalam satu warp (NVIDIA) atau wavefront (AMD) mengeksekusi instruksi load secara bersamaan. Kalau alamat yang diakses ke-32 thread itu berurutan, hardware menggabungkannya (coalesce) menjadi sedikit transaksi memori saja. 

Warp = 32 thread. Thread ke-t membaca posisi x milik elemen ke-t.

SoA:
thread :   t0    t1    t2    t3   ...   t31
alamat :  x[0]  x[1]  x[2]  x[3]  ...  x[31]
          \__________ 128 byte berurutan __________/
          => digabung jadi transaksi memori minimal (coalesced)

AoS (stride 16 byte):
thread :   t0        t1        t2        ...
alamat :  p[0].x    p[1].x    p[2].x     ...
          (loncat-loncat 16 byte antar thread)
          => butuh transaksi memori jauh lebih banyak,
             bandwidth efektif anjlok

Karena itu, hampir semua kode GPU yang serius memakai layout SoA untuk data yang diproses per-elemen. Ini juga berlaku persis sama untuk kernel OpenCL.

Kapan AoS Justru Lebih Baik

SoA bukan jawaban universal. AoS unggul kalau pola aksesnya "semua field dari satu elemen sekaligus":

  • Akses acak (random access) per objek — misalnya collision detection: begitu ketemu partikel ke-i, kamu butuh x, y, z, dan mass-nya sekaligus. Dengan AoS, satu cache line langsung membawa seluruh objek itu. Dengan SoA, kamu malah kena 4 cache miss di 4 array berbeda.
  • Objek sering di-insert/delete/dipindah sebagai satu kesatuan.
  • Data di-serialize atau dikirim per-objek (misalnya lewat jaringan atau MPI dengan datatype per-struct).
  • Kode lebih mudah dibaca dan di-maintain — jangan remehkan ini untuk kode yang bukan hotspot.

Aturan praktisnya: 

Loop menyentuh SATU field dari BANYAK elemen   --> SoA
Loop menyentuh SEMUA field dari SATU elemen    --> AoS

AoSoA: Jalan Tengah

Array of Structures of Arrays (AoSoA), kadang disebut tiled SoA, menggabungkan keduanya: data dipecah jadi blok-blok kecil selebar register SIMD, dan di dalam blok disusun ala SoA. 

constexpr int W = 8;            // lebar SIMD (AVX2 = 8 float)

struct ParticleBlock {
    float x[W], y[W], z[W], mass[W];
};

std::vector<ParticleBlock> blocks(N / W);   // <-- AoSoA

// Akses partikel ke-i:
//   blocks[i / W].x[i % W]

+-------------------------------+-------------------------------+
|           Blok 0              |            Blok 1             |
| x0..x7 | y0..y7 | z0..z7 | m..| x8..x15| y8..y15| z8..z15| ...|
+-------------------------------+-------------------------------+
  ^ di dalam blok: SoA (ramah SIMD)
  ^ antar blok: AoS (lokalitas objek tetap lumayan)

Kelebihan: load SIMD tetap berurutan, tapi field-field satu elemen masih "berdekatan" di memori. Kekurangan: indexing jadi lebih ribet. Layout ini dipakai antara lain oleh compiler ISPC (tipe soa<N>) dan banyak kode simulasi partikel/MD.

Contoh Praktis: Mengukur Sendiri

Benchmark mini untuk membuktikan efeknya (kompilasi dengan -O3 -march=native): 

#include <chrono>
#include <cstdio>
#include <vector>

constexpr int N = 1 << 24;   // ~16 juta elemen

struct ParticleAoS { float x, y, z, mass; };

int main() {
    std::vector<ParticleAoS> aos(N, {1, 2, 3, 4});
    std::vector<float> soa_x(N, 1.0f);

    // --- AoS: jumlahkan x ---
    auto t0 = std::chrono::steady_clock::now();
    float s1 = 0;
    for (int i = 0; i < N; ++i) s1 += aos[i].x;
    auto t1 = std::chrono::steady_clock::now();

    // --- SoA: jumlahkan x ---
    float s2 = 0;
    for (int i = 0; i < N; ++i) s2 += soa_x[i];
    auto t2 = std::chrono::steady_clock::now();

    auto ms = [](auto a, auto b) {
        return std::chrono::duration<double, std::milli>(b - a).count();
    };
    std::printf("AoS: %.2f ms | SoA: %.2f ms (s1=%f s2=%f)\n",
                ms(t0, t1), ms(t1, t2), s1, s2);
}

Yang perlu diamati: loop SoA membaca 64 MB, loop AoS harus "menyeret" 256 MB dari RAM untuk hasil yang sama — selisih waktunya biasanya mendekati rasio bandwidth itu (sekitar 3–4x) pada dataset yang jauh lebih besar dari cache. Cek juga laporan vektorisasi compiler dengan -fopt-info-vec (GCC) atau -Rpass=loop-vectorize (Clang).

Tabel Perbandingan

Aspek AoS SoA AoSoA
Pola akses ideal Semua field dari 1 elemen 1 field dari banyak elemen Streaming + butuh beberapa field
Auto-vectorization (SIMD) Susah (gather/shuffle) Mudah (load berurutan) Mudah
GPU memory coalescing Buruk Sangat baik Baik
Efisiensi cache (akses parsial) Rendah (bisa 25% atau kurang) ~100% Tinggi
Efisiensi cache (akses seluruh objek) Tinggi Rendah (miss di banyak array) Sedang–tinggi
Keterbacaan / kenyamanan kode Paling natural (OOP) Agak repot Paling repot (indexing 2 tingkat)
Insert/delete elemen Mudah Repot (semua array harus sinkron) Repot

Tips Praktis

  • Profiling dulu. Ubah layout hanya untuk struktur data di hotspot. Mengubah layout itu mahal secara refactoring.
  • Align array SoA ke 64 byte (alignas(64), std::aligned_alloc) supaya load SIMD aligned dan tidak membelah cache line.
  • Beri tahu compiler bahwa pointer tidak saling tumpang tindih dengan __restrict__ — sering jadi penentu berhasil/tidaknya auto-vectorization.
  • Di CUDA/OpenCL: field yang diakses per-thread hampir selalu lebih cepat dalam bentuk SoA; tipe vektor bawaan seperti float4 bisa jadi kompromi karena di-load sebagai satu transaksi 16 byte.
  • Library yang membantu: Kokkos (Kokkos::View bisa ganti LayoutLeft/LayoutRight tanpa mengubah kode kernel), Intel SDLT (SIMD Data Layout Templates), dan ISPC dengan tipe soa.
  • Ingat trade-off-nya: SoA menukar kenyamanan kode dengan bandwidth. Untuk kode non-kritis, AoS yang enak dibaca sering kali pilihan yang benar.

Lihat Juga

Referensi

Kategori:HPC Kategori:Optimasi Performa Kategori:Arsitektur Komputer

Retrieved from "https://wiki.haidhi.my.id/wiki/index.php?title=SoA_vs_AoS&oldid=751"