Jak znaleźć brakujące indeksy w bazie danych?

Home

Optymalizacja bazy danych i zapytań to temat rozległy i szeroki jak morze i nie jedną książka napisano na ten temat. Ja dzisiaj napiszę o dosyć prostej technice pozwalającej znaleźć brakujące indeksy w bazie danych MSSQL. Zapewne każdy korzystający z MSSQL Management Studio wie, że można poprosić o wyświetlenie planu wykonania zapytania (opcje Dispaly Actual Execution Plan oraz Include Actual Execution Plan). Dodatkowo po wykonaniu zapytania MSSQL zasugeruje nam jakich indeksów brakuje.

Fajnie, ale co w sytuacji kiedy widzimy, że nasza aplikacja działa wolno. Mamy podejrzenie, że problem dotyczy bazy danych, ale przecież nie będziemy uruchamiali każdego możliwego zapytania w SSMS. W takiej sytuacji możemy de facto użyć tej samej funkcjonalności co w przypadku uruchamiania zapytania z SSMS. Mam tutaj na myśli Missing Indexes Feature, która jest cechą MSSQL, a nie środowiska SSMS. Informacje o brakujących indeksach silnik bazy danych odkłada mianowicie w kilku widokach systemowych z rodziny sys.dm_db_missing_index_*. Wystarczy więc uruchomić aplikację i zobaczyć jakie indeksy sugeruje nam MSSQL. Ja w tym celu używam zapytania, które znalazłem na blogu SQL Authority.

Przykład z życia. Ostatnio musiałem zoptymalizować pewne obliczenia i postąpiłem dokładnie jak napisałem wyżej. Uruchomiłem w aplikację, zmierzyłem czas obliczeń, zapisałem czas ich uruchomienia i zakończenia, a następnie wyświetliłem listę sugerowanych indeksów do utworzenia. Było ich 6. Na początek odrzuciłem te o niskiej wartości w kolumnie Avg_Esitmated_Impact. Z pozostałych indeksów 2 różniły się tym, że jeden miał klauzulę INCLUDE, a drugi nie. Stwierdziłem, że w pierwszym podejściu skupię się na jednym.

W dalszej kolejności wykonałem testy aby zobaczyć jaki uzysk daje założenie każdego z tych 3 indeksów, a także 2 z nich czy wszystkich 3. Okazało się, że zastosowanie jednego z nich skrócił czas obliczeń o ponad 30%, a pozostałe dwa o małe kilka. Dla rzetelności testy powtórzyłem, a wyniki uśredniłem. Na koniec dokładnie przeanalizowałem proponowany indeks i porównałem go do indeksów już utworzonych na tabeli. Okazało się, że istniał już bardzo podobny indeks. Konkretnie, MSSQL zaproponował coś takiego:

CREATE INDEX IX_Test ON dbo.Table(Col_1, Col_2) INCLUDE (Col_4);

A istniejący indeks wyglądał tak:

CREATE INDEX IX_Test ON dbo.Table(Col_1, Col_2, Col_3);

Wystarczyło, wieć go zmodyfikować w następujący sposób:

CREATE INDEX IX_Test ON dbo.Table(Col_1, Col_2, Col_3) INCLUDE (Col_4);

Na koniec sprawdziłem jak taka modyfikacja wpływa na operacje wstawiania/aktualizacji danych do/w docelowej tabeli. W tym celu napisałem zapytania wstawiające setki tysięcy rekordów do tej tabeli, a także takie, które modyfikuje kolumnę Col_4.. Wyniki pokazały niewielkie spadek wydajności. Był on znacznie mniejszy niż zysk przy odczycie danych, a po drugie wiedziałem, że w praktyce omawiana tabela jest częściej czytana niż modyfikowana.

