Threads Ausführung in Threads ist langsamer als ohne Threads

[Enomine]

Hi,

ich habe zwei einfache abstrakte Programme erstellt um euch hier zu zeigen was mir beim Programmieren eines Programmes passiert ist.

Es geht darum, dass ich verschachtelte for-Schleifen habe, die dann auch zunächst je eine if-Bedingung haben und wenn diese nicht erfüllt ist wird die Schleife betreten und dadurch die Unterschleifen. Kurzgesagt: Das Programm zählt nur weiter, wenn kein Wert doppelt vor kommt. (Ja ich weiß, dass ich auch ein Set benutzen kann um keine doppelten Werte zu haben. Ich brauche aber auf den untersten ebenen eine garantiert 100% Überdeckung aller Fälle.)

Jedenfalls wollte ich den Prozess parallelisieren, um Zeit zu sparen. Dabei ist mir aufgefallen, dass das gleiche Programm in 10 Threads 15 mal länger braucht als ohne Threads.

Ich möchte wissen warum, was ich falsch gemacht habe und wie ich es beheben kann.

Die Programme findet ihr im Anhang.

Prozessor: AMD FX 8350 mit 4.01 GHz; RAM: 32 GB davon 16 GB frei.

EDIT: Möglicherweise könnte jemand argumentieren, dass die Umschaltzeit zwischen den Prozessen bei 10 Prozessen mehr aufhält als das hochzählen an sich. Deshalb hab ich es mit nur 4 Threads ausprobiert, die nur bis 361.380.096 zählen, statt bis 903.450.240 und diese 4 Threads haben dafür immernoch 4 Sekunden, also 4 mal länger gebraucht.

Danke - Enomine

 

[Thallius]

Wenn du alle threads joinst wie soll es dann schneller werden?

 

[Bitfehler]

Ich nehme mal an, das LoopInThreadsCounter das Programm mit den Threads ist, was deiner Ansicht nach zu lange braucht und LoopCounter dein Vergleichsprogramm ist?

Dir ist schon gewusst, dass du dein Hochzählen im Programm LoopCounter einmal durchlaufen lässt und in dem anderen Programm 10 Mal, weshalb es auch länger dauert, wenn ich mich gerade nicht versehen habe?

 

[Enomine]

Wenn du alle threads joinst wie soll es dann schneller werden?

Hi, die Threads werden erst gejoint nachdem alle gestartet wurden. Das ist Standard. Das muss man machen um den Zeitpunkt abzuwarten wo alle Threads fertig sind. Sonst kann ich doch das Ergebnis nicht gemeinsam ausgeben. Die Threads arbeiten trotzdem parallel und das macht ja den Vorteil aus. Bzw. soll es

Ich nehme mal an, das LoopInThreadsCounter das Programm mit den Threads ist, was deiner Ansicht nach zu lange braucht und LoopCounter dein Vergleichsprogramm ist?

Dir ist schon gewusst, dass du dein Hochzählen im Programm LoopCounter einmal durchlaufen lässt und in dem anderen Programm 10 Mal, weshalb es auch länger dauert, wenn ich mich gerade nicht versehen habe?

Beide Programme zählen bis 903.450.240. Du hast dich verguckt. In dem einen Zähle ich eben in 10 Threads und in dem anderen eben 10 mal die erste ebene der for-schleife.

Danke - Enomine

 

[kneitzel]

Also Du hast einmal in der äußersten Schleife einen Zähler bis 100 und einmal nur bis 10. Also da ist ein Faktor von 10 durchaus etwas, das ich erwarten würde.

Und dann noch die 50% länger könnten einfach durch die Umschaltvorgänge zwischen den Threads bedingt sein.

Runtime.getRuntime().availableProcessors() könnte einmal zeigen, wieviele Threads im optimalen Fall parallel laufen könnten bei Dir. Die Ausgabe davon wäre evtl. auch einmal interessant.

Konrad

 

[kneitzel]

Ach, sorry. Hab mich verschaut. Die äußerste for-Loop ist entspricht ja den 10 Threads bei der threaded Variante.
Aber bei mir ist da "nur" ein Faktor von 2,5 als Differenz zu sehen. Einmal 2 sec und einmal 5 sec. Also deutlich geringer.

 

[kneitzel]

