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.

DateTime.Parse vs DateTime.ParseExact

Home

Ostatnio spotkałem się z taka sytuacją. Ktoś zdefiniował sobie dość specyficzny format daty na swoje potrzebny. Wszystko było ok kiedy był on używany do zamiany typu DateTime na ciąg znaków. Problemy zaczęły się przy próbie wykonania operacji odwrotnej. Okazało się, że rodzina metod DateTime.(Try)Parse sobie z tym nie radzi. Rozwiązaniem okazało się użycie metod z rodziny DateTime.(Try)ParseExact, która od tych wcześniejszych różni się tym, że jawnie wymaga podania formatu, który ma zostać użyty przy parsowaniu.

Postawione pytanie brzmiało czemu DateTime.(Try)Parse nie działa w tym przypadku, a w innych tak? Moja odpowiedź jest taka. Nie wiem czemu podjęto taką decyzję, ale DateTime.(Try)Parse nie obsługuje wszystkich możliwych formatów i to nawet jeśli kultura używana przez aplikację zawiera wszystkie potrzebne informacje. Oto fragment z dokumetnacji:

If you parse a date and time string generated for a custom culture, use the ParseExact method instead of the Parse method to improve the probability that the parse operation will succeed. A custom culture date and time string can be complicated, and therefore difficult to parse. The Parse method attempts to parse a string with several implicit parse patterns, all of which might fail.

A to jeszcze jeden:

The Parse and TryParse methods do not fully iterate all strings in patterns when parsing the string representation of a date and time. If you require a date and time string to have particular formats in a parsing operation, you should pass the array of valid formats to the DateTime.ParseExact...

W skrócie DateTime.(Try)Parse jest z założenia "upośledzone" i nie umie wszystkiego. Dlaczego? Może dlatego, że obsłużenie wszystkich możliwych przypadków jest bardzo trudne? A może dlatego, że gdyby napisano kombajn obsługujący wszystko to działałby wolno? To tylko zgadywanie, ale trzeba pamiętać, że:

Jeśli używamy własnych formatów daty i czasu to zaleca się użycie DateTime.(Try)ParseExact.

Kodować jak w NASA

Home

Kolega podesłał mi link do ciekawego artykułu na temat 10 zasad stosowanych w NASA, aby pisać naprawdę bezpieczny, czytelny i dobry kod. Zasady te w oryginale dotyczą języka C i zacząłem się zastanawiać czy da się je zastosować do .NET'a. Na zielono zaznaczyłem te zasady, które moim zdaniem da się użyć w .NET'cie, na pomarańczowo te dyskusyjne, a na czerwono takie, których się nie da.

Stosuj tylko bardzo proste konstrukcje sterujące przepływem sterowania w programie. Nie używaj goto i rekursji.

Mi ta zasada przypomina inną Keep it simple stupid, czyli nie starajmy się na siłę pokazać jakimi super programistami jesteśmy i piszmy możliwie prosto. To, że bez goto można się obejść to oczywiste. Bardzo dyskusyjny jest natomiast zakaz użycia rekursji. Autor zasady argumentuje to tym, że brak rekursji ułatwia pracę analizatorom kodu źródłowego, a także dowodzenie poprawności kodu. Ciężko mi z tym dyskutować, bo nie wiem jakiego analizatora używa NASA i nie spotkałem się też z dowodzeniem poprawności kodu w .NET. Osobiście uważam, że rekursja jest przydatna i w wielu przypadkach algorytmy zapisane rekurencyjnie są po prostu łatwiejszych do zrozumienia. Trzeba jednak uważać o czym już pisałem w tym albo w tym artykule.

Wszystkie pętle powinny mieć sztywno określoną górną granicę liczby iteracji.

Znowu dyskusyjna sprawa i znowu ma to służyć temu, aby można było udowodnić, że pętla się kiedyś zakończy. Dać się pewnie da tak pisać, ale wygodne to to pewnie nie jest. Ponieważ w .NET'ie nie piszemy oprogramowania dla statków kosmicznych tą zasadę bym pominął.