Przy pracy z Missing Indexes Feature warto wiedzieć o kilku dodatkowych rzeczach. MSSQL może nam zasugerować wiele brakujących indeksów i nie koniecznie wszystkie muszą dotyczyć zapytać wykonanych przez nas. Aby wyeliminować ten problem sugeruję wykonywanie takich ćwiczeń na dedykowanej bazie danych. Przydatne będą też kolumny last_user_seek oraz last_user_scan z widoku sys.dm_db_missing_index_group_stats. Zawierają one informacje o tym kiedy dany brakujący indeks był potrzebny. Po pierwsze podany czas możemy porównać z czasem uruchomienia/zakończenia obliczeń i odrzucić te indeksy, które nie mieszczą się w tym zakresie. Po drugie te czasy mogą zgrubnie wskazać, w którym momencie działania aplikacji występuje problem. Napisałem, że przy wyborze indeksów do dalszej analizy bazowałem na kolumnie Avg_Esitmated_Impact. Trzeba na to jednak uważać. Ta wartość to tylko pewne przybliżenie i może nas wyprowadzić na manowce. Z 3 indeksów jakie wybrałem do dalszej analizy największy zysk miał ten o najmniej wartości w tej kolumnie.

Końcowa uwaga jest taka, że Missing Indexes Feature to pomocna rzecz, ale nie jest to magiczna formuła, która rozwiąże wszystkie problemy za nas. Ma też swoje ograniczenia, o których należy wiedzieć.

Podsumowując:

• MSSQL sugeruje brakujące indeksy.
• Brakujące indeksy można odczytać z bazy danych.
• Testy wydajności należy powtórzyć kilka razy.
• Testy wydajności dobrze wykonywać w dedykowanym do tych celu środowisku.
• Missing Indexes Feature to nie magiczna formuła i ma swoje ograniczenia.
• Proponowane brakujące indeksy należy zawsze poddać analizie i porównać do istniejących indeksów.
• Należy pamiętać, że indeksy spowalniają operacje aktualizacji i wstawiania danych.
• Wartość w kolumnie Avg_Esitmated_Impact należy traktować ostrożnie.

Czy sposób pisania pętli for ma wpływ na wydajność?

Home

Przy okazji codziennej prasówki natknąłem się na ten artykuł na temat wydajności pętli for w JavaScript'cie dla różnych przeglądarek. W skrócie chodzi o to czy powinniśmy pisać pętlą for tak:

for (int i = 0; i < array.Length; i++)
   ...

A może raczej tak, czyli zapamiętać długości tablicy w zmiennej pomocniczej i nie odczytywać jej przy każdym przebiegu pętli:

for (int i = 0, len = array.Length; i < len; i++)
   ...

Z ciekawości sprawdziłem czy taka mikro optymalizacja ma jakiekolwiek znaczenie w przypadku programowania na platformę .NET. Do zmierzenia czasu użyłem takiej metody pomocniczej:

public static void MeasureIt<T>(Action<T> action, T arg, int noOfIterations)
{
   var sw = new Stopwatch();
   sw.Start();

   for (var i = 0; i < noOfIterations; ++i)
      action(arg);

   sw.Stop();
   Console.WriteLine("Total time: " + sw.ElapsedMilliseconds);
}

Następnie wykonałem następujący test:

var noOfIterations = 100000;
var noOfElements = 10000;
var array = Enumerable.Repeat(1, noOfElements).ToArray();
//Przypadek 1
MeasureIt(arg =>
{
   var total = 0;
   for (var i = 0; i < arg.Length; i++)
      total += a[i];  
}, array, noOfIterations);
//Przypadek 2
MeasureIt(arg =>
{
   var total = 0;
   for (int i = 0, len = arg.Length; i < len; i++)
      total += a[i];
}, array, noOfIterations);

Dla rzetelności testy uruchomiłem wielokrotnie. Czas wykonywania obliczeń w obu przypadkach wynosił około 320ms z dokładnością do kilku milisekund. Czasami pierwsze podejście było szybsze, a czasami drugie. Z jednej strony czegoś takiego się spodziewałem. Z drugiej strony sądziłem, że jednak zaobserwuję pewien zysk w drugim przypadku. Dlaczego?

Otóż jeśli spojrzymy na kod pośredni wygenerowany przez kompilator to te dwie implementacje bynajmniej nie są identyczne. W pierwszym przypadku długość tablicy odczytywana jest wielokrotnie na koniec pętli, a w drugim tylko raz przed właściwą pętlą. Najwidoczniej jest to jednak tak szybka operacja, że się nie liczy (w IL do odczytania długości jednowymiarowej tablicy istnieje dedykowana instrukcja ldlen).

