arek o sofcie

Albo “o co chodzi benchmarkach”.

Istnieje sobie portal benchmarksgame-team.pages.debian.net, który na przykładzie kilku algorytmów pozwala porównać wydajność wydajność implementacji w różnych językach.

W swojej historii pisałem w wielu różnych językach i niejednokrotnie mam możliwość wybrania języka dla realizowanego projektu. Takie porównania są więc interesujące, bo w sytuacji, gdy gdzieś kluczowa jest wydajność, dobrze jest wiedzieć, czy wybrałem właściwe narzędzie albo jak bardzo mój wybór jest nieoptymalny.

Z różnych powodów interesuje mnie porównanie wydajności języków Java i Go. Wchodząc pod ten adres https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/go.html można się przekonać, że Go jest ogólnie porównywalny z Javą albo nawet szybszy, poza jednym przypadkiem: Binary trees!

Przypadki, gdy coś jest 10% szybsze albo wolniejsze, coś oczywiście mówią, ale w realnych programach najprawdopodobniej takie zyski rozmyją się w natłoku innych, niezbędnych i nieuniknionych elementów programu. W praktyce oprogramowanie, które piszę, co chwila coś wysyła po sieci, albo czeka na rezultaty z sieci i sekunda więcej na obliczeniach (choć ważna) nie boli tak bardzo. Zawsze można dodać CPU lub kolejną maszynę wirtualną i ogólna wydajność systemu spełni wymagania.

Ale w tym wypadku jest dramat: implementacja w Go jest 5,6 razy wolniejsza.

Przyjrzyjmy się więc kodom źródłowym najszybszej implementacji Go.

package main
import (
   "flag"
   "fmt"
   "strconv"
   "sync"
)
type Node struct {
   left, right *Node
}
var pool = sync.Pool {
     New: func() interface{} {
          return &Node{}
     },
}
const minDepth = 4
func trees(maxDepth int) {
   longLastingNode := createTree(maxDepth)
   depth := 4
   for depth <= maxDepth {
      iterations := 1 << uint(maxDepth-depth+minDepth) // 16 << (maxDepth - depth)
      loops(iterations, depth)
      depth += 2
   }
   fmt.Printf("long lived tree of depth %d\t check: %d\n", maxDepth,
      checkTree(longLastingNode))
}
func loops(iterations, depth int) {
   check := 0
   item := 0
   for item < iterations {
      t := createTree(depth)
      check += checkTree(t)
      pool.Put(t)
      item++
   }
   fmt.Printf("%d\t trees of depth %d\t check: %d\n",
      iterations, depth, check)
}
func checkTree(n *Node) int {
   if n.left == nil {
      // parent will sync.Pool.Put
      return 1
   }
   check := checkTree(n.left) + checkTree(n.right) + 1
   pool.Put(n.left)
   n.left = nil
   pool.Put(n.right)
   n.right = nil
   return check
}
func createTree(depth int) *Node {
   node := pool.Get().(*Node)
   if depth > 0 {
      depth--
      node.left = createTree(depth)
      node.right = createTree(depth)
   }
   return node
}
func main() {
   n := 0
   flag.Parse()
   if flag.NArg() > 0 {
      n, _ = strconv.Atoi(flag.Arg(0))
   }
   maxDepth := n
   if minDepth+2 > n {
      maxDepth = minDepth + 2
   }
   {
      stretchDepth := maxDepth + 1
      t := createTree(stretchDepth)
      check := checkTree(t)
      pool.Put(t)
      fmt.Printf("stretch tree of depth %d\t check: %d\n", stretchDepth, check)
   }
   trees(maxDepth)
}

Powyższy program tworzy wielokrotnie drzewo binarne, czyli strukturę składającą się z wielu węzłów (Node), z których każdy ma dwa wskaźniki łączące węzeł z dokładnie dwoma węzłami potomnymi — lewym i prawym.

Trzy poziomy drzewa binarnego pokazano na poniższym rysunku.

Za tworzenie drzewa odpowiada rekurencyjna funkcja createTree a następnie liczba węzłów w drzewie jest liczona za pomocą funkcją checkTree, która jednocześnie dokonuje destrukcji drzewa zwalniając wszystkie węzły.

Operacja tworzenia i niszczenia drzewa wykonywana jest wielokrotnie (funkcja loops) z kolejno zwiększającą się wysokością drzewa. Liczba iteracji wyznaczana jest w funkcji trees, która dodatkowo alokuje jedno drzewo o maksymalnej wskazanej głębokości na cały czas testu.

Jak nie trudno się domyślić, benchmark testuje wydajność i efektywność alokacji pamięci na stercie.

Mamy tu dwie kwestie:

1. Szybkość alokacji wielu małych obiektów
2. Obsługa zwalniania pamięci.