Nie stosuj dynamicznej alokacji pamięci (w szczególności garbage collector'a) już po zainicjowaniu aplikacji.

No cóż w .NET bez garbage collector'a się nie da. Można próbować minimalizować tworzenie nowych obiektów w czasie działania aplikacji, ale tak na co dzień to właściwie po co? To, co powinno się rozważyć, to załadowanie do pamięci danych niezmiennych (referencyjnych, słownikowych czy jak to zwał) i korzystanie z nich przez cały czas życia aplikacji.

Metody powinny być możliwie krótkie tj. nie więcej niż 60 linii kodu.

Czy 60 to dobre ograniczenie? Można dyskutować, ale z pewnością metody powinny być możliwie krótkie bo to podnosi ich czytelność. Po drugie jeśli metoda jest krótka to znaczy, że robi jedną konkretną rzecz, a nie kilka lub kilkanaście.

Średnia liczba asercji na metodę powinna wynosić minimum 2. Asercje powinny zabezpieczać przez sytuacjami, które w ogóle nie powinny wystąpić i nie mieć efektów ubocznych.

Co do tego jak pisać asercje to się zgadzam, ciężko mi natomiast powiedzieć, czy 2 to dobra średnia asercji na metodę. W komentarzu do tej zasady autor pisze, że przeciętnie testy jednostkowe wykrywają 1 błąd na 10-100 linii kodu, a asercje jeszcze zwiększają szansę na wykrycie błędów. Ja to rozumiem tak, że sugeruje się używanie tego i tego. Ok, ale ja bym jednak explicite wspomniał potrzebę testów jednostkowych czy ogólnie testów automatycznych w tej zasadzie.

Zmienne powinny mieć możliwe mały zasięg.

Czyli nie stosujemy globalnego stanu, nie re-używamy tej samej zmiennej do różnych celów itd.

Wyniki zwracane przez metody powinny być zawsze sprawdzane przez metodę wołającą. Każda wołana metoda powinna zawsze sprawdzać parametry wejściowe.

Innymi słowy nie ufamy nikomu, nie stosujemy konwencji (na przykład takiej, że jeśli metoda zwraca kolekcję to nigdy nie zwróci null'a, ale pustą kolekcję) itp. Ja jednak lubię konwencję, a parametry wejściowe staram się weryfikować głównie dla metod publicznych i chronionych. Wyniki zwracane przez metody weryfikuję natomiast przede wszystkim przy użyciu zewnętrznych bibliotek.

Należy ograniczyć użycie pre-procesora, makr i kompilacji warunkowej.

Preprocesora i makr nie mamy w .NET, ale możliwość kompilacji warunkowej już tak. Czemu ich nie używać? Ponieważ utrudniają przewidzenie wyniku kompilacji. Autor zasady podaje taki przykład. Załóżmy, że w programie mamy 10 dyrektyw kompilacji warunkowej. Załóżmy, że używają innych warunków. Daje 2^10 = 1024 różnych możliwych wyników kompilacji tego samego kodu, które mogą działać inaczej!

Należy ograniczyć użycie wskaźników. W szczególności stosujemy co najwyżej jeden poziom dereferencji. Wskaźniki na funkcje nie są dozwolone.

Autor ponownie argumentuje, że brak wskaźników ułatwia weryfikację kodu. Tą zasadę ciężko jednak przełożyć na .NET. Niby z typowych wskaźników też można korzystać, ale nie jest to często używane. Jeśli natomiast pod słowo ''wskaźnik'' w tej regule podstawimy ''referencja'', a pod ''wskaźnik na funkcję'' terminy ''delegat'' lub ''wyrażenia lambda'' to okaże się, że w .NET nie możemy zrobić właściwie nic. Podsumowując ta zasada nie ma zastosowania do .NET'a.

Kod musi się kompilować i to bez ostrzeżeń. Przynajmniej raz dziennie kod źródłowy musi przejść weryfikację przy pomocy narzędzi do statycznej analizy kodu z zerową liczbą ostrzeżeń.

To, że kod musi się kompilować to oczywiste. Jeśli chodzi o ostrzeżenia to moim zdaniem w przypadku projektów prowadzonych od zera liczba ostrzeżeń rzeczywiście powinna być równa 0. Jeśli uważamy, że jakieś ostrzeżenia są "głupie" to trzeba odpowiedzieć sobie na pytanie czy używamy dobrych narzędzi? W przypadku tzw. kodu zastanego sprawa jest trudniejsza, ale te 10 zasad służy m.in. właśnie temu, aby nie tworzyć takiego kodu.

Jak widać nie wszystkie z tych zasad da się zastosować w .NET czy przy tworzeniu aplikacji typowo biznesowych. Z drugiej strony są firmy, które w .NET piszą oprogramowanie medyczne. Niektóre z tych zasad wydają się bardzo drakońskie, ale jak już pisałem NASA w swoich projektach osiąga wynik 0 błędów na tysiąc linii produkcyjnego kodu.

Polecam też zapoznanie się z oryginalnym dokumentem NASA’s 10 rules for developing safety-critical code.

Co wyróżnia bardzo dobrego programistę (2)?

Home

Pewnie słyszeliście o strumieniach (ang. stream) w .NET. O tym, że się je otwiera, a po użyciu zamyka. Zresztą w innych technologiach jest podobnie. Sprawa stara jak świat i wydawałoby się, że każdy o tym wie. Ja w każdym razie z definicji tak robię.

Dziwi mnie więc, że po tylu latach istnienia .NET ciągle pojawiają się pytanie z tym związane, jak na przykład to na stackoverflow.com. Dziwi mnie również, że przy okazji tego rodzaju pytań często pojawiają się najróżniejsze koncepcje / pomysły / odpowiedzi i to od użytkowników, którzy wcale nie są początkujący. Tymczasem wystarczy wrócić do podstaw, aby rozwiązać problem.

A może jest tak, że kiedy na co dzień pracujemy z skomplikowanymi algorytmami / trudnymi problemami biznesowymi / strukturami danych (niepotrzebne skreślić) to w pewnym momencie tracimy perspektywę i każdy napotkany problem od razu wydaje się nam skomplikowany.

Kolejny czynnik powodujący tą utratę perspektywy to chyba również mnogość różnych technologii i bibliotek, jakie są u obecnie używane. Ta biblioteka do tego, tamta ułatwia to, ta automatyzuje tamto itd. W ten sposób przyzwyczajamy się do tego, że wiele rzeczy coś robi za nas i my nie wnikamy w szczegóły i równocześnie zapominamy również o podstawach.

Nie mówię, że nie należy używać bibliotek, framework'ów czyli ułatwiać sobie pracy, ale bardzo dobry programista powinien również wiedzieć co, się za tym wszystkim kryje i nie zapominać o podstawach.

Co wyróżnia bardzo dobrego programistę?

Home

Sądzę, że dla każdego bycie bardzo dobrym programistą oznacz trochę coś innego, na przykład do wyboru: znajomość nowych technologii, minimalizowanie używania myszki na rzecz posługiwania się głównie klawiaturą, samodzielne doszkalanie się, blogowanie, udział w konferencjach, komunikatywność, umiejętność pracy pod presją czasu... Ja jednak chciałbym zwrócić uwagę na inną rzecz.

Czasami jest tak, że dostajemy do naprawienie jakiś "wredny" błąd. Niekoniecznie wymaga on wielu zmian w kodzie, ale jest trudny do odtworzenia. Być może brakuje nam też danych, aby go powtórzyć lub opis jest niedokładny. A może jest tak, że błąd dotyczy nieznanego nam obszaru, kod jest brzydki albo to kolejny błąd dotyczący podobnej rzeczy i zaczyna nas to irytować.

W każdym razie mamy dosyć i, jak tylko znajdziemy przyczynę i wyk-minimy rozwiązanie (być może nietrywialne i wymagające dużo technicznej wiedzy), to szybko robimy commit i zapominamy o sprawie. To jest moim zdaniem ten moment, kiedy można zobaczyć na czym polega bycie bardzo dobrym programistą. Moim zdaniem w takiej sytuacji bardzo dobry programista, nawet mimo zniechęcenia, zada sobie dodatkowe pytania:

• Czy ten błąd nie występuje jeszcze gdzieś indziej, nawet jeśli zgłoszenie tego nie dotyczy?
• Jak jego poprawka wpłynie na resztę systemu? Powiązania pomiędzy różnymi modułami systemu mogą być nieoczywiste i często uzyskanie odpowiedzi na takie pytanie wymaga dużo wysiłku.
• Jaka jest pra-przyczyna błędu? Na przykład NullReferenceException można "naprawić" bardzo łatwo przy pomocy jednego if'ka. Często będzie to dobre rozwiązanie, ale może być też tak, że null nigdy nie powinien się pojawić w danym miejscu i jest on wynikiem zmiany gdzieś indziej.

To mogą być bardzo niewygodne pytania, szczególnie, jeśli się nam nie chce, ręce bolą i jest coś ciekawszego do zrobienia, ale równocześnie bardzo potrzebne, szczególnie, jeśli pracujemy z starszymi systemami czy nawet tymi młodszymi, ale bez testów automatycznych.

Nie wiem jak Wy, ale ja na początku swojej kariery uważałem, że w zawodzie programisty właściwie liczy się tylko strona techniczna, znajomość nowych technologii, bibliotek itd. W obecnej chwili rzeczy te uważam za niezwykle ważne, ale nie najważniejsze i coraz większą wagę przywiązuje do umiejętności i predyspozycji, nazwijmy je około-technicznych i miękkich. A co wy o tym myślicie? Też tak macie, a może to tylko moje "zboczenie"?

10000 UserObjects

Home

10000 to limit User Objects jakie na moim sprzęcie mogła zaalokować aplikacja zanim się wywaliła. 10000 to w gruncie rzeczy bardzo duża liczba i jeśli osiągamy ten limit to z dużą pewnością mamy jakiś problem i tak było w przypadku aplikacji napisanej w WinForms jaką miałem naprawić.

Po podłączeniu się debugger'em do aplikacji szybko stwierdziłem, że problem dotyczy jednej z kontrolek, która była alokowana dynamcznie w pętli. Na menadżerze zadań bardzo ładnie było widać jak wzrasta liczba User Objects z każdą kolejną instancją tej kontrolki. Nie byłem natomiast pewny czemu te kontrolki nie były zwalniane pomimo, że były usuwane z UI i nie było na nich wskazań (jak się później okazało pozornie). Tutaj z pomocą przyszedł ANTS Memory Profiler. Jedno uruchomienie i już wiedziałem w czym tkwi problem. Mrówki pokazały, że nie zwolnione kontrolki wciąż są wskazywane przez obiekt klasy System.Windows.Forms.DropTarget.

To dość częsty błąd, a dzieje się tak jeśli kontrolka wspiera Paste & Copy i w związku z tym ma ustawioną właściwość AllowDrop na true. Powoduje to, że kontrolka wskazywana jest przez wspominany obiekt klasy DropTarget dopóki nie ustawimy AllowDrop z powrotem na false. Poprawka błędu okazała się więc trywialna. Wystarczyło, że przy usuwaniu kontrolki z UI ustawiłem tą właściwość na false. W sumie drobna rzecz, ale łatwa do pominięcia.

Jeszcze krótki komentarz odnośnie technologii WPF. Tutaj też mamy właściwość AllowDrop, ale opisany problem nie występuje ponieważ WPF ma zupełnie inne bebechy niż WinForms.

Czy użycie if zamiast else if ma znaczenie?

Home

Historia zaczyna się od prostego fragmentu kodu pokazanego poniżej. Kod ten to fragment walidatora, ktory ma za zadanie określić, czy dane są prawidłowe. Jeśli nie, to zmienna isValid powinna zostać ustawiona na false.

var isValid = true;

if (condition_1)
   isValid = false;

if (condition_2)
   isValid = false;

Kod ten działał do momentu, kiedy wprowadzono do niego małą zmianę pokazaną poniżej. Było to pewne uszczegółowienie logiki walidacji danych wejściowych.

var isValid= true;

if (condition_1)
   isValid = false;

if (condition_2)
   isValid = false;
//Wprowadzona zmiana
else 
{
   if (condition_3)
      isValid = true;
   else if (condition_4)
      isValid = false;
}

Po zastanowieniu się z pewnością stwierdzicie, że coś tutaj nie pasuje. Problem polega na tym, że w określonych warunkach zmienna isValid może zostać z powrotem ustawiona na true nawet jeśli wcześniej stwierdzono, że dane są błędne i ustawiono ją na false!

Może są jakieś rzadkie i dziwne przypadki kiedy błędne dane mogą stać się nagle poprawne, ale w przypadku, z jakim się spotkałem, był to ewidentny błąd i przeoczenie albo brak zrozumienia działania kodu. Moim zdaniem błąd tkwi jednak w jeszcze jednym miejscu tj. w użyciu wielu if'ów zamiast konstrukcji else if w kodzie pokazanym na samym początku. Gdyby początkowy kod wyglądał w ten sposób:

var isValid = true;

if (condition_1)
   isValid = false;
// else if zamiast if
else if (condition_2)
   isValid = false;

To nawet jego modyfikacja w opisany wcześniej sposób nie spowodowałaby, że walidator pozwolił na kontynuację przetwarzania pomimo błędnych danych. Może wydawać się, że kilka if'ów zamiast użycia else if nie robi różnicy bo to przecież oczywiste jak ten kod działa. Może i oczywiste, ale tu i teraz. Za kilka tygodni lub miesięcy, dla kogoś innego, może już nie być takie oczywiste. Ktoś inny może również to po prostu przeoczyć.

Tworząc kod trzeba się starać, aby był możliwie łatwy do zrozumienia, rozszerzania i wprowadzania zmian, a w tym celu w przypadkach podobnych do opisanego wystarczy po prostu użycie trochę inne konstrukcji językowej, która lepiej wyrazi nasze zamiary innym.

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!

Niepozorna pomyłka

Home

Regularnie przeglądam różne portale na temat szeroko pojętego bezpieczeństwa w IT i co raz to dziwię się jak pozornie małe błędy programistów doprowadzają do poważnych problemów i awarii. Czytając ostatnio taki artykuł przypomniałem sobie rozmowę na temat implementacji stronicowania (ang. paging), czyli podziału dużej liczby rekordów na mniejsze porcje i przesyłanie tych porcji do klienta m.in. w celu ograniczenia ruchu w sieci.

W tym przypadku domyślna wielkość strony była skonfigurowana po stronie serwera, ale wysyłając żądanie klient mógł ją nadpisać i podać własną wielkość strony. Rozwiązanie w miarę standardowe, coś podobnego można zrobić odpytując Active Directory, o czym pisałem w tym artykule. Problem w tym przypadku polegał na tym, że wartość podana przez klienta nie była w żaden sposób sprawdzana po stronie serwera. Teoretycznie można więc było zażądać zwrócenie z serwera dowolnie dużej porcji danych. Innymi słowy, wysyłając żądanie wielkości kilku kilobajtów można było otrzymać odpowiedzieć wielkości na przykład 10 MB, a to przecież gigantyczne zwielokrotnienie. A gdyby takich żądań wysłać kilkadziesiąt, kilkaset, a może kilkanaście tysięcy, a do tego podmienić w żądaniu adres odbiorcy?

O czymś podobnym można było niedawno przeczytać w kontekście protokołu NTP. Wspomniany przeze mnie przypadek to w porównaniu z tym pikuś, gdyż użyty protokół komunikacyjny był specyficzny dla danej aplikacji, liczba użytkowników była niewielka itd. więc i zakres potencjalnego ataku był bardzo ograniczony. Z drugiej strony, skoro programista napisał taki kod raz, to może go napisać drugi, trzeci i w którymś momencie nie będzie to mała aplikacja. Na takie rzeczy należy, więc zawsze zwracać uwagę, nawet jeśli w danym przypadku wydaje się to nadmiarowe. Możliwe, że twórca kodu wybrał takie rozwiązanie celowo, ale równie dobrze może to być po prostu przeoczenie lub pomyłka.

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"];
                            ...
                        }
                    }
                }
            }
        }
    }
}