Und interessant: Das Problem scheint der Zugriff auf das counter Array zu sein. Ich habe jetzt einfach den Code umgeschrieben und im run() eine lokale Variable long localCounter = 0; hinzugefügt. Innerhalb der Schleife habe ich nun ein localCounter++; und nur ganz am Ende ein setzen des Arrays und schon habe ich die volle Geschwindigkeit, die ich erwartet habe.

Es scheint den Zugriff auf das Array zu synchronisieren was dann alles extrem ausbremst. Aber ich habe jetzt nicht die Zeit, in der jls und jvms nach der genauen Erklärung zu schauen.

Konrad

 

[Thallius]

Na das ist ja logisch. Zum Glück synchronisiert er das, sonst würde da nur Blödsinn bei rauskommen wenn mehrere Threads gleichzeitig auf ein globales Array schreibend zugreifen.

Man merke -> Globale (static) Variablen haben in thread nichts aber auch absolut gar nichts verloren.

Gruß

Claus

 

[Meniskusschaden]

Vielleicht ist noch folgende Beobachtung interessant: Ich habe die Schleife für die Variable j bis 2000 anstelle 100 laufen lassen, um die Laufzeit zu erhöhen. Ohne Threads läuft das Programm bei mir dann ca. 26s und mit Thread ca. 39s.

Ich habe mir währenddessen die Prozessorauslastung angesehen. Ohne Threads stieg die Auslastung bei drei Kernen deutlich an und schwankte dann auf dem höheren Niveau, stieg aber nicht höher als ca. 60%. Mit Threads stieg die Prozessorauslastung bei allen acht Kernen durchgehend auf 100%.

 

[Enomine]

Na das ist ja logisch. Zum Glück synchronisiert er das, sonst würde da nur Blödsinn bei rauskommen wenn mehrere Threads gleichzeitig auf ein globales Array schreibend zugreifen.

Man merke -> Globale (static) Variablen haben in thread nichts aber auch absolut gar nichts verloren.

Gruß

Claus

Hi Claus,

es ist nicht umsonst ein Array der breite 10 Jeder Thread greift auf seinen >>eigenen<< Arrayeintrag zu.

Es scheint den Zugriff auf das Array zu synchronisieren was dann alles extrem ausbremst. Aber ich habe jetzt nicht die Zeit, in der jls und jvms nach der genauen Erklärung zu schauen.

Konrad

Mh das kann ich mir eigentlich nicht vorstellen, dass es synchronisiert. Denn: Ich habe vor einigen Monaten mal das Phänomen gehabt, dass ich von vielen Threads eine einzige Variable hab hochzählen lassen. Das Ergebnis war dann aber kleiner als erwartet. Das liegt wohl daran, dass beide Threads gleichzeitig den Inhalt auslesen und dann um 1 incrementieren und dann das Ergebnis wieder in der Variable ablegen. Aus 5 wird dann eben eine 6 anstatt 7, weil die parallelen Threads gleichzeitig gelesen haben und beides mal die 5 gelesen haben. Deswegen habe ich überhaupt eine Array-Zähler-Variable eingeführt, die genau so breit ist wie die Anzahl meiner Threads. Dies wiederspricht also deiner Theorie der Synchronisierung.

Trotzdem werde ich es mal so probieren wie du gesagt hast, Hauptsache die Geschwindigkeit stimmt =)

Danke - Enomine

 

[kneitzel]

Also dies ist die Ursache. Bitte prüfe es doch einfach selbst und mach diese Änderung so wie von mir beschrieben.

Und wenn ich die Zeit finde, dann suche ich dies in den Spezifikationen heraus alleine weil ich hier offensichtlich eine Lücke habe, die es gilt aufzuarbeiten.

 

[Thallius]

Hi Claus,

es ist nicht umsonst ein Array der breite 10 Jeder Thread greift auf seinen >>eigenen<< Arrayeintrag zu.

Danke - Enomine

Für wie "schlau" hälst du so einen Interpreter eigentlich? Woher soll der denn wissen das jeder Thread nur auf einen ihm zugewiesenen 'Eintrag zugreift? Ok, er kann vorher einmal den Code komplett durchlaufen lassen um es festzustellen aber dann wäre es wohl eher noch langsamer...

