Wie groß ist eigentlich ein HashMap?

[fatfox]

Hallo alle,

Ich möchte 36 millionen Einträge in eine ArrayList von HashMap(c.a. 15,000 Stück) eingeben. Aber Warum nach ein paar Millionen Einträge Eingaben ist mein Computer unglaublich langsam geworden?

Meine <Key> type ist Short und <Value> type ist Float. Ich benutze put(key, value) Funktion.

Ich denke: 36,000,000 × (2 + 4) ÷1024÷1024 = 205 MB, also 205MB Ram muss reichen, aber warum im Real ist es anders?


Vielen Dank!

 

[faetzminator]

Weil du da keine primitiven Datentypen nutzen kannst. Mit Millionen von Referenzen hat man irgendwann den Speicher voll. Schreib dir etwas mit Arrays o.ä., bei denen du primitive Datentypen nutzen kannst.

 

[SlaterB]

wenn du es genau wissen willst dann bietet Runtime.getRuntime() Methoden zum Java-Speicher,
teste zunächst z.B. ein short[] im Vergleich zu einem Short[]

selbst wenn man Objekte verwenden muss, kann es sich schon lohnen, die 30.000 oder 60.000 möglichen Werte zu cachen und mehrfach zu verwenden,
jedes Objekt ist eine Referenz von 4 Byte + dem Objekt selber, ein Short vielleicht 20 Byte oder so, testen

Langsamheit ist auch eher 100% CPU-Last als irgendwas mit Speicher?

 

[Landei]

Wenn du collectionartige Klassen willst, die mit Primitiven arbeiten, schau dir mal Trove an.

 

[fatfox]

Danke alle! Der "Short" ist so groß habe ich gar nicht gewusst! ( ° △ °|||)︴

To Landei: der Trove sieht sehr sehr gut aus, aber irgendwie weiß ich gar nicht, wo und wie ich das anfangan soll....Gibt es irgendwo ein Tutorial?

 

[Landei]

Schau einfach in die JavaDoc. Wenn du z.B. eine Map von short nach float brauchst, müsste das TShortFloatHashMap sein. Das ist dann - zumindest von der Bedienung her - eine 1:1 "Übersetzung" des Map-Interfaces in Primitive, also überall wo bei Map<K,V> ein K steht, steht hier short, und anstatt V eben float, z.B. wird aus [c]V get(K key)[/c] ein [c]float get(short key)[/c].

 

[fatfox]

Schau einfach in die JavaDoc. Wenn du z.B. eine Map von short nach float brauchst, müsste das TShortFloatHashMap sein. Das ist dann - zumindest von der Bedienung her - eine 1:1 "Übersetzung" des Map-Interfaces in Primitive, also überall wo bei Map<K,V> ein K steht, steht hier short, und anstatt V eben float, z.B. wird aus [c]V get(K key)[/c] ein [c]float get(short key)[/c].

Cool!!! Der TShortFloatHashMap funktioniert!!! und ich kann jetzt alle 36 millionen Einträge eingeben.

Aber es ist einbisschen komisch, weil die TShortFloatHashMap trotzdem c.a. 1.4 GB Ram braucht.

Nach der Hinweise von SlaterB ist der Object so groß:

jedes Objekt ist eine Referenz von 4 Byte + dem Objekt selber

[36000000 × ( 2 + 4 ) + ( 15000 × 4 ) ] ÷ 1024 ÷ 1024 + 15000= 206 MB (short ist 2 byte, float ist 4 byte; Referenz 4 byte, ich habe 15000 Stücke TShortFloatHashMaps)

Warum???

 

[SlaterB]

die Map-Objekte an sich sind bisschen größer, haben noch Attribute, brauchen als Objekt initial vielleicht noch etwas mehr Bytes,
jedes der Array-Objekte vielleicht genaue auch ein paar Bytes, aber in der kleinen Anzahl nicht so entscheidend,
großzügig kann man da 15.000 x 100 rechnen und ist immer noch im einstelligen MB-Bereich,

etwas interessanter ist, dass dem SourceCode nach
Java > Open Source Codes > gnu > trove > TPrimitiveHash _ Java API By Example, From Geeks To Geeks.
mindestens noch ein drittes Array für alle Einträge besteht, allerdings mit byte, also vielleicht auch nur 36 MB zusätzlich,

am ehesten richtig Verbrauch könnte die Tatsache schaffen, dass die Maps ihren Platz im Voraus anlegen und das nicht bei jedem Einfügen neu machen wollen,
wenn eine Map voll oder ziemlich voll ist können Arrays mit bis zur doppelten der vorherigen Größe angelegt werden

