Odczytywanie kodu dla złożoności

Grep znajduje kandydatów. Odczytywanie potwierdza je. Gdy otwierasz plik kandydata, czytasz z jedną pytaniami: czy koszt operacji rośnie wraz ze wzrostem rozmiaru wejścia?

Dla MOAD-0001, procedura potwierdzenia:

1. Znajdź zewnętrzną pętlę. Jakie granice określają jej liczbę iteracji?
2. Znajdź operację wewnętrzną (.contains, .indexOf, 'in'). Jaką strukturę danych operuje ona?
3. Czy ta struktura danych rośnie w taki sam sposób, jak wprowadzenie zewnętrzne, które steruje pętlą?
4. Jeśli tak: koszt to O(N²), gdzie N to rozmiar wejścia. Potwierdzony błąd.
5. Jeśli nie: wewnętrzna struktura jest ograniczona (konfiguracja, enumeracja, mała stała). Fałszywy alarm.

Przetwarzanie grafu, w którym odwiedzane są N węzłów, a na każdym kroku sprawdzana jest lista odwiedzonych: zarówna pętla, jak i wewnętrzna struktura danych rosną wraz z N. Potwierdzony.

Obsługa żądania sprawdzająca allowlistę 5 IP administatorów: allowlist nigdy nie rośnie wraz z objętością żądań. Fałszywy alarm.

Ten sam protokół stosuje się dla każdego MOAD: zidentyfikuj zewnętrznego sterującego, zidentyfikuj wewnętrzną strukturę, zapytaj, czy oba skalują się razem.

Surge Score: Prioritizing Your Findings

Nie wszystkie potwierdzone wady wymagają natychmiastowej naprawy. MOAD w bibliotece o 10 000 zależnych w dół ma wyższy wynik surgu niż ten sam MOAD w prywatnym wewnętrznym narzędziu.

Wynik surgu = przyspieszenie × stopień wejścia. Przyspieszenie: jak szybciej działa naprawa w typowych skalach produkcji? Stopień wejścia: ile pakietów lub usług w dół automatycznie odziedziczy poprawkę, gdy upstream ją zintegruje?

Potwierdzony MOAD-0001 w rozwiązywaniu zależności Apache Maven, działającym na grafach o 50 000 węzłów, z +1 000 węzłów w dół Maven pluginów, które automatycznie dziedziczą zmiany: wynik surgu jest bardzo wysoki. Ta poprawka powinna być na pierwszym miejscu w swojej kolejce.

Potwierdzony MOAD-0001 w pojedynczym narzędziu CLI bez zależnych: wynik surgu bliski zeru. Warty poprawienie, ale nie pilny.

Pracoholik vs. glutton węzły. Węzeł o wysokiej miary pomiędzy a niskim przyspieszeniem jest pracoholikiem: obsługuje krytyczne przepływy i wyrzuci węzły w dół, gdy zostaną odblokowane. Napraw pracoholika tylko po potwierdzeniu zdolności w dół. Węzeł o wysokiej stopień wyjścia a niskim przyspieszeniem jest glutton: absorbuje wszystko, co karmi się go i nie odczuwa bólu. Naprawienie pracoholika bez etapowania zdolności w dół generuje MOAD-0005 (wściekły stadko) na skalę infrastruktury.

Skan do Połączenia: Pipeline MOAD

Potwierdzony błąd o wysokiej punktacji surgu przechodzi przez łańcuch. Każde stadium tworzy artefakty. Nie ma żadnego stadium opcjonalnego.

scan    → lista kandydatów (wyjście grep, wyniki analizy statycznej)
ticket  → opis błędu (numer MOAD, lokalizacja, analiza złożoności)
patch   → zmiana kodu (zmiana struktury danych, przyjęcie prymitywu)
test    → test jednostkowy (dowód O(1): czas naprawy przy N=100 i N=10,000)
UNDF    → publikacja w domenie publicznej (undefect.com)
disclose → odniesienie do CVE lub CWE jeśli błąd ma związek z bezpieczeństwem
PR      → żądanie pull z upstream z naprawą + testem + linkiem do UNDF
merge   → akceptacja przez utrzymanię; naprawa propaguje się za pomocą zwiększenia wersji

