Optymalizacja kodu C# – część III  

Autor: Piotr Zieliński

Opublikowano: 2013-03-07

Wprowadzenie

Kolejna część cyklu o pisaniu optymalnego kodu C# będzie dotyczyć głównie metod: rekurencja ogonowa, metody statyczne oraz konstruktory statyczne. Ponadto, przedstawiony zostanie przykład prawidłowego tworzenia listy, o którym często programiści zapominają. W przypadku rekurencji, zaprezentowana zostanie m.in. prosta transformacja, umożliwiająca łatwą implementację algorytmu w sposób iteracyjny.

Rekurencja ogonowa

Ze względów wydajnościowych należy zdecydowanie unikać rekurencji, której jedyną zaletą jest łatwość jej zaimplementowania, szczególnie dla algorytmów matematycznych, definiowanych nierzadko właśnie za pomocą rekurencji. Z kolei, główną wadą jest wysokie zapotrzebowanie na pamięć i generowanie zbyt dużego stosu, który dla większych liczb może spowodować StackOverflow. Alokacja takiej pamięci jest również czasochłonna.

W inżynierii oprogramowania pewien typ rekurencji zasługuje na szczególną uwagę, a mianowicie rekurencja ogonowa (tail recursion). Rekurencja ogonowa ma miejsce, gdy wywołanie rekurencyjnej funkcji jest dokładnie ostatnią instrukcją w danej metodzie. W takiej sytuacji, tak naprawdę, nie jest potrzebny stos. Skoro jest to ostatnia instrukcja, to znaczy, że nie trzeba przechowywać na stosie zmiennych lokalnych, ponieważ nie są one używane. Wystarczy po prostu powrócić do początku funkcji i przekazać nowe parametry. Najprostszy przykład może wyglądać następująco:

private static void RecursiveLoop(int iterationsCount)
{
          if(iterationsCount<=0)
              return;
          Console.WriteLine(iterationsCount);
          RecursiveLoop(iterationsCount-1);
}

Powyższa funkcja to zwykła pętla zaimplementowana w sposób rekurencyjny (przykład typowo akademicki). Warunkiem rekurencji ogonowej jest fakt, że wywołanie rekurencyjne jest ostatnią instrukcją w danej funkcji. Powyższy kod spełnia to i oznacza to, że nie trzeba, tak naprawdę, marnować zasobów na stos. Jeśli RecursiveLoop(10) wywołuje RecursiveLoop(9), to zmienne lokalne (iterationsCount) nie są w ogóle potrzebne. Wystarczy, że zamiast wywołania rekurencyjnego, adres aktualnie wykonywanej instrukcji zostanie ustawiony na początek funkcji, a parametry wejściowe zostaną w odpowiedni sposób podmienione:

private static void RecursiveLoop(int iterationsCount)
{
    begin:
    if(iterationsCount<=0)
         return;
    Console.WriteLine(iterationsCount);
          
    // RecursiveLoop(iterationsCount-1); niepotrzebne
    iterationsCount = iterationsCount - 1; // podmiana parametrów
    goto begin; // UWAGA: GOTO jest złą praktyką. Dodano tylko po to,
                // aby ułatwić zrozumienie rekurencji ogonowej
}

Jak pokazano na powyższym przykładzie, rekurencję ogonową łatwo zastąpić podejściem iteracyjnym za pomocą podmiany parametrów i przeskoczeniem do pierwszej instrukcji. Oczywiście goto jest złą praktyką i lepiej skorzystać z while lub, w tym przypadku, po prostu z for.

Powyższy przykład w praktyce nie występuje, bo każdy skorzystałby z for – jest to naturalne podejście. Ale łatwo sobie wyobrazić np. implementację silni. W takiej sytuacji podejście rekurencyjne jest już naturalne, ponieważ pokrywa się z wzorem matematycznym:

static int Factorial(int n)
{
    if (n < 2)
        return 1;
    return n * Factorial(n - 1);
}

Niestety, powyższa postać nie jest rekurencją ogonową, ponieważ występuje tam zmienna ‘n’. W takiej formie, stos jest niezbędny, gdyż po powrocie z Factorial trzeba pomnożyć wynik przez ‘n’, który jest przechowywany właśnie na stosie. Na szczęście można przerobić funkcję tak, aby wywołanie rekurencyjne było ostatnią instrukcją w funkcji:

