Autor Wątek: Optymalizacja przy pomocy delegatów  (Przeczytany 1414 razy)

Offline counterClockWise

  • Użytkownik

# Luty 14, 2012, 18:15:21
Pytanie jest trochę lamerskie, ale cóż ;P

Załóżmy, że mamy klasę Node reprezentującą węzeł/wierzchołek w drzewie.
Niech drzewo posiada np. 500 000 - 1000 0000 wierzchołków.

Rozpoczynając od korzenia wywołujemy funkcje, która coś na tym drzewie liczy, z tym, że w każdym węźle jest ogromny switch i w zależności od pewnych dyskretnych parametrów węzła, inna procedura inna metoda jest wywoływana. Różnych metod jest kilkadziesiąt.

Parametry nie zmieniają się w czasie, ustalane są w pewnym momencie programu, więc to jaka funkcja będzie wywołana w pewnym momencie (na początku runtime) już wiemy.

Gdyby przygotować zestaw np. 40 funkcji i w jednym preprocessingowym przejściu przez drzewo w zależności od parametrów ustawić delegata na odpowiednią funkcję (żeby wywalić już później switch) - czy to powinno jakoś zauważalnie przyspieszyć wykonywanie programu?

Może wyraźnie lepsze byłoby użycie dynamicznego generowania kodu, żeby rozwinąć tego switcha i przy okazji skorzystać przy okazji z dodatkowych optymalizacji kompilacji?

Nie znam się na takiej optymalizacji w C#, bo gdy tak trzeba było to pisałem w C++, ale tutaj nie mam wyboru. Zastanawiam się czy warto....
« Ostatnia zmiana: Luty 14, 2012, 18:17:05 wysłana przez counterClockWise »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline koirat

  • Użytkownik

# Luty 14, 2012, 19:45:11
http://stackoverflow.com/questions/44905/c-sharp-switch-statement-limitations-why#48259
Zobacz sobie ten link.
Wynika z niego iż jeśli chodzi o samego "switch case" to najlepiej jest mieć po kolei ustawione wartości dla case

case 3: blah; break;
case 4: blah; break;
case 5: blah; break;

W ten czas zostanie zastosowana tablica lookup [ O(1) ], i nie będzie miało wielkiego znaczenia jak dużo będzie przypadków.

Wydaje mi się iż zastosowanie tego szczególnego case może być szybsze niż delegaty.
« Ostatnia zmiana: Luty 14, 2012, 19:47:18 wysłana przez koirat »

Offline fn2000

  • Użytkownik

# Luty 20, 2012, 15:10:52
Nie znam szczegółów kodu i projektu, ale 40 switchów per węzeł, 40 funkcji to mi delikatnie zalatuje jakimś błędem w architekturze - po co potrzebujesz aż tyle tego?

Generalnie "goto" czyli wybranie odpowiedniej opcji w switch powinno być szybsze niż wywołanie metody, a tym bardziej delegata, który jest lekko wolniejszy niż wywołanie metody instancji klasy.

Offline Xender

  • Użytkownik

# Luty 20, 2012, 15:41:19
IMHO powinno być porównywalnie - dlaczego po prostu nie zrobisz prostego benchmarka i nie sprawdzisz? Nie sądzę że branch + skok pod stały offset będzie dużo szybszy niż skok pod pointer.

Offline koirat

  • Użytkownik

# Luty 20, 2012, 20:54:54
Co do tego iż narzut czasowy jest bardzo niewielki to się zgodzę, prawdopodobnie metody które wywołujesz będą setki razy dłużej się wykonywać niż czas samego ich wywołania.

@olo16
 Jeśli wywołujemy metody wprost to wywołanie jest bardzo zoptymalizowane. Obawiam się iż w c# na delegaty nie powinno się patrzyć  po prostu jako skok pod pointer. Jest tam znacznie wiecej do roboty, zauważmy iż delegaty w c# są multicastowe tą funkcjonalność jakoś trzeba obsłużyć.

http://msdn.microsoft.com/en-us/library/ms973852.aspx
Ta stronka podaje czasy dla operacji wykonywanych w CLR.
Poniżej podaje czasy minimalne z tej stronki:
Cytuj
1.1 GHz Pentium-III PC running Windows XP and .NET Framework v1.1
Cytuj
40.9    delegate invoke
6.1    static call
0.2    inlined static call
1.0    inlined instance call
6.8    instance call
0.2    inlined this inst call
6.2    this instance call
5.4    virtual call
5.4    this virtual call
6.5    interface call
1.0    inst itf instance call
0.2    this itf instance call
5.4    inst itf virtual call
5.4    this itf virtual call

Dane te są jeszcze z .Net 1.1 wiem iż troszku to przyspieszyli od tamtego czasu, pytanie tylko jak bardzo.

Offline Xender

  • Użytkownik

# Luty 20, 2012, 21:55:00
OK, mój błąd. W takim razie może da się użyć czegoś z mniejszym overheadem - vcalla na przykład? Bo nawet jeśli wywołania tych 40 funkcji da się zinlinować, to nie wiem jak z instrukcjami warunkowymi.

Offline koirat

  • Użytkownik

# Luty 20, 2012, 23:34:35
Jeśli zastosujemy switch-a w którym przypadki są liczbami ustawionymi po kolei to kompilator przerobi to na tablice "skoków" - jak już wcześniej wspominałem w tym wątku. I narzut wyboru metody mamy wtedy marginalny.