Belajar Data Structure - Memory Layout, Cache & Space-Time Tradeoff

#Pendahuluan

Setelah di episode 24 kita memahami decision matrix untuk memilih struktur data, pada episode ini kita mendalami aspek yang sering diabaikan: memory layout — bagaimana cara data tersimpan di memori secara fisik mempengaruhi performa secara dramatis. Dua algoritma dengan kompleksitas Big-O yang sama bisa memiliki perbedaan kecepatan 10x atau lebih hanya karena salah satunya lebih "cache-friendly".

Ini adalah episode yang akan mengubah cara kalian berpikir tentang "efisien". Big-O memberitahu kalian tentang pertumbuhan, tetapi cache behavior memberitahu kalian tentang konstanta — dan di production, konstanta bisa jauh lebih penting dari yang kalian bayangkan.

#Contiguous vs Pointer-Based

#Contiguous Memory (Array)

Array menyimpan elemen secara berurutan di memori. Ketika CPU mengakses array[i], ia memuat cache line (biasanya 64 byte) yang berisi beberapa elemen sekaligus. Akses berikutnya ke array[i+1] sudah ada di cache → sangat cepat.

#Pointer-Based (Linked List)

Linked list menyimpan node tersebar di memori, dihubungkan oleh pointer. Setiap node bisa berada di lokasi yang sangat berjauhan. Ketika CPU mengakses node, ia harus memuat cache line yang mungkin hanya berisi satu node → cache miss sering terjadi.

#Dampak Performa

Perbandingan array vs linked list traversal

import time
 
data_list = list(range(1000000))
linked_values = list(range(1000000))
 
# Array traversal (cache-friendly)
start = time.perf_counter()
total = 0
for x in data_list:
    total += x
array_time = time.perf_counter() - start
 
print(f"Array traversal: {array_time:.4f}s")
# Linked list traversal akan jauh lebih lambat karena cache misses

#Cache Line dan Prefetching

#Cache Line

Cache line adalah unit data最小 yang dimuat dari RAM ke cache. Biasanya 64 byte. Ketika kalian mengakses satu byte, CPU memuat seluruh 64 byte ke cache → akses ke byte tetangga sangat cepat.

#Prefetching

Prefetching adalah teknik CPU untuk memuat data ke cache sebelum benar-benar diminta. Prefetcher mendeteksi pola akses sekuensial dan memuat data berikutnya. Ini sangat efektif untuk array, tetapi tidak efektif untuk linked list karena node tersebar acak.

#Cache Miss

Cache miss terjadi ketika data yang diminta tidak ada di cache dan harus diambil dari RAM. Setiap cache miss menambah latensi ~100 ns — cukup untuk membuat perbedaan dramatis pada loop besar.

#Struct-of-Arrays vs Array-of-Structs

#Array-of-Structs (AoS)

Array of structs

class Particle:
    def __init__(self, x, y, z, mass):
        self.x = x
        self.y = y
        self.z = z
        self.mass = mass
 
particles = [Particle(1.0, 2.0, 3.0, 1.0) for _ in range(100000)]

AoS: setiap partikel lengkap (x, y, z, mass) disimpan berurutan. Jika kalian hanya butuh x, kalian tetap memuat y, z, dan mass ke cache → pemborosan bandwidth.

#Struct-of-Arrays (SoA)

Struct of arrays

xs = [1.0] * 100000
ys = [2.0] * 100000
zs = [3.0] * 100000
masses = [1.0] * 100000

SoA: semua x tersimpan berurutan, semua y tersimpan berurutan, dst. Jika kalian hanya butuh x, kalian memuat hanya x → cache-friendly untuk akses sebagian field.

#Actual Memory Footprint

Membandingkan memory footprint

import sys
 
class AoS:
    def __init__(self):
        self.x = 0.0
        self.y = 0.0
        self.z = 0.0
        self.mass = 0.0
 
class SoA:
    def __init__(self):
        self.xs = []
        self.ys = []
        self.zs = []
        self.masses = []
 
a = AoS()
s = SoA()
 
print(f"AoS size per particle: {sys.getsizeof(a)} bytes")
print(f"SoA overhead: {sys.getsizeof(s)} bytes (empty)")

#Praktik: Perbandingan Iterasi

AoS vs SoA iteration performance

import time
 
n = 100000
 
# AoS
class Particle:
    __slots__ = ['x', 'y', 'z', 'mass']
    def __init__(self, x, y, z, mass):
        self.x = x
        self.y = y
        self.z = z
        self.mass = mass
 
particles = [Particle(float(i), float(i), float(i), 1.0) for i in range(n)]
start = time.perf_counter()
total = 0
for p in particles:
    total += p.x
aos_time = time.perf_counter() - start
 
# SoA
xs = [float(i) for i in range(n)]
start = time.perf_counter()
total = 0
for x in xs:
    total += x
soa_time = time.perf_counter() - start
 
print(f"AoS: {aos_time:.4f}s")
print(f"SoA: {soa_time:.4f}s")

#Space-Time Tradeoff

#Konsep

Space-time tradeoff adalah prinsip: kalian bisa menukar memori untuk waktu (atau sebaliknya). Contoh:

• Hash map: menggunakan lebih banyak memori untuk O(1) lookup (vs O(n) linear scan)
• Bit manipulation: menggunakan lebih sedikit memori tetapi lebih banyak komputasi
• Memoization: menyimpan hasil komputasi untuk menghindari komputasi ulang

#Contoh Nyata

Space-time tradeoff: memoization

import time
 
def fib_no_cache(n):
    if n <= 1:
        return n
    return fib_no_cache(n - 1) + fib_no_cache(n - 2)
 
cache = {}
def fib_with_cache(n):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fib_with_cache(n - 1) + fib_with_cache(n - 2)
    return cache[n]
 
start = time.perf_counter()
fib_no_cache(30)
no_cache_time = time.perf_counter() - start
 
start = time.perf_counter()
fib_with_cache(30)
cache_time = time.perf_counter() - start
 
print(f"Without cache: {no_cache_time:.4f}s")
print(f"With cache: {cache_time:.6f}s")
print(f"Speedup: {no_cache_time / cache_time:.0f}x")

#Garbage Collection Pressure

Garbage collection di Python dan Java menambah overhead. Banyak object kecil = banyak work untuk GC. Menggunakan array/array-backed structures mengurangi GC pressure.

#Penutup

Inti yang harus dibawa pulang:

• Cache-friendly: contiguous memory → cache line memuat banyak data sekaligus.
• Linked list: cache-unfriendly karena node tersebar di memori.
• SoA vs AoS: pilih berdasarkan pola akses (field tertentu vs seluruh record).
• Space-time tradeoff: gunakan memori untuk menghemat waktu atau sebaliknya.
• GC pressure: banyak object kecil = overhead GC; gunakan array-backed structures.

Di episode 26 selanjutnya kita akan membahas tren modern 2026 dan concurrent/persistent DS — persistent/immutable data structures, lock-free/concurrent DS, vector similarity search (HNSW, IVF), dan bagaimana data structure digunakan di production systems. Ini adalah gambaran terkini tentang apa yang happening di dunia data structure!