Czy wyrażenie regularne może zawiesić naszą aplikację?

Home

Rozmawiałem dzisiaj z kumplem z zespołu na temat jednego z zadań i trochę od niechcenie rzuciłem, że można by zastosować tutaj wyrażenie regularne, które dodatkowo byłoby konfigurowalne. Ta z pozoru niewinna uwaga doprowadziła do ciekawej dyskusji. Otóż Tomek stwierdził, że nie jest dobrym pomysłem aby umieszczać wyrażenia regularne w konfiguracji, która może zostać zmieniona przez użytkownika. Dlaczego? W ten sposób umożliwiamy użytkownikowi zawieszenie naszej aplikacji i to nie dlatego, że wyrażenie będzie zawierało błędy składniowe. Aby zrozumieć o co chodzi przyjrzyjmy się takiemu prostemu przykładowi, w którym testuję dwa wyrażenie regularne:

private static void Main(string[] args)
{
   var input1 = "xxxxxxxxxxxxxxxxxxxxxxxxxy";
   var input2 = "xxxxxxxxxxxxxxxxxxxxxxxxx";

   var regex1 = "x+y";
   var regex2 = "(x+)+y";

   TestRegex(regex1, input1);
   TestRegex(regex2, input1);

   TestRegex(regex1, input2);
   TestRegex(regex2, input2);

   Console.WriteLine("Press any key...");
   Console.ReadLine();
}

