Nerešena zagonetka performansi

Način na koji rade dinamičke Java kolekcije kao što su ArrayList ili ByteOutputArrayStream je sledeći:

To se može predstaviti na ovaj način:

Ono što mi je zasmetalo je to što se prilikom proširivanja niza sadržaj kopira više puta. Tako se ovde, na primer, inicijalni plavi deo kopira tri puta; sledeći ljubičasti dva i tako redom. Naravno, svaki put pri proširivanju se kopira ceo prethodni niz, ali ostaje činjenica da se jedan te isti memorijski sadržaj prenosi više puta sa jednog na drugo mesto.

Pomislio sam da možda postoji bolje rešenje od ovoga, koje neće prenositi blokove memorije pri proširenju. On bi radio ovako:

Nešto, dakle, ovako:

Sva memorija se sada kopira samo jednom, na kraju, kada se zatraži sadržaj kolekcije.

Po svemu sudeći, drugi način bi trebalo da daje bolje performanse. Zar ne?

Misterija

Kada sam pustio JMH microbenchmark koji poredi drugi pristup sa prvim (oličen u klasi ByteOutputArrayStream), sačekalo me je iznenađenje. Drugi način je uvek davao lošije rezultate! Razlika nije dramatična, ali nije ni zanemarljiva. To nisam očekivao: u najgorem slučaju performanse bi trebalo da su bar iste.

Vreme je za analizu.

Jasno je da je drugi način kompleksniji, jer se barata sa nizom nizova. Ovaj pomoćni niz se takođe alocira na početku. Prva optimizacija je da se pomoćni niz kreira tek pri prvom proširenju, što znači da to tog trenutka oba pristupa rade isto.

Međutim, drugi algoritam opet degradira posle prvog proširenja. Preciznije, prvi algoritam nije pokazivao isti stepen degradacije usled proširenja niza! Onda sam uočio sledeće u benchmarku prvog algoritma:

# Warmup Iteration   1: 3296444.108 ops/s
# Warmup Iteration   2: 2861235.712 ops/s
# Warmup Iteration   3: 4909462.444 ops/s
# Warmup Iteration   4: 4969418.622 ops/s
# Warmup Iteration   5: 5009353.033 ops/s

Druga sesija “zagrevanja” je magična - JVM primenjuje optimizaciju i drastično ubrzava kod! To se ne dešava u drugom algoritmu. Optimizacija koju JVM primenjuje je rekompajliranje koda na najviši nivo, nivo 4. Inače, postoji JVM opcija koja ispisuje informacije o kompajliranju: -XX:+PrintCompilation.

Razlika dva algoritma sada je samo u načinu kako metoda za proširivanje radi. Probao sam da promenim kod tako da okinem isti stepen optimizacije JVM, ali je to davalo polovične rezultate: za jedne dužine niza drugi algoritam radi bolje, dok za druge radi sporije. Nisam uspeo da dođem do ujednačeno boljih rezultata za drugi algoritam.

Hibridno rešenje

Iako na papiru stvari izgledaju da bi trebalo da se ponašaju drugačije, u stvarnosti se to ne dešava. Optimizacija koju radi JVM je tolika da dodatna kopiranja pri proširenju niza u prvom slučaju ne utiču na performanse. Zaista, te prve veličine memorija pri prvi proširivanjima su toliko male, da se benefiti drugog algoritma izgube u optimizaciji JVM.

Šta nam to govori? Da možda možemo da pribegnemo hibridnom rešenju: prvih nekoliko proširenja uradimo na način kao u prvom algoritmu, a tek kasnije pređemo na drugi algoritam. Kada kasnije? Kada veličina blokova koji se kopiraju bude tolika da potre optimizaciju JVMa.

Vreme je za pogađanje: kolika je veličina niza posle koje ima smisla prebaciti se na drugi algoritam? Dakle? 256 bajtova? 1024? 10 KB? 512 KB?

Parti misterija

Pokazuje se da drugi algoritam ima smisla tek… mnogo kasnije. Negde oko 128 MB. Kako sada pa to? Pa… i ovo ima smisla (mada je lako praviti se generalom posle bitke): sa porastom dužine niza, broj proširivanja se smanjuje kako raste unutrašnji niz, te je i sam broj kopiranja mali. Kada konačna dužina niza pređe 128 MB, drugi algoritam krene da ispoljava svoje prednosti. Nažalost, i dalje ne sa ujednačenim performansama:

128 MB
fastBuffer    157810688  thrpt    2  126.644          ops/min
outputStream  157810688  thrpt    2  124.815          ops/min
256 MB
fastBuffer    268435456  thrpt    2  84.519          ops/min
outputStream  268435456  thrpt    2  55.932          ops/min
400 MB
fastBuffer    419430400  thrpt    2  35.836          ops/min
outputStream  419430400  thrpt    2  48.079          ops/min
512 MB
fastBuffer    536870912  thrpt    2  41.725          ops/min
outputStream  536870912  thrpt    2  28.819          ops/min

Šta je zaključak: da drugi algoritam možda i nema smisla na modernoj JVM.

Neočekivano.

🧧
Nisam definisan svojim stavovima. Stavove usvajamo, menjamo, nadograđujemo, ali oni ne čine nas same. Manje je važno da li se slažemo,
koliko da se razumemo.
> ČASTI KAFU <