Membaca Kode untuk Kompleksitas

Grep menemukan kandidat. Membaca mengonfirmasi. Ketika Anda membuka file kandidat, Anda membaca dengan satu pertanyaan: apakah biaya operasi ini tumbuh dengan ukuran input?

Untuk MOAD-0001, protokol konfirmasi:

1. Temukan loop luar. Apa yang membatasi jumlah iterasinya?
2. Temukan operasi inner (.contains, .indexOf, 'in'). Struktur data apa yang dijalankan?
3. Apakah struktur data itu tumbuh dengan input yang sama yang mendorong loop luar?
4. Jika ya: biayanya adalah O(N²) di mana N = ukuran input. Defek dikonfirmasi.
5. Jika tidak: struktur inner dibatasi (konfigurasi, enum, konstanta kecil). Positif palsu.

Traversal grafik mengunjungi N node, memeriksa daftar visited di setiap langkah: baik loop maupun struktur data inner tumbuh dengan N. Dikonfirmasi.

Handler permintaan yang memeriksa allowlist 5 IP admin: allowlist tidak pernah tumbuh dengan volume permintaan. Positif palsu.

Protokol yang sama berlaku untuk setiap MOAD: identifikasi driver luar, identifikasi struktur inner, tanyakan apakah keduanya skala bersama.

Skor Lonjakan: Memprioritaskan Temuan Anda

Bukan semua defek yang dikonfirmasi memerlukan perbaikan segera. MOAD dalam perpustakaan dengan 10.000 dependan hilir memiliki skor lonjakan lebih tinggi daripada MOAD yang sama dalam alat internal pribadi.

Skor lonjakan = speedup × in-degree. Speedup: seberapa banyak lebih cepat perbaikan berjalan pada skala produksi khas? In-degree: berapa banyak paket atau layanan hilir yang akan mewarisi perbaikan secara otomatis ketika upstream menggabungkannya?

MOAD-0001 yang dikonfirmasi dalam pemecah dependensi Maven Apache, berjalan pada grafik 50.000 node, dengan 1.000+ plugin Maven hilir yang mewarisi perubahan secara otomatis: skor lonjakan sangat tinggi. Perbaikan ini milik depan antrian Anda.

MOAD-0001 yang dikonfirmasi dalam alat CLI single-user tanpa dependan: skor lonjakan mendekati nol. Layak diperbaiki, tetapi tidak mendesak.

Node workaholic vs. glutton. Node dengan betweenness tinggi & speedup tinggi adalah workaholic: menangani aliran kritis & akan membuang antrian hilir ketika dibuka. Perbaiki hanya setelah mengonfirmasi kapasitas hilir. Node dengan out-degree tinggi & speedup rendah adalah glutton: mengonsumsi semua yang diberinya & tidak merasakan rasa sakit. Menambal workaholic tanpa staging kapasitas hilir menciptakan MOAD-0005 (kawanan mengamuk) pada skala infrastruktur.

Scan ke Merge: Pipeline MOAD

Defek yang dikonfirmasi dengan skor lonjakan tinggi bergerak melalui pipeline. Setiap tahap menghasilkan artifact. Tidak ada tahap yang opsional.

scan    → candidate list (grep output, static analysis results)
ticket  → defect description (MOAD number, location, complexity analysis)
patch   → code change (data structure swap, primitive adoption)
test    → unit test (O(1) proof: time the fix at N=100 and N=10,000)
UNDF    → public disclosure post (undefect.com, public domain)
disclose → CVE or CWE reference if security-relevant
PR      → upstream pull request with patch + test + UNDF link
merge   → maintainer acceptance; fix propagates via version bump

Setiap artifact memberi makan tahap berikutnya. Patch tanpa test tidak dapat diverifikasi. Test tanpa pengungkapan tidak dapat menyebar ke instance lain dari pola yang sama. Pengungkapan tanpa PR upstream meninggalkan perbaikan dalam fork.

Post MOAD (UNDF) adalah tahap yang paling banyak engineer lewati. Mereka memperbaiki defek, mengirimkan PR, & menganggap diri mereka selesai. Tetapi perbaikan tanpa post bernama berarti setiap engineer di masa depan yang mengalami pola yang sama harus menemukan kembali masalah & perbaikan secara independen. Post MOAD menutup loop pengetahuan: itu menamakan pola, menunjukkan metode deteksi, & link ke patch. Peneliti di masa depan menemukan perbaikan dengan mencari nama pola.