private static void TestRegex(string r, string input)
{
   var regex = new Regex(r);
   var sw = new Stopwatch();

   sw.Start();

   regex.Match(input);

   sw.Stop();

   Console.WriteLine("{0} ms", sw.ElapsedMilliseconds);
}

Oba użyte wyrażenie są proste. Drugie jest "dziwne" bo po co stosować tutaj konstrukcję grupującą. Oczywiście nie ma to tutaj sensu, ale zrobiłem to aby pokazać ideę problemu. Teraz przejdźmy do setna. Na moim komputerze powyższy program wypisze takie czasy:

30 ticks 0 ms
13 ticks 0 ms
31 ticks 0 ms
21621843 ticks 9246 ms

Różnica jest porażająca. Z pozoru niewinne wyrażenie regularne (x+)+y w przypadku kiedy wejściowy dane do niego nie pasują (w drugim przypadku na końcu ciągu znaków brakuje litery y) jest o duże kilka rzędów wielkości wolniejsze niż wyrażenie x+y Co gorsze im więcej x'ów w danych wejściowych tym te czasy będą gorsze:

Liczba x'ów	Czas (ms)
10	0
14	4
15	9
18	71
20	291
22	1169
24	4685
26	18741
28	74078

Mamy tutaj do czynienia z złożonością wykładniczą! Problem tkwi natomiast w użyciu w drugim wyrażeniu backtracking'u, który powoduje, że silnik wyrażeń regularnych niepotrzebnie wielokrotnie (na)wraca do znalezionych wcześniej dopasowań. Do tego potrzebne są również odpowiednio dobrane dane. Można mówić, że przykład jest tendencyjny (jak to przykład), ale skoro jest to możliwe to kiedyś się zdarzy i dlatego trzeba być świadomym takich rzeczy.

Kilka uwag końcowych:

• Pewnym obejściem problemu jest wyłączenie backtracking'u dla danej grupy w taki sposób: (?>(x+)+)y
• Można również określić maksymalny dopuszczalny czas przetwarzania wyrażenia regularnego np.: new Regex(r, RegexOptions.None, new TimeSpan(0,0,0,1))
• Jeśli to możliwe to zamiast backtracking'u należy stosować tzw. lookahead/lookbehind assertions, które nie nawracają.
• Problem opisałem na przykładzie .NET, ale może od dotyczyć każdego silnika wyrażeń regularnych, który obsługuje backtracking i który domyślnie z niego korzysta.
• Jeśli chcecie pogłębić temat to polecam ten artykuł albo ten.

Dlaczego należy jawnie specyfikować czy kolumna ma akceptować wartości puste czy nie?

Home

Załóżmy, że w procedurze składowanej mamy tabelkę tymczasową:

CREATE TABLE #Temp (Column1 Int, Column2 Varchar(15));

Wszystko działa bez zarzutu, może nawet w środowisku produkcyjnym, aż w pewnym momencie ktoś mówi: Wiesz co dzisiaj Twoja procedura wywaliła się i krzyczy, że kolumna Column1 nie pozwala na wartości NULL. Sprawdzasz błąd na swoim środowisku, ale wszystko działa. Sprawdzasz na innym serwerze, na innej bazie danych i też działa. Co u licha?! Magia czy co?

Jak to zwykle bywa w takich sytuacjach nie magia, ale PEBKAC. Jeśli tworzymy tabelkę tymczasową lub inną i nie podamy jawnie czy kolumna ma akceptować wartości NULL czy nie to domyślnie będzie ona... No właśnie tu tkwi problem, a odpowiedź brzmi to zależy.

Przy standardowych ustawieniach będzie akceptować wartości NULL, ale można to zmienić na poziomie bazy danych, a co gorsza na poziomie sesji użytkownika! Wystarczy, więc mała zmiana i nasz kod przestaje działać. Dlatego dobra praktyka mówi więc aby zawsze jawnie specyfikować czy kolumny mają akceptować puste wartości czy nie.

Co do opcji, które sterują tym zachowanie. Na poziomie bazy danych MSSQL służy do tego komenda:

ALTER DATABASE dbname SET ANSI_NULL_DEFAULT [OFF|ON]

Natomiast ustawienia sesji użytkownika określamy w SQL Server Management Studio:

Tools->Options->Query Execution->SQL Server->ANSI

Lub przy pomocy jednej z dwóch komend, które aby było łatwiej mają dokładnie przeciwne znaczenie i się wykluczają:

SET ANSI_NULL_DFLT_ON ON [OFF|ON]
SET ANSI_NULL_DFLT_OFF ON [OFF|ON]