Taki test jest szczególnie obciążający dla platform wykorzystujących Garbage Collector. Mamy setki tysięcy małych obiektów z referencjami między sobą. To powoduje, że podczas odśmiecania, GC musi przebiec po wszystkich tych obiektach, żeby ustalić, które z nich są żywe (tj. gdzieś w programie jest odwołanie do drzewa obiektów, co oznacza, że należy zachować je przy życiu), a które już nie posiadają odwołań, co oznacza, że pamięć przez nie zajmowana może być oznaczona jako wolna i posłużyć w kolejnych alokacjach.

Wiedząc to wszystko, można spokojnie przyjąć różnica w czasie wykonania programu w Java i Go jednoznacznie wskazuje, że Java ma prawie 6 razy lepszy Garbage Collector niż Go.

I w pewnym sensie tak jest. Java wykorzystuje generacyjny kolektor kompaktujący. To oznacza, że nowe obiekty tworzone są w specjalnym obszarze pamięci (“eden”), która jest zajmowana na zasadzie stosu (tj. istnieje wskaźnik, który mówi gdzie kończy się pamięć zajęta, a zaczyna wolna i każda alokacja kolejnego obiektu polega wyłącznie na przesunięciu tego wskaźnika). Gdy zajęty został cały obszar pamięci dla nowych obiektów, GC przebiega po nich sprawdzając, które są wciąż żywe i kopiuje je do innego obszaru pamięci, wskaźnik ustawiany jest znów na początek i mamy wolną pamięć na kolejne alokacje (bardzo to upraszczam, ale idea jest mniej więcej wyjaśniona).

To oznacza oczywiście, że JVM zmienia adresy zaalokowanych obiektów i trzeba zatrzymać działanie programu i zaktualizować wskaźniki, które na nie wskazują, ale sama alokacja jest faktycznie bardzo szybka.

W Go GC działa inaczej — nie ma generacji, czyli sekcji “nowe obiekty” i “stare obiekty” (Java ma trzy generacje). Raz zaalokowany obiekt nigdy nie zmienia swojego adresu ale alokacja tych obiektów trwa dłużej — trzeba po prostu znaleźć dla nich miejsce na stercie.

Nie ma przesuwania obiektów, nie ma kompaktowania sterty (czyli przesuwania obiektów tak, żeby odzyskać duże obszary wolnej pamięci), ale za to w większym stopniu możliwe jest działania GC równolegle do właściwego programu.

Benchmark wydaje się jednak pokazywać, że rozwiązanie Go się nie sprawdza — podejście Java jest dużo efektywniejsze. Ta wersja mikrobenchmarku Go korzysta nawet z puli obiektów (sync.Pool — obiekty, które nie są już potrzebne, są zwracane do puli, żeby zmniejszyć liczbę alokacji na stercie) i dalej jest wściekle wolna, w porównaniu do Javy.

Co zatem Go robi źle?

Otóż nic — ma zupełnie inne podejście. W Javie praktycznie nie ma innej możliwości niż zaalokowanie obiektu na stercie. Jeśli robię tablicę 100 obiektów typu “MojaKlasa”, to na stercie alokowanych jest 100 niezależnych obiektów oraz sto pierwszy obiekt — sama tablica. Tablica trzyma 100 wskaźników do moich 100 obiektów. Ponieważ każde utworzenie obiektu w Javie musi odbyć się na stercie, GC Javy ma wyrafinowane mechanizmy zapewniające, że te alokacje są bardzo efektywne. Nie dotyczy to wyłącznie typów podstawowych (np. intlub char), które w takiej tablicy zostaną zaalokowane jako ciągły obszar bajtów (referencje technicznie też są zrealizowane jako wskaźniki, które można potraktować jako typy proste, ale Java nie daje żadnego dostępu do tych wskaźników, poza oczywiście referencją do wskazywanego obiektu).

W Go tak nie jest.

Go ma kilka typów referencyjnych (np. chan, slice, map albo string), ale posiada też wskaźniki oraz value types! W Javie tylko zmienne typu int, bool, char etc są wartościami. W Go prawie wszystko jest wartością. Chyba, że potrzebujemy wskaźnika, wtedy wyrażamy to wprost, np var intPtr *int. Ta gwiazdka oznacza, że zmienna intPtr jest wskaźnikiem na wartość int. Zamiast int może być jednak dowolny obiekt — np. nasza struktura Node z powyższego programu.

Kolejna ważna rzecz — w Go można pobrać wskaźnik do wszystkiego co jest adresowalne. A większość obiektów jest: można mieć adres funkcji, adres dowolnej zmiennej, ale też co jest istotne — adres do składowej naszej struktury albo adres do elementu tablicy.

Na przykład:

