Obsah
1. Krátké ohlédnutí k problematice předávání parametrů hodnotou a odkazem
2. Role polí v programovacím jazyku Go
3. Řezy (slices) jako forma abstrakce nad „surovými“ poli
4. Řezy i pole se předávají hodnotou – co to ale konkrétně znamená?
5. Předávání polí a řezů: od teorie k praxi
9. Průchod všemi prvky pole či řezu
10. Benchmark měřicí dva způsoby průchodu polem
13. Benchmark měřicí dva způsoby průchodu mapou
15. Mutexy vs. kanály v roli synchronizační struktury
16. Benchmark: dva způsoby synchronizace
19. Repositář s demonstračními příklady
1. Krátké ohlédnutí k problematice předávání parametrů hodnotou a odkazem
V předchozím článku jsme se mj. zabývali technikou volání funkcí v jazyce Go. Řekli jsme si, že všechny parametry jsou předávány hodnotou a nikoli referencí. To by mohlo vést k dojmu, že uvnitř funkce (nebo metod) není možné modifikovat hodnotu parametru tak, aby to bylo zvenčí viditelné (tedy jinými slovy, že Go v tomto případě podporuje neměnitelné struktury). Ovšem ve skutečnosti tomu tak není; typickým příkladem jsou řezy, jejichž obsah je možné uvnitř funkce změnit. Podívejme se na jednoduchý příklad, v němž do funkce předáme řez, který je uvnitř funkce modifikován, přičemž změna je viditelná i vně funkce:
package main
import "fmt"
func changeMe(slice []int) {
slice[0] = 42
}
func main() {
// vytvoření řezu (nikoli pole)
s := []int{1, 2, 3}
fmt.Println(s)
changeMe(s)
fmt.Println(s)
}
Výsledek ukazuje, že byl řez skutečně modifikován, i když je předáván hodnotou a nikoli odkazem:
[1 2 3] [42 2 3]
Proč vlastně k tomuto chování dochází si vysvětlíme v navazujících kapitolách.
2. Role polí v programovacím jazyku Go
V programovacím jazyce Go se, ostatně podobně jako v mnoha dalších programovacích jazycích, setkáme s poli (array). Pole jsou v pojetí jazyka Go homogenní datovou strukturou, což v tomto kontextu znamená, že prvky pole mají vždy stejný a již v čase překladu známý typ, kterým ovšem může být v krajním případě i prázdné rozhraní (interface{}). Pole mají současně (minimálně v jazyce Go) neměnnou délku, kterou je nutné specifikovat již při vytváření pole a délka pole je součástí typu. Současně jsou ovšem pole plnohodnotnými datovými typy s vlastní sémantikou a dokonce i vlastními metadaty, na rozdíl od programovacího jazyka C, v němž je práce se skutečnými poli v mnoha případech omezena typovým systémem.
Podívejme se nejdříve na způsob definice pole bez jeho přímé inicializace. Prvky pole budou mít v takovém případě nulovou hodnotu (kde pojem „nulová hodnota“ záleží na tom, o jaký datový typ se jedná – může se totiž jednat i o struktury, jiná pole, řezy, ukazatele, řetězce atd.):
var a1 [10]byte
Pole ovšem můžeme současně inicializovat a navíc můžeme využít typové inference:
a3 := [10]int32{1,10,2,9,3,8,4,7,5,6}
„Čtení“ datového typu je zde provedeno přímočaře zleva doprava: „pole deseti prvků typu int32 s hodnotami 1,10 …“
Vytvořit pochopitelně můžeme i vícerozměrná pole:
var matice [10][10]float32
Pro zjištění délky pole použijeme funkci len, tj. například:
x := len(a1)
A pro přístup k prvkům se používají klasické hranaté závorky, přičemž první prvek má nulový index, podobně jako v dalších „céčkovských“ programovacích jazycích:
for i:= 0; i < len(a1); i++ {
a[i] = i*2;
}
Podívejme se nyní na úplný příklad, v němž se deklaruje a použije několik polí:
package main
import "fmt"
func main() {
var a1 [10]byte
var a2 [10]int32
a3 := [10]int32{1,10,2,9,3,8,4,7,5,6}
fmt.Printf("Delka pole 1: %d\n", len(a1))
fmt.Printf("Delka pole 2: %d\n", len(a2))
fmt.Printf("Delka pole 3: %d\n", len(a3))
var a[10]int
fmt.Printf("Pole pred upravou: %v\n", a)
for i:= 0; i < len(a1); i++ {
a[i] = i*2;
}
fmt.Printf("Pole po uprave: %v\n", a)
var matice [10][10]float32
fmt.Printf("Matice: %v\n", matice)
}
package main
import "fmt"
// je nutné uvést délku pole
func printLength(x [10]int) {
fmt.Println(len(x))
}
func main() {
// zde je délka pole vypočtena automaticky překladačem a doplněna na místo ...
x := [...]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
printLength(x)
}
Zajímavé bude zjistit, co se stane v případě, že v programu vytvoříme novou proměnnou a přiřadíme jí pole:
a2 := a1
V tomto případě se sémantika odlišuje podle použitého jazyka:
- V jazyce Go se provede skutečná kopie pole, takže výsledkem budou dvě na sobě nezávislá pole.
- V Javě (například) se jen přiřadí reference, takže dvě proměnné budou ukazovat na stejné pole.
Chování Go si můžeme velmi snadno otestovat na následujícím příkladu, v němž nejprve vytvoříme kopii pole a posléze původní pole změníme:
package main
import "fmt"
func main() {
var a1[10]int
a2 := a1
fmt.Printf("Pole 1: %v\n", a1)
fmt.Printf("Pole 2: %v\n", a2)
for i:= 0; i <len(a1); i++ {
a1[i] = i*2;
}
fmt.Printf("Pole 1: %v\n", a1)
fmt.Printf("Pole 2: %v\n", a2)
}
Výsledek odpovídá předchozímu popisu – pole jsou odlišná:
Pole 1: [0 0 0 0 0 0 0 0 0 0] Pole 2: [0 0 0 0 0 0 0 0 0 0] Pole 1: [0 2 4 6 8 10 12 14 16 18] Pole 2: [0 0 0 0 0 0 0 0 0 0]
Přibližně syntakticky (ne ovšem sémanticky!) ekvivalentní program v Javě by mohl vypadat takto:
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] a1 = new int[10];
int[] a2 = a1;
for (int i=0; i<a1.length; i++) {
a1[i] = i*2;
}
System.out.println(Arrays.toString(a1));
System.out.println(Arrays.toString(a2));
}
}
Po překladu a spuštění se ovšem vypíšou dva stejné řádky – to znamená, že v programové smyčce jsme měnili prvky pole sdíleného mezi proměnnými a1 a a2:
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18] [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
3. Řezy (slices) jako forma abstrakce nad „surovými“ poli
Jak jsme si již řekli v předchozí kapitole, nemusí být klasické pole dostatečně flexibilní datovou strukturou, která by plně vyhovovala potřebám vytvářené aplikace popř. implementovaného algoritmu. Pro dosažení větší flexibility byl do programovacího jazyka Go přidán další datový typ nazývaný řez neboli slice. Interně se jedná o referenci na automaticky vytvořené pole nebo na pole, které je explicitně „nasalámováno“ operací, s níž se seznámíme v navazující kapitole. Každý řez je v operační paměti uložen ve formě trojice hodnot (jde o záznam – struct či record):
- Ukazatele (reference) na zvolený prvek pole s daty, ke kterým přes řez přistupujeme.
- Délky řezu, tj. počtu prvků.
- Kapacity řezu (do jaké míry může řez narůstat v důsledku přidávání dalších prvků).
Tato interní struktura řezů s sebou přináší několik zajímavých důsledků. Je totiž možné, aby existovalo větší množství řezů ukazujících na obecně různé prvky jediného pole. Pokud nyní změníme prvek v jednom řezu, znamená to, že se vlastně modifikuje obsah původního pole a i ostatní řezy nový prvek uvidí. Co je však užitečnější – s řezy jako s datovým typem se velmi snadno pracuje; řezy mohou být předávány do funkcí, vráceny z funkcí atd.
4. Řezy i pole se předávají hodnotou – co to ale konkrétně znamená?
V jazyce Go se všechny parametry předávají do funkcí a metod hodnotou, což znamená, že interně vždy dochází ke kopii hodnoty. To platí i pro pole (na rozdíl od mnoha jiných programovacích jazyků), takže pole uvnitř funkce je kopií původního pole. V případě, že potřebujeme předat ukazatel na pole, je nutné tuto operaci explicitně zapsat do zdrojového kódu. Jak je tomu u řezů (slices)? Ty se taktéž předávají hodnotou, což znamená, že se provede kopie řezu. Ovšem jak již víme z předchozího textu, je řez reprezentován trojicí hodnot (velikost, kapacita, ukazatel na pole). Tyto hodnoty jsou zkopírovány (tj. například nelze změnit velikost řezu), ovšem samotné pole kopírováno není, protože v řezu je uložen pouze ukazatel na něj. To mj. znamená, že pole, na které se řez odkazuje, je možné uvnitř funkcí modifikovat (jinými slovy – Go nezaručuje absolutní neměnnost hodnot!). To ovšem platí i ve chvíli, kdy je pole součástí datové struktury:
Změna pole interně používaného řezem:
package main
import "fmt"
type Employee struct {
id int
name string
wages []int
}
func changeMe(employee Employee) {
employee.id = -1
employee.name = "Someone else"
employee.wages[0] = -1
}
func main() {
franta := Employee{
id: 1,
name: "Franta",
wages: []int{30000, 32000, 30500, 29900},
}
fmt.Println(franta)
changeMe(franta)
fmt.Println(franta)
}
Výsledky, z nichž je patrné, že pole referencované přes řez lze uvnitř funkce modifikovat:
$ go run pass_by_value_2.go
{1 Franta [30000 32000 30500 29900]}
{1 Franta [-1 32000 30500 29900]}
Předání struktury s polem:
package main
import "fmt"
const MONTHS = 12
type Employee struct {
id int
name string
wages [MONTHS]int
}
func changeMe(employee Employee) {
employee.id = -1
employee.name = "Someone else"
employee.wages[0] = -1
}
func main() {
franta := Employee{
id: 1,
name: "Franta",
wages: [...]int{30000, 32000, 30500, 29900, 10000, 35000, 30000, 32000, 30500, 29900, 10000, 35000},
}
fmt.Println(franta)
changeMe(franta)
fmt.Println(franta)
}
Výsledky ukazující, že modifikace pole uvnitř funkce changeMe je pouze lokální:
$ go run pass_by_value_3.go
{1 Franta [30000 32000 30500 29900 10000 35000 30000 32000 30500 29900 10000 35000]}
{1 Franta [30000 32000 30500 29900 10000 35000 30000 32000 30500 29900 10000 35000]}
5. Předávání polí a řezů: od teorie k praxi
Nyní již víme, jakým způsobem se předávají pole a řezy do funkcí a metod. Ajťácký selský rozum by tedy mohl napovídat, že u delších polí se bude provádět časově a paměťově velmi náročná kopie pole. Pojďme si tedy tento předpoklad ověřit na benchmarku, který bude volat (interně) podobné funkce, kterým se bude předávat řez, pole hodnotou a pole přes ukazatel (tedy vlastně odkazem). Tyto funkce budou modifikovat první a poslední prvek pole (protože přes řez se interně předává ukazatel na pole):
package main
import (
"testing"
)
const MAX_VALS = 1000
const DEFAULT_VALUE = 0
const FIRST_VALUE = -1
const LAST_VALUE = -2
func changeMe1(values []int) {
values[0] = FIRST_VALUE
values[MAX_VALS-1] = LAST_VALUE
}
func changeMe2(values [MAX_VALS]int) {
values[0] = FIRST_VALUE
values[MAX_VALS-1] = LAST_VALUE
}
func changeMe3(values *[MAX_VALS]int) {
values[0] = FIRST_VALUE
values[MAX_VALS-1] = LAST_VALUE
}
func BenchmarkPassSlice(b *testing.B) {
var values []int = make([]int, MAX_VALS)
for i := 0; i < b.N; i++ {
changeMe1(values)
}
if values[0] != FIRST_VALUE {
b.Fatal()
}
if values[MAX_VALS-1] != LAST_VALUE {
b.Fatal()
}
}
func BenchmarkPassArrayByValue(b *testing.B) {
var values [MAX_VALS]int = [MAX_VALS]int{DEFAULT_VALUE}
for i := 0; i < b.N; i++ {
changeMe2(values)
}
if values[0] != DEFAULT_VALUE {
b.Fatal()
}
if values[MAX_VALS-1] != DEFAULT_VALUE {
b.Fatal()
}
}
func BenchmarkPassArrayByReference(b *testing.B) {
var values [MAX_VALS]int = [MAX_VALS]int{DEFAULT_VALUE}
for i := 0; i < b.N; i++ {
changeMe3(&values)
}
if values[0] != FIRST_VALUE {
b.Fatal()
}
if values[MAX_VALS-1] != LAST_VALUE {
b.Fatal()
}
}
6. Výsledky benchmarku
Vyzkoušejme si nyní benchmark, jehož zdrojový kód byl uveden v předchozí kapitole, spustit. Výsledky nás možná překvapí:
$ go test -bench=. -benchtime=100000000x -cpuprofile profile.out goos: linux goarch: amd64 pkg: parameters-benchmark cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkPassSlice-8 100000000 0.4799 ns/op BenchmarkPassArrayByValue-8 100000000 0.2371 ns/op BenchmarkPassArrayByReference-8 100000000 0.4740 ns/op PASS ok parameters-benchmark 0.305s
Z výsledků vyplývá, že předávání polí hodnotou je nejrychlejší operací! Ovšem není tomu tak z toho důvodu, že by neustálé kopie tisíce hodnot typu int nějakým způsobem zrychlovalo operace prováděné mikroprocesorem. Důvod je jednoduchý – překladač programovacího jazyka Go zdetekoval, že operace s polem prováděná uvnitř funkce change2 není vně funkce viditelná (modifikace lokální kopie pole) a celé volání funkce odstranil (a posléze linker odstranil i objektový kód této funkce).
K témuž závěru můžeme dojít po otevření výsledků profileru, který se spustí příkazem:
$ go tool pprof -http=:6060 profile.out
Obrázek 1: Z benchmarku BenchmarkPassArrayByValue se ve skutečnosti žádná testovaná funkce nevolá.
Obrázek 2: I z tohoto výsledku je patrné, že se volají pouze funkce changeMe1 a changeMe3.
7. Reálnější benchmark
Abychom obešli optimalizaci kódu bez vnějšího efektu, upravíme předchozí benchmark do podoby, v níž se bude pole/řez nejenom modifikovat (ať již lokálně či globálně), ale vrátíme i nějakou hodnotu z této datové struktury. Takové funkce již není možné z výsledného kódu jednoduše odstranit a na druhou stranu je překladač jazyka Go dostatečně „hloupý“ na to, aby provedl inlining následovaný eliminací kopie atd.:
package main
import (
"testing"
)
const MAX_VALS = 1000
const DEFAULT_VALUE = 0
const FIRST_VALUE = -1
const LAST_VALUE = -2
func changeMe1(values []int) int {
values[0] = FIRST_VALUE
values[MAX_VALS-1] = LAST_VALUE
return values[MAX_VALS/2]
}
func changeMe2(values [MAX_VALS]int) int {
values[0] = FIRST_VALUE
values[MAX_VALS-1] = LAST_VALUE
return values[MAX_VALS/2]
}
func changeMe3(values *[MAX_VALS]int) int {
values[0] = FIRST_VALUE
values[MAX_VALS-1] = LAST_VALUE
return values[MAX_VALS/2]
}
func BenchmarkPassSlice(b *testing.B) {
var values []int = make([]int, MAX_VALS)
for i := 0; i < b.N; i++ {
r := changeMe1(values)
if r != DEFAULT_VALUE {
b.Fatal()
}
}
if values[0] != FIRST_VALUE {
b.Fatal()
}
if values[MAX_VALS-1] != LAST_VALUE {
b.Fatal()
}
}
func BenchmarkPassArrayByValue(b *testing.B) {
var values [MAX_VALS]int = [MAX_VALS]int{DEFAULT_VALUE}
for i := 0; i < b.N; i++ {
r := changeMe2(values)
if r != DEFAULT_VALUE {
b.Fatal()
}
}
if values[0] != DEFAULT_VALUE {
b.Fatal()
}
if values[MAX_VALS-1] != DEFAULT_VALUE {
b.Fatal()
}
}
func BenchmarkPassArrayByReference(b *testing.B) {
var values [MAX_VALS]int = [MAX_VALS]int{DEFAULT_VALUE}
for i := 0; i < b.N; i++ {
r := changeMe3(&values)
if r != DEFAULT_VALUE {
b.Fatal()
}
}
if values[0] != FIRST_VALUE {
b.Fatal()
}
if values[MAX_VALS-1] != LAST_VALUE {
b.Fatal()
}
}
8. Výsledky benchmarku
Opět si benchmark spustíme a zjistíme, jak se budou lišit časy volání funkcí s předáním pole hodnotou, odkazem a nepřímo přes řez:
$ go test -bench=. -benchtime=100000000x -cpuprofile profile.out goos: linux goarch: amd64 pkg: parameters-benchmark cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkPassSlice-8 100000000 0.4768 ns/op BenchmarkPassArrayByValue-8 100000000 135.3 ns/op BenchmarkPassArrayByReference-8 100000000 0.5629 ns/op PASS ok parameters-benchmark 13.734s
Nyní je vše jasné – předání pole hodnotou je podle očekávání (i podle ajťáckého selského rozumu) nejméně efektivní operací.
Pro úplnost se podívejme na výsledky získané profilerem:
$ go tool pprof -http=:6060 profile.out
Obrázek 3: Profiler zobrazí jen informace o druhém benchmarku, protože ten zabere prakticky 99% strojového času.
Obrázek 4: Tytéž informace jsou zobrazeny i na tomto reportu.
9. Průchod všemi prvky pole či řezu
Ve druhé části dnešního článku se budeme zabývat zdánlivě triviální úlohou. Na vstupu budeme mít pole nebo řez s prvky libovolného typu:
type item struct {
value int
payload [PAYLOAD_SIZE]byte
}
const MAX_ITEMS = 10000
var items [MAX_ITEMS]item
...
...
...
// inicializace prvků...
...
...
...
Naším úkolem bude projít všemi prvky pole (řezu) a vypočítat součet všech hodnot value. V jazyce Go se pro tento účel používá idiomatický zápis smyčky založený na klíčových slovech for a range:
for _, item := range items {
sum += item.value
}
Podstata problému spočívá v „maličkosti“ – hodnota každého prvku se bude kopírovat do lokální proměnné item. A to je potenciálně velká výkonnostní brzda, zejména pro interní smyčky (na tento problém jsme již několikrát narazili v praxi).
10. Benchmark měřicí dva způsoby průchodu polem
To, o jak velký problém se jedná, zjistíme dvojicí benchmarků, v nichž budeme jednou procházet prvky pole s využitím výše uvedené idiomatické programové smyčky a podruhé budeme „pouze“ přistupovat k prvkům pole přes jejich index, což je spíše „céčkový“ přístup vypadající následovně:
for j := 0; j < len(items); j++ {
sum += items[j].value
}
Zdrojový kód s benchmarky vypadá takto:
package main
import (
"testing"
)
const PAYLOAD_SIZE = 100
type item struct {
value int
payload [PAYLOAD_SIZE]byte
}
const MAX_ITEMS = 10000
func BenchmarkCountValues1(b *testing.B) {
b.StopTimer()
var items [MAX_ITEMS]item
for i := 0; i < len(items); i++ {
items[i].value = i
items[i].payload = [PAYLOAD_SIZE]byte{}
}
b.StartTimer()
for i := 0; i < b.N; i++ {
sum := 0
for _, item := range items {
sum += item.value
}
if sum != MAX_ITEMS/2*(MAX_ITEMS-1) {
b.Fatal(sum, MAX_ITEMS/2*(MAX_ITEMS-1))
}
}
}
func BenchmarkCountValues2(b *testing.B) {
b.StopTimer()
var items [MAX_ITEMS]item
for i := 0; i < len(items); i++ {
items[i].value = i
items[i].payload = [PAYLOAD_SIZE]byte{}
}
b.StartTimer()
for i := 0; i < b.N; i++ {
sum := 0
for j := 0; j < len(items); j++ {
sum += items[j].value
}
if sum != MAX_ITEMS/2*(MAX_ITEMS-1) {
b.Fatal(sum, MAX_ITEMS/2*(MAX_ITEMS-1))
}
}
}
11. Výsledky benchmarku
Benchmark spustíme pouze 100000×, protože každá testovaná operace spočívá v průchodu celým polem, což je sama o sobě dlouhotrvající operace v porovnání s předchozími benchmarky (které tak byly opakovány vícekrát):
$ go test -bench=. -benchtime=100000x goos: linux goarch: amd64 pkg: range-val-copy-1 cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkCountValues1-8 100000 70310 ns/op BenchmarkCountValues2-8 100000 10687 ns/op PASS ok range-val-copy-1 8.104s
Z výsledků je patrné, že první způsob průchodu programovou smyčkou (ten idiomatický) je přibližně sedmkrát pomalejší než způsob první. V tomto konkrétním případě jsou rozdíly tak velké zejména proto, že každý prvek pole je poměrně objemný.
Zajímavé bude zjistit, v jaké části kódu se stráví nejvíce času. Opět se, podobně jako tomu bylo v předchozím článku, jedná o rutinu duff copy, která je naprogramovaná v assembleru (rozbalená smyčka) a tedy obecně velmi rychlá:
File: range-val-copy-1.test
Type: cpu
Time: Dec 9, 2022 at 4:38pm (CET)
Duration: 8.42s, Total samples = 8.21s (97.51%)
Showing nodes accounting for 8.21s, 100% of 8.21s total
----------------------------------------------------------+-------------
flat flat% sum% cum cum% calls calls% + context
----------------------------------------------------------+-------------
6.67s 100% | testing.(*B).runN /opt/go/src/testing/benchmark.go:193
3.90s 47.50% 47.50% 6.67s 81.24% | range-val-copy-1.BenchmarkCountValues1 /home/ptisnovs/src/go-root/article_99/range-val-copy-1/parameters_test.go:31
0.22s 3.30% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:393
0.20s 3.00% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:408
0.18s 2.70% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:420
0.16s 2.40% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:413
0.16s 2.40% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:423
0.14s 2.10% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:418
0.13s 1.95% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:425
0.12s 1.80% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:392
0.11s 1.65% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:403
0.10s 1.50% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:398
0.10s 1.50% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:407
0.10s 1.50% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:412
0.09s 1.35% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:405
0.09s 1.35% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:410
0.08s 1.20% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:395
0.08s 1.20% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:402
0.08s 1.20% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:404
0.08s 1.20% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:414
0.08s 1.20% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:422
0.07s 1.05% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:397
0.07s 1.05% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:417
0.06s 0.9% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:400
0.06s 0.9% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:427
0.05s 0.75% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:415
0.05s 0.75% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:424
0.04s 0.6% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:399
0.04s 0.6% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:409
0.02s 0.3% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:394
0.01s 0.15% | runtime.duffcopy /opt/go/src/runtime/duff_amd64.s:419
----------------------------------------------------------+-------------
0.96s 100% | testing.(*B).runN /opt/go/src/testing/benchmark.go:193
0.96s 11.69% 59.20% 0.96s 11.69% | range-val-copy-1.BenchmarkCountValues2 /home/ptisnovs/src/go-root/article_99/range-val-copy-1/parameters_test.go:57
----------------------------------------------------------+-------------
0.31s 100% | testing.(*B).runN /opt/go/src/testing/benchmark.go:193
0.31s 3.78% 62.97% 0.31s 3.78% | range-val-copy-1.BenchmarkCountValues1 /home/ptisnovs/src/go-root/article_99/range-val-copy-1/parameters_test.go:32
----------------------------------------------------------+-------------
0.26s 100% | testing.(*B).runN /opt/go/src/testing/benchmark.go:193
0.26s 3.17% 66.14% 0.26s 3.17% | range-val-copy-1.BenchmarkCountValues2 /home/ptisnovs/src/go-root/article_99/range-val-copy-1/parameters_test.go:56
Kumulativní časy zobrazené graficky:
Obrázek 5: Výsledky benchmarku zobrazené graficky (pro odlišný počet běhů).
A konečně kumulativní časy zobrazené v tabulce:
Obrázek 6: Kumulativní časy benchmarků zobrazené v tabulkové podobě.
12. Průchod všemi prvky mapy
Programovací jazyk Go nabízí programátorům i možnost idiomatického zápisu programové smyčky určené pro průchod klíči a prvky mapy. Zápis je prakticky totožný, jako v případě polí či řezů, ovšem namísto indexů se vrací klíče:
for key, value := range items {
...
...
...
}
Ovšem opět platí, že klíče a hodnoty jsou v tomto případě kopírovány do lokálních proměnných key a value, což může u objemnějších datových struktur být dosti významným faktorem ovlivňujícím celkový výkon aplikace. Alternativně lze procházet jen klíči (což samo o sobě může vést ke kopiím, ovšem klíče nebývají příliš objemné) a k hodnotám mapy přistupovat přímo, ideálně k jejich adrese:
for key, _ := range items {
...
...
...
items[key]
...
...
...
}
13. Benchmark měřicí dva způsoby průchodu mapou
Abychom si oba výše zmíněné způsoby průchodu mapou otestovali a změřili jejich výpočetní složitost, použijeme opět benchmark, jenž nejdříve naplní mapu strukturami, z nichž každá má velikost přesahující 100 bajtů. Následně se ve smyčkách mapami projde a provede se výpočet, který zjistí, zda se skutečně prošlo všemi prvky mapy. Opět se ovšem měří pouze čas průchodu mapou, nikoli samotná alokace a inicializace mapy.:
package main
import (
"testing"
)
const PAYLOAD_SIZE = 100
type item struct {
value int
payload [PAYLOAD_SIZE]byte
}
const MAX_ITEMS = 10000
func BenchmarkCountValues1(b *testing.B) {
b.StopTimer()
var items map[int]item = make(map[int]item, MAX_ITEMS)
for i := 0; i < MAX_ITEMS; i++ {
items[i] = item{
value: i,
payload: [PAYLOAD_SIZE]byte{},
}
}
b.StartTimer()
for i := 0; i < b.N; i++ {
sum := 0
for _, item := range items {
sum += item.value
}
if sum != MAX_ITEMS/2*(MAX_ITEMS-1) {
b.Fatal(sum, MAX_ITEMS/2*(MAX_ITEMS-1))
}
}
}
func BenchmarkCountValues2(b *testing.B) {
b.StopTimer()
var items [MAX_ITEMS]item
for i := 0; i < len(items); i++ {
items[i].value = i
items[i].payload = [PAYLOAD_SIZE]byte{}
}
b.StartTimer()
for i := 0; i < b.N; i++ {
sum := 0
for key, _ := range items {
sum += items[key].value
}
if sum != MAX_ITEMS/2*(MAX_ITEMS-1) {
b.Fatal(sum, MAX_ITEMS/2*(MAX_ITEMS-1))
}
}
}
14. Výsledky benchmarku
Po spuštění benchmarku uvidíme ještě výraznější rozdíly v rychlosti, než tomu bylo v příkladu, v němž jsme procházeli (iterovali) prvky pole:
$ go test -bench=. -benchtime=100000x -cpuprofile profile.out goos: linux goarch: amd64 pkg: range-val-copy-1 cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkCountValues1-8 100000 144225 ns/op BenchmarkCountValues2-8 100000 12300 ns/op PASS ok range-val-copy-1 15.853s
Z grafického vyjádření je zřejmé, že největší množství času se strávilo ve funkci mapiternext, za níž následuje nám již známá (optimalizovaná) operace duff copy pro kopii hodnot.
Obrázek 7: Volání mapiternext a rutiny duff copy.
15. Mutexy vs. kanály v roli synchronizační struktury
Mezi nejlepší (a možná taktéž nejvíce diskutované) vlastnosti programovacího jazyka Go patří podpora takzvaných gorutin zajišťujících souběžný běh více funkcí, přičemž počet gorutin není prakticky omezen (bez problémů lze mít souběžně spuštěno například 100000 gorutin). Ovšem pochopitelně je nutné v aplikaci, v níž dochází k souběhu, dokázat mezi gorutinami předávat data. K tomu slouží buď kanály (channels) nebo sdílená paměť. V případě použití sdílené paměti je nutné použít buď atomické hodnoty nebo mutexy, které umožňují uzamčení části kódu tak, že k němu bude mít v daný okamžik přístup jen jediná gorutina (a v této části kódu je realizován přístup ke sdílené paměti).
Někdy se ovšem namísto mutexů používají pro zajištění exkluzivního přístupu taktéž kanály, které se ovšem nepoužijí pro přenosy dat mezi gorutinami, ale využívá se toho, že zápis i čtení z kanálů jsou blokující operace: čtení z prázdného kanálu vede k čekání na zápis jinou gorutinou a naopak zápis do plného kanálu vede k čekání na přečtení předchozí hodnoty jinou gorutinou.
16. Benchmark: dva způsoby synchronizace
Oba dva způsoby synchronizace mezi gorutinami se pravděpodobně budou lišit rychlostí operací. To si ostatně ověříme na benchmarku, jehož zdrojový kód je uveden pod tímto odstavcem. V tomto benchmarku je proveden souběžný (a většinou i paralelní) výpočet v několika subrutinách (souběžně může být spuštěno až 100 subrutin), které přistupují ke stejnému prvku i zvolené datové struktury. A právě při operaci přístupu je použit zámek (mutex nebo kanál) pro zajištění exkluzivity přístupu (alternativně lze použít i atomické typy):
package main
import (
"sync"
"testing"
)
type valueWithMutex struct {
i int
mutex *sync.Mutex
}
type valueWithChannel struct {
i int
channel chan struct{}
}
func (value *valueWithMutex) lock() {
value.mutex.Lock()
}
func (value *valueWithMutex) unlock() {
value.mutex.Unlock()
}
func (value *valueWithChannel) lock() {
// blokující přečtení hodnoty z kanálu
<-value.channel
}
func (value *valueWithChannel) unlock() {
// (blokující) zápis hodnoty do kanálu
value.channel <- struct{}{}
}
const MAX_ITEMS = 100
const EXPECTED_SUM = MAX_ITEMS / 2 * (MAX_ITEMS - 1)
func BenchmarkAccumulationMutexVariant(b *testing.B) {
var waitgroup sync.WaitGroup
value := &valueWithMutex{
mutex: new(sync.Mutex),
i: 0,
}
for n := 0; n < b.N; n++ {
value.i = 0
for i := 0; i < MAX_ITEMS; i++ {
waitgroup.Add(1)
go func(i int) {
value.lock()
defer value.unlock()
defer waitgroup.Done()
value.i += i
}(i)
}
waitgroup.Wait()
if value.i != EXPECTED_SUM {
b.Fatal(value.i, EXPECTED_SUM)
}
}
}
func BenchmarkAccumulationChannelVariant(b *testing.B) {
var waitgroup sync.WaitGroup
value := &valueWithChannel{
channel: make(chan struct{}, 1),
i: 0,
}
// ve výchozím stavu obsahuje kanál hodnotu
value.channel <- struct{}{}
for n := 0; n < b.N; n++ {
value.i = 0
for i := 0; i < MAX_ITEMS; i++ {
waitgroup.Add(1)
go func(i int) {
value.lock()
defer value.unlock()
defer waitgroup.Done()
value.i += i
}(i)
}
waitgroup.Wait()
if value.i != EXPECTED_SUM {
b.Fatal(value.i, EXPECTED_SUM)
}
}
}
17. Výsledky benchmarku
Po spuštění benchmarku, jehož zdrojový kód byl uveden v předchozí kapitole, získáme výsledky, které ukazují, že použití kanálu ve funkci synchronizační struktury není nejrychlejší způsob, protože klasické mutexy jsou přibližně dvakrát rychlejší:
$ go test -bench=. -benchtime=100000x goos: linux goarch: amd64 pkg: mutex-channel cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkAccumulationMutexVariant-8 100000 29044 ns/op BenchmarkAccumulationChannelVariant-8 100000 49570 ns/op PASS ok mutex-channel 7.864s
18. Shrnutí
Zajímavé je, že všechny optimalizace, které jsme si v dnešním článku ukázali, vlastně nutí programátory k opuštění idiomatického způsobu zápisu zdrojového kódu, tedy takového způsobu, který je doporučován a používán v oficiální dokumentaci, v učebnicích, v kurzech atd. Tyto optimalizace má tedy (většinou) smysl provádět až ve chvíli, kdy je takový kód volán velmi často (ve vnitřní smyčce atd.) a zejména tehdy, pokud jsou oba možné způsoby zápisu programu (idiomatický a optimalizovaný) ověřeny benchmarkem. Teprve v případě, že benchmark ukáže výrazné zlepšení, je vhodné zdrojový kód změnit, ideálně s případnými poznámkami pro kolegy (nebo budoucí já), v nichž bude vysvětleno, z jakého důvodu je daná část zdrojového kódu zkonstruována neidiomatickým způsobem. Neboli: pravidla je vhodné dodržovat, ovšem odborník by měl vědět, kdy je vhodné je porušit.
19. Repositář s demonstračními příklady
Zdrojové kódy všech minule i dnes použitých demonstračních příkladů byly uloženy do nového Git repositáře, který je dostupný na adrese https://github.com/tisnik/go-root (stále na GitHubu :-). V případě, že nebudete chtít klonovat celý repositář (ten je ovšem – alespoň prozatím – velmi malý, dnes má přibližně stovku kilobajtů), můžete namísto toho použít odkazy na jednotlivé demonstrační příklady, které naleznete v následující tabulce:
20. Odkazy na Internetu
- An Introduction to Benchmarking Your Go Programs
https://tutorialedge.net/golang/benchmarking-your-go-programs/ - How the Go runtime implements maps efficiently (without generics)
https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics - Go18DS (Go 1.18+ Data Structures)
https://github.com/daichi-m/go18ds - TreeMap v2
https://github.com/igrmk/treemap - Go Data Structures: Binary Search Tree
https://flaviocopes.com/golang-data-structure-binary-search-tree/ - Generics in Go
https://bitfieldconsulting.com/golang/generics - Tutorial: Getting started with generics
https://go.dev/doc/tutorial/generics - Gobs of data
https://blog.golang.org/gobs-of-data - Performance at Scale: MinIO Pushes Past 1.4 terabits per second with 256 NVMe Drives
https://blog.min.io/performance-at-scale-minio-pushes-past-1–3-terabits-per-second-with-256-nvme-drives/ - Benchmarking MinIO vs. AWS S3 for Apache Spark
https://blog.min.io/benchmarking-apache-spark-vs-aws-s3/ - Know Go: Generics (Kniha)
https://bitfieldconsulting.com/books/generics - Go 1.18 Generics based slice package
https://golangexample.com/go-1–18-generics-based-slice-package/ - Highly extensible Go source code linter providing checks currently missing from other linters
https://github.com/go-critic/go-critic - Fast linters runner for Go
https://github.com/golangci/golangci-lint - Checkers from the “performance” group
https://go-critic.com/overview#checkers-from-the-performance-group - rangeValCopy
https://go-critic.com/overview#rangeValCopy-ref - C vs Rust vs Go: performance analysis
https://medium.com/@marek.michalik/c-vs-rust-vs-go-performance-analysis-945ab749056c - Golang Performance Comparison | Why is GO Fast?
https://www.golinuxcloud.com/golang-performance/ - Go mutex vs channels benchmark
https://github.com/danil/go_mutex_vs_channels_benchmark
ČLÁNKY DO MAILU