Każdy artefakt odnosi się do następnego stadium. Naprawa bez testu nie może być zweryfikowana. Test bez publikacji nie może się przekazać do innych wystąpień tego samego wzorca. Publikacja bez żądania pull utrzymuje naprawę w węźle fork.

Ostatnim etapem (UNDF) w łańcuchu MOAD jest publikacja w domenie publicznej. Inżynierowie często naprawiają błąd, tworzą pull request i uważają, że już wszystko zrobili. Ale naprawa bez opisanego etapu nie gwarantuje, że inni inżynierowie, którzy napotkają ten sam problem, odkryją rozwiązanie samodzielnie. Publikacja MOAD zamyka pętlę wiedzy: nazwa wzorca, metoda wykrywania i link do naprawy. Inni badacze znajdą naprawę wyszukiwaniem nazwy wzorca.

Skalowanie planety poprzez naprawianie. Jedna naprawa MOAD-0001 w powszechnie używanej bibliotece przechodzi do każdego projektu, który ją importuje. Publikacja MOAD zapewnia, że inżynierowie w projektach, którzy nigdy nie zaktualizują tej biblioteki, dowiedzą się o naprawie. Obie ścieżki działają równolegle.

Tworzenie Błędowego Biletu

Dobry bilet błędu odpowiada na pięć pytań:

1. Gdzie: dokładny plik, klasa, funkcja i zakres linii
2. Co: typ struktury danych i operacja przeciwko niej
3. Dlaczego: analiza złożoności (O(N²) lub gorsze, z N zdefiniowanym)
4. Wpływ: co wyzwala zachowanie najgorsze, i na jakim poziomie
5. Naprawa: struktura danych lub prymityw do zastąpienia

Bilet, który odpowiada na wszystkie pięć, jest samodzielnym: utrzymaniowiec, który nigdy nie przeczytał twojego analizy, może powtórzyć twoje odkrycie i zweryfikować twoją naprawę. Bilety, które pomijają (3) lub (4), wymagają od utrzymaniowca powtórzenia twojej analizy złożoności przed złożeniem. Ta frakcja zmniejsza prawdopodobieństwo połączenia.

Wiarygodność się kumuluje. Pierwszy PR zawierający jasny bilet, dobrze skierowany patch oraz test benchmarking zostaje zaakceptowany. Drugi PR od tego samego autora jest przeglądany z mniejszym oporem. Trzeci PR jest przeglądany przez maintainera, który zaakceptował pierwsze dwa. W otwartym ośrodku reputacja to zapis księgi artefaktów: każdy akceptowany patch zdobywa zaufanie na kolejny.

Przegląd rzeczywistego kandydata

Oto rzeczywisty kandydat MOAD-0001 w języku Python. Przeczytaj i zrealizuj procedurę triażowania.

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

Pytania triażowe:

1. Jakie jest struktury danych `seen`?
2. Jaką operację wykonuje się na nim w linii 6?
3. Rosnie `seen` w miarę wzrostu wielkości wejścia?
4. Czy pętla sterująca wywołaniami rekurencyjnymi również rośnie w miarę wzrostu wielkości wejścia?
5. Czy to potwierdzony MOAD-0001, czy fałszywy alarm?

Twój Patch

Potwierdzona wada z wysokim wskaźnikiem surge wymaga kompletnego patcha: naprawa kodu, test sprawdzający poprawę & zarys wpisu w MOAD.

Test musi być testem wydajnościowym, a nie poprawnościowym. Test poprawności przeprowadza się przed i po naprawie - to właśnie jest punkt; wyjście się nie zmienia. Test wydajnościowych na dwóch rozmiarach wejścia dowodzi poprawą:

import time

def build_graph(n):
    # n pakietów, każdy zależny od poprzedniego
    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')

Przed naprawą czas rozważenia wzrasta kwadratowo wraz z n. Po naprawie wzrasta liniowo. Wypisz oba i włącz liczby w opisie PR.

Oszkoleńczy post MOAD obejmuje: nazwę wzorca, podstawę (zależność Pythona rozstrzygającego zależności), metodę wykrywania (grep dla in seen, gdzie seen zaczyna się jako []), rozwiązanie oraz link do Twojego PR. Post publikowany jest na undefect.com jako domena publiczna. Przyszli inżynierowie szukający 'Python list membership in loop slow' znajdą go.