Dodatkowo przeprowadziłem podobny test dla użycia listy generycznej List<T>. Tym razem różnice były już zauważalne i wynosiły około 27% na rzecz zapamiętania liczby elementów listy w dodatkowej zmiennej. Średnio pierwsza wersja wykonywała się 957ms, a druga 752ms. Wynika to z tego, że aby odczytać liczbę elementów w liście należy odczytać właściwość Count czyli metodę get_Count. Na poziomie IL jest to robione przy pomocy instrukcji callvirt (w telegraficznym skrócie służącej do wołania metod na rzecz obiektów), a nie dedykowanej (i pewnie zoptymalizowanej) instrukcji ldlen jak ma to miejsce w przypadku tablic. Pomimo tych różnic uważam jednak, że w codziennej praktyce programistycznej nie należy się tym przejmować gdyż różnice w czasach obliczeń, w porównaniu do dużej liczby iteracji (100000), są zbyt małe.

Sortowanie w czasie liniowym

Home

Teoria mówi, że optymalna złożoność obliczeniowa dla algorytmów sortowania opartych o porównywanie wynosi O(nlogn), czyli, innymi słowy, szybciej być już nie może. Taką złożoność optymistyczną ma na przykład używany w .NET algorytm sortowania szybkiego. Ale chwila, co to znaczy sortowanie oparte o porównywanie? To w ogóle istnieje inna możliwość? Przecież, aby posortować na przykład listę liczb całkowitych, to trzeba je porównywać!

Okazuje się, że do problemu można podejść inaczej. Jeśli zrezygnujemy z porównywania, to, pod pewnymi warunkami, osiągniemy złożoność liniową O(n). Niby szybciej, ale czy rzeczywiście warto się tym przejmować? Postanowiłem to sprawdzić i porównałem zachowanie algorytmu sortowania używanego przez .NET, naiwnej rekurencyjnej implementacji sortowania szybkiego oraz algorytmu sortowania w czasie liniowym o nazwie sortowanie przez zliczanie.

Sortowanie przez zliczanie zostało opisane choćby na Wikipedii, dlatego tutaj przybliżę tylko jego ideę. Zacznijmy od tego, że algorytm ten bardzo dobrze nadaje się do sortowania liczb całkowitych z zadanego zakresu, powiedzmy od K do N. Im N mniejsze tym lepiej i jest to oczywiście istotne jego ograniczenie. Jego działanie opiera się na policzeniu, ile razy w tablicy do posortowania pojawiła się liczba K, ile razy liczba K + 1 ... i ile razy liczba N. W tym celu wystarczy odwiedzić każdy element tablicy tylko raz. Kiedy mamy już te informacje, sortowanie właściwie jest zakończone. Na przykład: jeśli liczba 0 wystąpiła 10 razy, a liczba 3 wystąpiła 2 itd., to jako wynik wypiszemy najpierw 10 razy 0, potem 2 razy 3 itd.

Wyniki porównania wspomnianych 3 algorytmów zaprezentowałem na 2 wykresach poniżej. Oś X pokazuje liczbę elementów do posortowania, a oś Y czas sortowania w ms. Pierwszy wykres pokazuje przypadek, kiedy dane do posortowania zawierały liczby z zakresu od 0 do 100, a drugi od 0 do 100 tysięcy.



Wnioski są następujące, niektóre bardzo ciekawe:

• Dla małego zakresu liczb naiwna implementacja sortowania szybkiego działa bardzo słabo (mamy tutaj pesymistyczny przypadek i złożoność O(n^2)).
• Nie widać tego na wykresie, lecz dla małego zakresu liczb sortowanie przez zliczanie jest nieznacznie szybsze od implementacji używanej przez .NET: dla 1 miliona elementów jest to 15 ms w porównaniu do 64 ms.
• W związku z tym pojawia się pytanie, czym różni się naiwna rekurencyjna implementacja sortowania szybkiego od tej używanej przez .NET? Można by o tym dużo napisać, więc tutaj tylko zasygnalizuję o co chodzi. Otóż w rzeczywistości .NET używa tzw. sortowanie introspektywnego, który stanowi połączenie "zwykłego" sortowania szybkiego, sortowania przez kopcowanie i sortowania przez wstawianie, przez co wyeliminowano przypadek pesymistyczny, kiedy QuickSort ma złożoność wielomianową.
• Dla dużego zakresu elementów różnica pomiędzy 3 porównywanymi algorytmami zaciera się chociaż rekurencyjna implementacja QuickSort jest wciąż najwolniejsza, a sortowanie przez zliczanie jest trochę szybsze od tego co oferuje .NET.
• Sprawdziłem czas sortowania dla maksymalnie 50 milionów elementów i trwało to 2 s dla sortowanie przez zliczanie oraz 5 s dla hybrydowego.
• Wniosek końcowy jest taki, że biorąc pod uwagę ograniczenia i wady sortowania przez zliczanie oraz to, jak dobrze działa implementacja hybrydowa w .NET należy jej po prostu używać i nie zastanawiać się specjalnie nad innymi wynalazkami.

