Cześć!

Ostatnie trzy maile było dla jaroszy. Rzodkieweczka, jarmuż i rukola. Dzisiaj będzie mięśnie, więc można zapinać pasy.

Chciałbym dzisiaj pokazać Ci prostą (?) praktykę programistyczną, która może Ci się przydać do szybkiej optymalizacji kodu. Praktyka ta nazywa się Memoizacja - z ang. “memoization”. Praktyka ta pochodzi z języka funkcyjnego i służy do zapamiętywania wyniku funkcji. Chodzi o to, żeby właściwy kod funkcji wykonał sie tylko raz, a potem wynik był zwracany z cache.

Przykład będzie w C#, ale powinien być zrozumiały jeśli preferujesz inny.

Utworzymy sobie statyczną klasę, która posiada “extension method” Memoize. Dzięki temu będziemy w stanie wywoływać ją wygodniej dla wybranej przez nas funkcji.

Metoda Memoize jako parametr przyjmuje funkcję jednoparametrową (o typie TInput), zwraca również funkcję. Tak jak opisałem powyżej - ideą jest, że przekazujemy funkcję, która wykonuje jakieś obliczenia i zwracamy jej opakowaną o cache wersję.

public static class Memoizer
    {
        public static Func<TInput, TResult> Memoize<TInput, TResult>(this Func<TInput, TResult> func)
        {
            // utwórz cache
            var memo = new Dictionary<TInput, TResult>();

            // opakuj funkcję o cache
            return input =>
            {
                // sprawdź czy w cache znajujde się już wynik 
                // dla zadanego parametru wejściowego
                if (memo.TryGetValue(input, out var fromMemo))
                    // jeśli tak - zwróc z cache
                    return fromMemo;

                // jeśli nie wywołaj funkcję
                var result = func(input);

                // dodaj do cache
                memo.Add(input, result);

                // zwróć wynik
                return result;
            };
        }
    }

Korzystamy tutaj z zakresów funkcji (closure). Definiujemy sobie słownik (zmienna memo), w którym będziemy zapamiętywać wyniki funkcji.

Następnie generujemy metodę opakowującą, która będzie sprawdzała czy dla zadanego parametru wejściowego jest już wynik w cache. Jeśli jest to zwraca wynik z cache i nie wywołuje samej funkcji. Jeśli nie ma to wywołuje funkcje, dodaje wynik do cache i zwraca wynik.

To co jest ważne to, że funkcja, którą będziemy “memoizować” powinna być determistyczna i nie powodować efektów ubocznych. Co to znaczy w praktyce? Znaczy to, że dla zadanego parametru wejściowego zawsze zwróci ten sam wynik i nie będzie dokonywać żadnych zmian. Np. dla zadanego kodu pocztowego zawsze wiadomo, że to będzie to miasto. Dany pesel odpowiada konkretnej osobie itd. Taką metodę nazywamy również “funkcją wyższego rzędu” (Higher Order Function).

Bardziej życiowym przykładem mogą być np. wolne operacje ale deterministyczne jak np. mechanizm refleksji. Memoizacja mogłaby się nam przydać np. do sprawdzenia czy dany typ ma jakiś konkretny atrybut (annotację).

Zdefiniujmy sobie metodę do weryfikacji czy dany typ ma dany attrybut jako:

Func<Type, Type, bool> hasAttribute =
    (type, attributeType) => type.GetCustomAttributes(attributeType, true).Any();

Niestety tej metody nie możemy zmemoizować w obecnej formie bo nasza metoda zakłada, że funkcja będzie miała jeden parametr wejściowy. Powyższa ma dwa.

Musimy tę funkcję zwinąć. Jak tego dokonać? Cechą funkcji wyższego rzędu jest to, że da się je komponować. Na przykład następująco:

Func<Type, bool> hasSomeCustomAttribute = 
    type => hasAttribute(type, typeof(SomeCustomAttribute));

Tworzymy sobie dodatkową funkcję, która jako typ atrybutu przyjmuje konkretny parametr - odpowiadający wybranego przez nas typowi attrybutu.

Taką funkcję możemy już zmemoizować poprzez:

Func<Type, bool> hasSomeCustomAttributeMemo = hasSomeCustomAttribute.Memoize();

Jeśli teraz ją użyjemy kilkukrotnie, to dzięki memoizacji dla danego typu attrybutu funkcja hasAttribute zostanie wywołana tylko raz.

Kiedy warto używać memoizacji? Szczególnie tam gdzie mamy wiele razy wywoływany ten sam kod w ramach jednej operacji. Jeżeli ten kod jest deterministyczny to można bardzo dużo uciąć z czasu wykonania. Oczywiście podstawą jest to, żeby ten kod był deterministyczny. Można też użyć to do np. cache w Redis, jeżeli go zinwalidujemy to po prostu pobierze nam nową wartość. Podstawa optymalizacji to zacząć od operacji wykonywanych bardzo często. Jest to prosta matematyka, jeśli na operacji wykonywanej 1000 razy urwiemy 0.1 sekundy na każdym wywołaniu to zyskamy 100 sekund. Jeśli operacja jest wykonywana 10 razy i zyskamy na każdym sekundę, to w sumie zyskamy 10 sekund.

Jest to bardzo prosta technika ale potrafi przynieść bardzo wymierne efekty. Dodatkowo jest przykładem, że programowanie funkcyjne wcale nie jest takie abstrakcyjne, ale też praktyczne.

Na koniec jeszcze garść linków. Tym razem w ciągu tygodnia wypuściłem dwa posty:

• kod do powyższego przykładu - https://github.com/oskardudycz/Memoization
• Jaka jest różnica między komendą a zdarzeniem - https://event-driven.io/en/whats_the_difference_between_event_and_command/ - sprawa wcale nie jest taka oczywista jaka się wydaje, podrążyłem temat dosyć mocno
• Jak zrobić macierz testów dla XUnit - https://event-driven.io/en/how_to_setup_a_test_matrix_in_xunit/ - czyli jak wywołać wszystkie testy kilka razy ze zmienioną konfiguracją (np. z innym serializerem). Jest to post zainpirowany wprost moją walką w Marten z System.Text.Json. Zakończoną wreszcie sukcesem!
• Nowe ArchitectureWeekly z mocną sekcją o bezpieczeństwie - https://github.com/oskardudycz/ArchitectureWeekly#22nd-february-2021

Mam nadzieje, że pomogłem!

Pozdrawiam Oskar