Im endeffekt "sieht" der Interpreter/Kompiler nur, dass du das Static in einem Thread benutzt und somit macht er ihn atomar. Und schon darf immer nur ein Thread darauf zugreifen und dazu noch sau langsam, weil das System vorher erstnoch klären muss ob und wenn wann er das darf.

 

[Tarrew]

Wenn das wirklich so wäre, dann müsste die Ausgabe bei diesem Programm immer "200000" sein.
Ist sie aber nie, weil die Threads parallel auf das Array zugreifen (obwohl es static ist).

public class ThreadTest implements Runnable {
    static long[] array = new long[10];

    @Override
    public void run() {
        for (int i = 0; i < 100000; i++) {
            array[0]++;
        }
    }

    public static void main(String[] args) {
        Thread t1 = new Thread(new ThreadTest());
        Thread t2 = new Thread(new ThreadTest());
        t1.start();
        t2.start();

        try {
            t1.join();
            t2.join();
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        System.out.println(array[0]);
    }

}

Wie das in dem Programm von dem TE genau läuft hab ich noch nicht ganz verstanden, eigentlich sollte der Zugriff auf das Array nicht synchronisiert sein. Wenn man mal explizit einen synchronisierten Zugriff darauf macht, also:

synchronized (counter) {
    counter[this.id]++;
}

, dann läuft das Programm auch 30 Sekunden anstatt 3 Sekunden.

Wobei irgendein Zusammenhang ja da sein muss. Vllt. ist nur der schreibende Zugriff synchronisiert aber konnte auf die Schnelle bei Google nichts finden :/

 

[nvidia]

[...]
Jedenfalls wollte ich den Prozess parallelisieren, um Zeit zu sparen. Dabei ist mir aufgefallen, dass das gleiche Programm in 10 Threads 15 mal länger braucht als ohne Threads.

Ich möchte wissen warum, was ich falsch gemacht habe und wie ich es beheben kann.[...]

Du hast prinzipiell so nichts falsch gemacht, das passiert leider auf Prozessorebene und die JVM hat nicht viel damit zu tun. Hast du schon mal von https://en.wikipedia.org/wiki/False_sharing gehört? Arg vereinfacht ausgedrückt wird das Array mit den Teilergebnissen, weil es so klein ist, vermutlich in eine Cache-Line gezogen. Das ist wiederrum unpraktisch für die anderen Prozesse, weil die dann da nicht einfach so ran dürfen.

Die einfachste Lösung für wäre anstelle eines Runnables ein Callable zu verwenden um die Rückgabewerte zu summieren. Die Futures die man zurück bekommt blockieren beim Aufruf von get(), die Gesamtdauer richtet sich dann dort also nach der "längsten" Aufgabe. Besser wäre wohl die direkte Verwendung von ForkJoin, da aber alle ungefähr gleich schnell ablaufen sollten ist das für das Beispiel akzeptabel. Mal schnell hingeschrieben.

public class LoopInThreadsCounterWithReturn implements Callable<Integer> {
    public static void main(String[] args) throws InterruptedException, ExecutionException {

        ExecutorService executorService = Executors.newFixedThreadPool(10);
        List<Future<Integer>> futures = new ArrayList<>(10);

        final long starttime = System.currentTimeMillis();

        for (int i = 0; i < 10; i++) {
            futures.add(executorService.submit(new LoopInThreadsCounterWithReturn(i)));
        }
        executorService.shutdown();

        int count = 0;
        for(Future<Integer> result : futures){
            count = count + result.get().intValue();
        }

        System.out.println(count);
        System.out.println("Time to execute: " + ((System.currentTimeMillis() - starttime)) + " seconds");
    }

    int id;

    public LoopInThreadsCounterWithReturn(int id) {
        this.id = id;
    }

    @Override
    public Integer call() throws Exception {
        final int i = id;
        int counter = 0;
        for (int j = 0; j < 100; j++) {
            if (j == i) {
                continue;
            }
            for (int k = 0; k < 100; k++) {
                if ((k == i) || (k == j)) {
                    continue;
                }
                for (int l = 0; l < 100; l++) {
                    if ((l == i) || (l == j) || (l == k)) {
                        continue;
                    }
                    for (int m = 0; m < 100; m++) {
                        if ((m == i) || (m == j) || (m == k) || (m == l)) {
                            continue;
                        }
                        counter++;
                    }
                }
            }
        }
        return Integer.valueOf(counter);
    }
}