type Moja struct {
  a int
  b int
}
// ....
// "moja" jest zmienną o rozmiarze dwu int-ów i jest to wartość.
// w przykładzie poniżej zostanie zaalokowana na stosie - tj. w ogóle nie trafia na stertę
moja := Moja{
  a: 1,
  b: 2,
}
// dzięki użyciu operatora &, zmienna mojaPtr jest wskaźnikiem do obiektu typu Moja. Obiekt został zaalokowany na stercie.
mojaPtr := &Moja{
  a: 10,
  b: 20,
}
// zmieniam wartość wskaźnika mojaPtr i przypisuję do niego adres obiektu "moja" (tego utworzone wcześniej)
mojaPtr = &moja
// i tu najlepsze mogę tez pobrać adres składowej obiektu:
var intPtr *int
intPtr = &moja.b
// i tablice - tablica 10 obiektów Moja (pojedynczy, ciągły blok 
// pamięci, w którym mieści się 10 obiektów Moja, czyli 20 int-ów
var tab [10]Moja
// mojaPtr wskazuje na ostatni element tablicy
mojaPtr = &tab[9]

Te cechy języka powodują, że:

1. Nie jest potrzebny specjalny “eden” na stercie, ponieważ krótko żyjące obiekty mogą być z powodzeniem tworzone na stosie, który będzie pełnił taką samą rolę.

2. Zaalokowanie tablicy obiektów (nie ważne, czy na stosie, czy na stercie) gwarantuje, że te obiekty są wewnątrz ciągłego bloku pamięci i mogę odwoływać się do nich przez wskaźniki. Co jest fajne — jeśli sekwencyjnie iteruję po obiektach w ciągłym bloku RAM, CPU potrafi dużo efektywniej wykorzystywać cache, niż w przypadku, gdy skaczę chaotycznie po randomowych adresach.

3 Znacznie rzadziej występuje potrzeba alokowania obiektów na stercie, a dodatkowo mogę je tam alokować całymi grupami, a nie tylko pojedynczo.

Skoro tak, to czemu nie wykorzystać tych właściwości. Zmieniłem program w taki oto sposób:

package main
import (
 "flag"
 "fmt"
 "strconv"
)
type Node struct {
   left, right *Node
}
// --- Istotne zmiany:
var pool = NewArena[Node](1000)
type Arena[N any] struct {
 nodes []N
 chunk int
}
func NewArena[N any](size int) Arena[N] {
 return Arena[N] {
  chunk: size,
  nodes: make([]N, 0, size),
 }
}
func (arena *Arena[N]) New() *N {
    if len(arena.nodes) == 0 {
        arena.nodes = make([]N, arena.chunk)
    }
    n := &(arena.nodes)[len(arena.nodes)-1]
    arena.nodes = (arena.nodes)[:len(arena.nodes)-1]
    return n
}
// -- koniec
const minDepth = 4
func trees(maxDepth int) {
   longLastingNode := createTree(maxDepth)
   depth := 4
   for depth <= maxDepth {
      iterations := 1 << uint(maxDepth-depth+minDepth) // 16 << (maxDepth - depth)
   loops(iterations, depth)
      depth += 2
   }
   fmt.Printf("long lived tree of depth %d\t check: %d\n", maxDepth,
      checkTree(longLastingNode))
}
func loops(iterations, depth int) {
   check := 0
   item := 0
   for item < iterations {
      t := createTree(depth)
      check += checkTree(t)
      item++
   }
   fmt.Printf("%d\t trees of depth %d\t check: %d\n",
      iterations, depth, check)
}
func checkTree(n *Node) int {
   if n.left == nil {
      // parent will sync.Pool.Put
      return 1
   }
   check := checkTree(n.left) + checkTree(n.right) + 1
   n.left = nil
   n.right = nil
   return check
}
func createTree(depth int) *Node {
   node := pool.New()
   if depth > 0 {
      depth--
      node.left = createTree(depth)
      node.right = createTree(depth)
   }
   return node
}
func main() {
   n := 0
   flag.Parse()
   if flag.NArg() > 0 {
      n, _ = strconv.Atoi(flag.Arg(0))
   }
   maxDepth := n
   if minDepth+2 > n {
      maxDepth = minDepth + 2
   }
   {
      stretchDepth := maxDepth + 1
      t := createTree(stretchDepth)
      check := checkTree(t)
      fmt.Printf("stretch tree of depth %d\t check: %d\n", stretchDepth, check)
   }
   trees(maxDepth)
}

Istotne zmiany oznaczyłem komentarzem. Reszta była tylko prostym dostosowaniem kodu do nowego wywołania New() i usunięciem zbędnych w tej wersji wywołań pool.Put.

Nie będę szczegółowo opisywał na czym polega ten kod (używa generyków z go 1.18! :) ) ale istotniejsza jest idea. Nowy obiekt w go można utworzyć np .tak:

node := new(Node)

albo tak:

node := &Node{}

W obu wypadkach w zmiennej node pojawi się wskaźnik do utworzonego na stercie obiektu Node.

Jedno takie wywołanie, to jedna alokacja. Więc robię małą sztuczkę — stosuję własny alokator, który od zaalokuje tablicę 1000 obiektów node i zwróci wskaźnik do jednego z nich.

Moja metoda New zwraca obiekt z zaalokowanej tablicy (jest to wskaźnik na ostatni element tablicy):

n := &(arena.nodes)[len(arena.nodes)-1]
return n

Kolejne tworzenie obiektu nie powoduje już alokacji następnego obiektu ze sterty, tylko zwróci następny element z uprzednio zaalokowanej tablicy. Po 1000 takich wywołań stworzona zostanie kolejna tablica z tysiącem elementów. Efekt tego jest taki, że jest 1000 razy mniej alokacji i 1000 razy mnie obiektów na stercie (choć obiekty są 1000 razy większe).

Jaki będzie tego efekt? Na moim komputerze oryginalny program wykonywał się 21,550 sekund:

time ./binary-trees-6 21
stretch tree of depth 22  check: 8388607
2097152  trees of depth 4  check: 65011712
524288  trees of depth 6  check: 66584576
131072  trees of depth 8  check: 66977792
32768  trees of depth 10  check: 67076096
8192  trees of depth 12  check: 67100672
2048  trees of depth 14  check: 67106816
512  trees of depth 16  check: 67108352
128  trees of depth 18  check: 67108736
32  trees of depth 20  check: 67108832
long lived tree of depth 21  check: 4194303
real 0m21,550s
user 0m22,448s
sys 0m0,156s

A moja poprawiona wersja:

time ./binary-trees-ar 21
stretch tree of depth 22  check: 8388607
2097152  trees of depth 4  check: 65011712
524288  trees of depth 6  check: 66584576
131072  trees of depth 8  check: 66977792
32768  trees of depth 10  check: 67076096
8192  trees of depth 12  check: 67100672
2048  trees of depth 14  check: 67106816
512  trees of depth 16  check: 67108352
128  trees of depth 18  check: 67108736
32  trees of depth 20  check: 67108832
long lived tree of depth 21  check: 4194303
real 0m4,384s
user 0m8,965s
sys 0m0,142s

Czyli jest 4,9 razy szybszy!

Niezły wynik. Ale moje rozwiązanie nie jest jakoś szczególnie odkrywcze, więc dlaczego nikt na to nie wpadł i nie przesłał takiej wersji programu?

Otóż wpadłem na to kilka lat temu i wysłałem taką poprawioną wersję (nie było wtedy jeszcze generyków), ale została odrzucona, ponieważ regulamin (czy jak to nazwać) mówi, że nie można stosować dedykowanych/specyficznych alokatorów.

Nie wiem, czy wersja “generyczna” alokatora (tak jak ją przedstawiłem) już spełniałaby kryteria, ale to jest bez znaczenia, bo zrozumiałem wtedy, że celem tych benchmarków jest pokazanie silnych i słabych stron platformy, a nie odpowiedź na pytanie, który język jest “szybszy”.

Z tego można wyciągnąć parę wniosków:

1. Nie kłóć się o to, który język jest szybszy, podpierając mikrobenchmarkami, bo nie taki jest ich cel i zawsze może się okazać, że ktoś w Pythonie stworzy szybszą implementację danego algorytmu niż Ty w C++ (albo assemblerze — niektórzy do dziś wierzą, że “assembler jest najszybszy”).
2. Mikrobenchmarki pokazują silne i słabe strony platformy — jak widzisz, że któraś z platform (runtime, maszyna wirtualna) w czymś niedomaga, to oznacza to, że nie należy próbować czegoś w ten sposób używać i należy znaleźć jakieś obejście. Każda platforma ma jakieś słabsze strony.
3. Nie pisz w Go programu będącego kalką kodu Java (ani C, ani C++). Każdy język ma swoją specyfikę, swoje idiomy. Należy je zrozumieć i wykorzystać wszystko to, co dany język ma najlepszego. Prawdopodobnie niektóre algorytmy mogą być w jakimś języku w ogóle trudne do efektywnej implementacji. Może należy wtedy użyć zupełnie innego algorytmu? Ważne jest osiągnięcie celu — droga do niego może być dowolna.

Tym niemniej przyspieszenie czego ponad 5 razy zawsze cieszy.

Dzięki, jeśli doszedłeś aż do tego miejsca ;)

Jeśli masz jakiś uwagi, napisz na @ark_r@mastodon.social

#go #golang #optymalizacja #benchmark

Kontakt ze mną: @ark_r@mastodon.social