Memory z funkcjami

Chyba nie pozostaje mi nic innego jak tłuc tematykę Javaslang w najbliższych dniach. Tego typu maratony mają tę zaletę, że można się dużo i szybko nauczyć. Dziś zapamiętywanie wyników działania funkcji. Jest to jeden z idiomów, które można zaimplementować samodzielnie, albo wykorzystać gotowe rozwiązanie.

Funkcja niezmienną jest

Przynajmniej funkcja, która jest czysta, czyli nie ma efektów ubocznych. Nie pisze po dysku lub bazie, nie wyrzuca wyjątków, nie komunikuje się ze światem zewnętrznym, w sposób zmieniający jego stan. Czasami jednak funkcja sięga do czegoś, gdzieś daleko, co też jest niezmienne. Czasami wykonuje bardzo złożone i czasochłonne obliczenia, które dla danych parametrów zawsze dadzą taki sam wynik (rzadki przypadek, ale się zdarza). W takim przypadku warto pomyśleć o zapamiętaniu wyniku w celu użycia go w przyszłości. Skoro będzie on taki sam dla danego zestawu parametrów wejściowych, to czemu by nie. Pozwoli to na zaoszczędzenie kilku… miliardów cykli procesora.

Mechanizm ten zazwyczaj nazywa się cachem. Sama memoryzacjaW, to rodzaj optymalizacji. Na siłę można to podciągnąć pod wzorzec projektowy.

Na czym to polega

Zacznijmy od prostej funkcji, którą chcemy poddać procedurze memoryzacji:

Listing 1. Funkcja wyjściowa

public void memorize() {
    Function1<Integer, String> f = i -> i + " is OK " + new Random().nextInt();
    System.out.println(f.apply(1));
    System.out.println(f.apply(1));
}

Jak widać, za każdym razem otrzymamy inny wynik. To znak, że funkcja została wywołana. Jeżeli twoja funkcja ma zwracać, za każdym razem inny wynik, to nie zapamiętuj wyników! Tu element losowy pełni tylko rolę markera.

Obudujmy naszą funkcję w mechanizm memoryzacji wyniku:

Listing 2. Dodanie memoryzacji

public void memorize() {
    Function1<Integer, String> f = i -> i + " is OK " + new Random().nextInt();
    Function1<Integer, String> mf = f.memoized();
    System.out.println(mf.apply(1));
    System.out.println(mf.apply(2));
    System.out.println(mf.apply(1));
}

Po uruchomieniu zobaczymy, że w przypadku wywołania z parametrem równym 1, wynik pierwszego został zapamiętany i później wyświetlony. Oznacza to, że funkcja f nie została wywołana. Jeszcze jeden przykład obrazujący co się dzieje:

Listing 2. Funkcja z oczekiwaniem na wynik

public void memorize() {
    Function1<Integer, String> f = i -> {
        try {
            Thread.sleep(5000L);
        } catch (InterruptedException e) {

        }
        return i + " is OK " + new Random().nextInt();
    };
    System.out.println(f.apply(1));
    System.out.println(f.apply(1));

    Function1<Integer, String> mf = f.memoized();
    System.out.println(mf.apply(1));
    System.out.println(mf.apply(2));
    System.out.println(mf.apply(1));
}

Pomiędzy dwoma ostatnimi wywołaniami nie ma odczuwalnego opóźnienia.

Jak to działa i armaci

Metoda memorize zwraca nam funkcję wyposażoną w wewnętrzny mechanizm pamięci podręcznej. Jest to prosta mapa, do której dostęp jest synchronizowany. Gdy po raz pierwszy wywołujemy funkcję z danym parametrem, wynik jest zapamiętywany w mapie. Kolejne wywołanie pobierze już obliczony wynik.

Podsumowanie

Mechanizm ten jest znany od dawna i implementowany jako standardowy element w językach funkcyjnych. Choć nie zawsze, bo np. erlang nie ma tego mechanizmu. Zanim jednak hura optymistycznie ruszymy przepisywać nasz kod, należy zwrócić uwagę na dwa zagrożenia.

Pierwszym z nich jest brak mechanizmu unieważniania pamięci podręcznej. Zatem możemy zapomnieć o użyciu tego rozwiązania jako rodzaju cacha wyników z bazy danych. Chyba że nasze rekordy się nie zmieniają. Drugim, znacznie poważniejszym, jest możliwość doprowadzenia do zapełnienia pamięci. Wyobraźmy sobie funkcję, która jako parametr przyjmuje duży obiekt. Zwraca też duży obiekt. Obiekt wejściowy ma błędnie zaimplementowane hashCode i equlas lub jest ich wiele, ale mają w teorii krótki czas życia. W momencie, gdy zostaną zapamiętane to, zamiast zostać usunięte przez GC, będą wisiały w mapie, a my będziemy zastanawiać się, dlaczego serwerowi kończy się pamięć.

3 myśli na temat “Memory z funkcjami

  1. Co do przepełnienia pamięci, mapa nie powinna zostać utworzona z użyciem WeakReference? Rozwiązałoby to ten problem?

  2. No nie do końca. Ponieważ wtedy tracisz tak naprawdę całą zaletę wynikającą z tego mechanizmu. Wystarczy, że:

    public String someCode(){
       MyObject val = mem.apply(arg);
       return val.toString();
    }

    mem.apply przy pierwszym wywołaniu someCode wylicza wartość val i zapisuje w WeakMap. Co stanie się przy drugim wywołaniu?

    Jeżeli pomiędzy wywołaniami nie było GC, to sprawa jest prosta, obiekt wraca do życia.
    Jeżeli pomiędzy wywołaniami było GC, to trzeba powtórzyć wszystkie obliczenia, bo val zakończyło życie przy wyjściu z metody i obiekt został usunięty.

    Kolejny problem. Jeżeli wynikiem obliczeń jest null, to czy w mapie masz obiekt „żywy”, czy też „martwy”? Czy należy powtórzyć obliczenia czy też nie? W przypadku zwykłej mapy nie ma tego problemu, bo nie musimy sprawdzać wartości, a jedynie pobrać po kluczu.

Napisz odpowiedź

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax