Pendalaman optimasi performa

Optimasi performa dengan caching, keunggulan algoritmik, dan momen beralih ke numpy.

Daftar isi

Optimasi performa yang baik mengikuti urutan kerja yang tetap, yaitu mengukur, mengubah satu hal, lalu mengukur kembali. Topik ini membahas tiga tuas yang paling sering memberikan hasil pada program Python, yaitu caching dengan functools.lru_cache, perbaikan algoritmik yang mengurangi jumlah pekerjaan, dan momen yang tepat untuk memindahkan pekerjaan numerik ke numpy. Setiap tuas disertai kode yang dijalankan dengan keluaran aslinya, sedangkan angka waktu yang bersifat variatif diberi catatan pada prosanya. Setelah membacanya, urutan langkah optimasi dari yang termurah hingga yang paling mahal dapat diterapkan dengan bukti pengukuran, bukan tebakan.

Cache dengan lru_cache#

Cache menyimpan hasil pemanggilan fungsi agar pemanggilan berikutnya dengan argumen yang sama tidak menghitung ulang. Pada pustaka standar, peran itu dipegang oleh decorator lru_cache dari modul functools, yang menyimpan hasil berdasarkan argumen dan membuang entri yang paling lama tidak dipakai ketika kapasitasnya penuh. Decorator ini dipasang pada fungsi murni, yaitu fungsi yang keluarannya hanya ditentukan oleh argumennya. Cache pada fungsi yang keluarannya berubah-ubah akan menyimpan hasil yang menyesatkan.

Ukuran dampaknya terlihat pada fungsi rekursif klasik yang menghitung deret Fibonacci. Versi tanpa cache menghitung submasalah yang sama berkali-kali, dan jumlah pemanggilannya dapat dihitung secara persis.

python Contoh: rekursi tanpa cache

JUMLAH_PANGGILAN = 0

def fibonacci(n):
    """Versi tanpa cache: submasalah yang sama dihitung berulang kali."""
    global JUMLAH_PANGGILAN
    JUMLAH_PANGGILAN += 1
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

hasil = fibonacci(25)
print("hasil fibonacci(25) :", hasil)
print("jumlah pemanggilan  :", JUMLAH_PANGGILAN)

text Keluaran

hasil fibonacci(25) : 75025
jumlah pemanggilan  : 242785

Menghitung satu nilai saja menuntut 242785 pemanggilan fungsi, sebab submasalah yang sama dihitung berulang di setiap cabang rekursi. Satu decorator mengubah keadaan itu sepenuhnya.

python Contoh: rekursi dengan lru_cache

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    """Versi ber-cache: setiap submasalah hanya dihitung satu kali."""
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

hasil = fibonacci(30)
print("hasil fibonacci(30):", hasil)
print(fibonacci.cache_info())

text Keluaran

hasil fibonacci(30): 832040
CacheInfo(hits=28, misses=31, maxsize=None, currsize=31)

Nilai fibonacci(30) kini dihitung dengan 31 perhitungan sungguhan yang dilaporkan sebagai misses, sedangkan 28 pemanggilan sisanya dilayani langsung dari cache dan dilaporkan sebagai hits. Angka pada cache_info() bersifat tetap karena urutan pemanggilannya tidak berubah, sehingga blok keluarannya dapat direproduksi apa adanya. Waktu eksekusinya juga turun drastis, dan penurunannya bertambah besar seiring bertambahnya nilai argumen.

Perbaikan algoritmik#

Cache mempercepat fungsi yang sama dengan menyimpan hasil lamanya, sedangkan perbaikan algoritmik mengurangi jumlah pekerjaan itu sendiri. Dampak keduanya tidak sebanding. Memotong kompleksitas dari kuadrat menjadi linear memberi keuntungan yang terus melebar seiring bertambahnya data, sesuatu yang tidak dapat dicapai oleh penyimpanan hasil apa pun. Perbaikan semacam ini biasanya berawal dari satu pertanyaan, yaitu apakah seluruh data perlu dibandingkan satu per satu.

Contoh berikut membandingkan dua cara mendeteksi nilai duplikat pada daftar. Versi pertama membandingkan setiap pasangan, sedangkan versi kedua menyimpan nilai yang pernah dilihat pada set.

python Contoh: pendeteksi duplikat dengan dua kompleksitas

def ada_duplikat_lambat(nilai):
    """Membandingkan setiap pasangan, sekitar n kuadrat langkah."""
    langkah = 0
    for i in range(len(nilai)):
        for j in range(i + 1, len(nilai)):
            langkah += 1
            if nilai[i] == nilai[j]:
                return True, langkah
    return False, langkah

def ada_duplikat_cepat(nilai):
    """Menyimpan nilai yang sudah dilihat, sekitar n langkah."""
    terlihat = set()
    langkah = 0
    for x in nilai:
        langkah += 1
        if x in terlihat:
            return True, langkah
        terlihat.add(x)
    return False, langkah

data = list(range(2000))
lambat = ada_duplikat_lambat(data)
cepat = ada_duplikat_cepat(data)
print("versi lambat:", lambat[0], "dengan", lambat[1], "langkah")
print("versi cepat :", cepat[0], "dengan", cepat[1], "langkah")

text Keluaran

versi lambat: False dengan 1999000 langkah
versi cepat : False dengan 2000 langkah

Banyaknya langkah menjelaskan selisih waktunya tanpa perlu mengukur. Versi perbandingan pasangan menempuh $O(n^2)$ langkah, yaitu 1999000 perbandingan untuk 2000 data, sedangkan versi berbasis set menempuh $O(n)$ langkah, yaitu 2000 pemeriksaan. Selisihnya sekitar seribu kali lipat pada ukuran data ini dan terus melebar ketika data bertambah. Angka waktu yang diukur tetap bervariasi antar mesin, tetapi rasio jumlah langkahnya bersifat tetap dan itulah petunjuk yang paling andal.