CTE i wydajność

Home

Ten post będzie o tym jak można zrobić sobie krzywdę stosując skądinąd bardzo fajne narzędzia. W tym przypadku mam na myśli CTE (ang. Common Table Expressions). Moim zdaniem stosowane z umiarem podnoszą czytelność kodu, z drugiej jednak strony użycie CTE może wpłynąć negatywnie na wydajność naszych zapytań.

Należy pamiętać o tym, że CTE nie mają fizycznej reprezentacji w tempdb tak jak tabele tymczasowe czy zmienne tabelaryczne. Na CTE można patrzeć jak na taki tymczasowy, nie zmaterializowany widok. Kiedy MSSQL wykonuje zapytanie i napotka CTE to odwołanie do tego CTE zastępuję jego definicją. W związku z tym jeśli dane CTE jest używane kilkakrotnie w danym zapytaniu to ten sam kod zostanie wykonany kilka razy i MSSQL tego nie optymalizuje. Ten kod pokazuje to zachowanie:

WITH  Test (Id)  
AS (SELECT  NEWID())
SELECT * FROM Test
UNION ALL
SELECT * FROM Test

Na ekran zostaną wypisane 2 różne identyfikatory. Gdyby Test było tabelą otrzymalibyśmy ten sam wynik. W skrajnych przypadkach może to spowodować, że zapytanie będzie koszmarnie wolne. Optymalizacja jest natomiast prosta. Wystarczy w pewnym momencie wrzucić dane do tabeli tymczasowej i dalej używać tej tabeli zamiast odwoływać się do CTE.

Jakiś czas temu widziałem przypadek gdzie dzięki temu jakże prostemu zabiegowi zapytanie zamiast wykonywać się kilka minut wykonywało się kilka sekund!

Jak napisać szybki program pobierający dane z AD

Home

Post ten dotyczy tematu efektywnego pobierania danych z Active Directory. Załóżmy, że chcemy pobrać listę użytkowników przy czym interesują nas tylko niektóre właściwości, które ich opisują. Pokażę trzy niewiele różniące się z pozoru sposoby odczytania potrzebnych nam danych. Pozornie ponieważ te trzy podejścia znacząco różnią się wydajnością. W celu zademonstrowania różnic napisałem prostą klasę ADTester. Zawiera ona tylko jedną metodę Run w parametrach, której określamy tryb działania oraz liczbę obiektów do pobrania. Różnica pomiędzy trybami jest następująca:

• W trybie szybkim (Mode.Fast) dla każdego obiektu z bazy danych Active Directory pobrane zostają tylko wybrane 4 właściwości, a to dzięki zastosowaniu właściwości DirectorySearcher.PropertiesToLoad
• W trybie normalnym (Mode.Normal) dla każdego obiektu z bazy danych Active Directory pobrane zostają wszystkie dostępne dla danego obiektu właściwości.
• W trybie wolnym (Mode.Slow) zamiast użyć danych zawartych w obiektach SearchResult korzystam z metody SearchResult.GetDirectoryEntry.

Poniższa tabela pokazuje czas działania programu w ms w zależności od trybu działania oraz liczby obiektów do pobrania:

maxNumberOfObjects	Mode.Fast	Mode.Normal	Mode.Slow
100	363	463	7507
200	407	661	1600
500	797	2212	39323
1000	1353	3060	75935

W najlepszym przypadku tryb prosty jest 2.7 szybszy niż tryb normalny i prawie 60 razy szybszy niż tryb wolny. Różnica jest wręcz powalająca, a wnioski nasuwają się same.