Ja vs Active Directory

Home

Od niedawna mam okazję pracować, przy pomocy API .NET'owego, z usługami katalogowymi w wydaniu Microsoft'u, czyli z Active Directory. Dla mnie nowa rzecz, więc z zapałem dziecka, które dostało nową zabawkę, zabrałem się do pracy i, jak to często bywa w takich sytuacjach, od razu napotkałem problemy właściwe dla początkujących. W ten sposób dowiedziałem się wielu rzeczy, które dla wyjadaczy mogą być oczywiste, ale dla mnie były nowością. Zebrałem więc je do kupy i tak powstała poniższa lista ku pamięci.

Niektóre z tych rzeczy to drobnostki i jeśli o nich zapomnimy nic wielkiego się nie stanie. Niektóre są jednak bardzo ważne i ich pominięcie może sprowadzić na nas większe kłopoty. Tego rodzaju rzeczy oznaczyłem jako [Ważne]

Projektowanie schematu

• [Ważne] Przy projektowaniu schematu AD (definicja klas, atrybutów) trzeba być bardzo ostrożnym. AD nie wspiera usuwania klas lub atrybutów, a wiele rzeczy można zdefiniować tylko przy ich tworzeniu, na przykład atrybuty obowiązkowe dla danej klasy. AD wspiera natomiast tzw. dezaktywację. Ma to podobne skutki jak usunięcie, ale i tak wprowadzanie zmian do już używanego schematu AD może być bardzo kłopotliwe.
• [Ważne] AD to nie C# i nie możesz sobie tak po prostu dodać nowego atrybutu do klasy i oczekiwać, że wszystkie jej instancje zostaną z automatu uaktualnione. Mam tutaj na myśli atrybut mustContain, który określa atrybuty obowiązkowe. Niestety, ale można go podać tylko przy tworzeniu danej klasy. Więcej ograniczeń znajdziecie tutaj.
• Zamiast atrybutu mustContain można jednak użyć atrybutu mayContain, który określa atrybuty potencjalne.
• Pisząc skrypt ldif definiujący nowy atrybut nie wystarczy użyć atrybutu attributeSyntax. Potrzebny jest jeszcze atrybut oMSyntax.

Limit 8KB

• [Ważne] Ponownie AD to nie C#. Obiekty w AD nie mogą mieć więcej niż 8KB, a co za tym idzie, nie mogą zawierać dowolnej liczby atrybutów i wartości. Należy o tym pamiętać szczególnie, jeśli używamy atrybutów wielowartościowych. Ja analizowałem błąd, w którym nie można było dodać nowych wartości do atrybutu właśnie z tego powodu. Przekroczenie limitu 8KB dla danego obiektu skutkuje błędem Administrative limit for this request was exceeded
• Aby było śmieszniej, nie można łatwo wyznaczyć maksymalnej dopuszczalnej liczby wartości, jakie zmieszczą się w danym atrybucie. Zależy to na przykład od tego, ile atrybutów ma dany obiekt. Ten artykuł zawiera fajną dyskusję praktycznych limitów na liczbę wartości w obiekcie. Sekcja Maximum Database Record Size

Atrybuty powiązane

• Pewnym rozwiązaniem problemu ograniczonej wielkości obiektów są tzw. atrybuty powiązane (ang. linked attributes), w których zawartość jednego atrybutu zależy od zawartości innych obiektów. Problemem jest natomiast to, że taki wyliczany atrybut musi być typu distinquished name, a więc nie obsłużymy w ten sposób np.: listy liczb całkowitych.
• [Ważne] Jeśli atrybuty mają być powiązane to muszą być takie od początku.
• Działanie atrybutów powiązanych może nie być intuicyjne, a więc załączam poglądowy schemat. Jak widać atrybuty połączone to para atrybutów tzw. forward link oraz backward link. Backward link przechowuje wskazania na obiekty, które wskazują go w atrybucie forward link.

Stronicowanie

• AD ma ograniczenie na liczbę obiektów, jakie można pobrać z bazy w jednym zapytaniu. .NET pozwala to jednak bardzo łatwo obejść dzięki stronicowaniu. Należy ustawić właściwość DirectorySearcher.SizeLimit na 0, a właściwość DirectorySearcher.PageSize na wartość inną niż 0. Nic więcej nie trzeba robić. Więcej szczegółów tutaj.
• [Ważne] Domyślnie .NET nie używa stronicowania. Jeśli o ty zapomnimy, może dojść do sytuacji, kiedy nasz program nagle przestanie działać, bo nie będzie pobierał wszystkich oczekiwanych obiektów z AD.

Inne

• [Ważne] Klasy z przestrzeni nazw System.DirectoryServices, takie jak DirectorySearcher, DirectoryEntry, SearchResultCollection implementują interfejs IDisposable. Piszę o tym ponieważ nawet przykłady na MSDN nie biorą tego pod uwagę!
• Skrypt ldif, służy do wprowadzania zmian do AD i składa się z sekwencji operacji dodania, usunięcia lub zmodyfikowania czegoś. W przypadku operacji modyfikacji (changetype: add) na końcu powinien znaleźć się znak „-“.
• Uwaga na spacje w atrybucie cn. Mój skrypt ldif dodający do schematu nowy atrybut wywalił się, bo wartość dla atrybutu cn zawierała na końcu spacje.
• AD ma różne limity ograniczające, na przykład maksymalna liczbę wartości, jakie można pobrać, maksymalną wielkość strony itp. Pełną listę można znaleźć tutaj.

Lista ta z pewnością nie jest kompletna. Jeśli macie jakieś sugestie to chętnie ją rozszerzę.

Czy zadajesz pytania?

Home

Czy próbowaliście kiedy rozwiązać następujące zadanie?

Napisz program, który wypisze na ekran konsoli swój własny kod. Możesz pominąć białe znaki.

(01-09-2014) Dodatkowe wymaganie:
Kod programu nie powinien być wczytany z pliku, bazy danych lub innego nośnika.

Zachęcam do sprawdzenia swoich sił. Zadanie to wysłałem również swoim kolegom z pracy. Wcześniej rozwiązałem je samemu i w gruncie rzeczy spodziewałem się podobnych do mojego rozwiązań. Zostałem jednak zaskoczony, bo okazało się, że inni podeszli do tego problemu troszkę inaczej, uzyskując ten sam wynik co ja, a nawet lepszy, bo w prostszy sposób. Sytuacja ta przypomniała mi kilka innych, w których zadanie prostego pytania:

Co o tym myślisz? Jak byś zabrał się do tego zadania?

