morzel.net

.net, js, html, arduino, java... no rants or clickbaits.

Jak szybki jest .NET Garbage Collector? Część 1.

.NET GC jest bardzo szybki! Mam nadzieje, że ta pocieszająca informacja Ci nie wystarcza i potrzebujesz nieco więcej szczegółów :) Pokaże Ci kilka testów, które dowodzą, że nie kłamię. Na początek jednak przyda się krótkie przypomnienie tego czym jest GC:

Garbage Collector to podstawowy komponent .NET CLR. Odpowiada on za zwalnianie pamięci na stercie zarządzanej tak by programista nie musiał troszczyć się o dealokację. W przeciwieństwie do obiegowej opinii, GC zajmuje się zarówno pamięcią typów referencyjnych jak i wartościowych. Dlaczego? Często przestrzeń dla takich rzeczy jak np. struktury i typy numeryczne jest alokowana na stercie. Dzieje się tak na przykład gdy typ wartościowy jest elementem tablicy lub polem w instancji klasy.

GC w .NET używa algorytmu mark and sweep: przemierza graf obiektów począwszy od tzw. rootów (np. zmiennych statycznych, referencji na stosie lub rejestrach) i oznacza wszystkie elementy do może dotrzeć. Kiedy obieg jest zakończony, GC wie, że może bezpiecznie zwolnić pamięć zajętą przez nieoznaczone obiekty – ponieważ jako nieosiągalne są one bezużyteczne dla aplikacji.

Ze względów wydajnościowych GC wspiera pojęcie generacji. Świeżo utworzony obiekt przynależy do Gen 0 (za wyjątkiem tzw. dużych obiektów). Jeśli obiekt z Gen 0 przetrwa cykl zbiórki jest przenoszony do Gen 1. Jeśli przetrwa kolejny cykl trafia do Gen 2 i w niej zostaje (nie ma Gen 31). Większość obiektów żyje krótko – nie wychodzą poza Gen 0 lub Gen 1 więc .NET najpierw zwalnia pamięć z niższych generacji. Zbieranie nieużytków z Gen 2 (tzw. full collection) odbywa się znacznie rzadziej niż zbieranie w Gen 0. Jeśli obiekt jest duży tj. powyżej 850002 bajtów jest on alokowany na LOH (Large Object Heap) i trafia od razu do Gen 2. Traktowanie dużych obiektów tak samo jak małych miałoby negatywny wpływ na algorytmy defragmentacji3 sterty ponieważ przenoszenie takich obiektów jest czasochłonne.

GC wspiera różne tryby pracy dla stacji roboczych i serwerów, potrafi wykonać cześć pracy w działających w tle wątkach, musi brać pod uwagę specjalne przypadki takie jak istnienie finalizatorów i przypiętych buforów pamięciowych, posiada wyspecjalizowane konfiguracje dla różnych platform (CLR na PC różni się na przykład od tego na Xbox)… Ok, starczy, obiecałem przecież "krótkie przypomnienie"!

Teraz czas na test!

W tym pierwszym poście pokażę Ci jak szybko .NET GC radzi sobie z dużymi tablicami typów wartościowych. Test będzie dotyczył tablicy bajtów zajmującej około dwóch giga. Pomimo swoich wielkich rozmiarów taki obiekt nie obciąża znacznie Garbage Collectora. Jest tak ponieważ jedyną referencją którą musi sprawdzić GC jest ta do tablicy. Jeśli tablica staje się niedostępna cała pamięć zajęta przez jej elementy może bez problemu zostać użyta ponownie. Dodatkowo, tablica taka, jako przynależna do LOH, nie jest kopiowana (w celu uniknięcia fragmentacji sterty) gdy przeżywa ona cykl zbiórki GC. W drugim odcinku tego artykułu pokaże Ci jak GC działa dla bardziej złożonych scenariuszy. Przetestujemy wydajność dla tablicy obiektów, oraz co ważniejsze, dla drzewa obiektów z tysiącami referencji…

Info o środowisku testowym: stacjonarny PC z procesorem Intel i-5 2400 3.1 GHz 4 Core CPU, 12 GB RAM DDR 3/1333 i Windows 7 Ultimate x64. Program testowy to konsolowa aplikacja .NET 4.0 skompilowana w trybie Relase i uruchomiona bez podłączania debuggera

Oto kod testowy:

static void TestSpeedForLargeByteArray()
{
    Stopwatch sw = new Stopwatch();

    Console.Write(string.Format("GC.GetTotalMemory before creating array: {0:N0}. Press any key to create array...", GC.GetTotalMemory(true)));
    Console.ReadKey();
    byte[] array = new byte[2000 * 1000 * 1000]; // About 2 GB
   
    sw.Start();
    for (int i = 0; i < array.Length; i++)
    {
        array[i] = 1; // Touch array elements to fill working set              
    }          
    Console.WriteLine("Setup time: " + sw.Elapsed);

    Console.WriteLine(string.Format("GC.GetTotalMemory after creating array: {0:N0}. Press Enter to set array to null...", GC.GetTotalMemory(true)));
    if (Console.ReadKey().Key == ConsoleKey.Enter)
    {
        Console.WriteLine("Setting array to null");
        array = null;
    }
               
    sw.Restart();
    GC.Collect();                 
    Console.WriteLine("Collection time: " + sw.Elapsed);
    Console.WriteLine(string.Format("GC.GetTotalMemory after GC.Collect: {0:N0}. Press any key to finish...", GC.GetTotalMemory(true)));

    Console.WriteLine(array); // To avoid compiler optimization...
    Console.ReadKey();
}

