10/03/2014

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'ówCzas (ms)
100
144
159
1871
20291
221169
244685
2618741
2874078

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.

25/02/2014

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]

24/02/2014

WolframAlpha - ponownie

Home

Rzadko zdarza się aby jakieś narzędzie zaskakiwało mnie tak często i tak przyjemnie jak WolframAlpha (pisałem już o nim tutaj lub tutaj). Po prostu kiedy potrzebuję coś policzyć, sprawdzić i szukam programu lub strony, która to dla mnie zrobi to bardzo często wracam właśnie do WolframAlpha.

Tym razem potrzebował czegoś, co wyznaczy mi linię trendu czyli nic dodać nic ująć tylko tzw. prosta regresja liniowa. Okazało się, że w WolframAlpha służy do tego komenda linear fit. Linia prosta to oczywiście bardzo prosty model, który nie zawsze będzie dobrze działać, ale przy tej okazji odkryłem, że WolframAlpha wspiera również bardziej zaawansowane modele, na przykład komenda cubic fit generuje model w postaci równania trzeciego stopnia. Po więcej przykładów odsyłam do tej strony, zachęcam do zapoznania się i własnych poszukiwań.

A do czego takie modele mogą się przydać? Na przykład do predykcji cen, długości życia w zależności od różnych czynników, liczby odwiedzin strony...

27/01/2014

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ę.

    16/01/2014

    Podsumowania roku są bardzo ważne

    Home

    Refleksja jak powyżej naszła mnie właśnie podczas takiego spotkania podsumowującego. Niby wiedziałem, jakie projekty były realizowane w czasie zeszłego roku, niby wiedziałem o wszystkich przedsięwzięciach podejmowanych w poszczególnych obszarach (innowacja, zarządzanie wiedzą itd.), zdawałem sobie również ze zmian w zespole... Pomimo tego, kiedy zebraliśmy wszystko do kupy byłem zaskoczony, ale w bardzo przyjemny sposób, i podbudowany jak dużo rzeczy udało się zrealizować.

    Niektóre ze zmian były całkiem duże i ewidentnie będą miały pozytywny, długofalowy wpływ. W szczególności mam tutaj na myśli wdrożenie automatycznych testów jednostkowych oraz integracyjnych, wypracowanie zasad ich tworzenia i włączenie ich w oficjalny proces wytwórczy, w czym maczałem swoje palce.

    Mniejszych i większych wydarzeń było sporo więcej i ważne, że wszyscy dowiedzieli się lub przypomnieli sobie, co się działo przez ostatni rok, a przecież nie każdy ma ekspozycję na wszystko co się dzieje. Dlatego uważam, że takie spotkania, o ile zrealizowane dobrze, najlepiej wewnątrz zespołu, tak aby skupić się na konkretach bez corporate bullshit, są bardzo potrzebne.

    Jeśli w Twojej firmie nie ma zwyczaju organizowania takich spotkań, to wyjdź z taką propozycją albo jeśli masz taką możliwość zorganizuj je samemu.