19/11/2012

StackOverflowException - jak sobie z nim radzić

Home

Każdy programista, czy to C#, C++ czy Java, musiał się kiedyś spotkać z przepełnieniem stosu, który, w przypadku platformy .NET, objawia się wyjątkiem StackOverflowException. Najłatwiej do takiego błędu doprowadzić pisząc nieskończoną rekursję. W tym poście zajmę się jednak tym jak poradzić sobie z przepełnieniem stosu, kiedy napisana metoda rekurencyjna wcale nie jest nieskończona. Zacznijmy od przykładu. Załóżmy, że mamy klasę Node i przy jej pomocy tworzymy drzewo binarne, w którym dla uproszczenia będziemy przechowywać liczby. Drzewa, które rozpatrujemy w tym przypadku nie są drzewami przeszukiwań i mogą być niezrównoważone.

public class Node
{
 public uint Data { get; set; }

 public Node Left { get; set; }
 public Node Right { get; set; }
}

Napisaliśmy również metodę rekurencyjną przeszukującą zadane drzewo w poszukiwaniu węzła przechowującego określoną wartość.

public static Node FindRec(Node root, uint i)
{
 if (root == null)
  return null;

 if (root.Data == i)
  return root;

 var res = FindRec(root.Right, i);

 if (res != null)
  return res;

 return FindRec(root.Left, i);
}

Metoda ta będzie działać, ale do czasu. Utwórzmy zdegenerowane drzewo czyli takie, które w rzeczywistości jest listą. Do wygenerowania takiego drzewa użyjemy następującego kodu:

public static Node CreateDegeneratedTree(uint noOfNodes)
{
 Node root = new Node() { Data = 0 };
 Node temp = root;

 for (uint i = 0; i <= noOfNodes; ++i)
 {
  temp.Right = new Node() { Data = i };
  temp = temp.Right;
 }

 return root;
}

W przypadku wystarczająco dużej liczby węzłów w zdegenerowanym drzewie (patrz parametr noOfNodes) wywołanie FindRec zakończy się wyjątkiem StackOverflowException. Wbrew pozorom, nie musi to być jakaś ogromna wartość. Na komputerze, na którym testowałem ten kod, wystarczyło aby drzewo zawierało 10 tyś węzłów. Trochę mało, czyż nie?

W takiej sytuacji musimy zrezygnować z rekursji na rzecz poczciwej pętli. Ja bym napisał taki kod:

public static Node Find(Node root, uint i)
{
 Queue<Node> toCheck = new Queue<Node>();
 toCheck.Enqueue(root);

 while (toCheck.Count > 0)
 {
  var node = toCheck.Dequeue();

  if (node != null)
  {
   if (node.Data == i)
    return node;
    
   toCheck.Enqueue(node.Right);
   toCheck.Enqueue(node.Left);
  }
 }

    return null;
}

Korzystam w nim z pomocniczej kolekcji, do której wrzucam kolejne węzły do sprawdzenia. Pętla kręci się dopóki nie zostanie znaleziony szukany węzeł albo dopóki wszystkie węzły nie zostaną sprawdzone. Podobne podejście możemy zastosować dla innych dla innych zagadnień tego typu.

Problem z StackOverflowException można również rozwiązać w sposób nie algorytmiczny, poprzez zwiększenie domyślnego rozmiaru stosu (1MB) przy pomocy narzędzia editbin albo tworząc nowy wątek o odpowiedniej wielkości stosu. Ja był jednak tego nie robił. Jeśli można osiągnąć jakiś efekt pisząc kod w odpowiedni sposób, to należy tak zrobić. W swojej karierze nie spotkałem jeszcze przypadku kiedy musiałbym zwiększyć wielkość stosu.

Na koniec załączam jeszcze kod metody Main. Cały program pozwala pobawić się pokazanymi powyżej metodami do wyszukiwania (iteracyjną i rekurencyjną) dla zdegenerowanego drzewa o zadanej liczbie węzłów. Program umożliwia również ustalenie wielkości stosu (w celach edukacyjnych :)). Kod może i jest trochę pokraczny, ale dla celów edukacyjnych się nada. Uwaga! Podanie zbyt dużej wartości jako Stack size in kilobytes (0 for default): albo Number of nodes in tree: może zakończyć się OutOfMemoryException.