Jak widzisz test jest bardzo prosty. Kod używa dwóch metod ze statycznej klasy GC: GC.GetTotalMemory oraz GC.Collect. Pierwsza zwraca ilość zaalokowanej pamięci zarządzanej a druga zmusza Garbage Collector do zwolnienia pamięci. Jedyna rzecz, która może Cię zaskoczyć to pętla odwołująca się do elementów tablicy. Bez niej zaobserwowałbyś “dziwne” zjawisko: po zdefiniowaniu tablicy GC.GetTotalMemory zaraportowałaby około 2 GB ale nie zauważyłbyś zwiększenia zużycia pamięci w Menadżerze zadań Windows! Jest tak ponieważ taksmgr.exe pokazuje dane zestawu roboczego (working set). Możesz użyć bardziej zaawansowanego narzędzia: Monitora zasobów (taskmgr.exe) by zobaczyć co się dzieje:

To screenshot sprzed “dotknięcia” elementów tablicy:

Zużycie pamięci przed dostępem do elementów tablicy. Kliknij aby powiększyć...

a to zrzut zrobiony po wykonaniu pętli:

Zużycie pamięci po dostępie do elementów tablicy. Kliknij aby powiększyć...

Pora na rezultaty testu:

GC.GetTotalMemory before creating array: 41,568. Press any key to create array...
Setup time: 00:00:01.0633903
GC.GetTotalMemory after creating array: 2,000,053,864. Press Enter to set array to null...
Setting array to null
Collection time: 00:00:00.1443391
GC.GetTotalMemory after GC.Collect: 53,800. Press any key to finish...

Możesz zauważyć, że wyczyszczenie około 2 GB pamięci zajęło GC około 150 milisekund. Nieźle, co? Prędkość tą można szczególnie docenić gdy zwróci się uwagę na to, że samo przejście w pętli przez elementy tablicy zabrało ponad sekundę!

Oto ekran z Monitora wydajności (perfmon.exe) z kilkoma licznikami dla pamięci .NET:

Monitor wydajności z licznikami pamięci zarządzanej. Kliknij aby powiększyć...

Nasza tablica jest dużym obiektem (znacznie większym niż próg LOH) – widać więc, że po jej zdefiniowaniu pamięć LOH zwiększa się a pamięć Gen 0 pozostaje bez zmian.

Poniżej znajdują się rezultaty wywołania GC.Collect dla przypadku gdy referencja do tablicy nie zostaje ustawiona na null:

GC.GetTotalMemory before creating array: 41,568. Press any key to create array..
Setup time: 00:00:01.0385779
GC.GetTotalMemory after creating array: 2,000,053,864. Press Enter to set array to null...
Collection time: 00:00:00.0001287
GC.GetTotalMemory after GC.Collect: 2,000,053,824. Press any key to finish...

Ułamek milisekundy. Zupełnie pomijalna wartość! Dlaczego w ogóle wspominam o sytuacji w kórej pamięć nie podlega zebraniu? W następnym poście zobaczysz, że GC ma zazwyczaj więcej pracy gdy elementy na strecie przeżywają cykl zbiórki nieużytków.

Planuje dodać drugą cześć artykułu za tydzień albo dwa. Niczego jednak nie obiecuję – wiesz, życie… ;)

Update 26.07.2014: Zmieniłem ilustrację z monitora wydajności (zwiększona skala Gen 0 i Gen 1)..

Update 24.06.2014: Kilka dni temu napisałem drugą cześć artykułu. Kliknij tutaj.

1. Możesz użyć metody GC.GC.MaxGeneration by to sprawdzić.

2. Próg LOH to detal implementacyjny. Większość źródeł wymienia 85KB jako limit ale nie jest to zawsze prawda - tablica double długości zaledwie 1000 elementów trafia na LOH (na x86)...

3..NET 4.5 wprowadza zmiany w LOH usprawniające zapobieganie fragmentacji poprzez balansowanie i usprawnione użycie listy wolnych bloków. Przyszłe edycje wprowadzą prawdopodobnie również opcje kompaktowania.

Html Agility Pack - masowe wyciąganie danych ze stron WWW

Niedawno potrzebowałem pozyskać zawartość pewnej bazy danych. Niestety była ona upubliczniona jedynie w formie serwisu WWW prezentującego 50 rekordów na pojedynczej stronie. Cała baza miała ponad 150 tysięcy rekordów. Co zrobić w takiej sytuacji? Przeklikiwać się przez 3000 stron, ręcznie gromadząc dane w pliku tekstowym? Tydzień i po sprawie! ;) Lepiej jednak napisać automat (tzw. scraper), który zrobi to za Ciebie. Automat musi zrobić trzy rzeczy:

  • wygenerować listę adresów stron, z których pobierane będą dane;
  • odwiedzać kolejno strony i wyciągać odpowiednie informacje z ich kodu HTML;
  • zrzucać dane do lokalnej bazy i logować postęp prac.

Generowanie adresów powinno być proste. W większości serwisów stronicowanie jest zrobione za pomocą zwykłych lików, w których numer strony jest łatwo widoczny w głównej części URL (http://example.com/somedb/page/1) lub w query stringu (http://example.com/somedb?page=1). Jeśli paginacja jest ajaxowa sprawa nieco się kompiluje, nie martwmy się tym jednak w tym poście... Gdy poznasz wzorzec przekazywania parametru z numerem strony, do stworzenia listy adresów wystarczy zwykła pętla z czymś w stylu:

string url = string.Format("http://example.com/somedb?page={0}", pageNumber)

Teraz pora na coś ciekawszego. W jaki sposób wyciągnąć dane ze strony WWW? Można użyć klas WebRequest/WebResponse lub WebClient z przestrzeni nazw System.Net do pobrania zawartości strony, po czym pozyskiwać informacje za pomocą wyrażeń regularnych. Można też spróbować potraktować pobraną treść jako XML i badać ją za pomocą XPath lub LINQ to XML. Nie są to jednak dobre podejścia. Przy skomplikowanej strukturze strony napisanie prawidłowego wyrażenia może być trudne, trzeba też pamiętać, że w większości przypadków strony internetowe nie są prawidłowymi dokumentami XML. Na szczęście powstała biblioteka Html Agility Pack, która umożliwia łatwe parsowanie stron HTML. Nawet tych, których kod nie przeszedłby walidacji bo np. nie zawiera poprawnych znaczników zamykających. HAP procesuje treść strony i buduje obiektowy model dokumentu, który można przetwarzać za pomocą LINQ to Objects lub XPath.

Aby zacząć pracę z HAP użyj NuGet by zainstalować pakiet HtmlAgilityPack (ja używałem wersji 1.4.6) po czym zaimportuj namespace o tej samej nazwie. Jeśli nie chcesz korzystać z NuGet (dlaczego?) pobierz plik zip ze strony projektu i dodaj referencje do pliku HtmlAgilityPack.dll stosownego dla Twojej platformy (zip zawiera np. wersje dla .NET 4.5 i Silverlight 5). Pomocna będzie też dokumentacja w pliku .chm. Uwaga! Gdy otworzyłem pobrany plik (w Windows 7), dokumentacja wyglądała na pustą. Pomogło użycie opcji „Odblokuj” z menu właściwości pliku.

Pobranie treści strony za pomocą HAP jest bardzo proste. Należy utworzyć obiekt klasy HtmlWeb po czym użyć metody Load podając adres strony:

HtmlWeb htmlWeb = new HtmlWeb();
HtmlDocument htmlDocument = htmlWeb.Load("http://en.wikipedia.org/wiki/Paintball");

W odpowiedzi otrzymamy obiekt klasy HtmlDocument, która stanowi centrum biblioteki HAP.

HtmlWeb zawiera właściwości, które mają wpływ na sposób pobierania dokumentu z sieci. Można np. wskazać czy ma być użyty mechanizm ciasteczek (UseCookies) oraz ustalić nagłówek User Agent dołączany do żądania HTTP (UserAgent). Mnie szczególnie przydały się właściwości AutoDetectEncoding i OverrideEncoding, dzięki którym mogłem poprawnie odczytać dokument z polskimi znakami:

HtmlWeb htmlWeb = new HtmlWeb() { AutoDetectEncoding = false, OverrideEncoding = Encoding.GetEncoding("iso-8859-2") };

Inna bardzo przydatną właściwością HttpWeb jest StatusCode (typu System.Net.HttpStatusCode). Informuje ona o rezultacie obsługi ostatniego żądania.

Mając obiekt HtmlDocument możemy przystąpić do wyciągania danych. Oto przykład jak wyciągnąć adresy i teksty linków z pobranej wcześniej strony (dodaj using System.Linq):

IEnumerable<HtmlNode> links = htmlDocument.DocumentNode.Descendants("a").Where(x => x.Attributes.Contains("href");
foreach (var link in links)
{
    Console.WriteLine(string.Format("Link href={0}, link text={1}", link.Attributes["href"].Value, link.InnerText));       
}

Właściwość DocumentNode typu HtmlNode wskazuje na root strony. Metodą Descendants pobieramy wszystkie linki (tag a) zawierające atrybut href, po czym wypisujemy adres linku i jego tekst na konsole. Prawda, że proste? Kilka innych przykładów:

Pobranie całego kodu HTML strony:

string html = htmlDocument.DocumentNode.OuterHtml;

Pobranie elementu o id footer”:

HtmlNode footer = htmlDocument.DocumentNode.Descendants().SingleOrDefault(x => x.Id == "footer");

Pobranie dzieci div o id „toc” i wyświetlenie nazw tych, których typ jest różny od Text:

IEnumerable<HtmlNode> tocChildren = htmlDocument.DocumentNode.Descendants().Single(x => x.Id == "toc").ChildNodes;
foreach (HtmlNode child in tocChildren)
{
    if (child.NodeType != HtmlNodeType.Text)
    {
        Console.WriteLine(child.Name);
    }
}

Pobranie elementów listy (tag li) mających klasę toclevel-1:

IEnumerable<HtmlNode> tocLiLevel1 = htmlDocument.DocumentNode.Descendants()
    .Where(x => x.Name == "li" && x.Attributes.Contains("class")
    && x.Attributes["class"].Value.Split().Contains("toclevel-1"));

Zwróć uwagę, że filtr Where jest dość złożony. Prosty warunek:

Where(x => x.Name == "li" && x.Attributes["class"].Value == "toclevel-1")

nie jest poprawny! Po pierwsze nie ma gwarancji, że każdy tag li ma atrybut class, więc mógłby się pojawić NullReferenceException. Po drugie sprawdzenie istnienia klasy toclevel-1 jest wadliwe. Element HTML może mieć wiele klas, dlatego zamiast == warto użyć Contains(). Samo Value.Contains to jednak za mało. Co jeśli szukamy klasy o nazwie „sec”, a element ma klasę „secret”? Taki element też zostanie dopasowany! Zamiast Value.Contains należy użyć Value.Split().Contains. Wówczas przeszukujemy nie string, a tablicę stringów (przy użyciu operatora równości).

Pobranie tekstów wszystkich elementów li, które zagnieżdżone są w co najmniej jedynym elemencie li:

var h1Texts = from node in htmlDocument.DocumentNode.Descendants()
              where node.Name == "li" && node.Ancestors("li").Count() > 0
              select node.InnerText;

Oprócz LINQ to Objects do wyciągania informacji można użyć również zapytań XPath. Przykładowo:

Pobranie tagów a, których wartość atrybutu href zaczyna się od # i jest dłuższa niż 15 znaków:

IEnumerable<HtmlNode> links = htmlDocument.DocumentNode.SelectNodes("//a[starts-with(@href, '#') and string-length(@href) > 15]"));

Znalezienie elementów li w div o idtoc”, które są trzecim dzieckiem w swoim elemencie zawierającym:

IEnumerable<HtmlNode> listItems = htmlDocument.DocumentNode.SelectNodes("//div[@id='toc']//li[3]");

XPath to skomplikowane narzędzie o ogromnych możliwościach, ja poprzestanę na tych dwóch przykładach...

HAP pozwala nie tylko na badanie struktury i treści strony, umożliwia też jej modyfikację i zapis. Istnieją metody pomocnicze m. in. do wykrycia kodowania (DetectEncoding) lub usunięcia encji HTML (DeEntitize). Można również pozyskać informacje o tym czy oryginalny dokument posiadał odpowiednio zamknięte tagi itp. Te tematy wykraczają jednak poza zakres postu.

W miarę pobierania informacji z kolejnych stron zrzucaj je do bazy, z której będziesz mógł wygodnie skorzystać (może wystarczy Ci plik .csv, może potrzebna będzie baza SQL - mnie wystarczył zwykły plik tekstowy).

Ostatnią rzeczą, która należy zrobić jest zadbanie o to by scraper logował informacje o postępie prac (chciałbyś przecież wiedzieć jak daleko zaszedł Twój automat i czy coś nie poszło źle). Do logowania najlepiej jest użyć wyspecjalizowanej biblioteki takiej jak np. log4net. W necie jest mnóstwo instrukcji o tym jak z niej korzystać, nie będę wiec o tym pisał. Dodam za to przykładową konfiguracje, której możesz użyć w aplikacji konsolowej:
<?xml version="1.0" encoding="utf-8" ?>
<configuration>
    <configSections>
        <section name="log4net" type="log4net.Config.Log4NetConfigurationSectionHandler, log4net"/>          
    </configSections>
    <log4net>        
        <root>
            <level value="DEBUG"/>            
            <appender-ref ref="ConsoleAppender" />
            <appender-ref ref="RollingFileAppender"/>
        </root>
        <appender name="ConsoleAppender" type="log4net.Appender.ColoredConsoleAppender">
            <layout type="log4net.Layout.PatternLayout">
                <conversionPattern value="%date{ISO8601} %level [%thread] %logger - %message%newline" />
            </layout>
            <mapping>
                <level value="ERROR" />
                <foreColor value="White" />
                <backColor value="Red" />
            </mapping>
            <filter type="log4net.Filter.LevelRangeFilter">
                <levelMin value="INFO" />                
            </filter>
        </appender>         
        <appender name="RollingFileAppender" type="log4net.Appender.RollingFileAppender">
            <file value="Log.txt" />
            <appendToFile value="true" />
            <rollingStyle value="Size" />
            <maxSizeRollBackups value="10" />
            <maximumFileSize value="50MB" />
            <staticLogFileName value="true" />
            <layout type="log4net.Layout.PatternLayout">
                <conversionPattern value="%date{ISO8601} %level [%thread] %logger - %message%newline%exception" />
            </layout>
        </appender>
    </log4net>    
</configuration>

Posiada ona dwa appendery: ConsoleAppender i RollingFileAppender. Pierwszy z nich loguje tekst do okna konsoli, dbając o to by błędy wyraźnie wyróżniały się kolorem. By ograniczyć ilość informacji ustawiony jest LevelRangeFilter dzięki czemu prezentowane są tylko wpisy o poziomie INFO lub wyższym.

Drugi appender loguje do pliku tekstowego (trafiają tam nawet wpisy o poziomie DEBUG). Maksymalny rozmiar pojedynczego pliku ustalony jest na 50MB, a poduszczana ilość plików archiwalnych to 10. Bieżący log znajduje się zawsze w pliku Log.txt...

I to wszystko, scraper jest gotowy! Odpal go i niech tyra za Ciebie. Wielogodzinną, monotonną robotę zostaw tym, którzy nie potrafią programować! :)

