1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen

Verschachtelte Schleife in Go

Dieses Thema im Forum "Sonstige Programmiersprachen" wurde erstellt von dominikb, 29. Dezember 2017.

  1. dominikb

    dominikb Member

    Hallo zusammen,

    eigentlich wollte ich nur einen kleinen Performance-Vergleich machen - der dann dazu führte, dass erstmal gar nichts mehr ging. Aber der Reihe nach.

    Ich habe gestestet, wie lange eine verschachtelte Schleife mit 1.000.000 * 100.000 Iterationen braucht, in der zusätzlich noch eine Variable inkrementiert wird.

    Code:
    public class Tests {
    
        public static long COUNT = 0;
    
        public static void main(String[] args) {
            long start = new Date().getTime();
         
            for (int i = 0; i < 1_000_000; i++) {
                for (int j = 0; j < 100_000; j++) {
                    increment();
                }
            }
            long end = new Date().getTime();
            long result = end - start;
    
            System.out.println(result);
            System.out.println(COUNT);
        }
     
        private static void increment() {
            COUNT++;
        }
     
    }
    3979 ms dauert das Ganze. Nett!

    Nun wollte ich den selben Test in Go machen:

    Code:
    package main
    
    import (
        "fmt"
        "time"
    )
    
    var count int64
    
    func main() {
        start := time.Now()
    
        for i := 0; i < 1000000; i++ {
            for j := 0; j < 100000; j++ {
                increment()
            }
        }
        end := time.Now()
        result := end.Sub(start)
    
        fmt.Println(result)
        fmt.Println(count)
    }
    
    func increment() {
        count++
    }
    Das Programm führt zu einer katastrophalen Laufzeit von knapp 3 Minuten. Doch es geht noch weiter: Wenn ich versuche, das Programm mit einer einfachen Goroutine zu parallelisieren, folgt kurz darauf der Programmabsturz.

    Code:
    package main
    
    import (
        "fmt"
        "time"
        "sync"
    )
    
    var count int64
    var mutex sync.Mutex
    
    func main() {
        start := time.Now()
    
        for i := 0; i < 1000000; i++ {
            for j := 0; j < 100000; j++ {
                go increment()
            }
        }
        end := time.Now()
        result := end.Sub(start)
    
        fmt.Println(result)
        fmt.Println(count)
    }
    
    func increment() {
        mutex.Lock()
        defer mutex.Unlock()
        count++
    }
    Hat jemand eine Ahnung, woran die schlechte Performance liegt und wie ich das Problem beheben kann?

    Danke im Voraus!
  2. asc

    asc Active Member c-b Experte

    Parallelisieren schön und gut, aber mit dem Mutex läuft das mehr oder weniger sequentiell. Genau genommen hast du 100.000.000.000 Threads gestartet (bzw. möchtest du starten) die alle der Reihe nach aufeinander warten. Dass das irgendwann abstürzt ist zwar unvorteilhaft, aber nicht verwunderlich. Vermutlich kommt der GC einfach nicht mehr hinterher oder dein OS gibt dem Programm keine weiteren Handles mehr.

    Wenn dus wirklich parallel haben möchtest, dann rechne in den Goroutinen Teilsummen aus und am Ende addierst du diese zusammen. Oder denk dir selbst was aus. Auf jeden Fall muss das ohne Mutex und mit weniger Threads (!!!) funktionieren.
  3. dominikb

    dominikb Member

    Sind es im Betriebssystem tatsächlich so viele Threads wie go-Anweisungen im Code auftauchen? Ich dachte eigentlich, das sehr eher unabhängig voneinander:

    Quelle: The Little Go Book

    Aber nein, verwunderlich ist es nicht. Warum es trotz der Goroutines mit Mutex (oder genau deswegen) quasi sequenziell abläuft, ist mir nun klar. :rolleyes: Ist ja auch logisch, wenn vor jedem Increment auf die Freigabe der vorherhigen Goroutine gewartet werden muss ...

    Dann bleibt für mich aber noch die Frage, warum mein erster Ansatz (ohne Parallelisierung) satte 3 Minuten braucht, und Java für die selbe Anzahl an Iterationen lediglich 3.9 Sekunden. Irgendwo scheint sich der Ablauf gehörig zu unterscheiden. :confused: Hast du da eine Idee?
  4. asc

    asc Active Member c-b Experte

    Du hast 100 Milliarden.

    Der Unterschied zwischen Java und Go ist vermutlich die bessere Optimierung des Codes durch den Compiler (Hotspot).

    Dein Code in C mit -O3 übersetzt hat das Ergebnis bereits vor der Ausführung berechnet und fertig zur Ausgabe wenn das Programm ausgeführt wird.

    Probier's aus:

    Code:
    #include <stdio.h>
    #include <stdint.h>
    
    static int64_t count = 0;
    
    void increment (void)
    {
      count++;
    }
    
    int main (void)
    {
      for (int i = 0; i < 1000000; i++) {
        for (int j = 0; j < 100000; j++) {
          increment();
        }
      }
    
      printf("%llu\n", count);
      return 0;
    }
    
    gcc -std=c11 -O3 -o test test.c

    ~5 Millisekunden
  5. dominikb

    dominikb Member

    Das ist eine Idee. Danke dir :) Dann informiere ich mich mal, wie ich den Go-Code analog zu O3 oder O2 bereits im Voraus optimieren kann ...