Jak zmierzyć złożoność w praktyce w dużym projekcie oprogramowania?

Na uniwersytecie, na naszych kursach z algorytmów, uczymy się, jak precyzyjnie obliczać złożoność różnych prostych algorytmów wykorzystywanych w praktyce, takich jak tabele skrótów lub szybkie sortowanie.

Ale teraz w dużym projekcie oprogramowania, gdy chcemy przyspieszyć, wystarczy spojrzeć na poszczególne elementy - kilka zagnieżdżonych pętli, które można zastąpić szybszą tabelą skrótów, powolne wyszukiwanie tutaj, które można przyspieszyć bardziej fantazyjna technika, ale nigdy nie obliczamy złożoności całego naszego rurociągu.

Czy istnieje jakiś sposób, aby to zrobić? A może ludzie w praktyce polegają tylko na „lokalnym” użyciu szybkiego algorytmu, aby przyspieszyć działanie całej aplikacji, zamiast globalnego rozpatrywania aplikacji jako całości?

(Ponieważ wydaje mi się, że nietrudne jest wykazanie, że jeśli zgromadzisz dużą liczbę algorytmów, o których wiadomo, że są bardzo szybkie same w sobie, kończy się to szybką aplikacją jako całością).

Pytam o to, ponieważ moim zadaniem jest przyspieszenie dużego projektu napisanego przez kogoś innego, w którym wiele algorytmów oddziałuje i pracuje na danych wejściowych, więc nie jest dla mnie jasne, w jaki sposób szybsze oddziaływanie na pojedynczy algorytm cała aplikacja.

Duże projekty oprogramowania składają się z wielu różnych komponentów i nie wszystkie są zwykle wąskim gardłem. Wręcz przeciwnie: w prawie każdym programie, w którym widziałem niską wydajność, stosowano zasadę Pareto : ponad 80% przyrostu wydajności można osiągnąć poprzez optymalizację mniej niż 20% kodu (w rzeczywistości ja myślę, że liczby te często przekraczały 95% do 5%).

Tak więc rozpoczęcie patrzenia na poszczególne elementy jest często najlepszym podejściem. Właśnie dlatego profilowanie (jak wyjaśniono w odpowiedzi Davida Arno ) jest w porządku, ponieważ pomaga zidentyfikować wspomniane 5% kodu, gdzie optymalizacja da ci „największy huk za grosze”. Optymalizacja „całej aplikacji” niesie ze sobą pewne ryzyko nadmiernej inżynierii, a jeśli zoptymalizujesz te 95% nawet 10-krotnie, często nie przyniesie to wymiernego efektu. Zauważ również, że profilowanie mówi o wiele więcej niż jakikolwiek hipotetyczny szacunek złożoności algorytmu, ponieważ prosty algorytm, który wymaga kroków O (N ^ 3), może nadal być szybszy niż złożony algorytm, który wymaga O (N log (N)) tak długo, jak N jest wystarczająco mały.

Po tym, jak profilowanie ujawniło gorące punkty, można je zoptymalizować. Oczywiście „hot spot” może być większy niż jeden lub dwa wiersze kodu, czasem trzeba wymienić cały komponent, aby był szybszy, ale zwykle będzie to nadal niewielka część podstawy kodu w większym programie .

Typowe techniki optymalizacji obejmują

• poprawa wykorzystania algorytmów i struktur danych

• dopracowanie tego pierwszego

• mikrooptymalizacje w niektórych prawdziwych gorących punktach

• przekodowywanie krytycznych sekcji przy użyciu kodu asemblera lub CUDA

Zauważ, że te techniki działają na różnych poziomach abstrakcji, niektóre z nich oglądają komponent bardziej „jako całość” niż inne. To zależy od tego, co rozumiesz przez „wszystko, co robimy, to patrzenie na poszczególne elementy” - jeśli miałeś na myśli jedynie mikrooptymalizacje, nie zgadzam się, że „my” pracujemy tylko nad tym. Ale jeśli masz na myśli zastosowanie optymalizacji w pełnej skali na izolowanych częściach lub komponentach, to „my” prawdopodobnie pracujemy nad odpowiednimi częściami i powinieneś zakwestionować swoje oczekiwania.

Standardowym, wypróbowanym i przetestowanym sposobem jest profilowanie kodu . Przeprowadzasz dynamiczną analizę działającego systemu, aby mierzyć czasy, zużycie pamięci itp. Następnie analizuj wyniki, aby znaleźć wąskie gardła wydajności.

Te wąskie gardła są następnie eksperymentalnie przepisywane, a wynik ponownie profilowany w celu ustalenia, że ​​osiągnięto wzrost prędkości, zmniejszenie zużycia pamięci itp. Proces ten jest następnie powtarzany aż do osiągnięcia akceptowalnego wzrostu wydajności.

Chociaż pozostałe odpowiedzi są poprawne i zawierają pewne wskazówki, myślę, że brakuje im kroku. W złożonym systemie, z którym obecnie pracujesz, zrozumienie różnych składników systemu jest kluczem do zrozumienia, dlaczego coś jest powolne.

Moim pierwszym krokiem byłoby zdobycie szczegółowego schematu architektury lub samemu go stworzyć. Dowiedz się, jakie kroki są podejmowane przez jakie elementy oprogramowania i jak długo trwa każdy krok.

Dowiedz się również, w jaki sposób komponenty współdziałają ze sobą. To może zrobić różnicę.

Na przykład widziałem kod w języku C #, w którym interfejs między dwoma komponentami przekazywał IEnumerable zbudowany przez pierwszy komponent, który został następnie wyliczony przez drugi komponent. W języku C # wymaga to przełączania kontekstu, co w pewnych okolicznościach może być kosztowne. Rozwiązanie tego problemu nie ma wpływu na algorytm. Prosta .ToList () upewnij się, że wynik zostanie zebrany, zanim następny krok rozwiąże ten problem.

Inną rzeczą do rozważenia jest wpływ na system, w którym działa kod. Interakcje sprzętowe mogą oczywiście stanowić czynnik w złożonych systemach. Szukaj IO dysku, alokacje dużej pamięci i sieciowe IO. Czasami można je rozwiązać bardziej efektywnie, modyfikując system, a nawet wymieniając sprzęt.