static int Factorial(int n,int product=1)
{
        if (n < 2)
            return product;
        return Factorial(n - 1, product * n);
}

W tej chwili funkcja jest już rekurencją ogonową i łatwo ją zamienić na rozwiązanie iteracyjne:

static int Factorial(int n,int product=1)
{
        while (n>=2)
        {                
            product = product * n;
            n = n - 1;
        }                        
        return product;
}

Ze względu na specjalne właściwości rekurencji ogonowej, część kompilatorów (np. F#) jest w stanie zoptymalizować kod, tworząc iteracyjną wersję algorytmu. Programiści mogą zatem pisać rekurencyjne algorytmy, które są łatwiejsze w napisaniu i zrozumieniu, a niektóre kompilatory zoptymalizują to do podejścia iteracyjnego. Niestety C# nie wspiera tego rozwiązania (a przynajmniej w pełni). Z kolei, sam CLR potrafi rozpoznać rekurencję ogonową i ją zoptymalizować. Na dzień dzisiejszy C# x86 tego nie wspiera i programiści sami muszą dokonać optymalizacji. Warto jednak wspomnieć, że x64 JITer może wyemitować optymalny kod (iteracyjny). Pisząc kod, należy również rozważać platformę x86, która nigdy nie rozpozna rekurencji ogonowej.

Statyczne konstruktory

Konstruktory statyczne służą zwykłe do inicjalizowania pól statycznych lub walidacji typów generycznych np.:

class Generic<T> where T: struct
{
    static Generic() {
        if (!typeof(T).IsEnum) {
            throw new ArgumentException("T must be an enum");
        }
    }
}

Dobrą informacją jest fakt, że statyczne konsturktory są thread-safe, co ułatwia implementację pewnych wzorców projektowych. Domyślnie statyczne konstuktory są generowane wyłącznie, gdy dana klasa posiada jakieś pola statyczne. Pytanie brzmi: kiedy konstruktor statyczny jest wywoływany?

CLR daje gwarancję, że:

• operacje w konstruktorze są thread-safe,
• konstruktor zostanie wywołany przed dostępem do pierwszego pola danej klasy. CLR nie określa kiedy dokładnie dojdzie do wywołania.

Pierwsza kwestia powinna być jasna, ale druga z pewnością wymaga rozwinięcia:

1. Konstruktor może zostać wywołany od razu przed dostępem do danego pola (precise semantics).
2. Konstruktor może być wywołany w jakimkolwiek momencie  przed dostępem do pola (before-init-semantics). Zgodnie z tym podejściem, konstruktor może zostać wywołany dużo wcześniej niż można byłoby się tego spodziewać.

Preferowane jest drugie podejście, ponieważ daje więcej swobody CLR i dzięki temu wywołanie może zostać zoptymalizowane. Programiści nie mogą jawnie określić sposobu wywołania konstruktora, ale istnieją pewne zasady, pomagające zrozumieć, w jaki sposób CLR wybiera odpowiednią semantykę. Przykład:

public class BeforeInitSemantics
{
   public static int Value = 10;
}
public class PreciseSemantics
{
   public static int Value;
   static PreciseSemantics()
   {
       Value = 20;
   }
}

Pierwsza klasa zostanie oznaczona jako before-init, ponieważ konstruktor nie jest jawnie zdefiniowany, i dlatego zostanie wygenerowany automatycznie (to właśnie w nim Value zostanie ustawiona na 10). Taka sytuacja jest najoptymalniejsza, ponieważ CLR sam zadba o jak najwyższą wydajność. Można się o tym przekonać, zaglądając do IL:

.class auto ansi nested public beforefieldinit BeforeInitSementics
    extends [mscorlib]System.Object
{
    .method private hidebysig specialname rtspecialname static void .cctor() cil managed
    {
    }

    .method public hidebysig specialname rtspecialname instance void .ctor() cil managed
    {
    }
    .field public static int32 Value
}

.method public hidebysig specialname rtspecialname instance void .ctor() cil managed
{
    .maxstack 8
    L_0000: ldarg.0
    L_0001: call instance void [mscorlib]System.Object::.ctor()
    L_0006: ret
}

Pierwsza klasa została oznaczona flagą beforefieldinit. Reguła jest prosta i wszystkie klasy z jawnymi konstruktorami nie będą opatrzone flagą beforefieldinit. Gdyby umożliwić wywołanie jawnych konstruktorów, które zawierają nieznaną logikę, mogłoby to spowodować efekty uboczne. Jest to w pełni zrozumiałe, ale  czy nie byłoby lepiej, gdyby użytkownicy mogli o tym również sami decydować? Programista, który zaimplementował dany konstruktor zdaje sobie sprawę, że logika w nim zawarta może przynieść efekty uboczne.

Warto dokładnie przenalizować wpływ konstruktorów statycznych na wydajność. Rozważmy następujący przykład:

public class BeforeInitSementics
{
    public static int Value = 10;
}
public class PreciseSemantics
{
    public static int Value;
    static PreciseSemantics()
    {
        Value = 20;
    }
}
internal class Program
{
    private const int Iterations = 100000000;

    private static void Test1()
    {
        // Precise
        Stopwatch stopwatch = Stopwatch.StartNew();
        for (int i = 0; i < Iterations; i++)
        {
            PreciseSemantics.Value = 10;
        }
        stopwatch.Stop();
        Console.WriteLine("Precise:{0}",stopwatch.ElapsedMilliseconds);

        // Before-init
        stopwatch = Stopwatch.StartNew();
        for (int i = 0; i < Iterations; i++)
        {
            BeforeInitSementics.Value = 10;
        }
        stopwatch.Stop();
        Console.WriteLine("Before-init:{0}", stopwatch.ElapsedMilliseconds);
    }
    private static void Main(string[] args)
    {
        Test1();
    }
}

W trybie Release uzyskano wyniki: 567 oraz 152. Różnica jest dość znacząca (kilkukrotna). Wspomniano już, że semantyka BeforeInit pozwala wyemitować wywołanie konstruktora w jakimkolwiek momencie. Kompilator jest na tyle sprytny, że emituje to przed pętlą for (tak więc cała logika będzie wykonana tylko raz). W przypadku semantyki precise musi to nastąpić przynajmniej o jedną linię kodu przed dostępem do pierwszego pola. Z tego wynika, że podejście precise będzie dużo wolniejsze – w każdej iteracji musi zostać wykonana pewna logika, taka jak synchronizacja, która sprawdza, czy konstruktor został już wywołany, itp.

Rozważmy kolejny przykład:

public class BeforeInitSementics
{
    public static int Value = 10;
}
public class PreciseSemantics
{
    public static int Value;
    static PreciseSemantics()
    {
        Value = 20;
    }
}
internal class Program
{
    private const int Iterations = 100000000;

    private static void Test1()
    {
        // Precise
        Stopwatch stopwatch = Stopwatch.StartNew();
        for (int i = 0; i < Iterations; i++)
        {
            PreciseSemantics.Value = 10;
        }
        stopwatch.Stop();
        Console.WriteLine("Precise:{0}",stopwatch.ElapsedMilliseconds);

        // Before-init
        stopwatch = Stopwatch.StartNew();
        for (int i = 0; i < Iterations; i++)
        {
            BeforeInitSementics.Value = 10;
        }
        stopwatch.Stop();
        Console.WriteLine("Before-init:{0}", stopwatch.ElapsedMilliseconds);
    }
    private static void Test2()
    {
        // Precise
        Stopwatch stopwatch = Stopwatch.StartNew();
        for (int i = 0; i < Iterations; i++)
        {
            PreciseSemantics.Value = 10;
        }
        stopwatch.Stop();
        Console.WriteLine("Precise:{0}", stopwatch.ElapsedMilliseconds);

        // Before-init
        stopwatch = Stopwatch.StartNew();
        for (int i = 0; i < Iterations; i++)
        {
            BeforeInitSementics.Value = 10;
        }
        stopwatch.Stop();
        Console.WriteLine("Before-init:{0}", stopwatch.ElapsedMilliseconds);
    }
    private static void Main(string[] args)
    {
        Test1();
        Test2();
    }
}

Test 1 wydrukuje takie same liczby jak w kroku I (567,151). Z kolei Test 2 wyświetli dwie podobne wartości (np. 151,151). Dlaczego? Wynika to z zasady emitowania wywołań do konstruktora. Kompilując metodę, kompilator sprawdza, czy konstruktor został już wywołany. Jeśli tak, nie trzeba już emitować żadnego kodu JIT, wywołującego konstruktor statyczny. W Test 1 kod taki został wyemitowany, ponieważ na tamtym etapie nie było jeszcze żadnego wywołania. Wyemitowany kod to m.in. synchronizacja, sprawdzenie, czy konstruktor został już wywołany. W Test 2 już wiadomo, że konstruktor statyczny został wykonany (w Test 1), zatem nie trzeba emitować jakiejkolwiek logiki. W takim przypadku Before i Precise zachowują się dokładnie tak samo.

Statyczne metody 

Pytanie brzmi: czy metody statyczne są wydajniejsze niż ich “zwykłe” odpowiedniki (instance methods)? Odpowiedź brzmi – tak, ponieważ:

• wywołanie jakiejkolwiek niestatycznej metody na klasie powoduje przekazanie parametru “this” – a to wymaga dodatkowego czasu,
• same wywołanie jest bardziej czasochłonne dla zwykłych metod. W klasach statycznych nie ma dziedziczenia i wirtualnych metod. W niestatycznych metodach kompilator musi dokonać kilka  dodatkowych operacji. Każda metoda niestatyczna jest wywoływana za pomocą instrukcji IL callvirt a statyczna call. callvirt musi sprawdzić całą hierarchie klas, co jest z reguły bardziej czasochłonne.

Napiszmy więc przykładowy test:

Stopwatch stopwatch=new Stopwatch();
stopwatch.Restart();

stopwatch.Stop();
stopwatch.Restart();

// wywolanie statycznej metody
for (int i = 0; i < testsNumber; i++)
 A.Method();

stopwatch.Stop();

long staticTime = stopwatch.ElapsedTicks;

stopwatch.Restart();

// wywolanie niestatycznej metody
for (int i = 0; i < testsNumber; i++)
 b.Method();

stopwatch.Stop();

long instanceTime = stopwatch.ElapsedTicks;

Wynik:

staticTime: 29864
instanceTime: 54746

Jaki z tego wniosek? Osobiście nie martwię się wydajnością, a skupiam się wyłącznie na prostym i przejrzystym projekcie. Wybierając typ metody, zastanawiam się bardziej, co jest lepsze dla API z punktu widzenia kosztów przyszłego utrzymania kodu. Dla biznesowych lub industrialnych aplikacji nie ma to znaczenia. Jeśli dla danego projektu taka mała różnica jest ważna, to lepiej zastanowić się nad zmianą języka, ponieważ C# nie został stworzony pod kątem takich problemów. Poza tym, z moich obserwacji wynika, że mają miejsce następujące dodatkowe optymalizacje:

• pierwsze wywołanie metody niestatycznej jest dużo bardziej czasochłonne niż pierwsze wywołanie metody statycznej,
• w trybie release wartości są dużą mniejsze – optymalizacja jest znacząca.

Powyższe rozważania należy zatem traktować jako ciekawostkę, która nie powinna decydować o wyborze metod statycznych lub niestatycznych. Najważniejszym kryterium wciąż musi być jakoś kodu, czytelność oraz łatwość jego późniejszego utrzymania.

Listy a alokacja nowej pamięci

Rozważmy następujący kod:

private IList<int> ParseString(string text)
{
  string[] numbersStr = text.Split(';');
  var numbers=new List<int>();
  foreach (string numberStr in numbersStr)
  {
      numbers.Add(Int32.Parse(numberStr));
  }
  return numbers;
}

Kod ma szereg problemów związanych z dobrymi praktykami, ale nie będą one tutaj omawiane. Z punktu wydajnościowego dużo lepszym podejściem byłoby użycie po prostu tablicy. Załóżmy jednak, że należy użyć listę. Jak to zrobić w sposób najbardziej optymalny?

Przede wszystkim trzeba zadać sobie pytanie, jak działa dynamiczna kolekcja danych „List”? Tak naprawdę jest to niestety zwykła tablica, która zmienia swój rozmiar, jeśli to tylko potrzebne. Początkowo tablica ma pojemność 0. W momencie dodania pierwszego elementu pojemność ustawiania jest na 4. Po przekroczeniu rozmiaru 4 podwajany jest on do 8, potem do 16, itp. Realokacja tablicy jest bardzo wolnym procesem, ponieważ należy stworzyć nową tablicę, a potem element po elemencie  skopiować zawartość. Jeśli rozmiar docelowy tablicy jest znany, warto przekazać początkową pojemność w konstruktorze:

private static IList<int> ParseString(string text)
{
  string[] numbersStr = text.Split(new[]{';'},StringSplitOptions.RemoveEmptyEntries);
  var numbers=new List<int>(numbersStr.Length);
  foreach (string numberStr in numbersStr)
  {
      numbers.Add(Int32.Parse(numberStr));
  }
  return numbers;
}

W taki sposób uniknięto ciągłej realokacji. Ponadto, List potrafi dostosowywać swoje wymagania do aktualnych potrzeb. Aby udowodnić to, warto napisać prosty program, pokazujący, jak zmienia się pojemność listy:

var numbers = new List<int>();
  Console.WriteLine(numbers.Capacity); // Pojemność: 0
  numbers.Add(1);
  Console.WriteLine(numbers.Capacity); // Pojemność: 4
  numbers.Add(1);
  numbers.Add(1);
  numbers.Add(1);
  numbers.Add(1);
  Console.WriteLine(numbers.Capacity); // Pojemność: 8
  numbers.Add(1);
  numbers.Add(1);
  numbers.Add(1);
  numbers.Add(1);
  Console.WriteLine(numbers.Capacity); // Pojemność: 16

Z jawną alokacją wygląda to następująco:

var numbers = new List<int>(16);
Console.WriteLine(numbers.Capacity); // Pojemność: 16
numbers.Add(1);
Console.WriteLine(numbers.Capacity); // Pojemność: 16
numbers.Add(1);
numbers.Add(1);
numbers.Add(1);
numbers.Add(1);
Console.WriteLine(numbers.Capacity); // Pojemność: 16

numbers.Add(1);
numbers.Add(1);
numbers.Add(1);
numbers.Add(1);
Console.WriteLine(numbers.Capacity); // Pojemność: 16

Duża część programistów używa domyślnego konstruktora, nie zastanawiając się, czy chociaż przybliżona liczba elementów jest znana. Nie zawsze trzeba podawać dokładny rozmiar, ale jeśli wiadomo, że lista powinna zajmować przynajmniej 50 elementów, wtedy warto przekazać 50 jako parametr do konstruktora.

Zakończenie

Niektóre optymalizacje, przedstawione w artykule, nie są zbyt duże i dlatego nie trzeba korzystać z nich zawsze – jakość kodu przede wszystkim. Mimo wszystko, warto znać te techniki, aby podejmować decyzje projektowe świadomie, a nie na zasadzie przypuszczeń. Z kolei transformacja rekurencji ogonowej do rozwiązania iteracyjnego ma zdecydowany wpływ na wydajność i zawsze powinna być przynamniej rozważana.

 

---

          

Piotr Zieliński

Absolwent informatyki o specjalizacji inżynieria oprogramowania Uniwersytetu Zielonogórskiego. Posiada szereg certyfikatów z technologii Microsoft (MCP, MCTS, MCPD). W 2011 roku wyróżniony nagrodą MVP w kategorii Visual C#. Aktualnie pracuje w General Electric pisząc oprogramowanie wykorzystywane w monitorowaniu transformatorów . Platformę .NET zna od wersji 1.1 – wcześniej wykorzystywał głównie MFC oraz C++ Builder. Interesuje się wieloma technologiami m.in. ASP.NET MVC, WPF, PRISM, WCF, WCF Data Services, WWF, Azure, Silverlight, WCF RIA Services, XNA, Entity Framework, nHibernate. Oprócz czystych technologii zajmuje się również wzorcami projektowymi, bezpieczeństwem aplikacji webowych i testowaniem oprogramowania od strony programisty. W wolnych chwilach prowadzi [blog o .NET i tzw. patterns & practices]http://www.pzielinski.com/.