Planet patching dalam skala. Perbaikan MOAD-0001 tunggal dalam perpustakaan yang banyak digunakan menyebar ke setiap proyek yang mengimpornya. Post MOAD memastikan bahwa engineer dalam proyek yang tidak akan pernah upgrade perpustakaan itu masih mempelajari perbaikan. Kedua jalur berjalan secara paralel.

Menulis Tiket Defek

Tiket defek yang baik menjawab lima pertanyaan:

1. Di mana: file exact, class, function, & line range
2. Apa: tipe struktur data & operasi terhadapnya
3. Mengapa: analisis kompleksitas (O(N²) atau lebih buruk, dengan N didefinisikan)
4. Dampak: input apa yang memicu perilaku kasus terburuk, & pada skala apa
5. Perbaiki: struktur data atau primitive untuk disubstitusi

Tiket yang menjawab semua lima self-contained: maintainer yang tidak pernah membaca analisis Anda dapat mereproduksi temuan Anda & memverifikasi perbaikan Anda. Tiket yang melewati (3) atau (4) memerlukan maintainer untuk mengulangi analisis kompleksitas Anda sebelum mereka dapat menggabungkan. Gesekan itu mengurangi probabilitas merge.

Kredibilitas compound. PR pertama yang mencakup tiket jelas, patch yang well-targeted, & test benchmark digabungkan. PR kedua dari penulis yang sama ditinjau dengan gesekan lebih sedikit. PR ketiga ditinjau oleh maintainer yang menggabungkan dua pertama. Reputasi dalam open source adalah buku transaksi artifact: setiap patch yang diterima mengumpulkan kepercayaan untuk PR berikutnya.

Membaca Kandidat Nyata

Berikut adalah kandidat MOAD-0001 nyata dalam Python. Bacalah & selesaikan protokol triase.

class DependencyResolver:
    def resolve(self, package, resolved=None, seen=None):
        if resolved is None:
            resolved = []
        if seen is None:
            seen = []
        if package in seen:
            return
        seen.append(package)
        for dep in self.registry.get_dependencies(package):
            self.resolve(dep, resolved, seen)
        resolved.append(package)
        return resolved

Pertanyaan triase:

1. Struktur data apa `seen`?
2. Operasi apa yang berjalan terhadapnya pada baris 6?
3. Apakah `seen` tumbuh dengan ukuran input?
4. Apakah loop yang mendorong panggilan rekursif juga tumbuh dengan ukuran input?
5. Apakah ini MOAD-0001 yang dikonfirmasi atau positif palsu?

Patch Anda

Defek yang dikonfirmasi dengan skor lonjakan tinggi memerlukan patch lengkap: perbaikan kode, test yang membuktikan peningkatan, & outline post MOAD.

Test harus test performa, bukan test kebenaran. Test kebenaran lolos sebelum & sesudah perbaikan — itu intinya; output tidak berubah. Test performa pada dua ukuran input membuktikan peningkatan:

import time

def build_graph(n):
    # n packages, each depending on the previous one
    return {f'pkg{i}': [f'pkg{i-1}'] if i > 0 else [] for i in range(n)}

for n in [100, 1000, 5000]:
    registry = build_graph(n)
    resolver = DependencyResolver(registry)
    start = time.perf_counter()
    resolver.resolve(f'pkg{n-1}')
    elapsed = time.perf_counter() - start
    print(f'n={n}: {elapsed:.4f}s')

Sebelum perbaikan, waktu elapsed tumbuh kuadrat dengan n. Setelah perbaikan, tumbuh linier. Cetak keduanya & sertakan angka dalam deskripsi PR Anda.

Outline post MOAD mencakup: nama pola, substrat (resolver dependensi Python), metode deteksi (grep untuk in seen di mana seen dimulai sebagai []), perbaikan, & link ke PR Anda. Post ini menuju undefect.com sebagai public domain. Engineer di masa depan yang mencari 'Python list membership in loop slow' akan menemukannya.