Post może być trochę dłuższy więc zacznę od ogółu. Muszę zoptymalizować funkcję która może się wykonać nawet kilka milionów razy i musi zrobić to szybko. Główny problem polega na tym,że chciałbym aby funkcja wykonywała się bez alokacji wielkiego buffora z ogromną tablicą za każdym razem kiedy się do niej odwołuje.
A teraz kilka szczegółów. Funkcja o której mówię to algorytm Quick Union. Nie jestem informatykiem z wykształcenia ale po ilości informacji na ten temat wnioskuje, że może to być jakiś klasyk informatyki.
Przygotowałem krótkie demko na którym wykonuje operację "root" lub "find" w zależności od nomenklatury na kilka różnych sposobów. Wykorzystuje dwa rodzaje algorytmu: z kompresją i bez kompresji drzewa. Z kompresją działa szybciej więc moje próby optymalizacji skupiły się na tej wersji algorytmu.
Moje wyniki: ( głębokość drzewa: 50, ilość wykonań funkcji 5 000 000)
Podejście nr 1: brak optymalizacji,bezpośrednio - bez funkcji, zał. 1 "brak optymalizacji" czas wykonania 111 ms
- brak optymalizacji.png (24.64 KiB) Przejrzano 5165 razy
- in place.png (25.88 KiB) Przejrzano 5165 razy
- reentrant.png (21.03 KiB) Przejrzano 5165 razy
Podejście nr 5: użycie Reference Data Value i struktury in place, odwołanie do funkcji reentrant, zał4. "RDV", czas wykonania 2077 ms
- RDV.png (24.62 KiB) Przejrzano 5165 razy
1. Z tego co rozumiem ustawiając funkcje jako inline, wstawiamy ją w kod tak jak makra wstawia się w tekstowych językach programowania przez co nie tracimy czasu na odwoływanie się do niej i przekazywanie argumentów. Mam racje? Dlaczego algorytm z funkcją inline chodzi szybciej od tego samego algorytmu bez zastosowania funkcji. Wydaje mi się że powinien wykonywać się porównywalnie, a on jest szybszy. Dlaczego?
2.
Dlaczego pomimo, że wybrałem funkcję inline, nadal widzę ( po wybraniu narzędzia profile>> show buffer allocation) alokację bufora na kontrolce wejściowej do funkcji? Jak mogę się tego pozbyć?
3. Jaki jest sens używania funkcji, która przekazuje argument poprzez RDV, a później i tak w strukturze in place jest ona wartość jest na nowo alokowana ( narzędzie show buffer...)
W załączniku wrzucam dodatkow demko w którym można przesymulować to co tu napisałem. Gratuluję wszystkim, którzy dotatarli do tego miejsca czytając ;) i mam nadzieje, że ktoś mi pomoże.
