Optimasi Array

Preallocation memastikan array tidak tumbuh; vectorization mengganti loop dengan panggilan array. Chapter ini menurunkan satu lapis lagi: bagaimana elemen array tersusun di RAM dan bagaimana susunan itu menentukan kecepatan akses. MATLAB menyimpan matriks per kolom (column-major) — fakta ini memengaruhi urutan iterasi, biaya transpose, pilihan indeks, hingga kapan sparse mengalahkan matriks penuh. Cakupan materinya:

• Iterasi per kolom vs per baris dengan timing terukur
• Indeks linear, sub2ind, dan biaya transpose berulang
• Tipe data single untuk volume besar dan recap copy-on-write
• sparse untuk matriks dominasi-nol (0.1% nonzero)

Column-Major: Iterasi Kolom Lebih Cepat dari Baris #

Aturannya: bila loop harus memproses matriks sepotong-sepotong, potong per kolom, bukan per baris. Mekanismenya: MATLAB menata elemen matriks dalam satu blok memori berurutan per kolom — seluruh kolom pertama, lalu kolom kedua, dan seterusnya. Dengan demikian A(:, j) adalah blok memori contiguous, sedangkan A(i, :) berisi elemen yang terpencar dengan jarak m elemen (stride m). CPU memuat memori per cache line; akses berurutan memicu sedikit cache miss, akses terpencar memicu banyak. Pengukurannya pada matriks 2500 × 2500:

m = 2500;
A = rand(m, m);

tic;
sKolom = 0;
for j = 1:m
    sKolom = sKolom + sum(A(:, j));   % satu kolom = blok memori berurutan
end
tKolom = toc;

tic;
sBaris = 0;
for i = 1:m
    sBaris = sBaris + sum(A(i, :));   % satu baris = elemen terpencar stride m
end
tBaris = toc;

fprintf('iterasi  : kolom %.4f s | baris %.4f s | speedup %.1fx\n', tKolom, tBaris, tBaris / tKolom);
fprintf('selisih hasil (floating point): %.2e\n\n', max(abs(sKolom - sBaris)));

Output yang Dihasilkan:

iterasi  : kolom 0.0137 s | baris 0.0627 s | speedup 4.6x
selisih hasil (floating point): 1.02e-08

Mari kita bedah baris-baris kode di atas:

1. Baris 2 (A = rand(m, m);): membuat matriks 50 MB — cukup besar agar efek cache terasa, bukan sekadar noise pengukuran.
2. Baris 4-7 (for j = 1:m ... sum(A(:, j))): loop luar menyapu kolom; setiap A(:, j) membaca blok memori berurutan.
3. Baris 11-14 (for i = 1:m ... sum(A(i, :)): loop luar menyapu baris; setiap A(i, :) menghimpun elemen ber-stride m — CPU harus melompat-lompat di memori.
4. Baris 18 (fprintf ...): tBaris / tKolom melaporkan speedup; rasio di atas 4x ini murni efek tata letak memori, karena keduanya memanggil sum sama banyaknya.

Indeks Linear di Loop Panas #

Aturannya: di dalam hot loop, akses elemen dengan indeks subskrip B(i, j) atau indeks linear yang dihitung manual; panggil sub2ind sekali untuk seluruh grid, bukan per elemen. Mekanismenya: indeks linear k memetakan langsung ke posisi penyimpanan column-major lewat rumus k = i + (j - 1) * m — operasi aritmetika murah. sub2ind melakukan hal yang sama, tetapi sebagai function call lengkap dengan validasi argumen, sehingga biayanya berlipat bila dipanggil puluhan ribu kali. Bandingkan dua loop identik secara hasil pada matriks 200 × 200:

tic;
s1 = 0;
for j = 1:n
    for i = 1:n
        s1 = s1 + B(i, j);
    end
end
tSub = toc;

tic;
s2 = 0;
for j = 1:n
    for i = 1:n
        idx = sub2ind(size(B), i, j);   % satu panggilan fungsi per elemen
        s2 = s2 + B(idx);
    end
end
tInd = toc;

fprintf('indexing : subskrip %.4f s | sub2ind %.4f s | speedup %.1fx\n', tSub, tInd, tInd / tSub);
fprintf('hasil identik: %d\n\n', isequal(s1, s2));

Output yang Dihasilkan:

indexing : subskrip 0.0602 s | sub2ind 0.2089 s | speedup 3.5x
hasil identik: 1

Indeks linear juga bahasa asli logical indexing dan find: B(B > 0.5) bekerja pada vektor indeks linear, bukan pasangan (i, j). Bila rumus manual terasa rawan salah, hitung sub2ind sekali untuk seluruh grid berpasangan (sub2ind menerima vektor indeks dan mengembalikan vektor indeks linear), lalu pakai hasilnya di loop.

Transpose Bukan Sekadar Label #

Aturannya: lakukan transpose satu kali sebelum loop, simpan hasilnya, lalu gunakan hasil tersimpan. Mekanismenya: C.' tidak sekadar menukar label dimensi — untuk matriks penuh, MATLAB menyalin seluruh data ke tata letak baru karena penyimpanan tetap harus berurutan per kolom. Salinan O(m × n) yang sekali jalan terasa murah menjadi mahal bila muncul di setiap iterasi. Pengukurannya:

C = rand(1500, 1500);
tic;
for r = 1:25
    T = C.';   % 25 salinan 18 MB wajib terjadi
end
tTrans = toc;
fprintf('transpose: 25x salin 1500x1500 = %.4f s\n\n', tTrans);

Output yang Dihasilkan:

transpose: 25x salin 1500x1500 = 0.1054 s

Tipe Data dan Operasi Batch #

Aturannya: untuk array berukuran besar yang presisinya cukup dengan ~7 digit signifikan, pertimbangkan single (4 byte per elemen) menggantikan double (8 byte). Mekanismenya: setengah ukuran berarti setengah bandwidth memori yang harus dipindahkan — operasi memory-bound adalah penerima manfaat utamanya, di samping ruang RAM yang hemat. Pengecekan ukurannya deterministik:

Ad = rand(2000, 2000);
As = single(Ad);
fprintf('tipe data: double %d byte | single %d byte | kelas %s / %s\n', ...
    numel(Ad) * 8, numel(As) * 4, class(Ad), class(As));

Output yang Dihasilkan:

tipe data: double 32000000 byte | single 16000000 byte | kelas double / single

Konsekuensinya jujur saja: single menyimpan ~7 digit signifikan, jadi hasil numerik bisa menyimpang tipis dari double — jangan dipakai untuk akumulasi presisi tinggi. Sementara untuk batch: satu panggilan f(v) untuk seluruh array selalu mengalahkan loop yang memanggil f(v(k)) per elemen, karena overhead panggilan dibayar sekali — angka terukurnya kita bahas tuntas di chapter Optimasi Function.

Sparse untuk Matriks Dominasi-Nol #

Aturannya: matriks yang hampir seluruhnya nol (matriks ketetanggaan graf, diskretisasi PDE) sebaiknya disimpan sebagai sparse, bukan array penuh (dense). Mekanismenya: sparse hanya menyimpan nilai nonzero beserta indeksnya; operasi seperti perkalian matriks-vektor menyapu entri tersimpan, melewati jutaan nol tanpa menyentuhnya. Pengukurannya pada matriks 2500 × 2500 berkepadatan 0.1% (±6250 nonzero):

n2 = 2500;
rng(42);
Asp  = sprandn(n2, n2, 0.001);   % sekitar 6250 elemen nonzero
Aden = full(Asp);
x    = randn(n2, 1);

tic;  yD = Aden * x;  tD = toc;
tic;  yS = Asp  * x;  tS = toc;

byteD = numel(Aden) * 8;    % dense: 8 byte per elemen
byteS = nnz(Asp) * 12;      % sparse: perkiraan nilai + indeks per nonzero

fprintf('sparse   : dense %.4f s | sparse %.5f s | speedup %.0fx\n', tD, tS, tD / tS);
fprintf('memori   : dense %d byte | sparse ~%d byte | hemat %.0fx\n', byteD, byteS, byteD / byteS);
fprintf('maks selisih hasil: %.2e\n', max(abs(yD - yS)));

Output yang Dihasilkan:

sparse   : dense 0.0013 s | sparse 0.00009 s | speedup 15x
memori   : dense 50000000 byte | sparse ~75000 byte | hemat 667x
maks selisih hasil: 4.44e-16

Tabel Praktik dan Dampak #

Satu topik jangan diulang dari sini: penyalinan data. Assignment y = x tetap murah berkat copy-on-write dan modifikasi pertama pemilik baru yang memicu salinan penuh; bentuk x(:) = x(:) + 1 menulis ke buffer yang sudah ada tanpa alokasi baru. Mekanisme lengkapnya sudah kita bedah di chapter Memory Usage — cukup ingat bahwa kebiasaan chapter ini (akses contiguous, batch, tipe tepat) bekerja di atas fondasi tersebut.

Ringkasan #

Tata letak column-major menjadikan kolom sebagai jalur cepat: iterasi per kolom 4.6x lebih cepat dari per baris pada contoh kita, indeks linear lebih murah dari sub2ind per elemen, dan transpose yang ditimbang berulang adalah salinan data berulang. single memotong memori dan bandwidth menjadi setengah untuk volume besar, sementara sparse mengubah matriks dominasi-nol menjadi 15x lebih cepat dengan memori 667x lebih hemat. Lapisan berikutnya bukan lagi tentang data, melainkan tentang function: berapa mahal sebuah panggilan, dan bagaimana bentuk fungsi yang bersahabat dengan optimasi.