• Jeśli z góry wiemy jakie właściwości nas interesują to używajmy właściwości DirectorySearcher.PropertiesToLoad.
• Korzystajmy z danych zwróconych przez klasę DirectorySearcher w postaci obiektów SearchResult.
• Tylko jeśli to absolutnie konieczne korzystajmy z metody SearchResult.GetDirectoryEntry. Taka potrzeba zachodzi na przykład wtedy jeśli chcemy zmodyfikować dane w AD.

Na koniec jeszcze jedna uwaga. Wyniki czasu działania programu będą się różnić w zależności od tego gdzie znajduje się serwer Active Directory. W moim przypadku znajdował się on poza krajem. Na koniec zamieszczam kod programu do własnych testów:

public class ADTester
{
    public enum Mode { Fast, Normal, Slow }

    public void Run(Mode mode, int maxNumberOfObjects)
    {
        var ldapPath = "YOUR_LDAP_PATH";

        using (var root = new DirectoryEntry(ldapPath))
        {
            using (var searcher = new DirectorySearcher(root)
                    {
                        Filter = "(&(objectClass=user))", SearchScope = SearchScope.Subtree, SizeLimit = maxNumberOfObjects
                    })
            {
                if (mode == Mode.Fast)
                    searcher.PropertiesToLoad.AddRange(new[]{ "displayName","name", "pwdLastSet","userAccountControl" });

                using (SearchResultCollection searchResult = searcher.FindAll())
                {
                    foreach (SearchResult user in searchResult)
                    {
                        if (mode != Mode.Slow)
                        {
                            var displayName = user.Properties["displayName"];
                            ...
                        }
                        else
                        {
                            var entry = user.GetDirectoryEntry();
                            var displayName = entry.Properties["displayName"];
                            ...
                        }
                    }
                }
            }
        }
    }
}

Mała wskazówka jak pisać szybsze makra dla Excela

Home

Od dłuższego czasu do śledzenie rodzinnych wydatków używam programu Excel wraz z napisanym przez siebie makrem, które wylicza statystyki, sumuje wydatki według kategorii itp. Po przesiadce na nowy komputer makro zaczęło jednak działać wolniej. Wcześniej przeliczenie arkusza zajmowało chwilę, a teraz nawet kilka sekund. Dodatkowo w czasie działania makra arkusz migał. Ewidentnie wygląda to na problemy z szybkim odświeżaniem ekranu. Może spowodował to nowy system operacyjny, a może nowy sterownik karty graficznej?

Nie wiem jaka dokładnie była przyczyna ale rozwiązanie problemy było bardzo proste. Postanowiłem poszukać Excel'owego odpowiednika metod SuspendLayout/ResumeLayout znanych z technologii Windows Forms. Bardzo szybko znalazłem właściwość Application.ScreenUpdating, która pozwala włączyć/wyłączyć odświeżanie ekranu. Jej ustawienie na False w makrze przed rozpoczęciem obliczeń, a potem znowu na True rozwiązało mój problem w 100%.

Ciekawe zgłoszenie błędu

Home

Jest to druga, poprawiona wersja tego postu. Za wcześniejsze pomyłki przepraszam.

W poście tym chciałbym opisać interesujący błąd. Wszystko zaczęło się od zgłoszenia od klienta dotyczącego problemów z wydrukami. Nie wchodząc w szczegóły okazało się, że cały problem sprowadza się do utworzenia dostatecznie dużej bitmapy. Co jednak ciekawe analiza pokazała, że system dysponuje znaczną ilością wolnej pamięci (ok 1.5 GB) podczas gdy do utworzenia bitmapy potrzebne było "raptem" kilkaset megabajtów. Tutaj dodam, że mówimy o systemie 32 bitowym.

Z pomocą przyszedł tutaj program vnmap, który służy do analizy pamięci wirtualnej i fizycznej procesu. Pokazał on, że proces rzeczywiście dysponuje znaczną ilością pamięci ale największy ciągły jej obszar to tylko 200 MB. Do zaalokowania bitmapy potrzeba natomiast właśnie ciągłego obszaru pamięci. Nie dotyczy to zresztą tylko bitmap, podobny problem możemy wystąpić przy ładowaniu bibliotek dll.