Pomogło mi rozwiązać problem szybciej, lepiej, sprawniej... W pracy programisty niezwykle ważne jest konfrontowanie swoich pomysłów z rozwiązaniami innych. Wydaje Ci się, że wszystko zrobiłeś dobrze? A może ślęczysz nad jakimś problem już bardzo długo i cały czas nie możesz znaleźć zadowalającego rozwiązania?

Zawsze warto zapytać kolegi\koleżanki siedzącej obok o zdanie. To nie kosztuje dużo, a bardzo się opłaca. Nie ma głupich pytań chyba, że jak to powiedział mi kiedyś kumpel chcesz zapytać czy jak staniesz na torach i chwycisz się trakcji to pojedziesz jak tramwaj :)

Co robię z poufnymi...

Home

Post ten jest częściowo powiązany z poprzednim, w którym napisałem, jak podchodzę do bezpieczeństwa swoich danych. Tym razem opiszę, jak pozbywam się poufnych danych...

Zacznijmy od papierowych dokumentów, które są już nam do niczego potrzebne. Pomimo tego, że staram się ograniczyć ich "produkcję", to trochę się tego zbiera: paragony ze sklepów, rachunki, faktury, stare umowy, wyciągi z banków itd. Przynajmniej na części z nich można znaleźć nasze dane teleadresowe i na przykład powiązać wyciąg z banku z mieszkaniem numer X przy ulicy Y. Może i jestem przewrażliwiony, ale ja takich rzeczy nie wyrzucam do kosza. Już dawno temu sprawiłem sobie niszczarkę firmy Fellowers i wszystkie poufne dokumenty lądują właśnie w niej.

Podejście do poufnych dokumentów rozciąga się również na świat elektroniczny. Kiedy jakiś czas temu miałem problemy z telefonem i musiałem oddać go na gwarancję, usunąłem z niego wszystkie dane. Ponieważ jednak nie byłem pewny gdzie dokładnie trzymane są hasła do mojego konta Google oraz kont pocztowych na wszelki wypadek, przed oddaniem sprzętu do serwisu, zmieniłem hasła. Kiedy wyciekły hasła z portalu LinkedIn, to, pomimo tego sądzę, że moje oparłoby się metodzie słownikowej, a jego złamanie zajęłoby trochę czasu, bez zastanowienia je zmieniłem.

Rok temu chciałem zezłomować stary, niedziałający laptop. Niejeden pewnie wyrzuciłby go do kosza lub oddał to wyznaczonego punktu. I jak tak rozbiłem, ale wcześniej wyciągnąłem z niego dysk. Z jednej strony był jeszcze sprawny, a z drugiej po co ryzykować. Jeszcze nie potrzebowałem tego robić ale gdybym chciał się pozbyć dysku to najpierw użyłbym jakiegoś narzędzia do zamazywania danych (na przykład CCleaner), potem go sformatował, a na koniec uszkodził go fizycznie choćby przy pomocy młotka ;)

Co jeśli chcę usunąć jakieś pojedyncze pliki z dysku? W większości wypadków po prostu je usuwam i opróżniam Kosz, choć ta operacja tak naprawdę nie gwarantuje fizycznego usunięcia danych z dysku. W 99.9% przypadków to mi jednak wystarcza. Kiedy zależy mi na bezpowrotnym wymazania danych postępuję inaczej. Kiedyś korzystałem z opcji Wipe programu PGP. W tej chwili przestawiłem się na GPG, który nie posiada tej funkcji, a więc testuję program shred z pakietu GNU CureUtils. Jeśli nie chce się Wam używać takich narzędzi, to, moim zdaniem, przed usunięciem pliku warto przynajmniej otworzyć i nadpisać jego zawartość.

Jak zabezpieczam swoje dane

Home

Post ten będzie dotyczył rzeczy, na której mam chyba drobnego hopla, czyli tego jak zabezpieczyć się przed utratą danych np.: w wyniku kradzieży komputera. Moje podejście jest proste, aby czuć się bezpiecznym muszę posiadać 3 niezależne, fizycznie od siebie oddalone kopie swoich danych: na domowym komputerze oraz na dwóch dyskach przenośnych z czego jeden trzymam daleko poza domem. Tą drugą lokalizacją może być dom rodziców, skrytka bankowa, dom przyjaciela itd. Dysk trzymany w domu, po każdorazowym wykonaniu kopii bezpieczeństwa, zamieniam z tym drugim.

Do tworzenia kopii bezpieczeństwa nie używam jakiegoś specjalnego oprogramowania. Wszystkie dane, które są dla mnie istotne trzymam na komputerze w jednym miejscu, a więc zrobienie kopii polega na podłączeniu dysku i skopiowaniu na niego kilku folderów. Jeśli nie możecie znieść myśli o robieniu czegoś ręcznie ;) to łatwo to zautomatyzować. Dla mnie to zbyteczne, bo te kilka minut mnie nie zbawi. Takie kopie staram się wykonywać raz w miesiącu.

Do tematu szyfrowania kopii swoich danych podchodzę w ten sposób, że szyfruję tylko niektóre rzeczy np.: listy haseł, listy wydatków. W tym celu używam programu PGP/GPG oraz bardzo długiego i skomplikowanego hasła. Nie szyfruję wszystkiego ponieważ zajmuje to czas, a ja nie posiadam danych, których wyciek mógłby mi lub komuś zaszkodzić czy też skompromitować (to najlepsze z możliwych zabezpieczeń).

Jeśli pracuję nad czymś ważnym i nie mogę sobie pozwolić na czekanie do kolejnego backupu wykorzystuję Internet. Kiedyś wysyłałem archiwum na maila, teraz korzystam z dysków w chmurze. Przy czym, jeśli zależy mi na poufności danych, archiwum na wszelki wypadek zabezpieczam hasłem. Nie przypuszczam aby ktoś mnie szpiegował, ale przezorny zawsze zabezpieczony.

To prosty, ale mam nadzieję, że skuteczny system. Z mojej perspektywy najważniejsze jest fizyczne oddalenie od siebie kopii bezpieczeństwa. Jeśli w mój dom trafi meteoryt to zawsze pozostanie ta jedna kopia, nawet jeśli trochę stara. A Wy jak dbacie o swoje dane?

Warto też edukować swoją rodzinę i znajomych. Na przykład kupić im na Święta Bożego Narodzenia przenośny dysk i wytłumaczyć jak ważne jest robienie kopii zapasowej od czasu do czasu. Sądzę, że każdy ma jakieś dane warte zabezpieczenia: zdjęcia rodzinne, praca licencjacka, praca magisterska, kopia dokumentów urzędowych...

