sobota, stycznia 21, 2017

Nie inicjalizuj rozmiaru kolekcji...

Jednym z code smellsów na które zawsze źle reaguję jest deklarowanie rozmiaru kolekcji takiej jak lista czy mapa w trakcie tworzenia obiektu...

Czemu?

Bo wkład na wydajność takich zmian jest mniej niż nikły, a zaciemnia kod.

Spójrzmy na sytuację z ArrayLista'ą.

Teoretycznie sama praca z ArrayList powinno wykonać do 4 razy szybciej w momencie gdy zadeklarujemy capacity ArrayList.
W najgorszym przypadku przy rozszerzaniu listy (startujemy od 10 elementów i za każdym razem rośniemy do 1.5 rozmiaru) możemy mieć srednio do 4 operacje zapisu na każdy element.
Przy ustawieniu capacity tych operacji powinno być dokładnie 1 na element.

W rzeczywistości okazuje się, że i tak więcej czasu spędzimy na przygotowywaniu elementów, które włożymy do listy i na operacjach w samej liście.
Gdy testowałem wkładanie kolejnych liczb różnica wynosiła około 25% na korzyść listy ze znanym capacity.

Nadal można twierdzić, że to jakiś zysk, jednak jeśli spojrzymy na kod to zwykle okazuje się, że taka operacja na liście jest tylko przygrywką do jakichś bardziej skomplikowanych operacji, a sama metoda nie jest wykorzystywana non-stop.
Przez co nikły zysk i tak maleje.

Z mapami jest jeszcze gorzej.

Po pierwsze w razie tworzenia HashMap z podaniem jej capacity rzadko kto podaje ułamek używany do wyliczenia progu po którym następuje zwiększenie liczby kubełków.
Przez to przy domyślnym ułamku wynoszącym 0.75 i tak mamy gwarantowane 1 rozszerzenie HashMap, co sprawia, że mamy przeciętnie 1.75 zapisu na element.

W przypadku tworzenia HashMap bez capacity zaczynamy od 16 kubełków, a po przekroczeniu thresholdu (czyli 12 elementów) zwiększamy rozmiar o 2 razy i tak dalej.

Teoretycznie liczba zapisów na 1 element w takim przypadku waha się od 2 do 3 na element, średnio to jakieś 2.4-2.5 zapisu na element.

I znów zwykle stworzenie klucza może trwać więcej niż te kilkukrotne zapisy.

Moje testy gdy kluczem są kolejne Integer'y pokazują, że w przypadku HashMap'y stworzonej bez capacity w wkładaniu elementów potrzebna góra 5% więcej czasu.

Tutaj czasem ktoś może się bronić, że jednak za każdym razem w momencie rozszerzania trzeba liczyć hashCode, a to jest dość czasochłonna operacja... co jest prawdą przy źle zaimplementowanych metodach hashCode, szybkie zajrzenie do JDK wskazuje, że dobrym zwyczajem w przypadku kosztownych hashCode'ów jest liczenie hashCode tylko raz, a później używanie zakitranej wartości.
Zresztą w przypadku elementów trzymanych w HashMap i tak musimy mieć niezmienny hashCode...

Czyli znów teoretycznie powinno być tak na oko 2 razy szybciej, a zwykle jest tylko o parę procent szybciej.

Które to parę procent rozpłynie się w reszcie operacji, które wykonujemy w okolicach prac z mapą.

Można w tym momencie bronić użycia rozmiarów jako czegoś co nie szkodzi, a może pomóc.
Niby tak, ale jednak gdy czytamy kod chwilę trzeba spędzić nad zastanowieniem się co to za wartość jest przekazywana do konstruktora i po co, oraz sprawdzić czy np. nie będzie ujemna, albo null'em.
Dodatkowo może się zdarzyć, że ta liczba rzeczywiście będzie ujemna i może pojawić się ciekawa klasa problemów ;-)

Stąd lepiej unikać przekazywania rozmiaru kolekcji i robić to tylko wtedy gdy mamy za sobą już inne optymalizacje i da nam to coś więcej niż zaciemnienie kodu.


Podobne postybeta
Java 32 bit vs. Java 64 bit
Pythonowe formatowanie kodu ma jednak swoje zalety ;-)
Algorytm ;-)
Lecę do Stanów... i co z tego? ;-)
Transhumanizm [długo i nudno ;-)]