static void Main(string[] args)
{
    Console.Write("Do you want to use recursion (Y for yes)?: ");
    
    string line = Console.ReadLine();
    bool useRecursion = String.Equals(line, "Y", StringComparison.OrdinalIgnoreCase);

    if(useRecursion)
        Console.WriteLine("Recursion search will be used");

    Console.Write("Stack size in kilobytes (0 for default): ");

    line = Console.ReadLine();
    uint stackSize;
    if (!UInt32.TryParse(line, out stackSize))
        stackSize = 1024

    Console.WriteLine("Stack size is {0} kilobytes ", stackSize);

    var th = new Thread(
  new ThreadStart(() =>
  {
   Console.Write("Number of nodes in tree: ");

   while ((line = Console.ReadLine()) != String.Empty)
   {
    uint noOfNodes;
    if (UInt32.TryParse(line, out noOfNodes))
    {
     Node root = CreateDegeneratedTree(noOfNodes);

     Stopwatch sw = new Stopwatch();

     if (useRecursion)
     {
      sw.Start();
      var res = FindRec(root, noOfNodes);
      sw.Stop();
     }
     else
     {
      sw.Start();
      var res = Find(root, noOfNodes);
      sw.Stop();
     }

     root = null;
     Console.Write("Processing time (ms): {0}\n\n", sw.ElapsedMilliseconds);
    }

    Console.Write("Number of nodes in tree: ");
   }
  }), (int)stackSize * 1024);

 th.Start();
}

29/10/2012

Trochę więcej o serializacji

Home

W poprzednim poście pisałem o serializacji XML'owej, a w tym wrócę jeszcze do tematu. Skorzystamy z tego samego kodu co poprzednio ale tym razem uruchomimy go korzystając z innych serializatorów. Zamieńmy, więc XmlSerializer na SoapFormatter lub BinaryFormatter i uruchommy przykładowy kod jeszcze raz (można użyć też DataContractSerializer ale z drobną modyfikacją kodu).

Efekt końcowy będzie inny niż dla serializatora XML'owego - po deserializacji właściwość Name będzie miała taką samą wartość jak przed serializacją. To nie jedyna różnica. Jeśli do konstruktora domyślnego dodamy linijkę:

Console.WriteLine("I'm in a constructor");

i popatrzymy na liczbę wypisanych na ekran napisów I'm in a constructor to okaże się, że w przypadku serializatora XML'owego konstruktor domyślny został wywołany dwa razy (przy tworzeniu obiektu oraz przy deserializacji), a w przypadku pozostałych klas tylko jeden raz (przy tworzeniu obiektu).

Należy postawić pytanie, jak w takim razie pozostałe serializatory tworzą obiekty przy deserializacji. Przecież muszą wołać jakiś konstruktor. Otóż nie koniecznie. O ile wiem taki BinaryFormatter, pozostałe serializatory korzystają zapewne z podobnych mechanizmów, używa metody FormatterServices.GetSafeUninitializedObject, która jest odpowiedzialna za zaalokowanie odpowiednio dużego fragmentu pamięci dla obiektu zadanego typu.

Po co to wszystko? Czy nie łatwiej wywołać konstruktor? Początkowo pomyślałem, że to kwestia wydajności. Ale szybki test pokazuje, że użycie FormatterServices.GetSafeUninitializedObject jest troszkę wolniejsze niż utworzenie obiektu za pomocą konstruktora.

var s = new Stopwatch();
s.Start();

for(int i = 0; i < 1000000; ++i)
 FormatterServices.GetSafeUninitializedObject(typeof(A));

s.Stop();

Console.WriteLine(s.ElapsedMilliseconds); //Na mojej maszynie ~130 ms

s.Reset();
s.Start();

for (int i = 0; i < 1000000; ++i)
    new A();

s.Stop();

Console.WriteLine(s.ElapsedMilliseconds); //Na mojej maszynie ~20 ms
Po chwili zastanowienia doszedłem do innego wniosku. Otóż, jeśli na proces deserializacji popatrzymy jak na proces "przywracania do życia" już raz utworzonych obiektów, to ponowne wywołanie konstruktora po prostu nie ma sensu albo wręcz jest niewskazane. Macie jakieś inne pomysły? Jak sądzicie czemu jedne serializatory wołają konstruktor, a inne nie?

27/10/2012

XmlSerializer- taka ciekawostka

Home

Serializator XML'owy platformy .NET jest bardzo łatwy i przyjemny w użyciu, ale czasami jego działanie może sprowadzić nas na manowce. Poniższy kod obrazuje o co mi chodzi. Zacznijmy od przykładowej, bardzo prostej klasy, którą będziemy serializować:

public class A
{
 public string Name { get; set; }
 
 public A()
 {
  Name = "Hello"; 
 }
}

Oraz kawałka kodu:

var obj = new A() { Name = null };

var stream = new MemoryStream();
var serializer = new XmlSerializer(typeof(A));

serializer.Serialize(stream, obj);

stream.Position = 0;

var obj2 = (A)serializer.Deserialize(stream);

Kod jest bardzo prosty. Tworzymy obiekt klasy A i ustawiamy właściwość Name na null. Następnie zapisujemy obiekt do strumienia. Po zapisaniu przesuwamy wskaźnik odczytu/zapisu strumienia na początek aby móc zdeserializować obiekt. W czym tkwi haczyk? Spróbujcie odpowiedzieć na to pytanie bez zaglądania do dalszej części posta:

Jaka będzie wartość właściwości Name po odczytaniu obiektu ze strumienia?

Otóż po zdeserializowaniu właściwość Name nie będzie pusta. Serializator XML'owy odczytując obiekt ze strumienia najpierw wywoła konstruktor domyślny. Potem zobaczy, że w strumieniu właściwość Name jest pusta i stwierdzi, że w takim wypadku nie trzeba niczego przypisywać do właściwości Name deserializowanego obiektu. W konstruktorze znajduje się natomiast kod, który ustawia tą właściwości. A więc po zdeserializowaniu właściwość Name będzie zawierała ciąg znaków "Hello", czyli inną niż przed serializacją.

Teraz wyobraźmy sobie trochę bardzie skomplikowaną sytuację. Załóżmy, że mamy kod pobierający jakieś dane z bazy danych i ładujący je do odpowiednich klas. Klasy te są napisane w podobny sposób jak klasa A powyżej, czyli w konstruktorze domyślnym niektóre właściwości są inicjowane wartościami innymi niż null. Dane (obiekty) są następnie udostępniane aplikacji klienckiej przez web service'y (stare dobre ASMX, usługi WCF jeśli użyto XmlSerializerFormatAttribute)  czyli muszą być najpierw zserializowane, a potem zdeserializowane. Kod działa poprawnie.

Teraz zabieramy się za pisanie testów integracyjnych i używamy tego samego kodu odpowiedzialnego za wczytywanie danych. W momencie, kiedy chcemy użyć tych samych obiektów (tak samo stworzonych i wypełnionych danymi) co aplikacja kliencka, nawet w ten sam sposób, okazuje się, że dostajemy wyjątek NullReferenceException.

Dlaczego? Ano dlatego, że w testach integracyjnych obiekty nie zostały przesłane przez sieć, czyli nie były serializowane i deserializowane, czyli konstruktor domyślny nie został wywołany drugi raz przy deserializacji i puste właściwości nie zostały ustawione tak jak opisano powyżej.

Jak w wielu innych podobnych sytuacjach, to żadna wiedza tajemna, ale jak się o tym nie wie, może napsuć trochę krwi. Pomijam tutaj fakt, że korzystanie z opisanej "funkcjonalności", świadomie czy nie, nie jest najlepszym pomysłem.

14/10/2012

Make Object ID

Home

Z komendy Make Object ID korzystam już od bardzo dawna, nie codziennie ale w niektórych sytuacjach jest ona nieodzowna. Ostatnio zorientowałem się jednak, że nawet doświadczeni użytkownicy VS mogą o niej wiedzieć i stąd pojawił się pomysł na ten post.





