Wpadka z mapą

„Będę … grał w gry” tak mi się skojarzyło, jak napisałem słowo „Będę”, na początku tego wpisu, nie wiem, może chodzi o ten popularny kiedyś i wcale nie śmieszny filmik, może :). A zatem, będę dzisiaj pisał na temat najbardziej popularnej implementacji interfejsu java.util.Map mianowicie java.util.HashMap. Każdy lekko zaawansowany w programowaniu w Java w zasadzie zakończy czytanie w tym miejscu, bo co można jeszcze o mapie więcej powiedzieć, poza tym, że jest i działa. Zachęcam jednak do poświęcenia odrobiny uwagi, w zamian oferuję co następuje … po pierwsze doznanie małego szoku, jak można było tak zepsuć implementację tak ważnej klasy. Po drugie, jak to mogło (to zepsucie) tak długo trwać (do dzisiaj?). Po trzecie, szok kolejny, że od dawna to dosyć powszechnie wiadomo. No i po czwarte, że dzięki niejakiemu XenoAmess i jego zmianom w wersji 19 Javy, pojawiła się szansa na łatwą poprawę wydajności naszych aplikacji a w zasadzie sprytny programista może to zrobić w wersji w sumie dowolnej.

Zaczynamy od prostego kodu, mamy znaną liczbę elementów, i chcemy ją umieścić na mapie w celu np. optymalizacji wyszukiwania po pewnym kluczu. Np:

Oczywiście ten kod nie będzie tak wydajny jakby mógł być. Nie określono początkowego rozmiaru mapy więc będzie ona miała rozmiar domyślny, aktualnie równy 16. Czyli przy dodawaniu dużo większej (niż 16) ilości elementów, mapa będzie wielokrotnie zmieniała swoją pojemność żeby je pomieścić, a zaznaczmy, że operacja ta jest w aktualnej implementacji bardzo kosztowna. W tym przypadku mapa będzie zmieniała rozmiary z 16 na 32 potem 64, 128, 256, 512, 1024 (aktualna implementacja zakłada wielkości jako potęgi 2) … czyli 6 razy (w rzeczywistości jeszcze więcej razy, ale o tym dalej). Można by sądzić, że oprócz produkowania coraz to większych tablic (mapa używa właśnie tablic w swojej wewnętrznej implementacji) które GC będzie musiał od-śmiecić nic kosztownego tu się nie dzieje, jest jednak inaczej. Algorytm indeksowania wewnętrznej tablicy oparty jest o jej rozmiar, za każdym razem gdy mapa tworzy nową większą tablicę, musi na nowo przepisać wszystkie istniejące już elementy w nowe miejsca, nowej tablicy, wyliczając ich nowe indeksy. Niestety jest tam po prostu pętla która to „mozolnie” robi, a nie coś w rodzaju szybkiego czy wręcz natywnego kopiowania tablicy jak np. w implementacji ArrayList, nie, tu tak się nie da. Ale nie o tym chciałem pisać. Zakładam, że w takiej sytuacji programista wie, że należy pisać tak:

Teraz jest dużo lepiej. Skoro mapa zna zwój rozmiar początkowy to od razu zostanie utworzona taka wewnętrzna tablica aby zmieściła wszystkie elementy z listy. No właśnie nie! Utworzona zostanie mapa o rozmiarze 1024 (najbliższa potęga 2), to oczywiste, ale przy dodawaniu 769 go elementu wewnętrzna tablica w mapie zostanie … zwiększona dwukrotnie z rozmiaru 1024 do rozmiaru 2048. Uff. Dlaczego? Dlatego, że taka jest, niefartowna dosyć implementacja. Tłumacząc to w prosty sposób, twórcy w celu zapewnienia późniejszej wydajności mapy zakładają pewien wewnętrzny zapas, reprezentuje go parametr loadFactor, jego domyślna wartość to 0.75. To znaczy, że za każdym razem jak mapa przekroczy 75% zajętości swojego rozmiaru, to się zwiększy dwukrotnie, z tym nie dyskutujemy. Dlaczego twórcy implementacji nie zaimplementowali konstruktora przyjmującego rozmiar mapy tak aby uwzględniał loadFactor i tworzył rozmiar wewnętrznej tablicy tak, aby mapa nie musiała jej potem zwiększać? Nie wiem. Ale znam konsekwencje. Prawie wszystkie poprawne użycia mapy (z podaniem rozmiaru) w całym kodzie większości aplikacji na świecie powodują niezerowy problem wydajnościowy, tracimy czas, tracimy pamięć, defragmentujemy ją, męczymy GC. Co zatem robić? Od wersji 19tej Java’y, w klasie HashMap pojawiła się metoda statyczna:

HashMap.newHashMap(int numMappings)

Metoda ta tworzy nam nową mapę w dobry sposób (podziękowania dla XenoAmess). Co ciekawe ta złożona poprawka zawiera także zmiany w kilkudziesięciu klasach JDK tak, aby zamiast konstruktora wywołać tą metodę. Prawdopodobnie uznano, że te miejsca są krytyczne dla wydajności. Przypominam Java 19 … trochę jednak późno. Dlaczego nie poprawiono działania konstruktora a dodano statyczną metodę fabrykującą, nie wiem. Kompatybilność? Może. Wiem, że twórcy innych bibliotek jak np. guava walczyli z tematem odrobinę wcześniej, i tak w guava mamy

Maps.newHashMapWithExpectedSize(int size)

gdzie zastosowano dokładnie taką samą metodę naprawczą jak w HashMap.newHashMap. Reasumując, jak używasz Java 19+ newHashMap() cię wyzwoli, jak nie, to może wyzwoli cię guava albo … no cóż może manipulacje wartością loadFactor (nie polecam), a może tak:

czuć lekko desperacją, ale przynajmniej jest wydajnie. Kończąc, pozdrawiam najpierw autorów implementacji, bez złośliwości, nikt nie jest idealny, no i osoby które dobrnęły do końca i mam nadzieję siadają właśnie to poprawiania tych tysięcy miejsc … uff, nie zazdroszczę.