Możesz jeszcze wykonać małe ćwiczenie: zamiast tworzyć listę wszystkich stron do odwiedzenie, ustal jedynie pierwszą stronę po czym spróbuj znaleźć link do następnej strony w kodzie bieżącej.

P.S. Pamiętaj o tym, że HAP działa na kodzie HTML, który został nadesłany przez serwer i to na bazie tego kodu buduje model dokumentu. DOM, który obserwujesz w narzędziach deweloperskich swojej przeglądarki często jest wynikiem działania skryptów i może znacznie różnić się od tego, który wynikałby z odpowiedzi HTTP.

Aktualizacja 08.12.2013: Zgodnie z prośbą stworzyłem proste demo (w Visual Studio 2010) użycia Html Agility Pack i log4net. Aplikacja wyciąga linki ze strony wiki i zapisuje je w pliku tekstowym. Strona wiki zrzucona jest do pliku htm by uniknąć zależności od strony w sieci, która może się zmienić. Pobierz.

Krótkie ale bardzo użyteczne wyrażenie regularne - lookbehind, lazy, group i backreference

Ostatnio chciałem wyciągnąć z logów komunikaty wysyłane do zewnętrznego systemu i przeprowadzić kilka operacji LINQ to XML na pozyskanych danych. Oto przykładowa linia logu (uproszczona, rzeczywisty log był o wiele bardziej skomplikowany ale nie ma to znaczenia w tym poscie):

Call:<getName seqNo="56789"><id>123</id></getName> Result:<getName seqNo="56789">John Smith</getName>

Interesowały mnie takie dane XML ("call"):

<getName seqNo="56789">
  <id>123</id>
</getName>

Przy okazji: najprostszym sposobem na pozyskanie ładnie sformatowanego XMLa w .NET 3.5 lub nowszym jest wywołanie metody ToString na obiekcie XElement:

var xml = System.Xml.Linq.XElement.Parse(someUglyXmlString);     
Console.WriteLine(xml.ToString());

Jeśli chodzi o log, kilka rzeczy było pewnych:

  • XML z callem znajduje się po tekście „Call:” z początku linii
  • nazwa głównego elementu (roota) komunikatu będzie skądać się wyłącznie ze znaków alfanumerycznych lub podkreślenia
  • w komunikacie nie będzie znaków podziału linii
  • głowy element calla może wystąpić w logu także w sekcji „Result”
Otrzymanie prawidłowych danych było dosyć proste dzięki klasie Regex:
Regex regex = new Regex(@"(?<=^Call:)<(\w+).*?</\1>");
string call = regex.Match(logLine).Value;

To krótkie wyrażenie regularne ma kilka interesujących części. Nie jest może doskonałe ale okazało się bardzo przydatne podczas analizy logów. Jeśli powyższy regex nie jest dla Ciebie zupełnie jasny – czytaj dalej, prędzej czy później będziesz musiał użyć czegoś podobnego.

Poniżej jest to samo wyrażenie ale z komentarzami (ustawienie opcji RegexOptions.IgnorePatternWhitespace jest konieczne do przetworzenia wyrażenia zapisanego w ten sposób):

string pattern = @"(?<=^Call:) # Positive lookbehind dla znacznika wywołania
                   <(\w+)      # Capturing group dla nazwy tagu otwierającego
                   .*?         # Lazy wildcard (wszystko w środku)
                   </\1>       # Backreference do nazwy tagu otwierającego";   
Regex regex = new Regex(pattern, RegexOptions.IgnorePatternWhitespace);
string call = regex.Match(logLine).Value;

Positive lookbehind

(?<=Call:) to tzw. lookaround a dokładniej positive lookbehind. Jest to asercja zerowej szerokości, która pozwala na sprawdzanie czy tekst poprzedzony jest przez dany ciąg znaków. Tutaj „Call:” to tekst poprzedzający, którego szukamy. Zapis (?<=something) określa positive lookbehind. Istnieje również negative lookbehind zapisywany za pomocą (?<!something). Dzięki niemu można zweryfikować czy jakiś tekst nie posiada określonych znaków przed sobą. Lookaround sprawdza fragment tekstu ale nie stanowi on części dopasowanej wartości. Tak więc rezultatem tego:

Regex.Match("X123", @"(?<=X)\d*").Value

będzie „123” a nie „X123”

Silnik wyrażeń regularnych w .NET obsługuje także mechanizm lookaheads. Odwiedź  świetną stronę jeśli chcesz dowiedzieć się więcej o lookarounds.

Uwaga: w niektórych przypadkach (np. w naszym badaniu logu) zamiast positive lookaround można użyć grup nieprzechwytujących...

Capturing group

<(\w+) dopasowuje znak mniejszości, po którym następuje jeden lub więcej znaków z klasy \w (litery, cyfry lub znaki podkreślenia). Fragment \w+ jest otoczony nawiasami w celu utworzenia grupy zawierającej nazwę korzenia XML (getName dla przykładowej linii logu). Grupa ta jest później użyta do znalezienia tagu zamykającego przy użyciu odwołania wstecznego. (\w+) to grupa przechwytujaca (capturing group), co oznacza, że rezultat istnienia tej grupy jest dodawany do kolekcji Groups obiektu Match. Jeśli chcesz umieścić część wyrażenia w grupie ale nie chcesz wstawiać rezultatu do kolekcji Groups możesz skorzystać z grupy nieprzechwytującej. Grupę taką tworzy się poprzez dodanie pytajnika i dwukropka przed nawiasem otwierającym: (?:something) 

Lazy wildcard

.*? dopasowuje wszystkie znaki z wyjątkiem nowe linii (ponieważ nie używamy opcji RegexOptions.Singleline) w trybie leniwym (lazy lub non-gready) dzięki pytajnikowi umieszczonemu za gwiazdką. Domyślnie kwantyfikator * działa w trybie zachłannym (greedy) co oznacza, że silnik wyrażeń regularnych próbuje dopasować tak dużo tekstu jak to możliwe. W naszym przypadku, domyślny tryb spowodowałby zwrócenie zbyt długiego tekstu:

<getName seqNo="56789"><id>123</id></getName> Result:<getName seqNo="56789">John Smith</getName>

Backreference