falls du da nicht optimiert hast sind da im ungünstigsten Fall auch 100 MB unnötig reserviert

----

eine richtige Erklärung ist all das aber nicht, eher vermute ich Probleme beim restlichen Programm,
wie liest du die 36 Millionen Werte ein, sind die vielleicht noch irgendwo im Speicher vorhanden, gar im ungünstigen String-Format?
ich kann morgen vielleicht ein kleines Testprogramm schreiben, mit 36 Mio. Zufallswerten den Platz messen
bzw. im kleineren Maßstab

 

[fatfox]

eine richtige Erklärung ist all das aber nicht, eher vermute ich Probleme beim restlichen Programm,
wie liest du die 36 Millionen Werte ein, sind die vielleicht noch irgendwo im Speicher vorhanden, gar im ungünstigen String-Format?
ich kann morgen vielleicht ein kleines Testprogramm schreiben, mit 36 Mio. Zufallswerten den Platz messen
bzw. im kleineren Maßstab

Hi SlaterB, das ist echt nett von dir!!! Danke!!!

Ich habe am Anfang mit Augen gemessen, wie groß ist der Objekt. (Also gucke der System Monitor von Ubungtu ◑ˍ◐ ) Das ist c.a. 1.4 GB.
Dann habe ich noch mal mit deiner Methode [c]Runtime.getRuntime[/c] das Objekt gemessen:

t1 = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
.............
t2 = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
System.out.println( ( t1-t2 ) / 1024 / 1024 );

Das ist nur c.a.900 MB, wo sind die 500MB???? ╮(╯▽╰)╭

---------------------------

Ich habe das Objekt auch serialization gemacht. Die Datei ist nur c.a. 210MB.

Bei Lesen kostet der Computer c.a. 900 MB Speichern(per ◑ˍ◐), aber nach deiner Methode kostet c.a. 600 MB, wo sind die 300MB???? ╮(╯▽╰)╭

-----------------------------------

Du hast recht!!! Meine restliche Code erzeugt viele Müll!!! Nach meinem Test mit Augenbeobachtung ist c.a 500 MB Müll während TXT lesen erzeugt. Ich weiß nicht, wie ich meine Code verbessern kann. Ich habe einfach BufferedReader benutzt, und ein paar short und float Varialbe, sonst nichts.

Aber trotzdem ist 1.4GB - 0.5GB = 0.9GB ein bisschen zu viel...

-------------------------------------

P.S: Ich mache mal meine Code sauber und post hier spät... Noch mal danke!

 

[fatfox]

Hi SlaterB,

Könntest du für mich mal prüfen, ob meine Code zu viele Platz verschwendet?

Hier ist meine Code:

import gnu.trove.TShortFloatHashMap;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

import java.util.StringTokenizer;

public class Test {

	public static TShortFloatHashMap[] adjList ( String inputFile, int numberOfVertex ) {

		TShortFloatHashMap[] hm = new TShortFloatHashMap[numberOfVertex];

		for (int i = 0; i < numberOfVertex; i++) {
			hm[i] = new TShortFloatHashMap();
		}

		try {
			BufferedReader br = new BufferedReader(new FileReader(inputFile));
			String line = br.readLine();
			short s = 0, t = 0;
			Float leverage;
			StringTokenizer st;
 // Zeilen für Zeilen lesen:
			while (line != null) {
				st = new StringTokenizer(line, ";");
				leverage = Float.parseFloat(st.nextToken());
				s = Short.parseShort(st.nextToken());
				t = Short.parseShort(st.nextToken());
// Eintrag eingeben( In meine datei bietet eine Zeile die Informationen von 2 Einträge, deshalb zwei mal eingeben)
				hm[s].put(t, leverage);  
				hm[t].put(s, leverage);  
				
				line = br.readLine();
			}

			br.close();

		} catch (IOException e) {
			System.err.println(e.toString());
		}

		return hm;
	}


	public static void main(String[] args) {
		String inputFile = "/home/conny/Datei/Leverage_14842.csv";
		int numberOfVertex = 14842;
		
		adjList(inputFile, numberOfVertex);

	}

}

Und hier ist die Datei: http://www.phoenix-eyes.com/Diplom/Datei/Leverage_14842.csv
Datei ist groß, c.a. 268 MB °°°°°

 

[SlaterB]

bei mir werden ca. 700 MB belegt und das sind wie vermutet ca. 7 Byte pro Eintrag

allerdings sind es nicht 36 Mio. Einträge, sondern deutlich mehr, die Maps genehmigen sich noch viel mehr Platz als ich dachte,
am Ende 95 Mio. Einträge und mehr, das 2.6fache der eigentlich benötigten Menge,
soviel leerer Platz hilft wohl damit die Map effizient arbeitet, wenig Kollisionen der Hashwerte, was bei short sicher direkt die Keys sind,
vielleicht sorgen auch gerade die Kollisionen, die gleichen Keys, für mehr Platzbedarf,
müsste man im Detail nachschauen, aber das zumindest werde ich nicht mehr machen

hier ein Programm mit Speichermessung, ordentlich System.gc() scheint bei mir zuverlässig temporären Speicher wieder frei zu geben,
ansonsten habe ich auch stark variierende Zahlen bis zu 1 GB

public class Test {
	public static TShortFloatHashMap[] adjList(String inputFile,
			int numberOfVertex) throws Exception {

		TShortFloatHashMap[] hm = new TShortFloatHashMap[numberOfVertex];
		for (int i = 0; i < numberOfVertex; i++) {
			hm[i] = new TShortFloatHashMap();
		}
		long start = mem("");
		BufferedReader br = new BufferedReader(new FileReader(inputFile));
		String line = br.readLine();
		short s = 0, t = 0;
		Float leverage;
		StringTokenizer st;
		int c = 0;
		// Zeilen für Zeilen lesen:
		while (line != null) {
			st = new StringTokenizer(line, ";");
			leverage = Float.parseFloat(st.nextToken());
			s = Short.parseShort(st.nextToken());
			t = Short.parseShort(st.nextToken());
			// Eintrag eingeben( In meine datei bietet eine Zeile die
			// Informationen von 2 Einträge, deshalb zwei mal eingeben)
			hm[s].put(t, leverage);
			hm[t].put(s, leverage);

			line = br.readLine();
			c++;
			if (c % 1000000 == 0) {
				long l = mem("");

				int sumcap = 0;
				for (TShortFloatHashMap map : hm) {
					sumcap += map.capacity();
				}
				System.out.println(c + ", " + sumcap + ", " + (l - start)
						+ ", " + ((l - start) * 100 / sumcap));
			}
		}
		br.close();
		return hm;
	}

	public static void main(String[] args) throws Exception {
		String inputFile = "/home/slater/Leverage_14842.csv";
		int numberOfVertex = 14842;
		System.out.println("start");

		mem("mem ");
		TShortFloatHashMap[] hm = adjList(inputFile, numberOfVertex);
		mem("meme");
	}

        // Achtung, jeder Aufruf dauert eine Sekunde
	private static long mem(String st) throws Exception {
		Runtime r = Runtime.getRuntime();
		System.gc();
		System.gc();
		System.gc();
		Thread.sleep(500);
		System.gc();
		System.gc();
		System.gc();
		long l = (r.totalMemory() - r.freeMemory());
		if (st.length() > 0) {
			System.out.println(st + ": " + l);
		}
		return l;
	}
}

Ausgabe:

start
mem : 110680
1000000, 5844348, 38536016, 659 // = 6.59 Bytes pro Capacity
2000000, 12115398, 82429904, 680
3000000, 17521210, 120267944, 686
4000000, 22577446, 155659656, 689
5000000, 28474044, 196934176, 691
6000000, 35032110, 242839104, 693
7000000, 41492600, 288061224, 694
8000000, 47375318, 329238760, 694
9000000, 53196416, 369985120, 695
10000000, 58794254, 409168576, 695
11000000, 64240364, 447289904, 696
12000000, 69400868, 483412424, 696
13000000, 74409500, 518471728, 696
14000000, 79607082, 554853728, 696
15000000, 84602812, 589822832, 697
16000000, 89622976, 624962928, 697
17000000, 95158938, 663713656, 697
meme: 691889264

 

[fatfox]

Hi Slate,

Danke!!!!!!!!! Endlich habe ich das Problem verstanden!!!

Ich habe noch eine kleine Frage, warum hast du in "mem()" Funktion 6 mal [c]System.gc( )[/c] aufgerufen? Reicht einmal nicht?

 

[SlaterB]

kannst es ja ohne versuchen, nur einmal ohne sleep hat jedenfalls nicht bei mir gereicht,
ob mehrmals hilft kann ich nicht sicher sagen, ist vielleicht nur ein Gerücht, irgendwer hat es mal geschrieben, alle anderen machen es nach..

 

[fatfox]

kannst es ja ohne versuchen, nur einmal ohne sleep hat jedenfalls nicht bei mir gereicht,
ob mehrmals hilft kann ich nicht sicher sagen, ist vielleicht nur ein Gerücht, irgendwer hat es mal geschrieben, alle anderen machen es nach..

Mmmmm, dann mache ich es auch nach...