Obsah
1. Základní optimalizace v Go aneb pomáháme překladači (3)
2. Práce s řetězci v programovacím jazyku Go
3. Postupné skládání řetězce s využitím operátoru konkatenace
4. Skládání znaků do bufferu s následným převodem bufferu na řetězec
5. Využití objektu strings.Builder
6. Předalokace paměti pro řetězec: varianta s bufferem
7. Předalokace paměti pro řetězec: varianta s objektem strings.Builder
8. Která varianta je nejvýhodnější?
9. Realizace benchmarků pro skládání řetězce znak po znaku
11. Grafická vizualizace výsledků benchmarků
12. Podrobnější analýza prováděných operací
13. Postupné skládání řetězce z menších řetězců
14. Realizace konstrukce řetězce s využitím objektů bytes.Buffer a strings.Builder
15. Realizace benchmarků pro skládání řetězce z menších řetězců
17. Grafická vizualizace výsledků benchmarků
18. Kde funkce pro konstrukci řetězce stráví nejvíce času?
19. Repositář s demonstračními příklady
1. Základní optimalizace v Go aneb pomáháme překladači (3)
V dnešní části seriálu o programovacím jazyku Go se opět seznámíme s některými dalšími optimalizacemi, které je v mnoha případech vhodné či nutné provádět na úrovni zdrojového kódu. Zabývat se budeme zdánlivě triviální úlohou: jak efektivně zkonstruovat řetězec skládáním jednotlivých znaků a/nebo kratších řetězců. Podobné operace se v praxi skutečně provádí, i když mohou být poněkud skryté. Typickým příkladem je šablonovací systém, který interně postupně „skládá“ výsledný řetězec (dokument); dalším příkladem jsou pak systémy pro generování a tisk logovacích informací – i zde je na konci celé činnosti nějaká forma řetězce získaná postupným skládáním z kratších statických či dynamicky počítaných částí.
2. Práce s řetězci v programovacím jazyku Go
Interně je řetězec v paměti uložen jako velmi jednoduchá struktura s ukazatelem na oblast paměti se sekvencí bajtů a s délkou řetězce. Samotná sekvence bajtů může být sdílená větším množstvím řetězců, protože řetězce jsou v Go neměnné (immutable):
type stringStruct struct {
str unsafe.Pointer
len int
}
// Variant with *byte pointer type for DWARF debugging.
type stringStructDWARF struct {
str *byte
len int
}
Pro zajímavost se podívejme na dvě funkce, které se v runtime při operacích s řetězci volají velmi často. Ostatně tyto funkce můžeme vidět i ve výsledcích činnosti profileru (viz benchmarky uvedené níže). Jedná se o funkci volanou pro alokaci paměti pro řetězec a o funkci pro spojení dvou či více řetězců (což je funkce volaná při použití operátoru +):
// rawstring allocates storage for a new string. The returned
// string and byte slice both refer to the same storage.
// The storage is not zeroed. Callers should use
// b to set the string contents and then drop b.
func rawstring(size int) (s string, b []byte) {
p := mallocgc(uintptr(size), nil, false)
return unsafe.String((*byte)(p), size), unsafe.Slice((*byte)(p), size)
}
// concatstrings implements a Go string concatenation x+y+z+...
// The operands are passed in the slice a.
// If buf != nil, the compiler has determined that the result does not
// escape the calling function, so the string data can be stored in buf
// if small enough.
func concatstrings(buf *tmpBuf, a []string) string {
idx := 0
l := 0
count := 0
for i, x := range a {
n := len(x)
if n == 0 {
continue
}
if l+n < l {
throw("string concatenation too long")
}
l += n
count++
idx = i
}
if count == 0 {
return ""
}
// If there is just one string and either it is not on the stack
// or our result does not escape the calling frame (buf != nil),
// then we can return that string directly.
if count == 1 && (buf != nil || !stringDataOnStack(a[idx])) {
return a[idx]
}
s, b := rawstringtmp(buf, l)
for _, x := range a {
copy(b, x)
b = b[len(x):]
}
return s
}
3. Postupné skládání řetězce s využitím operátoru konkatenace
Předpokládejme, že máme realizovat funkci, která zkonstruuje řetězec, a to takovým způsobem, že do něj bude postupně přidávat jednotlivé znaky (resp. přesněji řečeno runy). Pochopitelně se v této konkrétní podobě jedná o umělý příklad, jenž je ovšem postaven na reálných základech, protože podobně mohou pracovat i další algoritmy (dekomprimace, šablonovací systémy, některé logovací systémy atd.). Zde se navíc jedná o mezní případ, kdy se postupně přidávají jednotlivé znaky a ne celé sekvence znaků, ovšem tím líp bude celý problém patrný:
package main
func BuildStringUsingConcatenation(n int) string {
// budeme pouzivat primo retezec
s := ""
// postupne pridavani prvku do vysledneho retezce
for i := 0; i < n; i++ {
s += "*"
}
// vysledny retezec
return s
}
Toto řešení je z pohledu programátora velmi čisté a výsledek je snadno pochopitelný i testovatelný. Ovšem problém tohoto řešení spočívá v tom, že se interně bude prakticky neustále provádět realokace paměti, což ostatně bude velmi dobře patrné na výsledcích benchmarků.
s += '*' ./concatenation.go:9:3: invalid operation: s += '*' (mismatched types string and untyped rune)
4. Skládání znaků do bufferu s následným převodem bufferu na řetězec
Existují však alternativní řešení výše uvedeného problému? Ukazuje se, že existují a dokonce jich je několik; všechna tato řešení jsou přitom postavena na standardní knihovně programovacího jazyka Go. Jedno z těchto řešení používá standardní balíček bytes, konkrétně datový typ bytes.Buffer. Tento datový typ skutečně realizuje buffer, do kterého je možné přidávat jednotlivé znaky metodou WriteRune, přičemž přidávání sice taktéž vyžaduje realokaci paměti, ale ta by měla být provedena optimálnějším :-) způsobem (tedy s menší frekvencí). Tento buffer můžeme na konci převést na klasický řetězec metodou String, takže celý algoritmus můžeme přepsat do této podoby:
package main
import "bytes"
func BuildStringUsingStringBuffer(n int) string {
// budeme pouzivat buffer
var bb bytes.Buffer
// postupne pridavani prvku do vysledneho retezce
for i := 0; i < n; i++ {
bb.WriteRune('*')
}
// prevod objektu na retezec
return bb.String()
}
5. Využití objektu strings.Builder
Další varianta spočívá ve využití objektu (datového typu) nazvaného strings.Builder. Jak již název napovídá, je tento datový typ součástí standardního balíčku strings; jeho popis nalezneme na adrese https://pkg.go.dev/strings@go1.20.1#Builder. Práce s objektem strings.Builder je prakticky totožná s předchozím příkladem založeným na objektu bytes.Buffer. I zde totiž nalezneme metodu WriteRune určenou pro přidání dalšího znaku a metodu String určenou pro převod hodnoty uložené v tomto objektu na běžný řetězec. Úprava celého algoritmu je tedy triviální:
package main
import "strings"
func BuildStringUsingStringBuilder(n int) string {
// budeme pouzivat String Builder
var sb strings.Builder
// postupne pridavani prvku do vysledneho retezce
for i := 0; i < n; i++ {
sb.WriteRune('*')
}
// prevod objektu na retezec
return sb.String()
}
6. Předalokace paměti pro řetězec: varianta s bufferem
Vraťme se nyní k využití bufferu, tedy datového typu bytes.Buffer. Paměť pro buffer, tedy v našem případě pro sekvenci znaků, je totiž možné předalokovat, a to konkrétně zavoláním metody Grow. Díky tomu můžeme – samozřejmě za předpokladu, že dopředu známe či alespoň dokážeme odhadnout výslednou délku řetězce – provést alokaci paměťového bloku jen jedenkrát, a to na začátku celého algoritmu. Ostatně si to můžeme velmi snadno otestovat:
package main
import "bytes"
func BuildStringUsingPreallocatedStringBuffer(n int) string {
// budeme pouzivat buffer
var bb bytes.Buffer
// alokace pameti pro pozdeji vkladane prvky
bb.Grow(n)
// postupne pridavani prvku do vysledneho retezce
for i := 0; i < n; i++ {
bb.WriteRune('*')
}
// prevod objektu na retezec
return bb.String()
}
7. Předalokace paměti pro řetězec: varianta s objektem strings.Builder
A konečně – metoda Grow není dostupná pouze u objektů typu bytes.Buffer, ale i pro objekt strings.Builder, což nám umožňuje snadno předalokovat paměť i pro tento objekt. Samotný zápis programu se změní pouze nepatrně; vlastně se modifikuje pouze typ proměnné sb:
package main
import "strings"
func BuildStringUsingPreallocatedStringBuilder(n int) string {
// budeme pouzivat String Builder
var sb strings.Builder
// alokace pameti pro pozdeji vkladane prvky
sb.Grow(n)
// postupne pridavani prvku do vysledneho retezce
for i := 0; i < n; i++ {
sb.WriteRune('*')
}
// prevod objektu na retezec
return sb.String()
}
8. Která varianta je nejvýhodnější?
V předchozích kapitolách jsme si ukázali tři varianty postupného „lepení“ výsledného řetězce přidáváním dalších znaků resp. přesněji řečeno run. U variant postavených nad datovými strukturami bytes.Buffer a string.Builder jsme navíc mohli velmi snadno provést předalokaci bloku paměti, což vede (resp. by alespoň teoreticky mělo vést) ke zmenšení volání funkce pro kopii bloků dat při postupných paměťových realokacích. Ovšem která varianta konstrukce řetězce bude nejrychlejší a paměťově nejzajímavější v praxi? K tomuto účelu si vytvoříme sadu benchmarků, které budou postupně – tj. prozatím znak po znaku – konstruovat řetězec a vypisovat dosaženou rychlost. Pro realizaci benchmarků budou použity balíčky ze standardní knihovny jazyka Go, zejména balíček testing a konkrétně datový typ B představující realizaci benchmarku.
top - 13:07:52 up 65 days, 23:33, 3 users, load average: 3,14, 2,97, 2,51
Tasks: 327 total, 1 running, 325 sleeping, 0 stopped, 1 zombie
%Cpu0 : 11,8 us, 5,9 sy, 0,0 ni, 76,5 id, 0,0 wa, 0,0 hi, 5,9 si, 0,0 st
%Cpu1 : 18,8 us, 0,0 sy, 0,0 ni, 81,2 id, 0,0 wa, 0,0 hi, 0,0 si, 0,0 st
%Cpu2 : 11,8 us, 5,9 sy, 0,0 ni, 76,5 id, 0,0 wa, 0,0 hi, 5,9 si, 0,0 st
%Cpu3 : 25,0 us, 0,0 sy, 0,0 ni, 75,0 id, 0,0 wa, 0,0 hi, 0,0 si, 0,0 st
%Cpu4 : 25,0 us, 0,0 sy, 0,0 ni, 75,0 id, 0,0 wa, 0,0 hi, 0,0 si, 0,0 st
%Cpu5 : 6,2 us, 0,0 sy, 0,0 ni, 93,8 id, 0,0 wa, 0,0 hi, 0,0 si, 0,0 st
%Cpu6 : 18,8 us, 0,0 sy, 0,0 ni, 81,2 id, 0,0 wa, 0,0 hi, 0,0 si, 0,0 st
%Cpu7 : 47,1 us, 23,5 sy, 0,0 ni, 29,4 id, 0,0 wa, 0,0 hi, 0,0 si, 0,0 st
MiB Mem : 31893,9 total, 4228,9 free, 5697,8 used, 21967,2 buff/cache
MiB Swap: 662,2 total, 659,8 free, 2,4 used. 21328,6 avail Mem
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
2605576 ptisnovs 20 0 982076 97100 2068 S 193,3 0,3 23:10.61 string-builders
1 root 20 0 1300148 13312 8440 S 0,0 0,0 2366:31 systemd
2 root 20 0 0 0 0 S 0,0 0,0 0:10.90 kthreadd
3 root 0 -20 0 0 0 I 0,0 0,0 0:00.00 rcu_gp
4 root 0 -20 0 0 0 I 0,0 0,0 0:00.00 rcu_par_gp
6 root 0 -20 0 0 0 I 0,0 0,0 0:09.69 kworker/0:0H-events_highpri
8 root 0 -20 0 0 0 I 0,0 0,0 0:00.00 mm_percpu_wq
9 root 20 0 0 0 0 S 0,0 0,0 32:55.30 ksoftirqd/0
9. Realizace benchmarků pro skládání řetězce znak po znaku
Samotná realizace benchmarků je vlastně velmi přímočará, protože již máme připraveny všechny potřebné algoritmy a známe funkce a metody, které se musí použít. Každý konkrétní benchmark nejdříve zkonstruuje řetězec (svým vlastním způsobem) a následně zavolá funkci checkBuiltString, která zkontroluje, jestli má řetězec očekávanou délku a taktéž zda obsahuje očekávané znaky, což by měla být sekvence hvězdiček o délce N (kde N se zadává při spouštění benchmarků). Samotná kontrola obsahu řetězce se již nezapočítává do času benchmarku. Podívejme se nyní na úplný zdrojový kód benchmarků:
package main
import (
"bytes"
"strings"
"testing"
)
func checkBuiltString(b *testing.B, s *string) {
// kontrola delky vysledneho retezce
if len(*s) != b.N {
b.Fatal("Wrong string length")
}
// kontrola obsahu vysledneho retezce
for i, r := range *s {
if r != '*' {
b.Fatal("Wrong rune", r, "at index", i)
}
}
}
func BenchmarkBuildStringUsingConcatenation(b *testing.B) {
// budeme pouzivat primo retezec
s := ""
// postupne pridavani prvku do vysledneho retezce
for n := 0; n < b.N; n++ {
s += "*"
}
// zkontrolovat obsah vytvoreneho retezce po zastaveni casovace
b.StopTimer()
checkBuiltString(b, &s)
}
func BenchmarkBuildStringUsingStringBuffer(b *testing.B) {
// budeme pouzivat buffer
var bb bytes.Buffer
// postupne pridavani prvku do vysledneho retezce
for n := 0; n < b.N; n++ {
bb.WriteRune('*')
}
// prevod objektu na retezec
s := bb.String()
// zkontrolovat obsah vytvoreneho retezce po zastaveni casovace
b.StopTimer()
checkBuiltString(b, &s)
}
func BenchmarkBuildStringUsingPreallocatedStringBuffer(b *testing.B) {
// budeme pouzivat buffer
var bb bytes.Buffer
// alokace pameti pro pozdeji vkladane prvky
bb.Grow(b.N)
// postupne pridavani prvku do vysledneho retezce
for n := 0; n < b.N; n++ {
bb.WriteRune('*')
}
// prevod objektu na retezec
s := bb.String()
// zkontrolovat obsah vytvoreneho retezce po zastaveni casovace
b.StopTimer()
checkBuiltString(b, &s)
}
func BenchmarkBuildStringUsingStringBuilder(b *testing.B) {
// budeme pouzivat String Builder
var sb strings.Builder
// postupne pridavani prvku do vysledneho retezce
for n := 0; n < b.N; n++ {
sb.WriteRune('*')
}
// prevod objektu na retezec
s := sb.String()
// zkontrolovat obsah vytvoreneho retezce po zastaveni casovace
b.StopTimer()
checkBuiltString(b, &s)
}
func BenchmarkBuildStringUsingPreallocatedStringBuilder(b *testing.B) {
// budeme pouzivat String Builder
var sb strings.Builder
// alokace pameti pro pozdeji vkladane prvky
sb.Grow(b.N)
// postupne pridavani prvku do vysledneho retezce
for n := 0; n < b.N; n++ {
sb.WriteRune('*')
}
// prevod objektu na retezec
s := sb.String()
// zkontrolovat obsah vytvoreneho retezce po zastaveni casovace
b.StopTimer()
checkBuiltString(b, &s)
}
10. Výsledky benchmarků
Podívejme se nyní na výsledky benchmarků, které byly zjištěny pro N (tedy výslednou délku řetězce) postupně rostoucí v řadě 1, 10, 100, 1000, 10000 a 100000, což znamená, že počet znaků ve výsledném řetězci je v každé další iteraci desetkrát větší oproti předchozí iteraci.
Pro malou výslednou délku řetězce jsou rozdíly minimální a ne zcela vypovídající o prováděných operacích:
goos: linux goarch: amd64 pkg: string-builders cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkBuildStringUsingConcatenation-8 1 370.0 ns/op BenchmarkBuildStringUsingStringBuffer-8 1 765.0 ns/op BenchmarkBuildStringUsingPreallocatedStringBuffer-8 1 746.0 ns/op BenchmarkBuildStringUsingStringBuilder-8 1 635.0 ns/op BenchmarkBuildStringUsingPreallocatedStringBuilder-8 1 738.0 ns/op PASS
Na tomto benchmarku a benchmarku navazujícím se ukazuje, že inicializace a popř. převod výsledku na řetězec se postupně eliminují a začne narůstat význam výsledné délky řetězce:
goos: linux goarch: amd64 pkg: string-builders cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkBuildStringUsingConcatenation-8 10 197.60 ns/op BenchmarkBuildStringUsingStringBuffer-8 10 86.90 ns/op BenchmarkBuildStringUsingPreallocatedStringBuffer-8 10 95.10 ns/op BenchmarkBuildStringUsingStringBuilder-8 10 129.90 ns/op BenchmarkBuildStringUsingPreallocatedStringBuilder-8 10 72.70 ns/op PASS
goos: linux goarch: amd64 pkg: string-builders cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkBuildStringUsingConcatenation-8 100 95.02 ns/op BenchmarkBuildStringUsingStringBuffer-8 100 165.60 ns/op BenchmarkBuildStringUsingPreallocatedStringBuffer-8 100 13.55 ns/op BenchmarkBuildStringUsingStringBuilder-8 100 14.10 ns/op BenchmarkBuildStringUsingPreallocatedStringBuilder-8 100 32.82 ns/op PASS
Už u relativně krátkého řetězce o délce 1000 znaků se začíná ukazovat nevýhoda prosté konkatenace a naopak přednost předalokace paměti:
goos: linux goarch: amd64 pkg: string-builders cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkBuildStringUsingConcatenation-8 1000 242.80 ns/op BenchmarkBuildStringUsingStringBuffer-8 1000 34.08 ns/op BenchmarkBuildStringUsingPreallocatedStringBuffer-8 1000 5.595 ns/op BenchmarkBuildStringUsingStringBuilder-8 1000 22.61 ns/op BenchmarkBuildStringUsingPreallocatedStringBuilder-8 1000 4.322 ns/op PASS
Rozdíl mezi naivní konkatenací a ostatními variantami se ještě dále zvětšuje:
goos: linux goarch: amd64 pkg: string-builders cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkBuildStringUsingConcatenation-8 10000 693.60 ns/op BenchmarkBuildStringUsingStringBuffer-8 10000 8.015 ns/op BenchmarkBuildStringUsingPreallocatedStringBuffer-8 10000 4.251 ns/op BenchmarkBuildStringUsingStringBuilder-8 10000 4.221 ns/op BenchmarkBuildStringUsingPreallocatedStringBuilder-8 10000 3.420 ns/op PASS
goos: linux goarch: amd64 pkg: string-builders cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkBuildStringUsingConcatenation-8 100000 4318.000 ns/op BenchmarkBuildStringUsingStringBuffer-8 100000 5.693 ns/op BenchmarkBuildStringUsingPreallocatedStringBuffer-8 100000 3.219 ns/op BenchmarkBuildStringUsingStringBuilder-8 100000 4.333 ns/op BenchmarkBuildStringUsingPreallocatedStringBuilder-8 100000 2.797 ns/op PASS
Zajímavé je, že u dlouhých řetězců (zde milion znaků) již není předalokace tak významným prvkem pro výsledný čas. Stále hraje svoji roli, ale ne již tak zásadní, jako například u varianty s řetězcem o délce 1000 znaků:
goos: linux goarch: amd64 pkg: string-builders cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkBuildStringUsingConcatenation-8 1000000 46829.000 ns/op BenchmarkBuildStringUsingStringBuffer-8 1000000 4.672 ns/op BenchmarkBuildStringUsingPreallocatedStringBuffer-8 1000000 4.387 ns/op BenchmarkBuildStringUsingStringBuilder-8 1000000 4.735 ns/op BenchmarkBuildStringUsingPreallocatedStringBuilder-8 1000000 3.255 ns/op PASS
11. Grafická vizualizace výsledků benchmarků
Výsledky benchmarků uvedené v číselné podobě si pochopitelně můžeme převést do grafické podoby, což nám umožní lepší porovnání jednotlivých algoritmů:
Obrázek 1: Grafická vizualizace výsledků benchmarků pro N=1 až 10000, přepočteno na čas pro přidání jediného znaku.
Obrázek 2: Grafická vizualizace výsledků benchmarků pro N=1 až 1000000, přepočteno na čas pro přidání jediného znaku.
Obrázek 3: Kumulativní časy celkové doby trvání operace konstrukce řetězce pro N=1 až 10000.
12. Podrobnější analýza prováděných operací
Podrobnější informace o tom, které operace (funkce) se vlastně provádí při konkatenaci řetězců různými algoritmy, nám podá další standardní nástroj programovacího jazyka Go – profiler. Nejdříve ale musíme spustit benchmarky izolovaně a specifikovat přitom, že se má vygenerovat datový soubor s informacemi o volání funkcí:
$ go test -bench=BenchmarkBuildStringUsingConcatenation -benchtime=1000000x -cpuprofile concatenation.out $ go test -bench=BenchmarkBuildStringUsingStringBuffer -benchtime=1000000x -cpuprofile string_buffer.out $ go test -bench=BenchmarkBuildStringUsingStringBuilder -benchtime=1000000x -cpuprofile string_builder.out $ go test -bench=BenchmarkBuildStringUsingPreallocatedStringBuffer -benchtime=1000000x -cpuprofile preallocated_string_buffer.out $ go test -bench=BenchmarkBuildStringUsingPreallocatedStringBuilder -benchtime=1000000x -cpuprofile preallocated_string_builder.out
Dále se každý z vygenerovaných souborů analyzuje profilerem:
$ go tool pprof -http=:6060 profile.out
Obrázek 4: Konkatenace řetězců s využitím operátoru +: nejvíce času se stráví ve funkci pro přesuny bloků paměti.
Obrázek 5: Při použití objektu bytes.Buffer se čas stráví z 50% při přidávání znaků a dalších 50% času správcem paměti (což je ovšem spíše náhoda, že byl GC vůbec spuštěn).
Obrázek 6: Při použití objektu strings.Builder se čas stráví přidáváním znaků, tedy vlastním algoritmem.
13. Postupné skládání řetězce z menších řetězců
Ve druhé části dnešního článku si předchozí způsob konstrukce řetězců rozšíříme a nepatrně upravíme. Tentokrát nebudeme výsledný řetězec postupně skládat z jednotlivých znaků, ale z menších řetězců. V jazyce Go pro tento účel opět můžeme použít operátor spojování (konkatenace) řetězců, který je zcela korektní jak ze syntaktického, tak i sémantického pohledu, ovšem výsledek bude velmi pomalý (což si ověříme v benchmarku):
package main
func BuildStringUsingConcatenation(n int) string {
// budeme pouzivat primo retezec
s := ""
// postupne pridavani prvku do vysledneho retezce
for i := 0; i < n; i++ {
s += "foo "
}
// vysledny retezec
return s
}
14. Realizace konstrukce řetězce s využitím objektů bytes.Buffer a strings.Builder
Předchozí program lze upravit takovým způsobem, že namísto konkatenace řetězců použijeme objekty bytes.Buffer a strings.Builder. Ty totiž kromě výše použité metody WriteRune nabízí i metody WriteString, což umožňuje do bufferu resp. do builderu připojovat další řetězce. Výsledek pochopitelně na konci musíme převést na řetězec metodou String.
Varianta příkladu ze třinácté kapitoly převedená do podoby s objektem typu bytes.Buffer bude vypadat takto:
package main
import "bytes"
func BuildStringUsingStringBuffer(n int) string {
// budeme pouzivat buffer
var bb bytes.Buffer
// postupne pridavani prvku do vysledneho retezce
for i := 0; i < n; i++ {
bb.WriteString("foo ")
}
// prevod objektu na retezec
return bb.String()
}
Malou úpravou funkci změníme tak, aby se používal objekt typu strings.Builder:
package main
import "strings"
func BuildStringUsingStringBuilder(n int) string {
// budeme pouzivat String Builder
var sb strings.Builder
// postupne pridavani prvku do vysledneho retezce
for i := 0; i < n; i++ {
sb.WriteString("foo ")
}
// prevod objektu na retezec
return sb.String()
}
A pochopitelně máme opět pro oba datové typy k dispozici metodu Grow, která nám umožní předalokaci paměťového bloku:
package main
import "bytes"
func BuildStringUsingPreallocatedStringBuffer(n int) string {
// budeme pouzivat buffer
var bb bytes.Buffer
// alokace pameti pro pozdeji vkladane prvky
bb.Grow(n * len("foo "))
// postupne pridavani prvku do vysledneho retezce
for i := 0; i < n; i++ {
bb.WriteString("foo ")
}
// prevod objektu na retezec
return bb.String()
}
a:
package main
import "strings"
func BuildStringUsingPreallocatedStringBuilder(n int) string {
// budeme pouzivat String Builder
var sb strings.Builder
// alokace pameti pro pozdeji vkladane prvky
sb.Grow(n * len("foo "))
// postupne pridavani prvku do vysledneho retezce
for i := 0; i < n; i++ {
sb.WriteString("foo ")
}
// prevod objektu na retezec
return sb.String()
}
package main
import (
"fmt"
)
func main() {
const n = 20
s := BuildStringUsingConcatenation(n)
fmt.Println("Concatenation: ", s)
s2 := BuildStringUsingStringBuffer(n)
fmt.Println("StringBuffer (initially empty): ", s2)
s3 := BuildStringUsingPreallocatedStringBuffer(n)
fmt.Println("StringBuffer (preallocated): ", s3)
s4 := BuildStringUsingStringBuilder(n)
fmt.Println("StringBuilder (initially empty): ", s4)
s5 := BuildStringUsingStringBuilder(n)
fmt.Println("StringBuilder (preallocated): ", s5)
}
s výsledkem:
Concatenation: foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo StringBuffer (initially empty): foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo StringBuffer (preallocated): foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo StringBuilder (initially empty): foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo StringBuilder (preallocated): foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo
15. Realizace benchmarků pro skládání řetězce z menších řetězců
Na základě příkladů uvedených v předchozí kapitole můžeme sestavit benchmarky, které jednotlivé způsoby skládání řetězce z celé řady menších řetězců porovnají. Vstupní řetězec, který je neustále připojován ke konstruovanému řetězci, má délku sta znaků a vzhledem k tomu, že se jedná o znak „*“ z ASCII, je délka tohoto řetězce současně rovna 100 bajtům:
package main
import (
"bytes"
"strings"
"testing"
)
const appendedString = "****************************************************************************************************"
func checkBuiltString(b *testing.B, s *string) {
// kontrola delky vysledneho retezce
if len(*s) != len(appendedString)*b.N {
b.Fatal("Wrong string length", len(*s), b.N)
}
// kontrola obsahu vysledneho retezce
for i, r := range *s {
if r != '*' {
b.Fatal("Wrong rune", r, "at index", i)
}
}
}
func BenchmarkBuildStringUsingConcatenation(b *testing.B) {
// budeme pouzivat primo retezec
s := ""
// postupne pridavani podretezce do vysledneho retezce
for n := 0; n < b.N; n++ {
s += appendedString
}
// zkontrolovat obsah vytvoreneho retezce po zastaveni casovace
b.StopTimer()
checkBuiltString(b, &s)
}
func BenchmarkBuildStringUsingStringBuffer(b *testing.B) {
// budeme pouzivat buffer
var bb bytes.Buffer
// postupne pridavani podretezce do vysledneho retezce
for n := 0; n < b.N; n++ {
bb.WriteString(appendedString)
}
// prevod objektu na retezec
s := bb.String()
// zkontrolovat obsah vytvoreneho retezce po zastaveni casovace
b.StopTimer()
checkBuiltString(b, &s)
}
func BenchmarkBuildStringUsingPreallocatedStringBuffer(b *testing.B) {
// budeme pouzivat buffer
var bb bytes.Buffer
// alokace pameti pro pozdeji vkladane prvky
bb.Grow(b.N * len(appendedString))
// postupne pridavani podretezce do vysledneho retezce
for n := 0; n < b.N; n++ {
bb.WriteString(appendedString)
}
// prevod objektu na retezec
s := bb.String()
// zkontrolovat obsah vytvoreneho retezce po zastaveni casovace
b.StopTimer()
checkBuiltString(b, &s)
}
func BenchmarkBuildStringUsingStringBuilder(b *testing.B) {
// budeme pouzivat String Builder
var sb strings.Builder
// postupne pridavani podretezce do vysledneho retezce
for n := 0; n < b.N; n++ {
sb.WriteString(appendedString)
}
// prevod objektu na retezec
s := sb.String()
// zkontrolovat obsah vytvoreneho retezce po zastaveni casovace
b.StopTimer()
checkBuiltString(b, &s)
}
func BenchmarkBuildStringUsingPreallocatedStringBuilder(b *testing.B) {
// budeme pouzivat String Builder
var sb strings.Builder
// alokace pameti pro pozdeji vkladane prvky
sb.Grow(b.N * len(appendedString))
// postupne pridavani podretezce do vysledneho retezce
for n := 0; n < b.N; n++ {
sb.WriteString(appendedString)
}
// prevod objektu na retezec
s := sb.String()
// zkontrolovat obsah vytvoreneho retezce po zastaveni casovace
b.StopTimer()
checkBuiltString(b, &s)
}
16. Výsledky benchmarků
Opět se podívejme na výsledky benchmarků všech pěti způsobů konstrukce řetězce z menších řetězů pro N rostoucí od 1 do 1000000, kde výsledná délka řetězce je rovna N×100 znakům.
Pro velmi malé počty iterací je inicializace potřebných datových struktur a popř. převod na klasický řetězec hlavním faktorem určujícím dobu trvání operace:
goos: linux goarch: amd64 pkg: string-builders cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkBuildStringUsingConcatenation-8 1 322.0 ns/op BenchmarkBuildStringUsingStringBuffer-8 1 2740.0 ns/op BenchmarkBuildStringUsingPreallocatedStringBuffer-8 1 3579.0 ns/op BenchmarkBuildStringUsingStringBuilder-8 1 2475.0 ns/op BenchmarkBuildStringUsingPreallocatedStringBuilder-8 1 370.0 ns/op PASS ok string-builders 0.002s goos: linux goarch: amd64 pkg: string-builders cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkBuildStringUsingConcatenation-8 10 1890.0 ns/op BenchmarkBuildStringUsingStringBuffer-8 10 2016.0 ns/op BenchmarkBuildStringUsingPreallocatedStringBuffer-8 10 123.8 ns/op BenchmarkBuildStringUsingStringBuilder-8 10 1013.0 ns/op BenchmarkBuildStringUsingPreallocatedStringBuilder-8 10 92.80 ns/op PASS ok string-builders 0.003s
Ale už pro N=100 je jasně patrné, že konkatenace je nejpomalejší operací a naopak se ukazuje přednost použití objektu strings.Builder:
goos: linux goarch: amd64 pkg: string-builders cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkBuildStringUsingConcatenation-8 100 1634.0 ns/op BenchmarkBuildStringUsingStringBuffer-8 100 344.7 ns/op BenchmarkBuildStringUsingPreallocatedStringBuffer-8 100 170.3 ns/op BenchmarkBuildStringUsingStringBuilder-8 100 186.3 ns/op BenchmarkBuildStringUsingPreallocatedStringBuilder-8 100 48.44 ns/op PASS ok string-builders 0.003s goos: linux goarch: amd64 pkg: string-builders cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkBuildStringUsingConcatenation-8 1000 5430.0 ns/op BenchmarkBuildStringUsingStringBuffer-8 1000 55.94 ns/op BenchmarkBuildStringUsingPreallocatedStringBuffer-8 1000 44.43 ns/op BenchmarkBuildStringUsingStringBuilder-8 1000 152.4 ns/op BenchmarkBuildStringUsingPreallocatedStringBuilder-8 1000 28.23 ns/op PASS ok string-builders 0.010s
Pro ještě větší hodnotu N se již stává prostá konkatenace neúnosnou operací (což ostatně odpovídá její teoretické časové složitosti):
goos: linux goarch: amd64 pkg: string-builders cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkBuildStringUsingConcatenation-8 10000 41270.0 ns/op BenchmarkBuildStringUsingStringBuffer-8 10000 81.49 ns/op BenchmarkBuildStringUsingPreallocatedStringBuffer-8 10000 70.64 ns/op BenchmarkBuildStringUsingStringBuilder-8 10000 136.1 ns/op BenchmarkBuildStringUsingPreallocatedStringBuilder-8 10000 16.45 ns/op PASS ok string-builders 0.423s goos: linux goarch: amd64 pkg: string-builders cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkBuildStringUsingConcatenation-8 100000 781287.0 ns/op BenchmarkBuildStringUsingStringBuffer-8 100000 126.2 ns/op BenchmarkBuildStringUsingPreallocatedStringBuffer-8 100000 42.36 ns/op BenchmarkBuildStringUsingStringBuilder-8 100000 138.0 ns/op BenchmarkBuildStringUsingPreallocatedStringBuilder-8 100000 20.56 ns/op PASS goos: linux goarch: amd64 pkg: string-builders-2 cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz BenchmarkBuildStringUsingConcatenation-8 1000000 6508452.0 ns/op BenchmarkBuildStringUsingStringBuffer-8 1000000 42.56 ns/op BenchmarkBuildStringUsingPreallocatedStringBuffer-8 1000000 24.46 ns/op BenchmarkBuildStringUsingStringBuilder-8 1000000 125.4 ns/op BenchmarkBuildStringUsingPreallocatedStringBuilder-8 1000000 22.31 ns/op PASS ok string-builders-2 6509.271s
17. Grafická vizualizace výsledků benchmarků
Opět se podívejme na grafickou vizualizaci výsledků vybraných benchmarků. Na prvním grafu je patrné, že i pro řetězce o relativně malé délce nemá příliš význam uvažovat o použití operátoru +, protože se z časového hlediska jedná o velmi pomalou operaci:
Obrázek 7: Grafická vizualizace výsledků benchmarků pro N=1 až 10000, přepočteno na čas pro přidání jediného znaku.
Zajímavější a užitečnější bude porovnání ostatních čtyř přístupů pro větší hodnoty N. Ze zobrazených výsledků můžeme vyčíst, že použití objektu strings.Builder má význam především tehdy, pokud dokážeme dopředu odhadnout délku výsledného řetězce a tudíž můžeme provést předalokaci paměti. Bez této předalokace se zdá být výhodnější využít objekt bytes.Buffer:
Obrázek 8: Průměrně časy připojení jednoho kratšího řetězce (sto znaků) ke konstruovanému řetězci. Klasická konkatenace není zobrazena vzhledem ke značně odlišným (mnohem delším) časům.
18. Kde funkce pro konstrukci řetězce stráví nejvíce času?
Podrobnější pohled na operace prováděné při konstrukci dlouhého řetězce různými způsoby nám opět zpřístupní profiler, který dokáže vypsat kumulativní časy strávené v jednotlivých funkcích ve standardní knihovně a/nebo v samotném runtime programovacího jazyka Go:
Obrázek 9: Konkatenace řetězců; nejvíce času se stráví v přesunech znaků mezi různými verzemi konstruovaného řetězce. Zbytek času zabere činnosti správce paměti (GC).
Obrázek 10: Použití strings.Builder s předalokovanou pamětí. Nejvíce času zabere převod na řetězec, který vyžaduje paměťový přesun (paradoxně se více času stráví v kontrole výsledků, než samotnou konstrukcí řetězce).
Obrázek 11: Použití bytes.Buffer s předalokovanou pamětí. Nejvíce času zaberou převody malých řetězců na sekvenci bajtů..
19. Repositář s demonstračními příklady
Zdrojové kódy všech demonstračních příkladů, na nichž byly popsány vybrané optimalizační techniky jazyka Go, 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ář, 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 - Techniques to Maximize Your Go Application’s Performance
https://golangdocs.com/techniques-to-maximize-your-go-applications-performance - Go language performance optimization
https://www.programmerall.com/article/8929467838/ - Ultimate Golang Performance Optimization Guide
https://www.bacancytechnology.com/blog/golang-performance - Optimizing a Golang service to reduce over 40% CPU
https://medium.com/coralogix-engineering/optimizing-a-golang-service-to-reduce-over-40-cpu-366b67c67ef9 - Tutorial for optimizing golang program
https://github.com/caibirdme/hand-to-hand-optimize-go/blob/master/README.md - How to optimise your Go code
https://codeburst.io/how-to-optimise-your-go-code-c6b27d4f1452 - Datový typ bytes.Buffer
https://pkg.go.dev/bytes@go1.20.1#Buffer - Datový typ strings.Builder
https://pkg.go.dev/strings@go1.20.1#Builder
ČLÁNKY DO MAILU