Jump to content

SoA vs AoS

From Haidhi Wiki
Revision as of 07:29, 3 July 2026 by SanzSkuy (talk | contribs) (Created page with "'''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 High Performance Computing, 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.<ref nam...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 High Performance Computing, 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.<ref name="drepper" /><ref name="cuda" />

Prinsip utamanya satu kalimat: susun data mengikuti pola aksesnya, bukan mengikuti "kerapian" konsep OOP. Ini adalah ide inti dari data-oriented design.<ref name="fabian" /><ref name="acton" />

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).<ref name="drepper" /> 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.<ref name="drepper" /><ref name="hp" />

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.<ref name="agner" /><ref name="intelopt" /> 

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.<ref name="agner" />

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.<ref name="cuda" /> 

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>)<ref name="ispc" /> 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.<ref name="ispc" />
  • 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

<references> <ref name="drepper">Ulrich Drepper, What Every Programmer Should Know About Memory, Red Hat, Inc., 2007. https://people.freebsd.org/~lstewart/articles/cpumemory.pdf</ref> <ref name="cuda">NVIDIA, CUDA C++ Best Practices Guide — bagian "Coalesced Access to Global Memory". https://docs.nvidia.com/cuda/cuda-c-best-practices-guide/</ref> <ref name="agner">Agner Fog, Optimizing Software in C++: An Optimization Guide for Windows, Linux, and Mac Platforms. https://www.agner.org/optimize/</ref> <ref name="intelopt">Intel Corporation, Intel 64 and IA-32 Architectures Optimization Reference Manual — pembahasan data layout dan vectorization.</ref> <ref name="fabian">Richard Fabian, Data-Oriented Design: Software Engineering for Limited Resources and Short Schedules, 2018. https://www.dataorienteddesign.com/dodbook/</ref> <ref name="acton">Mike Acton, "Data-Oriented Design and C++", CppCon 2014. https://www.youtube.com/watch?v=rX0ItVEVjHc</ref> <ref name="ispc">Intel, ISPC User's Guide — "Structure of Array Types". https://ispc.github.io/ispc.html</ref> <ref name="hp">John L. Hennessy & David A. Patterson, Computer Architecture: A Quantitative Approach, 6th Edition, Morgan Kaufmann, 2017 — bab Memory Hierarchy Design.</ref> </references>

Kategori:HPC Kategori:Optimasi Performa Kategori:Arsitektur Komputer

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