Make Object ID to komenda (pokazana na powyższych zrzutach ekranu), która dostępna jest z poziomu menu kontekstowego w okienku Locals i Watch czy też z poziomu edytora kodu. Po jej wywołaniu dla danego obiektu zostanie wygenerowany identyfikator. Nadanie identyfikatora objawia się tym, że w oknie Locals czy też Watch w kolumnie Value zostanie dodany przyrostek {ID#}.



Mając taki identyfikator możemy w dowolnym momencie debugowania programu odwołać się do danego obiektu i podejrzeć jego zawartość wpisując w okienku Watch identyfikator w formacie ID#. Co najważniejsze możemy to zrobić nawet jeśli w danym momencie nie mamy dostępu (referencji) do danego obiektu:



Wyobraźmy sobie, że debugujemy problem i dochodzimy do wniosku, że stan jakiegoś obiektu zmienił się w niepowołany sposób pomiędzy jego utworzeniem/zainicjowaniem, a miejscem użycia. Niestety prześledzenie "drogi" jaką przebył obiekt krok po kroku jest bardzo trudne. W międzyczasie wywołanych zostało setki jeśli nie tysiące metod, kod jest skomplikowany, uzyskanie referencji do danego obiektu jest w wielu miejscach trudne lub niemożliwe itd. W tym przypadku Make Object ID ułatwi nam znalezienie miejsca gdzie obiekt został popsuty. W praktyce mogłoby wyglądać to tak:
  • Generujemy identyfikator dla obiektu w momencie jego inicjalizacji.
  • Stawiamy pułapkę w miejscu gdzie podejrzewamy, że obiekt jest już zmieniony.
  • Po zatrzymaniu się na pułapce sprawdzamy stan obiektu.
  • Jeśli obiekt jest zmieniony to przesuwamy pułapkę w kierunku miejsca gdzie został zainicjowany.
  • Jeśli obiekt jest niezmieniony to przesuwamy pułapkę w kierunku przeciwnym do miejsca gdzie został zainicjowany.
  • Powtarzamy procedurę.
Opisana procedura to coś w rodzaju przeszukiwania połówkowego, prosty ale skuteczny sposób. Make Object ID przyda się za każdym razem kiedy chcemy podejrzeć stan obiektu, do którego w danym momencie nie możemy się w łatwy sposób odwołać.

Na koniec dwie uwagi. Spotkałem się z informacją, że Make Object ID jest dostępne tylko w Visual Studio w wersji Ultimate. Nie mam teraz dostępu do innej wersji środowiska więc nie mogę tego zweryfikować. Po drugie, o ile wiem, nie istnieje sposób aby wylistować listę obiektów i nadanych im identyfikatorów. W praktyce trzeba więc albo zapamiętać albo zapisać sobie na kartce nadane identyfikatory.

14/09/2012

Dziwne zachowanie konstruktora statycznego - ciąg dalszy 2

Home

Niedawno kolega opowiedział mi o jeszcze jednym przypadku kiedy opisane przeze mnie zachowanie konstruktora statycznego w środowiskach x86/x64 doprowadziło do kłopotów. Scenariusz był dość ciekawy, dlatego go opiszę na uproszczonym przykładzie. Zacznijmy od tego, że napisaliśmy zarządzany komponent COM. Komponent ten w konstruktorze statycznym czyta wartość jakiegoś parametru konfiguracyjnego z pliku i na tej podstawie coś robi. W poniższym przykładzie, żeby nie komplikować sprawy, po prostu zapisuje jego wartości do pliku:

[ComVisible(true)]
public class MySimpleCOM : ServicedComponent
{
 static MySimpleCOM()
 {
  File.AppendAllText(
   @"c:\log.txt",
   String.Format("Value of configuration parameter = '{0}' in the domain '{1}'\n.", ConfigurationManager.AppSettings["Test"], AppDomain.CurrentDomain.FriendlyName));
 }
 
 public MySimpleCOM() {}
 public void Fun() {}
}

Dodam jeszcze, że do pliku AssemblyInfo.cs w projekcie z naszym zarządzanym komponentem zostały dodane takie atrybuty:

[assembly: ApplicationActivation(ActivationOption.Server)]
[assembly: ApplicationAccessControl(false)]

ApplicationActivation zapewnia, że nasz komponent będzie hostowany poza procesem, w którym się do niego odwołamy, dokładniej przez proces dllhost.exe. Drugi atrybut jest opcjonalny ale ułatwia testy i mówi, że nie jest wymagana żadna kontrola dostępu (uprawnień) kiedy ktoś będzie próbował użyć naszego komponentu. Kod testujący nasz komponent jest jeszcze prostszy:

class Program
{
 static void Main(string[] args)
 {
  using (var host = new MySimpleCOM())
  {
   host.Fun();
  }
 }
}

Warto zwrócić uwagę, że nie trzeba samemu rejestrować komponentu. Zostanie to zrobione za nas.

Na koniec dodajemy jeszcze do pliku konfiguracyjnych programu testującego (app.config) oraz komponentu COM (Application.config) sekcję appSettings z parametrem test. Dla rozróżnienia niech wartość tego parametru różni się w obu przypadkach np.:

<appSettings>
 <add key="test" value="Tester"/>
</appSettings>

oraz

<appSettings>
 <add key="test" value="COM"/>
</appSettings>

Aby zobaczyć na czym dokładnie polega problem najłatwiej postąpić w następujący sposób. Najpierw kompilujemy oba projekty z opcją x86, uruchamiamy i zaglądamy do pliku z log.txt. Dalej kompilujemy ponownie oba projekty z opcją x64 i znowu uruchamiamy pamiętając aby uprzednio odinstalować wersję x86 komponent COM. Można to zrobić na przykład przy pomocy narzędzia Usługi składowe (dcomcnfg) wbudowanego w system Windows.

W pierwrzym przypadku (x86) plik log.txt będzie wyglądał tak:

Value of configuration parameter = 'COM' in the domain 'DefaultDomain'.

A w drugim (x64) w następujący sposób:

Value of configuration parameter = 'COM' in the domain 'DefaultDomain'.
Value of configuration parameter = 'Tester' in the domain 'Tester.vshost.exe'.

Jak widać w przypadku środowiska x64 kod inicjalizujący w konstruktorze statycznym został wywołany dwa razy, do tego z różnymi wartościami parametru konfiguracyjnego. W prawdziwym systemie mogłoby to doprowadzić do powstania jakichś błędów i chyba sami przyznacie, że ich przyczyna nie byłaby trywialna do wykrycia.

PS.

Jeśli przy własnoręcznym odtwarzaniu tego scenariusza napotkacie problem, że komponent COM nie będzie czytał konfiguracji ze pliku Application.config, to odsyłam na przykład do tego wpisu, w którym wszystko jest wyjaśnione.