VM Argumente - Das Maximum rausholen

[Don83]

Hallo,

ich würde gerne Java VM Argumente setzen.
Den HeapSpace habe ich bereits erweitert:
-Xmx1024m

Ich würde aber gerne auch die Rechengeschwindigkeit erhöhen - ,muss ich hierzu VM Argumente angeben(falls ja wie lauten diese) oder geht dies direkt über die Hardware?

 

[Firephoenix]

An der Rechengeschwindigkeit kannst du eigentlich nichts ändern, du kannst intern aber mehrere Threads benutzen damit das System die Leistung besser verteilen kann.
Was du optimieren kannst sind hauptsächlich Einstellungen für den Garbage-Collector (hier kann evtl auch CPU-Last gespart werden) und Einstellungen für den Heap (das wäre dann eher speicherorientierte Optimierung).
[EDIT]@SlaterB wieviele Millisekunden lagen bei uns zwischen dem Klick auf Antworten?
Deine Antwort war schon hinter meiner eingetragen als nach dem Klick auf "Antworten" die Seite mit dem Thread geladen wurde [/EDIT]
Gruß

 

[SlaterB]

Rechengeschwindigkeit erhöhen, nicht schlecht, dazu noch der Parameter 'Strom produzieren statt verbrauchen',

nein, Rechengeschwindigkeit ist nicht variabel, während Festplatte unstrukturierten allgemeinen Zugriff unterliegt
und Arbeitsspeicher wohldosiert zwischen Programmen aufgeteilt wird, nur letzteres hat einen Parameter

Zugriff auf Rechenkerne ist noch am ehesten interessant, aber auch das ist nicht per Parameter zu steuern,
wenn ich mich nicht sehr irre

wie sich überhaupt verschiedene Programme bei jeweils mehreren CPU-Wünschen organisieren ist durchaus interessant,
aber letztlich kann man das in Millesekundenschnelle wechseln, während Arbeitsspeicher langfristig belegt wird,
feste Zuordnung weniger nötig

 

[Don83]

Hm nagut,
ich dachte Java beschränkt das irgendwie und dass man es dann manuell Erweitern muss. Aber abgesehen davon, was ist eigentlich das Maximum was man bei -Xmx angeben kann im Bezug auf die Hardware. Ich denke mal wenn man dies zu hochsetzt spielt der Rechner nichtmehr ordentlich mit?

 

[Firephoenix]

Da sollte es eigentlich möglich sein soviel zuzuweisen wie dein Betriebssystem verwalten kann (natürlich nicht mehr als auch tatsächlich eingebaut ist).

Gruß

 

[maki]

[c]-server[/c] kann die Performance verbessern.

 

[timbeau]

Denke bevor man in der Richtung sucht, sollte man den Code analysieren.

 

[Don83]

Der code ist ziemlich trivial. Geht nur ums im Endeffekt quadratische Vergleichen von 13 Mio Zeilen. Hab das ganze jetzt mal auf einen server mit ner Menge Rechenleistung gepackt :>.

– Dual Xeon Multi-Core Motherboard, Intel C602 Chipsatz, SATA
– 2x Intel Xeon Six-Core E5-2620(2 GHz, 72. GT/s QPI, 95W)
– 64 GB DDR3 SDRAM, 1333 MHz (8 x 8GB)

Damit klappen die ersten Teile der Analyse schonmal ganz gut. Also z.B. das Einlesen und das Sortieren der Zeileneinträge. Bei der Abschlussanalyse scheint aber sogar der Server in die Knie zu gehen .

PS: Was hat es mit -server auf sich? War das ein Witz oder funktioniert das Kommando wirklich? Würde gerne mal nachlesen was das Kommando bewirkt. Googlesuchen alla '-server vm java' haben mir jetzt noch nicht wirklich weiter geholfen.

 

[Marco13]

Poste genauere Infos/Code, dann kann mag ggf. mehr dazu sagen...

EDIT: Wegen -server: Das sorgt dafür, dass die Hotspot-Optimierung früher einsetzt. Mehr Infos z.B. jvm - Real differences between "java -server" and "java -client"? - Stack Overflow oder Java HotSpot(TM) Client and Server Virtual Machines

 

[KSG9|sebastian]

Der code ist ziemlich trivial. Geht nur ums im Endeffekt quadratische Vergleichen von 13 Mio Zeilen. Hab das ganze jetzt mal auf einen server mit ner Menge Rechenleistung gepackt :>.

Damit klappen die ersten Teile der Analyse schonmal ganz gut. Also z.B. das Einlesen und das Sortieren der Zeileneinträge. Bei der Abschlussanalyse scheint aber sogar der Server in die Knie zu gehen .

PS: Was hat es mit -server auf sich? War das ein Witz oder funktioniert das Kommando wirklich? Würde gerne mal nachlesen was das Kommando bewirkt. Googlesuchen alla '-server vm java' haben mir jetzt noch nicht wirklich weiter geholfen.

Für solche Berechnungen ist schneller Code selten wirklich trivial..daher würde ich erstmal den Code optimieren...

 

[gst]

PS: Was hat es mit -server auf sich? War das ein Witz oder funktioniert das Kommando wirklich? Würde gerne mal nachlesen was das Kommando bewirkt. Googlesuchen alla '-server vm java' haben mir jetzt noch nicht wirklich weiter geholfen.

Drei mal darfst du raten was du Google sagst wenn du ein Minus vor einen Suchbegriff schreibst...

 

[Don83]

Naja gut - ich poste in diesem Fall eigentlich nur ungern Quellcode - aber der Teil der nun relativ viel Zeit kostet ist dieser:

for (int i = 0; i < keysize - 1; i++) {
	for (int j = i + 1; j < keysize; j++) {

				if (id1.get(i).equals(id1.get(j))) {
//id1, id2 und values sind Listen die über den Index verknüpft sind. Sie sind nach value absteigend sortiert und haben jeweils die Größe 'keysize'.
					id1.remove(j);
					id2.remove(j);
					values.remove(j);
					keysize--;
					j--;

				} else {
					if (id2.get(i).equals(id2.get(j))) {
						id1.remove(j);
						id2.remove(j);
						values.remove(j);
						keysize--;
						j--;

					}
				}
			}
		}

Ich kann kurz erklären was hierbei passiert.
Ich habe 3 Listen, 2 mit einer ID und eine mit einem Gewicht. Diese sind wie absteigend geordnet.

ID1,ID2,Gewicht
10,55,53.22345
24,66,52.2123
....
13,51,-99.34342
111,222,-103.2123

Die IDs stellen Links dar. In den Listen kommt es vor, das von einer ID mehrere Links ausgehen.
Z.B.:
10,55,53.22345
10,78,49.22345
10,103,42.22345

Hier soll dann immer der stärkste Link genommen werden, die anderen sollen aus den Listen gelöscht werden so dass es von einem Link, bzw. einer ID ausgehend immer nur einen Link gibt. Hierzu sind beide Richtungen zu beachten <-,->. Die IDs in den beiden Listen sind voneinander unabhängig. Es kann also einen Link 10,53 und auch einen Link 53,10 geben.

10,55,53.22345
[STRIKE]10,78,49.22345[/STRIKE]
[STRIKE]10,103,42.22345[/STRIKE]

Auf meinen bisherigen Datensätzen hat das bisher problemlos funktioniert - bzw. dieser Teil hat schon immer etwas gedauert, aber war machbar. Auf den Listen mit über 13 Mio einträgen geht das eher träge voran. Ich habe dazu mal printmeldungen gestaltet um einen kleinen Eindruck dazu zu vermitteln:

[15:31:02]: 0 Links wurden bisher auf *-Links geprüft.Dabei wurden 0 *-Links entfert. 13643786 Links gibt es noch zu prüfen.
[15:31:21]: 10 Links wurden bisher auf *-Links geprüft.Dabei wurden 290 *-Links entfert. 13643496 Links gibt es noch zu prüfen.
[15:32:40]: 20 Links wurden bisher auf *-Links geprüft.Dabei wurden 4298 *-Links entfert. 13639488 Links gibt es noch zu prüfen.
[15:34:33]: 30 Links wurden bisher auf *-Links geprüft.Dabei wurden 11326 *-Links entfert. 13632460 Links gibt es noch zu prüfen.
[15:35:58]: 40 Links wurden bisher auf *-Links geprüft.Dabei wurden 16842 *-Links entfert. 13626944 Links gibt es noch zu prüfen.

usw...
Zwar schrumpft die Liste nach und nach (sollte auf ca. 400.000 schrumpfen), aber ob das ganze in diesem Jahrtausend fertig werden würde wage ich zu bezweifeln .

Ich will nicht ausschließen dass man etwas verbessern kann, aber funktionieren tuts. Wäre natürlich schon wenn man noch optimieren könnte - bislang bestand da noch keine Notwendigkeit.

 

[SlaterB]

> Wäre natürlich schon wenn man noch optimieren könnte - bislang bestand da noch keine Notwendigkeit.

aber an der VM wolltest du schon die Leistung hochdrehen?

-------


ein klassisches Sackgassen-Programm, geht wahrscheinlich auch in wenigen Sekunden bis Minuten

1. Schritt:
führe eine Klasse ein mit mehreren Attributen, du brauchst nur eine Liste mit Objekten, in denen alles zum jeweiligen Eintrag steht

2. Schritt:
sortiere die Liste nach Id1, evtl. sekundär Gewichtung, was immer wichtig ist,
alle Ids in Reihenfolge hintereinander,
[ich weiß dass das für sich evtl. eine größere Aufgabe ist, hier bewußt ohne Implementierungs-Details]

edit:

Damit klappen die ersten Teile der Analyse schonmal ganz gut. Also z.B. das Einlesen und das Sortieren der Zeileneinträge.

oh, umso besser, mit verschiedenen Listen nicht ganz so leicht,
wenn du das schon hast, dann eine einzelne Klasse nicht mehr ganz so dringend,
allgemein aber immer (doch dringend ) zu empfehlen



3. Schritt:
dann musst du nur noch benachbarte Einträge vergleichen,
statt n^2 größtenteils unsinnige nur noch n Vergleiche, was n-mal schneller geht, also um Faktor Mio. besser,
da müsstest du sonst schon das halbe Internet als Rechenleistung zum Ausgleich dazuschalten,

Sortieren davor ist allerdings noch paar Stufen aufwendiger, Aufwand n log(n), ein Faktor 10 geht doch wieder verloren

danach evtl. nach zweiter Id sortieren und nochmal das ganze,

------

andere Möglichkeiten hätten von Details ab, z.B. ist Einfügen in ein Set generell das beste Entfernen von Doppelten,
sofern HashCode und equals entsprechend funktionieren,
allerdings ohne Gewichtung

viel Entfernen kann bei einer LinkedList statt ArrayList günstiger sein,
noch besser bei einfachen Durchlauf evtl. wiederum, nur die guten Einträge in eine neue zweite Liste aufzunehmen

 

[SlaterB]

um bei deinem Code mit der Doppelschleife zu bleiben:
wenn nach Id1 sortiert ist, ist es immerhin schon gut, nur mit größeren j als i zu vergleichen,
dennoch sind das im Mittel n/2 = Millionen Vergleiche, dabei können doch nur maximal ein paar folgende Einträge gleich sein,
sobald der erste equals-Vergleich fehlschlägt, kannst du den Rest doch vergessen,
mit continue zum nächsten i übergehen
-> schon nur noch wenige Vergleiche pro i statt Millionen, rasend schnell statt mehrere sec für jedes i

nach Id2 kannst du dann nicht gleichzeitig prüfen, da dort alles beliebig verteilt ist,
-> vorher oder nachher in einem zweiten Durchlauf erst nach Id2 sortieren und dann wieder nur benachbart vergleichen

 

[Don83]

Hi,
danke für das feedback. Die Idee ist gar nicht mal so verkehrt sowohl nach ID als auch nach Gewicht zu sortieren. Ich weis nurnoch nicht genau ob das klappt, da ja beide Richtungen beachtet werden müssen ->, <-.

Beispiel: Du sortierst primär nach ID1 und sekundär nach Gewicht.

53,88,+100
53,77,+60
53,22,-30
...
64,88 +112


So ich wäre also bei 53 und würde mir immer den nächsten Vergleich ansehen. Das würde hier konkret wie folgend aussehen:
53,88,+100
[STRIKE]53,77,+60[/STRIKE]
[STRIKE]53,22,-30[/STRIKE]
...
64,88 +112

Nun habe ich aber die Gegenrichtung mit der ID 88 die in einem höheren Link 112 als Gewicht besitzt.
Damit besitzt quasi ID 2 durch das höhere Gewicht die Priorität und 53,88 müsste gelöscht werden.
Der echte Link für 53 wäre also 53,77 mit dem Gewicht 60. Bin mir noch nicht sicher, ob solche Fälle überhaupt auftreten können. Aber der Denkanstoß war schonmal gut - ich muss nochmal etwas genauer drüber nachdenken :rtfm:.

 

[SlaterB]

hmm, in der Tat verzwickt,
vielleicht dann folgendes:

erst nach Id1 sortieren, Gleiche nur sammeln, bei jedem Eintrag eine Liste mit Einträgen gleicher Id1,

genauso nach Id2 sortieren, bei jedem Eintrag eine zweite Liste mit Einträgen gleicher Id2,


letztlich wieder nach Gewicht sortieren, so wie du es bisher hast, ein drittes Mal die Liste durchgehen:
für jeden Eintrag nun aber eben nur noch die beiden vergleichsweise kleinen Listen gleicher Ids anschauen (*),

dabei nicht löschen, die richtigen Indexe bei neuer Sortierung eh kaum bekannt,
lieber die Einträge als 'nicht gut' markieren, hier lohnt sich mal wieder der Einsatz von Klassen/ Objekten:
man kann die anderen Einträge beeinflussen, ohne deren aktuelle genaue Position kennen/ suchen zu müssen, man hat eine eigene Referenz gemerkt

bei diesem Durchgang aufpassen Richtung deines Beispiels,
sobald bei 53,88,+100 angelangt, dürfte der ja schon schon als 'nicht gut' markiert sein,
dann für diesen nichts mehr tun, 53,77,+60 bleibt verschont,
wenn 53,77,+60 drankommt, dann 53,88,+100 ruhig nochmal als 'nicht gut' markieren, schadet nicht
auch 53,22,-30 muss dann dran glauben

nebenbei jeden Eintrag der drankam und nicht selber 'nicht gut', ergo gut ist, in eine neue Liste aufnehmen = Ergebnis


------

(*) die Listen können leider einen beträchtlichen Speicheraufwand bedeuten,
je voller die Listen werden, je mehr gleiche Ids, desto eher lohnt es sich noch, ein und dasselbe Listen-Objekt bei allen
in der Liste abzulegen

 

[Marco13]

*Kristallkugel* Es geht um einen Graphen, und man will nur die am höchsten gewichteten Kanten übrig lassen (unabhängig von ihrer Richtung)?


So, wie du es beschreibst, klingt es aber, als würden ohnehin die meisten Einträge wegfallen, d.h. man könnte auch gleich einen neuen, "bereinigten" Datensatz erstellen, und den alten wegwerfen.

Ein Punkt zum bestehenden Code: Ich gehe davon aus, dass diese Listen ArrayLists sind. Ein arrayList.remove(0) bewirkt, dass alle (13 Millionen!) nachfolgenden Einträge um 1 Position nach vorne verschoben werden müssen. Eine ArrayList ist für sowas also denkbar ungeeignet. (Wenn man NUR die relevanten Kanten in einen neuen Datensatz einfügen würde, würde sich diese Frage ggf. gar nicht stellen).

Ich denke aber auch, dass man das durch eine geeignete Datenstruktur deutlich beschleunigen könnte, und es eine Sache von Sekunden wäre. Mit etwas mehr Code (am besten KSKB mit Dummy-Daten) würde ich mir das mal ansehen. Weitere Informationen wären dann auch hilfreich (z.B. ob die "ids" immer einen integer-Bereich von 0 bis n beschreiben wobei n etwa die Anzahl der Datensätze ist).

 

[Firephoenix]

Von den Anforderungen sieht das ganze doch so aus als könnte [JAPI]TreeSet[/JAPI] passen?(insbesondere im Bezug auf logarithmische Laufzeiten bei den Basisoperationen und das Sortieren).

Gruß

 

[Marco13]

Hab' mal ein bißchen rumprobiert. Ist nur ercht schnell hingehackt, und natürlich mit viel Spekuklation verbunden und nicht verifiziert, aber könnte passen:

package javaforum;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;

public class WeightEdgeRemoval
{
    public static void main(String[] args)
    {
        int keysize = 100000;
        WeightEdgeRemoval w = new WeightEdgeRemoval();
        w.generate(keysize);
        
        long before = 0;
        long after = 0;
        
        System.out.println("Before");
        w.print(10);

        before = System.nanoTime();
        w.cleanup1();
        after = System.nanoTime();
        System.out.println("Duration1 "+(after-before)/1e6);

        System.out.println("After1");
        w.print(10);

        
        w.generate(keysize);
        
        before = System.nanoTime();
        w.cleanup2();
        after = System.nanoTime();
        System.out.println("Duration2 "+(after-before)/1e6);

        System.out.println("After2");
        w.print(10);
        
    }
    
    
    int keysize;
    List<Integer> id1;
    List<Integer> id2;
    List<Double> values;
    
    public WeightEdgeRemoval()
    {
    }
    
    void generate(int keysize)
    {
        this.keysize = keysize;
        Random random = new Random(0);
        class Link implements Comparable<Link>
        {
            int id1;
            int id2;
            double value;
            @Override
            public int compareTo(Link o)
            {
                return Double.compare(o.value, value);
            }
        }
        List<Link> links = new ArrayList<Link>();
        int numIds = keysize / 16; // Guess...
        for (int i=0; i<keysize; i++)
        {
            Link link = new Link();
            link.id1 = random.nextInt(numIds);
            link.id2 = random.nextInt(numIds);
            link.value = random.nextDouble() * 100;
            links.add(link);
        }
        Collections.sort(links);
        
        id1 = new ArrayList<Integer>();
        id2 = new ArrayList<Integer>();
        values = new ArrayList<Double>();
        for (int i=0; i<keysize; i++)
        {
            Link link = links.get(i);
            id1.add(link.id1);
            id2.add(link.id2);
            values.add(link.value);
        }
    }
    
    private void print(int n)
    {
        for (int i=0; i<Math.min(n, id1.size()); i++)
        {
            System.out.printf("%5d %5d %8.3f\n", id1.get(i), id2.get(i), values.get(i));
        }
    }
    
    void cleanup1()
    {
        for (int i = 0; i < keysize - 1; i++)
        {
            for (int j = i + 1; j < keysize; j++)
            {
                if (id1.get(i).equals(id1.get(j)))
                {
                    // id1, id2 und values sind Listen die über den Index
                    // verknüpft sind. Sie sind nach value absteigend sortiert
                    // und haben jeweils die Größe 'keysize'.
                    id1.remove(j);
                    id2.remove(j);
                    values.remove(j);
                    keysize--;
                    j--;

                }
                else
                {
                    if (id2.get(i).equals(id2.get(j)))
                    {
                        id1.remove(j);
                        id2.remove(j);
                        values.remove(j);
                        keysize--;
                        j--;

                    }
                }
            }
        }
    }
    
    
    
    void cleanup2()
    {
        class IntPair
        {
            private int i0;
            private int i1;
            
            IntPair(int i0, int i1)
            {
                this.i0 = i0;
                this.i1 = i1;
            }
            
            @Override
            public int hashCode()
            {
                return i0 ^ i1;
            }
            @Override
            public boolean equals(Object object)
            {
                if (object instanceof IntPair)
                {
                    IntPair other = (IntPair)object;
                    return 
                        (i0 == other.i0 && i1 == other.i1) ||
                        (i0 == other.i1 && i1 == other.i0);
                }
                return false;
            }
        }
        
        Map<Integer, Double> maxWeights = 
            new LinkedHashMap<Integer, Double>((int)(1.4*keysize));
        Map<IntPair, Double> map = 
            new LinkedHashMap<IntPair, Double>((int)(1.4*keysize));
        for (int i = 0; i < keysize; i++)
        {
            Integer i1 = id1.get(i);
            Integer i2 = id2.get(i);
            Double value = values.get(i);

            Double w1 = maxWeights.get(i1);
            if (w1 == null || w1 < value)
            {
                maxWeights.put(i1, value);
            }
            Double w2 = maxWeights.get(i2);
            if (w2 == null || w2 < value)
            {
                maxWeights.put(i2, value);
            }
        }
        
        for (int i = 0; i < keysize; i++)
        {
            Integer i1 = id1.get(i);
            Integer i2 = id2.get(i);
            Double value = values.get(i);

            Double w1 = maxWeights.get(i1);
            Double w2 = maxWeights.get(i2);
            Double max = Math.max(w1, w2);
            if (value >= max)
            {
                IntPair ip = new IntPair(i1, i2);
                map.put(ip, value);
            }
        }
        id1.clear();
        id2.clear();
        values.clear();
        for (Entry<IntPair, Double> entry : map.entrySet())
        {
            IntPair ip = entry.getKey();
            id1.add(ip.i0);
            id2.add(ip.i1);
            values.add(entry.getValue());
        }
    }
    
    
}

Es wird einmal durch die Listen gegangen, und für jede ID der maximale Wert gespeichert, an dem sie beteiligt ist. Dann wird nochmal durch die Liste gegangen, und jedes Paar von IDs gespeichert, das einen Wert hat, der der Maximale Wert einer der beiden IDs ist. Das ist ein bißchen hemdärmelig und braucht natürlich mehr speicher, und sicher könnte man das noch geschickter und effizienter machen, aber ... zumindest ist die Laufzeit jetzt Linear und ca. 100ms für etwas, was vorher ca. 17s gedauert hat.

 

[SlaterB]

[OT]
@Marco13
puh, ich bin schon ganz froh dass es (bisher) nicht so einfach wird wie bei dem Graph als Hampelmännchen
[/OT]