Momen beralih ke numpy#

Perulangan Python mengeksekusi setiap langkah di tingkat interpreter, sedangkan numpy menyimpan data dalam array padat bertipe seragam dan menjalankan operasinya sebagai satu fungsi yang ditulis dengan bahasa C. Untuk pekerjaan numerik atas array besar, keunggulan itu menimbulkan selisih waktu yang besar. Pertanyaannya bukan kapan numpy dipasang, melainkan kapan sebuah pekerjaan layak ditulis ulang di atasnya, yaitu ketika data berupa angka homogen dan operasinya berlaku untuk seluruh elemen sekaligus.

Contoh berikut menjumlahkan dua ratus ribu bilangan dengan kedua cara, lalu membandingkan hasil dan urutan kecepatannya. Pengukuran waktunya dilakukan sungguhan pada sesi penulisan, tetapi hanya kebenaran hasil dan urutan kecepatan yang dicetak, sebab angka waktunya berbeda pada setiap mesin.

python Contoh: perulangan Python versus vektorisasi numpy

import time
import numpy as np

n = 200000
data = np.arange(n, dtype=np.int64)

def jumlah_loop():
    """Menjumlahkan elemen satu per satu dengan perulangan Python."""
    total = 0
    for i in range(n):
        total += i
    return total

def jumlah_numpy():
    """Menjumlahkan seluruh elemen sekaligus di dalam numpy."""
    return int(data.sum())

mulai = time.perf_counter()
hasil_loop = jumlah_loop()
lama_loop = time.perf_counter() - mulai

mulai = time.perf_counter()
hasil_numpy = jumlah_numpy()
lama_numpy = time.perf_counter() - mulai

print("jumlah sama       :", hasil_loop == hasil_numpy)
print("numpy lebih cepat :", lama_numpy < lama_loop)

text Keluaran

jumlah sama       : True
numpy lebih cepat : True

Kedua garis keluaran bernilai tetap pada mesin mana pun, sedangkan besarnya selisih waktu tidak. Pada sesi penulisan topik ini, versi numpy selesai jauh lebih dulu untuk ukuran data yang sama, dan selisihnya bertambah besar ketika jumlah data dinaikkan. Untuk keputusan yang serius, ukur keduanya dengan timeit sebagaimana contoh berikut, dan baca hasilnya sebagai perbandingan antar varian, bukan angka mutlak.

bash Contoh: pengukuran kedua varian dengan timeit

# tidak-dijalankan
# angka waktunya berubah pada setiap mesin dan sesi, sehingga tidak ditangkap keluarannya
python3 -m timeit -s "n = 200000" "total = 0" "for i in range(n):" "    total += i"
python3 -m timeit -s "import numpy as np" "np.arange(200000).sum()"

Peralihan ke numpy bukan berarti mengganti seluruh kode. Logika bercabang per elemen, data campuran berbagai tipe, dan array berukuran kecil sering kali lebih jelas dan cukup cepat ditulis dengan perulangan biasa, sehingga biaya penulisan ulangnya tidak terbayar. Kenali momen yang tepat dari dua cirinya, yaitu data numerik yang homogen dan operasi yang sama untuk seluruh elemen.

Kesalahan umum#

Kesalahan pertama adalah mengoptimasi tanpa mengukur. Titik panas sering berada di tempat yang tidak diperkirakan, dan penyetelan mikro pada baris yang jarang dijalankan tidak pernah terasa oleh pengguna. Ukur terlebih dahulu dengan timeit atau profiler, ubah satu hal, lalu ukur kembali agar setiap perubahan punya bukti. Angka sebelum dan sesudahnya dicatat pada pesan commit sehingga perubahannya dapat ditelusuri kembali.

Kesalahan kedua adalah memasang cache pada fungsi yang argumennya jarang berulang. Setiap pemanggilan menambah entri baru tanpa pernah menjadi hits, sehingga memori membengkak tanpa manfaat apa pun. Periksa pola argumennya terlebih dahulu, dan tetapkan maxsize yang terbatas ketika argumen uniknya banyak.

Kesalahan ketiga adalah menulis ulang kode ke numpy untuk data yang kecil atau logika yang rumit. Overhead konversi antara list dan array dapat menghapus seluruh keunggulannya, sedangkan operasi bercabang per elemen justru lebih panjang dan sulit dibaca dalam bentuk vektor. Peralihan diupayakan hanya ketika dua ciri pada bagian sebelumnya terpenuhi.

Ringkasan#

lru_cache menyimpan hasil pemanggilan berdasarkan argumennya, dan perannya paling terasa pada rekursi yang menghitung submasalah yang sama berulang kali.
Perbaikan algoritmik mengurangi jumlah pekerjaan itu sendiri, misalnya dari $O(n^2)$ menjadi $O(n)$ , sehingga dampaknya bertambah seiring bertambahnya data.
numpy unggul untuk data numerik homogen dengan operasi yang sama pada seluruh elemen, dan keunggulannya diukur, bukan diasumsikan.
Urutan kerjanya tetap mengukur, mengubah satu hal, lalu mengukur kembali, dengan timeit sebagai alat pengukurannya.

Referensi#

functools — Python Software Foundation — Dokumentasi lru_cache beserta cache_info() yang dipakai pada contoh cache.
timeit — Python Software Foundation — Alat pengukuran mikro beserta antarmuka baris perintahnya.
NumPy Documentation — NumPy project — Referensi resmi numpy untuk ndarray dan operasi vektornya.