</\1> dopasowuje zamykający tag XML, którego nazwa dostarczona jest przez \1 backreference. Wspomniana wcześniej grupa (\w+) ma numer 1, przez użycie składni \1 odwołujemy się do tekstu dopasowanego przez tą grupę. Więc dla naszego przykładowego logu </\1> zwraca </getName>. Jeśli wyrażenie regularne jest skomplikowane, dobrym pomysłem jest porzucenie numerowanych referencji na rzecz nazwanych. Grupę można nazwać poprzez składnię <name> lub <’name’> a odwołać się do niej można dzięki k<name> lub k’name’. Wyrażenie może więc wyglądać tak:

@"(?<=^Call:)<(?<tag>\w+).*?</\k<tag>>"

lub tak:

@"(?<=^Call:)<(?'tag'\w+).*?</\k'tag'>"

W naszym przypadku wersja druga jest lepsza. Użycie znaków < > w przypadku dopasowywania XML jest mylące. Silnik regex poradzi sobie z zapisem używającym < > ale pamiętaj, że kod źródłowy piszę się dla ludzi...

Wyrażenia regularne wyglądają strasznie ale warto poświęcić kilka godzin na ich przećwiczenie, regexy to niesamowicie przydatne narzędzie (nie tylko w czasie analizy logów)!

Szybkie operacje pikselowe w .NET (z i bez unsafe)

Klasa Bitmap posiada metody GetPixel i SetPixel, które pozwalają na pobranie i zmianę koloru piksela. Metody te są bardzo proste w użyciu, niestety są też niezwykle powolne. Mój poprzedni post szczegółowo opisuje ten temat, kliknij tutaj jeśli chcesz wiedzieć więcej.

Na szczęście nie trzeba używać zewnętrznych bibliotek (lub całkowicie rezygnować z .NET) by efektywnie przetwarzać obraz. Framework ma wbudowaną klasę ColorMatrix pozwalającą na wykonanie zmian na mapie bitowej w krótkim czasie. Właściwości takie jak kontrast lub nasycenie mogą być modyfikowane w ten sposób. Co jednak z manipulowaniem pojedynczymi pikselami? Da się to zrobić za pomocą metody Bitmap.LockBits i klasy BitmapData

Dobrym testem szybkości operacji pikselowych jest badanie różnicy kolorów. Zadanie polega na znalezieniu fragmentów obrazu, które mają kolor podobny do zadanego koloru. Jak sprawdzić czy kolory są podobne? Pomyśl o kolorze jako punkcie w trójwymiarowej przestrzeni, gdzie osiami są: czerwony, zielony i niebieski. Dwa kolory to dwa punkty. Różnica między kolorami jest więc opisana przez dystans dzielący te dwa punkty w przestrzeni RGB.

Kolory jako punkty w przestrzeni 3D

diff = sqrt((C1R-C2R)2+(C1G-C2G)2+(C1B-C2B)2)

Ta technika jest bardzo prosta w realizacji i daje przyzwoite rezultaty. Porównywanie kolorów jest jednak zagadnieniem bardzo złożonym. Inne przestrzenie koloru niż RGB nadają się lepiej do tego zadania. Pod uwagę należy również brać sposób percepcji koloru przez człowieka (np. nasze oczy są bardziej wyczulone na różnice w odcieniach zieleni niż koloru niebieskiego). Trzymajmy się jednak prostego rozwiązania…

Naszym testowym obrazem będzie to zdjęcie* Ultra HD 8K: 7680x4320, 33.1Mpx (na potrzeby bloga je oczywiście zmniejszyłem by nie marnować transferu):

Obraz wejściowy dla badania różnicy koloru (zmniejszony dla bloga)

Oto metoda, która może np. wyszukać piksele R=253 G=129 B=84 (inaczej „różowy stanik”) i ustawić je na kolor biały (reszta stanie się czarna):

static void DetectColorWithGetSetPixel(Bitmap image, byte searchedR, byte searchedG, int searchedB, int tolerance)
{
    int toleranceSquared = tolerance * tolerance;

    for (int x = 0; x < image.Width; x++)
    {
        for (int y = 0; y < image.Height; y++)
        {
            Color pixel = image.GetPixel(x, y);

            int diffR = pixel.R - searchedR;
            int diffG = pixel.G - searchedG;
            int diffB = pixel.B - searchedB;

            int distance = diffR * diffR + diffG * diffG + diffB * diffB;

            image.SetPixel(x, y, distance > toleranceSquared ? Color.Black : Color.White);
        }
    }
}

Powyższy kod to nasza okropnie wolna baza porównawcza Get/SetPixel. Przy wywołaniu w taki sposób (parametry nazwana dla czytelności):

DetectColorWithGetSetPixel(image, searchedR: 253, searchedG: 129, searchedB: 255, tolerance: 84);

otrzymamy taki oto wynik:

Obraz wyjściowy dla badania różnicy koloru (zmniejszony dla bloga)

Rezultat jest całkiem ok ale czekanie na niego ponad 84300ms* to całkowita porażka.

Teraz rzuć okiem na tą metodę:

static unsafe void DetectColorWithUnsafe(Bitmap image, byte searchedR, byte searchedG, int searchedB, int tolerance)
{
    BitmapData imageData = image.LockBits(new Rectangle(0, 0, image.Width, image.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
    int bytesPerPixel = 3;

    byte* scan0 = (byte*)imageData.Scan0.ToPointer();
    int stride = imageData.Stride;

    byte unmatchingValue = 0;
    byte matchingValue = 255;
    int toleranceSquared = tolerance * tolerance;

    for (int y = 0; y < imageData.Height; y++)
    {
        byte* row = scan0 + (y * stride);

        for (int x = 0; x < imageData.Width; x++)
        {
            // Uwaga na rzeczywistą kolejność (BGR)!
            int bIndex = x * bytesPerPixel;
            int gIndex = bIndex + 1;
            int rIndex = bIndex + 2;

            byte pixelR = row[rIndex];
            byte pixelG = row[gIndex];
            byte pixelB = row[bIndex];

            int diffR = pixelR - searchedR;
            int diffG = pixelG - searchedG;
            int diffB = pixelB - searchedB;

            int distance = diffR * diffR + diffG * diffG + diffB * diffB;

            row[rIndex] = row[bIndex] = row[gIndex] = distance > toleranceSquared ? unmatchingValue : matchingValue;
        }
    }

    image.UnlockBits(imageData);
}

Robi dokładnie to samo ale wykonuje się tylko 230ms ponad 360 razy szybciej!

Kod ten używa metody Bitmap.LockBits, która jest oprawką na natywną funkcję GdipBitmapLockBits (GDI+, gdiplus.dll). LockBits tworzy tymczasowy bufor przechowujący informacje o pikselach w żądanym formacie (w naszym przypadku RGB, po 8 bitów na składową koloru). Wszelkie zmiany w tym buforze są kopiowane do bitmapy przy wywołaniu UnlockBits (dlatego zawsze należy używać LockBits i UnlockBits jako pary). Bitmap.LockBits zwraca obiekt BitmapData (namespace System.Drawing.Imaging), który posiada dwie interesujące właściwości: Scan0 i Stride. Scan0 zwraca adres danych pierwszego piksela. Stride to szerokość jednego rzędu pikseli (tzw. scan line) w bajtach (z opcjonalnym wypełnieniem tak by wartość była podzielna przez 4). 

Układ BitmapData

Zauważ, że nie używam odwołań do Math.Pow i Math.Sqrt by obliczyć dystans między kolorami. Pisanie takiego kodu:

double distance = Math.Sqrt(Math.Pow(pixelR - searchedR, 2) + Math.Pow(pixelG - searchedG, 2) + Math.Pow(pixelB - searchedB, 2));

do przetwarzania milionów pikseli do straszny pomysł. Taka linia uczyniła by naszą zoptymalizowaną metodę około 25 razy wolniejszą. Używanie Math.Pow z parametrami całkowitymi to czyste marnotrawstwo, nie trzeba też wyliczać pierwiastka kwadratowego by określić czy odległość mieści się w pewnej tolerancji.

Pokazana wcześniej metoda jest oznaczona słowem kluczowym unsafe. Pozwala ono programowi C# na użycie operacji wskaźnikowych. Niestety tryb unsafe ma istotne ograniczenia. Kod, który go używa musi być skompilowany z opcją \unsafe oraz musi być wykonywany w pełni zaufanym assembly.

Na szczęście istnieje metoda Marshal.Copy (z przestrzeni nazw System.Runtime.InteropServices), dzięki której można przenosić dane między zarządzaną a niezarządzana pamięcią. Możemy jej użyć do skopiowania danych obrazu do tablicy bajtów i manipulowania pikselami w bardzo efektywny sposób. Przeanalizuj tą metodę:

static void DetectColorWithMarshal(Bitmap image, byte searchedR, byte searchedG, int searchedB, int tolerance)
{        
    BitmapData imageData = image.LockBits(new Rectangle(0, 0, image.Width, image.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);

    byte[] imageBytes = new byte[Math.Abs(imageData.Stride) * image.Height];
    IntPtr scan0 = imageData.Scan0;

    Marshal.Copy(scan0, imageBytes, 0, imageBytes.Length);
  
    byte unmatchingValue = 0;
    byte matchingValue = 255;
    int toleranceSquared = tolerance * tolerance;

    for (int i = 0; i < imageBytes.Length; i += 3)
    {
        byte pixelB = imageBytes[i];
        byte pixelR = imageBytes[i + 2];
        byte pixelG = imageBytes[i + 1];

        int diffR = pixelR - searchedR;
        int diffG = pixelG - searchedG;
        int diffB = pixelB - searchedB;

        int distance = diffR * diffR + diffG * diffG + diffB * diffB;

        imageBytes[i] = imageBytes[i + 1] = imageBytes[i + 2] = distance > toleranceSquared ? unmatchingValue : matchingValue;
    }

    Marshal.Copy(imageBytes, 0, scan0, imageBytes.Length);

    image.UnlockBits(imageData);
}

Wykonuje się ona tylko 280ms, jest wiec jedynie odrobinę wolniejsza od wersji unsafe. Pod względem CPU kod jest oszczędny jednak zużywa więcej pamięci niż poprzednia metoda – prawie 100 megabajtów dla naszego testowego obrazu Ultra HD 8K w formacie RGB 24.

Jeśli chcesz uzyskać jeszcze większą prędkość obróbki obrazu możesz przetwarzać różne części obrazu równolegle. Musisz jednak wykonać nieco testów ponieważ dla małych obrazów koszt użycia wielu wątków może okazać się większy niż zysk z wykonywania równoległego. Poniższa metoda to przykład kodu, który używa 4 wątków do jednoczesnego procesowania 4 fragmentów obrazu. Na mojej maszynie daje to ok 30% wzrostu wydajności. Traktuj ten kod jako szybką wskazówkę, ten post jest już i tak zbyt długi…

static unsafe void DetectColorWithUnsafeParallel(Bitmap image, byte searchedR, byte searchedG, int searchedB, int tolerance)
{
    BitmapData imageData = image.LockBits(new Rectangle(0, 0, image.Width, image.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
    int bytesPerPixel = 3;

    byte* scan0 = (byte*)imageData.Scan0.ToPointer();
    int stride = imageData.Stride;

    byte unmatchingValue = 0;
    byte matchingValue = 255;
    int toleranceSquared = tolerance * tolerance;

    Task[] tasks = new Task[4];
    for (int i = 0; i < tasks.Length; i++)
    {
        int ii = i;
        tasks[i] = Task.Factory.StartNew(() =>
            {
                int minY = ii < 2 ? 0 : imageData.Height / 2;
                int maxY = ii < 2 ? imageData.Height / 2 : imageData.Height;

                int minX = ii % 2 == 0 ? 0 : imageData.Width / 2;
                int maxX = ii % 2 == 0 ? imageData.Width / 2 : imageData.Width;                        
                
                for (int y = minY; y < maxY; y++)
                {
                    byte* row = scan0 + (y * stride);

                    for (int x = minX; x < maxX; x++)
                    {
                        int bIndex = x * bytesPerPixel;
                        int gIndex = bIndex + 1;
                        int rIndex = bIndex + 2;

                        byte pixelR = row[rIndex];
                        byte pixelG = row[gIndex];
                        byte pixelB = row[bIndex];

                        int diffR = pixelR - searchedR;
                        int diffG = pixelG - searchedG;
                        int diffB = pixelB - searchedB;

                        int distance = diffR * diffR + diffG * diffG + diffB * diffB;

                        row[rIndex] = row[bIndex] = row[gIndex] = distance > toleranceSquared ? unmatchingValue : matchingValue;
                    }
                }
            });
    }

    Task.WaitAll(tasks);

    image.UnlockBits(imageData);
}

Oryginalnie miałem jakieś trójkąty i kwadraty jako ilustracje, ale modelki Victoria's Secret (źródło) są lepsze, co? :)

* Aplikacja konsolowa .NET 4 uruchamiana na laptopie MSI GE620 DX: Intel Core i5-2430M 2.40GHz (2 rdzenie, 4 wątki), 4GB DDR3 RAM, NVIDIA GT 555M 2GB DDR3, HDD 500GB 7200RPM, Windows 7 Home Premium x64.

Modyfikator ref dla typów referencyjnych i odrobina SOSu

Spójrz na poniższy kod i zastanów się jaka wartość zostanie wyświetlona na konsoli (pamiętaj, że string to typ referencyjny)?

using System;
               
class Program
{
    static void Test(string y)
    {
        y = "bbb";
    }

    static void Main()
    {
        string x = "aaa";
        Test(x);
        Console.WriteLine(x);
    }
}

Prawidłowa odpowiedź (aaa) nie jest wcale taka oczywista. Użytkownik zobaczy napis aaa, dlatego, że bez użycia modyfikatora ref, program napisany w C# przekazuje do metody kopię wartości parametru (dla typów wartościowych) lub kopię referencji (dla typów referencyjnych).

Gdy do parametru y w metodzie Test przypisywany jest nowy tekst, CLR nie modyfkuje tablicy znaków. Zamiast tego tworzy nowy string (więcej info tutaj) i przypisuje wskazanie do niego do zmiennej y. Zmienna y znajdująca się w metodzie Test jest jednak tylko kopią referencji do napisu wskazywanego przez zmienną x z metody Main. Skoro zmodyfikowana została jedynie kopia, to po wyjściu z metody, na konsole trafia pierwotny napis aaa.

By rzeczywiście zmienić tekst kryjący się pod zmienną x, użyj modyfikatora ref (musisz dodać go zarówno w deklaracji metody jak i jej wywołaniu – C# wymusza takie zachowanie by zwiększyć czytelność kodu):

using System;
               
class Program
{
    static void Test(ref string y)
    {
        y = "bbb";
    }

    static void Main()
    {
        string x = "aaa";
        Test(ref x);
        Console.WriteLine(x);
    }
}

Po takiej zmianie na konsole trafi napis bbb.

 

SOS

Sposób przekazywania parametrów do metody można zbadać za pomocą narzędzia SOS (Son of Strike). Posłużymy się poleceniem CLRStack -a, które wyświetli informacje o parametrach i zmiennych lokalnych na stosie kodu zarządzanego (jeśli nie wiesz jak używać SOS patrz tutaj i tutaj, jeśli dziwisz się skąd nazwa "Son of Strike" kliknij tu)...

Poniżej znajdują się rezultaty polecania CLRStack -a, wykonanego w momencie wejścia do metody Test.

Dla kodu bez modyfikatora ref:

!CLRStack -a
OS Thread Id: 0x176c (5996)
Child SP IP       Call Site
0031f114 00390104 Program.Test(System.String)
    PARAMETERS:
        y (0x0031f114) = 0x025cb948

0031f158 003900af Program.Main()
    LOCALS:
        0x0031f158 = 0x025cb948

0031f3c0 656721bb [GCFrame: 0031f3c0]

Dla kodu z modyfikatorem ref:

!CLRStack -a
OS Thread Id: 0x934 (2356)
Child SP IP       Call Site
001dee34 002f00f4 Program.Test(System.String ByRef)
    PARAMETERS:
        y (0x001dee34) = 0x001dee78

001dee78 002f00aa Program.Main()
    LOCALS:
        0x001dee78 = 0x027fb948

001df0ec 656721bb [GCFrame: 001df0ec]

Istotną różnicą widoczną na powyższych zrzutach jest wartość parametru y. W przypadku kodu bez modyfikatora ref jest to adres stringa aaa (0x025cb948), natomiast dla kodu z modyfikatorem ref, wartością parametru y jest adres zmiennej x z metody Main (0x001dee78)która wskazuje na string aaa.