Verschachtelte Schleife in Go

dominikb

Well-Known Member
#1
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.

Java:
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!
 

asc

Well-Known Member
c-b Experte
#2
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.
 

dominikb

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

Multiple goroutines will end up running on the same underlying OS thread. This is often called an M:N threading model because we have M application threads (goroutines) running on N OS threads. The result is that a goroutine has a fraction of overhead (a few KB) than OS threads. On modern hardware, it’s possible to have millions of goroutines.
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?
 

asc

Well-Known Member
c-b Experte
#4
it’s possible to have millions of goroutines.
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:

C:
#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
 
Oben