Taką sytuację nazywamy defragmentacją pamięci. Co było jej przyczyną? Zgodnie z tym co pokazał wspomniany program vnamp pamięć w dużym stopniu była poszatkowana przez biblioteki dynamiczne. Nie bez znaczenia jest tutaj fakt, że rozpatrywany przypadek dotyczył dość dużego systemu zbudowanego z wielu modułów.

Problem próbowałem zaleczyć przy użyciu narzędzia rebase.exe, które służy do ustawienia preferowanego adresu pod jaki ma zostać załadowana dll'ka. Testy niestety pokazały, że to nic nie daje.

Pytanie co jest przyczyną takiego położenia bibliotek w pamięci? Tutaj nie pozostaje mi nic innego jak rozłożyć ręce. Wcześniej byłem przekonany, że jest to związane z mechanizmem bezpieczeństwa, który losowo rozrzuca biblioteki po pamięci. Zwrócono mi jednak uwagę, że taki mechanizm (ASLR) pojawił się dopiero w Windows Vista. Sprawa jest więc otwarta. Jakieś pomysły?

Jak sobie z tym poradzić? Generalnie jednoznacznej odpowiedzi nie ma, ja znam trzy podejścia. Po pierwsze przejście na system 64 bitowy rozwiąże problem ale nie jest to zawsze możliwe. Po drugie można próbować wyeliminować konieczność alokacji tak dużej bitmapy ale może to być bardzo trudne. Można też użyć przełącznika /3GB, który pozwala procesom użytkownika użyć 3 GB pamięci wirtualnej zamiast domyślnych 2 GB ale nie jest to zalecane rozwiązanie.

Na zakończenie chciałbym podziękować koledze Damianowi z pracy, który analizował zgłoszenie klienta i podsunął mi pomysł na ten post.

Trochę o zwalnianiu zasobów

Home

Każdy dobry programista wie, że po skończeniu pracy z obiektem klasy implementującej interfejs IDisposable należy wywołać metodę Dispose (jawnie bądź nie jawnie). Dlatego kiedy ostatnio zobaczyłem kod, w którym programista beztrosko raz po raz tworzy ikonę, a następnie radośnie o niej zapomina powodując wzrost liczby obiektów GDI przez usta przeszły mi dość niecenzuralne słowa. Oczywiście od razu poprawiłem kod w mniej więcej taki sposób:

using(Icon icon = GetIcon())
{
   ...
}

Nic prostszego można powiedzieć. Jednak przy następnym uruchomieniu aplikacji ku mojemu zdziwieniu liczba obiektów GDI znowu zaczęła rosnąć. Zaglądam, więc do metody GetIcon. A tam widzę coś takiego:

return Icon.FromHandle(handle);

Nie kojarząc za bardzo metody FromHandle zaglądam do dokumentacji, a tam jest napisane coś takiego:

When using this method you must dispose of the resulting icon using the DestroyIcon method in the Win32 API to ensure the resources are released.

Kolejny mój krok to oczywiście sprawdzenie czy wywołanie DestroyIcon działa. Metodę tą należy zadeklarować w następujący sposób:

[System.Runtime.InteropServices.DllImport("user32.dll", CharSet=CharSet.Auto)]
extern static bool DestroyIcon(IntPtr handle);

Jej użycie oczywiście rozwiązało problem. Co dociekliwsi mogą jeszcze zapytać czemu wywołanie Dispose nie wystarcza. Sprawa jest dość ciekawa. Okazuje się, że klasa Icon używa wewnętrznie DestroyIcon do zwalniania zasobów ale tylko i wyłącznie wtedy kiedy jest właścicielem tych zasobów to jest kiedy sama je zaalokuje. W momencie tworzenia ikony przy pomocy uchwytu dostarczonego z zewnątrz trzeba samemu zadbać o jego zwolnienie.

Reasumując w opisanym przypadku dwóch programistów zrobiło dwa poważne błędy. Pierwszy zapomniał o zwolnieniu zasobów, a drugi o dokładnym przeczytaniu dokumentacji. Metoda GetIcon powinna zostać napisana tak aby korzystający z niej programista nie musiał posiadać wiedzy "tajemnej" aby dobrze jej użyć.

