ArrayList vs LinkedList - dziwne wyniki testów

0

Ostatnio przeczytałem ten oto artykuł: http://www.programcreek.com/2013/03/arraylist-vs-linkedlist-vs-vector/ . Wykres słupkowy, który pojawia się na końcu wydaje się być sensowny kiedy przyjrzymy się wewnętrznej implementacji tych struktur. Niemniej jednak postanowiłem sam skonfrontować wydajność tych kolekcji i niektóre wyniki trochę mnie zadziwiły.

Po pierwsze ArrayList wychodzi mi na testach zawsze lepiej niż LinkedList.
Po drugie czasy uzyskiwane przez LinkedList podczas dodawania elementów są zupełnie kosmiczno-randomowe.

Zdaję sobie sprawę, że nie zapewniłem tym testom laboratoryjnych warunków. Ale postarałem się jak mogłem aby były jak najbardziej rzetelne. Wyłączyłem wszystko co mogłoby działać w tle i zakłócać wyniki (w miarę możliwości). Testy były powtarzane setki razy dla uśrednienia czasów. Ponadto testy dla metody add(Object o) powtórzyłem następnego dnia, ale mimo to wyniki były tak samo dziwne. Mógłby mi ktoś wytłumaczyć dlaczego tak to wygląda?

user image

user image

user image

user image

0

W przypadku add dorzuć jeszcze analizę pamięci. Zapewne GC sobie śmiga gdzieś po drodze...

0

@Koziołek Tylko nie bardzo wiem jak miałbym tą analizę zrobić - skąd wziąć dane o pamięci? Czy liczyć tylko wywołania GC jakoś za pomocą finalize? Poza tym, teoretycznie GC powinien częściej się udzielać przy ArrayList co jeszcze bardziej przemawia na korzyść tej kolekcji.

0

Czemu częściej przy AL? LL pod spodem tworzy jednak dodatkowy obiekt opakowujący. AL ma tylko tablicę, którą trzeba utylizować raz na pewien czas (samą tablicę, ale nie zawartość). Do analizy gc można użyć http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/management/MemoryPoolMXBean.html

0

Tak, LL tworzy obiekty opakowujące i może mieć to wpływ na zużycie pamięci ale GC interesują tylko nieużytki, a podczas dodawania obiektów do LL, raczej żadne nie pozostają.

Zresztą zrobiłem testy dla metody add z wykorzystaniem MemoryMXBean i przy dodawaniu 500 tys elementów, AL potrzebował ok. 14,5 MB, a LL ok. 5,4 MB. Sprawdziłem jeszcze kontrolnie dla 1mln i 2mln i AL zawsze potrzebuje sporo więcej pamięci.
Więc tym bardziej nie rozumiem dlaczego LL wypada tak tragicznie w tym teście?

[edit]
Teraz sprawdziłem i sprawa wygląda jednak nieco inaczej. Dla 500 tys. el. AL zużywa ok 3 razy tyle pamięci co LL, ale dla 2 mln. el. już tylko 2 razy więcej, a dla 4 mln mniej więcej po równo.

0

AL zużywa więcej? A odpalałeś Full GC przed pomiarami?

Tak, LL tworzy obiekty opakowujące i może mieć to wpływ na zużycie pamięci ale GC interesują tylko nieużytki, a podczas dodawania obiektów do LL, raczej żadne nie pozostają.

GC skanuje wszystkie obiekty, ponadto w każdej sensownej JVMce są generacje obiektów i przy GC obiekty są przenoszone pomiędzy generacjami.

Tablica to jeden obiekt, więc przy użyciu AL jest niewiele obiektów do skanowania. Konkretnie to GC najpierw sprawdza obiekty ze świeżych generacji, a potem z mniej świeżych. Dlatego przy małych GC skanowane są tylko świeże obiekty, a dopiero przy Full GC skanowane jest wszystko.

0

@Wibowit Możliwe, że jest tak jak mówisz - ja się jakoś bardziej nigdy nie zagłębiałem w działanie JVM. Jak odpalić full GC ?