Przykład przeglądu kodu i co z tego wynikło

Home

Jakiś czas temu robiłem przegląd kodu i zwróciłem uwagę na taki fragment implementacji:

public class SrvObject
{
   public int Id { get; set; }
   public string Code { get; set; }
   ...
}
...
private Dictionary<int, SrvObject> _cache = new Dictionary<int, SrvObject>();
...
if (_cache.Values.Any(x => x.Code == codeToFind))
{
   var obj = _cache.Values.FirstOrDefault(x => x.Code == codeToFind);
   ...
}
else
{
   var obj = ReadObject(codeToFind);
   _cache.Add(obj.Id, obj);
   ...
}

Zacznijmy od tego, że mamy klasę, która modeluje jakąś encję z bazy danych i ta encja posiada zarówno identyfikator (wewnętrzny dla systemu) oraz kod, który można na przykład wyświetlić użytkownikowi.

Programista użył słownika, z kluczem w postaci identyfikatora, aby buforować już odczytane z bazy danych encje. Pierwsza rzecz jaka rzuca się w oczy to fakt, że kluczem jest identyfikator, a my wyszukujemy na podstawie kodu co wymaga iterowania po wszystkich zgromadzonych w słowniku obiektach. Wynika to z tego, że w większości przypadków posługujemy się identyfikatorem, a tylko czasami kodem i wspomniany kod został dodany później.

Załóżmy przez chwilę, że jest to ok. Druga rzecz na jaką należy zwrócić uwagę to fakt użycia metody Any i zaraz potem użycie FirstOrDefault. Jest to zbyteczne, kod ten robi dwa razy to samo, wystarczy zastosować tylko FirstOrDefault.

Wróćmy teraz do przeszukiwania słownika na podstawie kodu. Przy pokazanej implementacji musimy w najgorszym wypadku sprawdzić wszystkie obiekty w słowniku co ma złożoność liniową. Przy dużej liczbie obiektów w słowniku i częstych odwołaniach do niego jest to nieefektywne. W takim wypadku należy wprowadzić drugi słownik, w którym kluczem będzie kod. W zależności od sytuacji będziemy używać jednego albo drugiego słownika. Jeśli nie znajdziemy w którymś słowniku szukanego obiektu to dodajemy go do OBU słówników.

Przeprowadziłem mały test obu rozwiązań. Najpierw napisałem trzy metody wyszukujące encje:

• Znajdź na podstawie identyfikatora
• Znajdź na podstawie kodu bez dodatkowego słownika
• Znajdź na podstawie kodu z dodatkowym słownikiem

Początkowo słowniki są puste i generuję pewną liczbę N losowych identyfikatorów i kodów. Następnie znajduję te identyfikatory i kody korzystając z jednego słownika (Znajdź na podstawie identyfikatora + Znajdź na podstawie kodu bez dodatkowego słownika) oraz z dwóch słowników (Znajdź na podstawie identyfikatora + Znajdź na podstawie kodu z dodatkowym słownikiem). Oto wyniki:

Liczba N	Liczba unikalnych identyfikatorów	Czas (ms) dla dwóch słowników	Czas (ms) dla jednego słownika
100	63	3	4
500	320	2	4
1000	639	2	6
5000	3169	2	96
10000	6326	4	370
50000	31579	14	9190

Czas mierzyłem dla trybu Release. Jak widać nawet dla małej liczby elementów dwa słowniki są szybsze i to pomimo konieczności zarządzania jednym słownikiem więcej. Dla dużej liczby elementów przewaga jest miażdżąca. Jest to kolejny przykład, jak ważne są dobrze dobrane struktury danych.

Na koniec zwrócę jeszcze uwagę, że dwa słowniki oznaczają większe zapotrzebowanie na pamięć. W moich eksperymentach dwa słowniki dla 10 tyś elementów zużyły ~0.5MB więcej pamięci niż 1 słownik, dla 50 tyś elementów ~1.3 MB więcej, a dla 100 tyś elementów ~3.3 MB więcej.

Jeszcze o radzeniu sobie z głęboką rekursją

Home

W poście opisałem ogólne podejście to radzenia sobie z bardzo głęboką rekursją, która prowadzi do StackOverflowException. Dzisiaj powrócę do tematu. Od czasu do czasu, oprócz pogłębiania wiedzy na temat bibliotek, framework'ów itd. lubię rozwiązywać różnego rodzaju algorytmiczne zadania programistyczne. Jakiś czas temu rozwiązywałem takie zadanie:

Zadana jest mapa świata w postaci prostokątnej tablicy dwuwymiarowej. Każdy element tablicy ma swój kolor. Sąsiadujące (stykające się jednym z boków) z sobą elementy tego samego koloru należą do jednego kraju. Należy policzyć liczbę krajów na tej mapie. Jeśli dwa elementy tablicy mają ten sam kolor, ale nie znajdują się w jednym ciągłym obszarze, to należą do różnych krajów. 

Poniższy rysunek przedstawia przykładową mapę takiego świata, na który składa się 6 krajów.



Zacznijmy od głównej metody wykonującej obliczenia. Koncepcja jest prosta. Nie ulega wątpliwości, że należy odwiedzić wszystkie elementy tablicy aby móc zwrócić poprawny wynik. Aby nie zliczać tego samego elementu dwa razy używam wartości Int32.MaxValue jako znacznika już odwiedzonych elementów. Jeśli odwiedzając kolejny element znajduję wartość inną niż Int32.MaxValue to znaczy, że danego elementu jeszcze nie odwiedziłem i zwiększam licznik krajów.

public int Count(int[][] map)
{
 if (map == null) return 0;
 
 if (map.Length == 0) return 0;

 var numberOfCountries = 0;

 for (var y = 0; y < map.Length; ++y)
 {
  for (var x = 0; x < map[0].Length; ++x)
  {
   if (map[y][x] != Int32.MaxValue)
   {
    numberOfCountries++;
    /* Zaznacz elementy należące do danego kraju */
    VisitCountry(map, map[y][x], y, x);
   }
  }
 }

 return numberOfCountries;
}

Co kryje się pod tajemniczym Zaznacz elementy należące do danego kraju? W pierwszym podejście napisałem funkcję rekurencyjną, która począwszy od zadanego elementu odwiedzała wszystkie pola należącego do danego kraju i oznaczała je jako odwiedzone.

public void VisitCountry(int[][] map, int currentColor, int y, int x)
{
 if (y < 0 || x < 0 || y >= map.Length || x >= map[0].Length) return;

 if (map[y][x] != currentColor) return;
            
 map[y][x] = Int32.MaxValue;

 VisitCountry(map, currentColor, y + 1, x);
 VisitCountry(map, currentColor, y, x + 1);
 VisitCountry(map, currentColor, y - 1, x);
 VisitCountry(map, currentColor, y, x - 1);
}

Poniżej kod testujący dla przykładu z początku postu:

int[][] map = new int[5][];

for (int i = 0; i < map.Length; ++i)
 map[i] = new int[4];

map[0][0] = 1; map[0][1] = 3; map[0][2] = 3; map[0][3] = 2;
map[1][0] = 1; map[1][1] = 2; map[1][2] = 3; map[1][3] = 2;
map[2][0] = 1; map[2][1] = 1; map[2][2] = 1; map[2][3] = 1;
map[3][0] = 2; map[3][1] = 3; map[3][2] = 3; map[3][3] = 1;
map[4][0] = 2; map[4][1] = 2; map[4][2] = 2; map[4][3] = 2; 

var result = Count(map);

W warunkach zadania było jednak napisane, że szerokość/wysokość mapy może znajdować się w przedziale od 1 do 1000000. Sprawdźmy, więc czy kod ten obsłuż dużo większą mapę:

int[][] bigMap = new int[10000][];
for (int i = 0; i < bigMap.Length; ++i)
{
 bigMap[i] = new int[10000];
 for (int j = 0; j < bigMap.Length; ++j)
  bigMap[i][j] = i;
}

var result = Count(bigMap);

Na mojej maszynie wystarczy już mapa 10000 x 10000 aby pojawił sie wyjątek StackOverflowException. Zgodnie z tym co napisałem we wcześniejszym poście metoda VisitCountry powinna więc wyglądać tak:

public void VisitCountry(int[][] map, int startY, int startX)
{
 var toCheck = new Queue<Tuple<int, int>>();
 toCheck.Enqueue(new Tuple<int, int>(startY, startX));

 var currentColor = map[startY][startX];

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

  if (t.Item1 < 0 || t.Item2 < 0 || t.Item1 >= map.Length || t.Item2 >= map[0].Length) continue;

  if (map[t.Item1][t.Item2] != currentColor) continue;

  map[t.Item1][t.Item2] = Int32.MaxValue;

  toCheck.Enqueue(new Tuple<int, int>(t.Item1 + 1, t.Item2));
  toCheck.Enqueue(new Tuple<int, int>(t.Item1, t.Item2 + 1));
  toCheck.Enqueue(new Tuple<int, int>(t.Item1 - 1, t.Item2));
  toCheck.Enqueue(new Tuple<int, int>(t.Item1, t.Item2 - 1));
 }
}

Tym razem mapa 10000 x 10000 i większe zostanie poprawnie obsłużona. Kod ten można jeszcze optymalizować. Na przykład zliczać ile pól się już odwiedziło i przerwać dalsze przetwarzanie, jeśli odwiedziło się wszystkie. Dalszą optymalizację kodu można potraktować jako ćwiczenie.

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();
}

Problem z AssemblyResolve

Home

Niedawno miałem okazję pracować z aplikacją, w której zaimplementowano obsługę zdarzenia AppDomain.AssemblyResolve. Zdarzenie to pozwala załadować assembly jeśli standardowy mechanizm platformy .NET nie poradzi sobie z tym zadaniem. Aplikacja działała poprawnie aż do migracji na platformę .NET 4.0 Czemu? O tym właśnie będzie post. Zwrócę w nim uwagę na dość istotną różnicę pomiędzy platformą .NET 4.0, a jej wcześniejszymi wersjami jeśli chodzi o wspomniane zdarzenie. Różnica ta, w określonych warunkach, może napsuć krwi.

Przechodząc do meritum chodzi o to, że począwszy od .NET 4.0 zdarzenie AppDomain.AssemblyResolve generowane jest dla wszystkich assemblies, również tych z zasobami. Poniżej cytat z dokumentacji z MSDN'a.

Beginning with the .NET Framework 4, the ResolveEventHandler event is raised for all assemblies, including resource assemblies. In earlier versions, the event was not raised for resource assemblies. If the operating system is localized, the handler might be called multiple times: once for each culture in the fallback chain.

Oznacza to, że jeśli biblioteka SomeLibrary zawiera zasoby, to zdarzenie AppDomain.AssemblyResolve zostanie wygenerowane dla nie dwa razy. Raz z żądaniem załadowania assembly o nazwie SomeLibrary, a drugi raz z żądaniem załadowania SomeLibrary.resources. Fizycznie oba assembly znajdują się natomiast w dll'ce o nazwie SomeLibrary.dll.

Jeśli obsługa zdarzenia AppDomain.AssemblyResolve zaimplementowana została w uproszczony albo raczej błędy sposób mamy problem. Mam tu na myśli implementację, w której nie przewidziano, że nie uda się znaleźć dll'ki o nazwie zgodnej z nazwą assembly. W omawianym przypadku wyglądało to mniej więcej tak:

private static Assembly MyResolveEventHandler(object sender, ResolveEventArgs args)
{
 //Determine assembly path based on the configuration
 //...
 
 Assembly asm = Assembly.LoadFrom(path);
 return asm;
}

Łatwo się domyślić, że wywołanie Assembly.LoadFrom(path) dla ścieżki SOME_PATH\SomeLibrary.resources.dll zakończy się błędem bo taka ścieżka nie istnieje. W aplikacji objawi się to wyjątkiem FileNotFoundException przy próbie odczytania czegokolwiek z zasobów. Powinno to zostać zrobione wcześniej ale łatwo to naprawić:

private static Assembly MyResolveEventHandler(object sender, ResolveEventArgs args)
{
 //Determine assembly path based on the configuration
 //...
 
 try
 {
  return Assembly.LoadFrom(path);
 }
 catch(Exception ex)
 {
  //Log exception
  
  return null;
 }
}

Albo w taki sposób, jeśli chcemy obsłużyć tylko scenariusz z zasobami:

private static Assembly MyResolveEventHandler(object sender, ResolveEventArgs args)
{
 //Determine assembly path based on the configuration
 //...
 
 if(args.Name.Contains(".resources,"))
  return null;
  
 Assembly asm = Assembly.LoadFrom(path);
 return asm;
}

Zwrócenie null powoduje, że zostanie użyty standardowy mechanizm wyszukiwania i ładowania assemblies platformy .NET, a ponieważ dll'ka SomeLibrary.dll zostanie załadowana przy pierwszym żądaniu to poradzi sobie on z załadowaniem assembly z zasobami.