Dziś kolejny wpis na temat mikro-optymalizacji. Oczywiście dla większości aplikacji biznesowych taka różnica w wydajności nie ma kluczowego znaczenia. Myślę jednak, że jest to ciekawe z punktu widzenia IL i jak naprawdę działa język c#. Jeśli ktoś z kolei piszę np. grę albo aplikację czasu rzeczywistego, wtedy ma to już znaczenie, co robimy w każdej sekundzie.
Zacznijmy od razu od wniosku: foreach w niektórych przypadkach jest znacząco wolniejszy od klasycznego for. Nie powinno to dziwić – w końcu iterator dodaję kolejną warstwę abstrakcji.
Spójrzmy na poniższy program, który posłuży nam jako dowód:
internal class Program { private static void Main(string[] args) { int[] data = Enumerable.Range(0, 1000000).ToArray(); Stopwatch stopWatch1 = Stopwatch.StartNew(); TestForeachWithArray(data); Console.WriteLine(stopWatch1.ElapsedTicks); Stopwatch stopWatch2 = Stopwatch.StartNew(); TestForeachWithEnumerable(data); Console.WriteLine(stopWatch2.ElapsedTicks); Stopwatch stopWatch3 = Stopwatch.StartNew(); TestForWithArray(data); Console.WriteLine(stopWatch3.ElapsedTicks); } private static void TestForeachWithArray(int[] data) { foreach (int item in data) { } } private static void TestForeachWithEnumerable(IEnumerable<int> data) { foreach (int item in data) { } } private static void TestForWithArray(int[] data) { for (int i = 0; i < data.Length; i++) { int item = data[i]; } } }
Wynik:
Program przedstawia 3 testy. Pierwszy korzysta z foreach, ale operuje na zwykłej tablicy danych. Drugi również jest oparty na foreach, ale przechodzi przez typ enumerable. Ostatni test korzysta ze zwykłej pętli for i tablicy danych. Wynik foreach+tablica jest bardzo podobny do for+tablica. Połączenie jednak foreach i enumerable jest dużo wolniejsze. Dzieje się to mimo faktu, że enumerable wskazuje tak naprawdę na tablicę więc teoretycznie nie powinno mieć to znaczenia.
Pozostaje wyjaśnić dlaczego wyłącznie foreach+enumerable jest taki wolny. Ostatnie wpisy były o IL assembly, stąd nie powinno budzić zaskoczenia, że ILSpy czy Reflector będzie pierwszym narzędziem jakim posłużymy się.
IL dla TestForeachWithArray:
IL_0000: ldarg.0 IL_0001: stloc.0 IL_0002: ldc.i4.0 IL_0003: stloc.1 IL_0004: br.s IL_000e // loop start (head: IL_000e) IL_0006: ldloc.0 IL_0007: ldloc.1 IL_0008: ldelem.i4 IL_0009: pop IL_000a: ldloc.1 IL_000b: ldc.i4.1 IL_000c: add IL_000d: stloc.1 IL_000e: ldloc.1 IL_000f: ldloc.0 IL_0010: ldlen IL_0011: conv.i4 IL_0012: blt.s IL_0006 // end loop
TestForWithArray:
IL_0000: ldc.i4.0 IL_0001: stloc.0 IL_0002: br.s IL_000c // loop start (head: IL_000c) IL_0004: ldarg.0 IL_0005: ldloc.0 IL_0006: ldelem.i4 IL_0007: pop IL_0008: ldloc.0 IL_0009: ldc.i4.1 IL_000a: add IL_000b: stloc.0 IL_000c: ldloc.0 IL_000d: ldarg.0 IL_000e: ldlen IL_000f: conv.i4 IL_0010: blt.s IL_0004
Zanim przejdziemy do TestForeachWithEnumerable, przeanalizujmy powyższe dwa fragmenty kodu. Wyglądają one praktycznie tak samo. Obydwa korzystają z instrukcji skoku blt. Tak naprawdę kompilacja (pierwsza faza dokonywana przez VS) zamieni foreach na zwykł for, jeśli operujemy na tablicy danych. Niestety taka konwersja jest niemożliwa, gdy korzystamy z enumerable, nawet jak wskazuje on na tablicę. IL dla TestForeachWithEnumerable wygląda bardzo skomplikowanie:
IL_0000: ldarg.0 IL_0001: callvirt instance class [mscorlib]System.Collections.Generic.IEnumerator`1<!0> class [mscorlib]System.Collections.Generic.IEnumerable`1<int32>::GetEnumerator() IL_0006: stloc.0 .try { IL_0007: br.s IL_0010 // loop start (head: IL_0010) IL_0009: ldloc.0 IL_000a: callvirt instance !0 class [mscorlib]System.Collections.Generic.IEnumerator`1<int32>::get_Current() IL_000f: pop IL_0010: ldloc.0 IL_0011: callvirt instance bool [mscorlib]System.Collections.IEnumerator::MoveNext() IL_0016: brtrue.s IL_0009 // end loop IL_0018: leave.s IL_0024 } // end .try finally { IL_001a: ldloc.0 IL_001b: brfalse.s IL_0023 IL_001d: ldloc.0 IL_001e: callvirt instance void [mscorlib]System.IDisposable::Dispose() IL_0023: endfinally } // end handler
Od razu widać, że foreach dodaje bardzo dużo komplikacji. Można zauważyć m.in. try-catch-finally oraz drogą instrukcję callvirt – wywołanie metody wirtualnej, co spowoduje przeszukanie vtable.
W aplikacjach biznesowych ważniejsza jest jednak łatwość w utrzymaniu, stąd zwykle posiadamy wiele warstw w systemie, aby operować na abstrakcji. W takich sytuacjach ważniejsze dla nas jest, aby np. odseparować sposób w jaki przeglądamy dane od nich samych. Nie są to podejścia najbardziej wydajne, ale nie stanowią problemu dla wspomnianych aplikacji. Inne podejście akurat mają programiści np. sterowników kart graficznych czy gier komputerowych. Tam po prostu są inne wyzwania i priorytety.
Cześć,
bardzo fajny temat, dodatkowo przydała by się informacja czy jakikolwiek interfejs może zostać zoptymalizowany foreach -> for.
Dobry artykuł, na pewno przyda mi się w przyszłości 🙂
Jeżeli dobrze pamiętam, niektóre VMy (dokładnie mowa o Oracle HotSpot JVM oraz Chrome V8) są w stanie generować wyspecjalizowane odpowiedniki metod zoptymalizowane do konkretnego przypadku. W takim wypadku może nastąpić dynamiczna analiza struktur przekazywanych jako IEnumerable do wnętrza drugiej metody, a następnie – w przypadku kiedy np. została ona wywołana 1000 razy z parametrem w postaci tablicy – wygenerowana zostanie wyspecjalizowana “inline’owa” wersja tej metody zoptymalizowana specjalnie pod kątem tej kolekcji.
Taki proces wymaga jednak “rozgrzania” maszyny wirtualnej. Nie wiem czy obecny bądź przyszły CLR jest zdolny do wykonywania takich optymalizacji (może znasz odpowiedź?). Jeżeli rzeczywiście tak jest, podany przez Ciebie przykład nie byłby w stanie tego udowodnić.