Przykład tego jak nie należy pisać kodu

Home

Czasami jak patrzę na niektóre kody to zastanawiam się o czym myślał piszący je programista. Ostatnio natknąłem się na kod mniej więcej jak poniżej (zmieniłem nazwy zmiennych, metod itd.). Pomińmy jaka jest jego logika i gdzie został użyty. Proponuję natomiast przyjrzeć się przez chwilę temu fragmentowi i spróbować odpowiedzieć na pytanie co jest nie tak.

...
for (int i = 0; i < values.Length; i++)
{
  if (values[i] != null)
  {
    if (hash[values[i]] != null)
      Process(hash[values[i]]);

    if (hash[values[i]] != null)
    { 
      Process(values[i]);
      Process(values[i], hash[values[i]]);
      hash.Remove(values[i]);
    }
  }
}
...

Mnie uderzyła duża i zupełnie zbyteczna liczba odwołań do zmiennych values (tablica) i hash (Hashtable). Odwołanie do tej pierwszej występuje 8 razy, a do drugiej 5 razy! Po chwili pracy i wprowadzeniu bardzo prostych poprawek kod wygląda tak:

...
for (int i = 0; i < values.Length; i++)
{
  string val = values[i];
  if (val != null)
  {
    object obj = hash[val];
    if (obj != null)
      Process(obj);

    if (obj != null)
    {
      Process(val);
      Process(val, obj);
      hash.Remove(obj);
    }
  }
}
...

Odwołanie do zmiennych values oraz hash występuje tylko 1 raz. Czemu o tym piszę? Odpowiedź jest tak prosta jak wprowadzone poprawki: wydajność. Dodam jescze, że kod ten można jeszcze ulepszyć. W tym poście skupiam się jednak na tej jednej rzeczy.

W tym przypadku poprawiona wersja działa jakieś 3x/4x razy szybciej! Przyznam jednak, że całościowy efekt tej optymalizacji jest niezauważalny z dwóch powodów. Po pierwsze długość używanej w kodzie tablicy i liczba elementów w tablicy hashującej jest generalnie niewielka. Przeważnie nie przekracza kilkudziesięciu, może kilkuset elementów. W takim scenariuszu czas wykonania tego kodu nie przekracza milisekundy. Po drugi częstotliwość użycia tego kodu jest niewielka.

Z drugiej jednak strony programista, który napisał omawiany kod stosuje (zastosował) takie konstrukcje w wielu miejscach. Być może wywołuje jedną, ciężką, metodę wielokrotnie zamiast zapamiętać jej wynik wywołania na później. Przykładów takich można mnożyć.

Reasumując należy uczyć się na cudzych błędach i strzec się takich konstrukcji.

Ciekawy przypadek optymalizacji

Home

Ostatnio zajmowałem się optymalizacją aplikacji mapowej do planowania i inwentaryzacji sieci telekomunikacyjnych. Problem polegał na tym, że przy dużej liczbie warstw aplikacja zaczynała działać powoli. Warstwa to taki pojemnik na dane tego samego rodzaju np.: warstwa kabli, warstwa wzmacniaczy itd.

W określonych scenariuszach liczba takich warstw mogła sięgać nawet kilku tysięcy. Zacząłem od wrzucenia aplikacji do profilera (AQTime). Jak to często bywa w takich sytuacjach okazało się, że czas pożera kilka metod, które same z siebie wykonują się bardzo szybko ale są wołane bardzo dużo razy - proporcjonalnie do liczby rastrów. W rzeczywistości dojście to tego o jakie metody chodzi nie było oczywiście takie proste ale nie będę zanudzał szczegółami.

Po pierwsze postanowiłem ograniczyć liczbę wywołań tych metod. Niestety okazało się, że z różnych powodów nie da się tego zrobić. W drugim podejściu postanowiłem, więc ograniczyć czas potrzebny na ich wykonanie. Co ciekawe okazało się, że metody te pozornie prawie nic nie robią czyli zawierają tylko odwołania do właściwości Count czy też indeksera jakiejś kolekcji.