Zrobiłem jeszcze raz ten test z metodą add na innym kompie - notebooku. Wyszedł mniej kosmiczny, ale nadal AL wygrywa. Oto wyniki:

user image

user image

Nie wiem, może jakoś źle robię te testy? Kod wygląda tak (dla reszty metod jest analogiczny) :

                MemoryMXBean mBean = ManagementFactory.getMemoryMXBean();
		double memUsageStart, memUsageStop;
		double memUsageAL, memUsageLL;
		int k = 1000000;
		ArrayList<Integer> arrayList = new ArrayList<>();
		LinkedList<Integer> linkedList = new LinkedList<>();
		double timeStart, timeStop, timeAL, timeLL;
		DecimalFormat format = new DecimalFormat();
		
		format.setMinimumFractionDigits(2);
		memUsageAL = memUsageLL = 0;
		timeAL = timeLL = 0;
		int j =0;
		
		for(j =1; j<100; j++)
		{
			arrayList.clear();
			linkedList.clear();
			
			memUsageStart = mBean.getHeapMemoryUsage().getUsed();
			timeStart = System.currentTimeMillis();
			for(int i=0; i<k; i++)
			{
				arrayList.add(i);
			}
			timeStop = System.currentTimeMillis();
			memUsageStop = mBean.getHeapMemoryUsage().getUsed();
			timeAL += (timeStop-timeStart);
			
			if(j==1)
			{
				memUsageAL = (memUsageStop - memUsageStart);
				memUsageAL /= 1000000.0;
			}
			
			memUsageStart = mBean.getHeapMemoryUsage().getUsed();
			timeStart = System.currentTimeMillis();
			for(int i=0; i<k; i++)
			{
				linkedList.add(i);
			}
			timeStop = System.currentTimeMillis();
			memUsageStop = mBean.getHeapMemoryUsage().getUsed();
			timeLL += (timeStop-timeStart);
			
			if(j == 1)
			{
				memUsageLL = (memUsageStop - memUsageStart);
				memUsageLL /= 1000000.0;
			}
		}
		
		j--;
		System.out.println("ArrayList: ADD : " + format.format(timeAL/j)
				+ "\nMemUsage " + format.format(memUsageAL) + " MB \n");
		
		
		System.out.println("LinkedList: ADD : " + format.format(timeLL/j)
				+ "\nMemUsage: " + format.format(memUsageLL) + " MB \n");
0

jmap -histo:live wymusza Full GC. Nie pamiętam czy da się to wymusić z wewnątrz kodu Javowego. Możliwe że za pomocą jakiegoś JMX beana by się dało, ale uleciało mi to z głowy.

1

Testy są niemiarodajne ponieważ jako elementów list używasz malutkich i częściowo cache'owanych obiektów Integer. Są one nawet mniejsze od węzłów LL, więc niemal wcale nie wpływają na zajętość oraz fragmentację pamięci.
W takiej sytuacji AL będzie zawsze wygrywać. LL wymaga przy każdym dodawaniu nowego elementu tworzenia nowego węzła, a to oznacza jednostkowo czasochłonną operację new. AL również wymaga przydziałów pamięci, ale są one dużo rzadziej żądane, a pojedynczy koszt przydziału obiektu dużego i małego jest podobny gdy jest dużo pamięci wolnej. Dodatkowo w wielu komputerach zerowanie bloku pamięci potrzebne do new może być operacją sprzętową nie wymagającą aktywnego udziału CPU (pętli zerującej). Dlatego zmiany rozmiaru wewnętrznej tablicy AL są dużo mniej kosztowne niż mogłoby się to wydawać.
Do testów powinieneś użyć dużej puli istniejących oraz dla symulacji tworzonych i niszczonych obiektów zawierających co najmniej kilka ośmiobajtowych pól. Tak jest najłatwiej zasymulować dużą fragmentację pamięci. Dodatkowo zajętość pamięci powinna przed rozpoczęciem testów wynieść przynajmniej 80% maksymalnej pamięci możliwej do przydzielenia przez JVM.

1 użytkowników online, w tym zalogowanych: 0, gości: 1