Zanim przejdę dalej wyjaśnię, że jako platformę mapową używam rozwiązań firmy ESRI opartych o technologię COM. W związku z tym konieczne jest użycie mechanizmów interoperacyjności pomiędzy kodem zarządzanym i niezarządzanym. W omawianym przypadku wspomniana kolekcja nie była kolekcją zarządzaną ale wrapper'em na obiekt COM. Postanowiłem, więc zrezygnować z odwołań do tej kolekcji i użyć dobrze znanej klasy List<T>. W praktyce utworzyłem instancję listy zarządzanej istniejącą równolegle do kolekcji niezarządzanej. Elementy do obu kolekcji dodawane są równocześnie, podobnie usuwane. Nie jest to problem ponieważ czynność ta wykonywana jest jednorazowo.

Postępując podobnie w kilku innych miejscach, to znaczy eliminując odwołania do wrapper'ów do obiektów COM, zmniejszyłem czas wykonywania niektórych czynności o połowę! Wydaje mi się, że to niezły wynik szczególnie, że dalsze optymalizację cały czas są możliwe. Wniosek z tego taki, że czasem warto wprowadzić redundancję aby zyskać na wydajności.

Synchronizacja - wydajność

Home

Niedawno opublikowałem post dotyczący prymitywów synchronizacyjnych. Przy tej okazji zostałem zapytany czemu użycie prymitywów takich jak semafor czyli implementowanych po stronie systemu operacyjnego jest wolniejsze. Odpowiedź zamieściłem w odpowiedzi do komentarz. W tym poście chciałem przedstawić jeszcze wyniki krótkiego testu jaki przeprowadziłem. Dotyczył on zbadaniu wydajności rozpatrywanych wcześniej prymitywów i polegał na wielokrotnym wchodzeniu i wychodzeniu do/z sekcji krytycznej przez dwa watki. Sekcja krytyczna była oczywiście zabezpieczonej przez te prymitywy. Do pomiaru czasu użyłem klasy Stopwatch. Wyniki są zgodne z tym co napisałem. Zamieściłem je poniżej.

Wycieki obiektów GDI

Home

Ostatnio zajmowałem się w pracy nieprzyjemnym problem z wyciekiem obiektów GDI. Sytuacja wydawała się dziwna ponieważ wyglądało na to, że metoda Dispose() była wołana wszędzie gdzie było to potrzebne. Po mówiąc szczerze dłuższym czasie dowiedziałem się o dwóch istotnych rzeczach:

• Kontrolka TreeView zawiera bug polegający na tym, że jeżeli włączymy pokazywanie pól wyborów (ang. CheckBox) dla węzłów drzewa to zostaną zaalokowane cztery obiekty GDI. Nie zostaną one jednak zwolnione przy wywołaniu Dispose(). Ciekawą dyskusję na ten temat można znaleźć tutaj. Co gorsza jeśli poszperamy na sieci okaże się, że błąd jest znany od co najmniej kilku lat!
• Drugi bug, o którym chciałem powiedzieć dotyczy klasy ImageList. Otóż klasa ta ma problemy ze zwalnianiem zasobów dla umieszczonych w niej obrazków/ikon, co doprowadza oczywiście do wzrostu liczby obiektów GDI. O błędzie tym możemy przeczytać na stronach firmy Microsft. Rozwiązanie, a raczej obejście problemu polega na wywołaniu metod GC.Collect() oraz GC.WaitForPendingFinalizers() po wywołaniu Dispose() dla instancji ImageList. Rozwiązanie działa ale korzystanie z metody GC.Collect() może mieć negatywny wpływ na wydajność aplikacji. Co gorsza może wystąpić jeszcze mniej pożądany efekt. Opieram się tutaj na doświadczeniach kolegi. Zgodnie z nimi używanie GC.Collect() w aplikacjach korzystających z kontrolek ActiveX może doprowadzić do ich zawieszenia w losowym momencie.

  ...
  imageList.Dispose();
  
  GC.Collect();
  GC.WaitForPendingFinalizers();
  ...
  

Z opisanych przeze mnie rzeczy trzeba zdawać sobie sprawę i być uważnym przy stosowania klasy TreeView, a w szczególności klasy ImageList. W przypadku posługiwania się TreeView można pokusić się jeszcze o użycie, zaproponowanej we wspomnianej przeze mnie dyskusji, klasy LeaklessTreeView (testowałem i wygląda, że działa).