Hlavní navigace

Základní optimalizace v Go aneb pomáháme překladači

8. 12. 2022
Doba čtení: 35 minut

Sdílet

 Autor: Depositphotos
Seznámíme se se základními optimalizacemi, které je v některých případech vhodné či nutné provádět na úrovni zdrojového kódu. Některé dále zmíněné optimalizace jsou (zdánlivě) triviální, na druhou stranu ovšem opomíjené.

Obsah

1. Základní optimalizace v Go aneb pomáháme překladači

2. Prázdné mapy vs. mapy s předběžnou alokací prvků

3. Benchmark: naplnění prázdné mapy a předalokované mapy

4. Odlišné použití map: mapy s prvky typu int

5. Mapy, jejichž klíče mají velikost 100 bajtů

6. Výsledky benchmarků, výsledky činnosti profileru

7. Mapa použitá ve funkci množiny

8. Výsledky benchmarků a profileru

9. Předávání datových struktur do funkcí a metod hodnotou či odkazem?

10. Syntaxe pro předávání struktur do funkcí a metod hodnotou a odkazem, způsob překladu do assembleru

11. Benchmark zjišťující rozdíly v rychlosti volání funkcí a metod s využitím hodnoty a reference na předávanou strukturu

12. Výsledky benchmarku i profileru

13. Mapy vs. řezy při implementaci jednoduché paměťové cache

14. Výsledky benchmarků

15. Grafické porovnání výsledků

16. Mapy vs. řezy při implementaci množiny

17. Výsledky benchmarku

18. Závěrečné zhodnocení – triviální a přitom mnohdy důležité optimalizace

19. Repositář s demonstračními příklady

20. Odkazy na Internetu

1. Základní optimalizace v Go aneb pomáháme překladači

Programovací jazyk Go je v současnosti mezi vývojáři poměrně oblíben, a to mj. i díky jeho velmi rychlému překladači a linkeru, který dokáže v několika sekundách přeložit i velmi rozsáhlé aplikace. Rychlost překladače je do určité míry umožněna syntaxí samotného programovacího jazyka Go, ovšem na druhou stranu je nutné si přiznat, že se překladač příliš nezdržuje optimalizacemi, což je mnohdy patrné z vygenerovaného strojového kódu i výsledného výkonu aplikací (pokud porovnáváme s C, Rustem atd., nikoli například s Pythonem :-). V dnešním článku se seznámíme se základními optimalizacemi, které je v některých případech nutné provádět na úrovni zdrojového kódu. Některé dále zmíněné optimalizace jsou (alespoň zdánlivě) triviální, na druhou stranu ovšem opomíjené. A další optimalizace jsou naopak neintuitivní a vlastně jdou i proti „zdravému rozumu“. Podrobnosti si řekneme v navazujících kapitolách.

Poznámka: nosnou myšlenkou dnešního článku je, že v praktických zadáních (například viz níže zmíněný požadavek na paměťovou cache explicitně navrženou pro malý počet prvků) mohou být zdánlivě méně efektivní algoritmy lepší, než sofistikovanější řešení. A proto je vhodné v případě potřeby provádět benchmarky, ideálně s reálnými daty (počet a velikost zpracovávaných prvků) a přímo na cílové platformě.

2. Prázdné mapy vs. mapy s předběžnou alokací prvků

Mapy jsou jedním z nejčastěji používaných kontejnerů, a to i v programovacím jazyku Go. Připomeňme si, že v Go je možné použít jako klíč prakticky jakýkoli datový typ, což užitečnost map ještě zvyšuje.

Existuje poměrně velké množství způsobů implementace map, přesněji řečeno způsobů ukládání dvojic klíč-hodnota do paměti s možností jejich pozdějšího přečtení. Jednotlivé implementace se od sebe odlišují svými základními vlastnostmi, například tím, zda jsou prvky v mapě setříděny na základě svého klíče, zda je naopak zachováno pořadí prvků podle pořadí jejich vkládání do mapy či zda jsou prvky obecně neuspořádány. Liší se i časové složitosti základních operací – tedy operace pro vložení prvku do mapy a operace pro získání prvku na základě jeho klíče. Navíc v některých případech vyžadujeme specifické chování mapy, například možnost mapování nejenom v jednom směru (tedy klasické klíč→hodnota), ale i ve směru opačném (hodnota→klíč). Toto chování realizují mapy, v jejichž jméně se objevuje zkratka „bidi“ (neboli bi-directional).

V rámci tohoto článku se zaměříme na základní implementaci map, která je nedílnou součástí samotného programovacího jazyka Go.

Poznámka: tak jako v jiných jazycích platí, že klíče použité v jedné mapě musí být unikátní; hodnoty však mohou být naprosto libovolné.

Ukažme si nyní způsob deklarace proměnné pojmenované m1, která je typu mapa celé číslo:řetězec:

var m1 map[int]string

Samozřejmě můžeme vytvořit i jinou mapu, konkrétně mapu s klíči typu string a hodnotami typu User

var m2 map[string]User

V dalším demonstračním příkladu vytvoříme proměnnou typu mapa a posléze se do ní pokusíme zapsat novou dvojici s klíčem rovným nule a hodnotou „nula“:

package main
 
import "fmt"
 
func main() {
        var m1 map[int]string
        fmt.Println(m1)
 
        m1[0] = "nula"
}

Při pokusu o spuštění tohoto příkladu ovšem dojde k běhové chybě, která vypadá takto:

map[]
panic: assignment to entry in nil map
 
goroutine 1 [running]:
main.main()
        /home/tester/go-root/article_03/15_uninitialized_map.go:16 +0x76
exit status 2

Co to znamená? Předchozí proměnná byla sice deklarována korektně, ovšem uplatnila se zde již dříve popsaná pravidla pro inicializaci hodnoty proměnné. Zde se konkrétně vytvořila mapa a byla jí přiřazena speciální hodnota nil – proto se nazývá nil-mapou. Pokud budeme skutečně chtít mapu použít (naplnit ji dvojicemi klíč-hodnota), musíme při inicializaci zavolat vestavěnou funkci make.

Korektní inicializace mapy je ukázána na dalším příkladu:

package main
 
import "fmt"
 
func main() {
        var m1 map[int]string = make(map[int]string)
        fmt.Println(m1)
 
        m1[0] = "nula"
        m1[1] = "jedna"
        m1[2] = "dva"
        m1[3] = "tri"
        m1[4] = "ctyri"
        m1[5] = "pet"
        m1[6] = "sest"
 
        fmt.Println(m1)
}

Po spuštění tohoto příkladu se nejdříve vypíše prázdná mapa a posléze mapa naplněná šesti dvojicemi:

map[]
map[6:sest 0:nula 1:jedna 2:dva 3:tri 4:ctyri 5:pet]
Poznámka: povšimněte si, že dvojice jsou vypsány v jiném pořadí, než jak byly vkládány do mapy. To je výchozí a očekávané chování této datové struktury.

Z hlediska výkonu aplikace je důležitý taktéž fakt, že do vestavěné funkce make je možné ve druhém parametru předat očekávanou kapacitu mapy. To povede k prealokaci paměti pro prvky, ovšem současně se nejedná o maximální kapacitu (mapa může mít více prvků, než je její prvotní kapacita):

package main
 
import "fmt"
 
func main() {
        var m1 map[int]string = make(map[int]string, 6)
        fmt.Println(m1)
 
        m1[0] = "nula"
        m1[1] = "jedna"
        m1[2] = "dva"
        m1[3] = "tri"
        m1[4] = "ctyri"
        m1[5] = "pet"
        m1[6] = "sest"
 
        fmt.Println(m1)
}

3. Benchmark: naplnění prázdné mapy a předalokované mapy

Na tomto místě je dobré se na chvíli zastavit a zjistit, zda má vůbec smysl se snažit o předalokaci mapy, tj. o zjištění či odhad počtu prvků, které budou do mapy vloženy. Pro tento účel vznikl jednoduchý benchmark, který je vypsán pod tímto odstavcem. V benchmarku se do mapy s klíči typu UUID ukládají časová razítka – pro každé UUID jedno razítko. První benchmark využívá předalokovanou mapu, druhý prázdnou mapu (která však není nil-mapou):

package main
 
import (
        "testing"
        "time"

        "github.com/google/uuid"
)
 
type UUID string
 
func BenchmarkInsertIntoPreallocatedMapUUIDKey(b *testing.B) {
        m := make(map[UUID]time.Time, b.N)
        t := time.Now()
 
        for i := 0; i < b.N; i++ {
                b.StopTimer()
                id := UUID(uuid.New().String())
                b.StartTimer()
                m[id] = t
        }
}
 
func BenchmarkInsertIntoEmptyMapUUIDKey(b *testing.B) {
        m := map[UUID]time.Time{}
        t := time.Now()
 
        for i := 0; i < b.N; i++ {
                b.StopTimer()
                id := UUID(uuid.New().String())
                b.StartTimer()
                m[id] = t
        }
}
Poznámka: zdrojový kód tohoto benchmarku naleznete na adrese https://github.com/tisnik/go-root/blob/master/article98/map­s/map1_test.go.

4. Odlišné použití map: mapy s prvky typu int

Chování map do značné míry závisí na typu klíčů i typu hodnot. Proto si v této kapitole ukažme podobný benchmark, jaký byl uveden v předchozí kapitole, nyní ovšem upravený do podoby, kdy klíče jsou typu int a hodnoty jsou taktéž typu int. Výsledná mapa tedy bude i přes velký počet uložených hodnot, obecně menší, než mapa z předchozího textu. Úprava benchmarku vypadá následovně:

package main
 
import (
        "testing"
)
 
func BenchmarkInsertIntoPreallocatedMapIntKeyIntValue(b *testing.B) {
        m := make(map[int]int, b.N)
 
        for i := 0; i < b.N; i++ {
                m[i] = i
        }
}
 
func BenchmarkInsertIntoEmptyMapIntKeyIntValue(b *testing.B) {
        m := map[int]int{}
 
        for i := 0; i < b.N; i++ {
                m[i] = i
        }
}
Poznámka: zdrojový kód tohoto benchmarku naleznete na adrese https://github.com/tisnik/go-root/blob/master/article98/map­s/map2_test.go.

5. Mapy, jejichž klíče mají velikost 100 bajtů

V pořadí již třetí benchmark je zaměřen na test vkládání prvků do mapy, jejichž prvky jsou poměrně velké – mají totiž velikost nepatrně přesahující 100 bajtů. Pro tento účel je klíč definován v datové struktuře nazvané jednoduše key:

package main
 
import (
        "testing"
)
 
type key struct {
        ID      int
        payload [100]byte
}
 
type value struct{}
 
func BenchmarkInsertIntoPreallocatedMapCompoundKey(b *testing.B) {
        m := make(map[key]value, b.N)
 
        for i := 0; i < b.N; i++ {
                k := key{
                        ID: i,
                }
                m[k] = value{}
        }
}
 
func BenchmarkInsertIntoEmptyMapCompoundKey(b *testing.B) {
        m := map[key]value{}
 
        for i := 0; i < b.N; i++ {
                k := key{
                        ID: i,
                }
                m[k] = value{}
        }
}
Poznámka: zdrojový kód tohoto benchmarku naleznete na adrese https://github.com/tisnik/go-root/blob/master/article98/map­s/map4_test.go.

6. Výsledky benchmarků, výsledky činnosti profileru

Podívejme se nyní na výsledky všech tří benchmarků popsaných v předchozí trojici kapitol. Benchmarky jsou spouštěny s využitím standardních nástrojů programovacího jazyka Go:

$ go test -bench=. -benchtime=1000000x
 
goos: linux
goarch: amd64
pkg: map-bench
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkInsertIntoPreallocatedMapUUIDKey-8              1000000               163.9 ns/op
BenchmarkInsertIntoEmptyMapUUIDKey-8                     1000000               354.7 ns/op
BenchmarkInsertIntoPreallocatedMapIntKeyIntValue-8       1000000                66.26 ns/op
BenchmarkInsertIntoEmptyMapIntKeyIntValue-8              1000000               137.4 ns/op
BenchmarkInsertIntoPreallocatedMapCompoundKey-8          1000000               177.7 ns/op
BenchmarkInsertIntoEmptyMapCompoundKey-8                 1000000               332.2 ns/op
PASS
ok      map-bench       27.959s

Z výsledků je zřejmé, že se skutečně vyplatí, když jsou prvky mapy předalokovány, samozřejmě za předpokladu, že je to možné.

Můžeme si dokonce zjistit i to, v jaké oblasti tráví benchmark nejvíce času. Testy můžeme spustit s povolením záznamu dat pro profiler CPU:

$ go test -bench=. -benchtime=1000000x -cpuprofile profile.out

Výsledkem by měl být (kromě výsledků benchmarku) i soubor profile.out, který můžeme snadno prozkoumat přímo v prostředí webového prohlížeče:

$ go tool pprof -http=:6060 profile.out

Obrázek 1: Webová stránka s výsledky benchmarků.

Obrázek 2: Časové rozdíly v přidávání prvků do prázdné vs. předalokované mapy.

Zajímavější může být zjištění, jak se od sebe budou odlišovat paměťové náročnosti jednotlivých benchmarků:

$ go test -bench=. -benchtime=1000000x -memprofile profile.out

Výsledky paměťového profileru si opět můžeme zobrazit přímo v prostředí webového prohlížeče. Povšimněte si, jak velké jsou paměťové nároky pro původně prázdnou mapu:

$ go tool pprof -http=:6060 profile.out

Obrázek 3: Rozdíly ve velikosti obsazené paměti v průběhu přidávání prvků do prázdné vs. předalokované mapy.

Obrázek 4: Odlišný pohled na stejná data změřená profilerem.

7. Mapa použitá ve funkci množiny

Programovací jazyk Go neobsahuje podporu pro práci s množinami. Z tohoto důvodu je nutné při požadavku existence této datové struktury použít odlišné techniky. Poměrně často se pro tyto účely používají mapy, jejichž hodnoty jsou prázdnými strukturami. Vzhledem k tomu, že prázdné struktury mají nulovou velikost, je jejich použití z hlediska obsazení paměti efektivnější, než použití (například) pravdivostních hodnot. Opět platí, že pokud bude takto zkonstruovaná množina obsahovat velký počet prvků, je výhodnější ji předalokovat v těch případech, kdy je počet prvků dopředu známý či alespoň dobře odhadnutelný. Rozdíl mezi postupným naplňováním původně prázdné množiny, resp. množiny s předalokovanými prvky můžeme zjistit z následujícího jednoduchého benchmarku:

package main
 
import (
        "testing"
)
 
type emptyValue struct{}
 
func BenchmarkInsertIntoPreallocatedMapIntKeyEmptyValue(b *testing.B) {
        m := make(map[int]emptyValue, b.N)
 
        for i := 0; i < b.N; i++ {
                m[i] = emptyValue{}
        }
}
 
func BenchmarkInsertIntoEmptyMapEmptyValue(b *testing.B) {
        m := map[int]emptyValue{}
 
        for i := 0; i < b.N; i++ {
                m[i] = emptyValue{}
        }
}
Poznámka: zdrojový kód tohoto benchmarku naleznete na adrese https://github.com/tisnik/go-root/blob/master/article98/map­s/map3_test.go.

8. Výsledky benchmarků a profileru

Opět se podívejme na výsledky benchmarků, z nichž jsou jasně patrné rozdílné časové náročnosti:

$ go test -bench=. -benchtime=100000000x
 
goos: linux
goarch: amd64
pkg: map-bench
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkInsertIntoPreallocatedMapIntKeyEmptyValue-8    100000000               97.77 ns/op
BenchmarkInsertIntoEmptyMapEmptyValue-8                 100000000              156.1 ns/op
PASS
ok      map-bench       25.405s

Získání CPU profilu s jeho zobrazením v prohlížeči:

$ go test -bench=. -benchtime=10000000x -cpuprofile profile.out
$ go tool pprof -http=:6060 profile.out

Obrázek 5: Graficky zobrazené výsledky CPU profileru.

Obrázek 6: Odlišný pohled na stejná data.

Paměťový profil:

$ go test -bench=. -benchtime=10000000x -memprofile profile.out
$ go tool pprof -http=:6060 profile.out

Z profilu je zřejmé, že u prázdné mapy bylo nutné paměť několikrát realokovat:

Obrázek 7: Graficky zobrazené výsledky paměťového profileru.

Obrázek 8: Odlišný pohled na stejná data.

9. Předávání datových struktur do funkcí a metod hodnotou či odkazem?

V prakticky všech aplikacích naprogramovaných v jazyku Go se do některých funkcí nebo metod předávají relativně rozsáhlé datové struktury. Častější a vlastně i méně viditelný je tento problém u metod, protože taková datová struktura může být použita jako příjemce (receiver) metody; je tedy využita jako objekt metody a tím pádem nemusí být problém na první pohled patrný.

Podívejme se na příklad převzatý z praxe. Jedná se konkrétně o službu naprogramovanou v jazyce Go, která je nakonfigurována přes konfigurační soubor ve formátu TOML a taktéž přes proměnné prostředí. Interně se pro načtení konfigurace používá knihovna Viper. Celá konfigurace může vypadat následovně (pouze jsem změnil některé interní hodnoty):

[logging]
debug = true
log_level = "info"
 
[kafka_broker]
enabled = true
address = "kafka:29092" #provide in deployment env or as secret
security_protocol = "PLAINTEXT"
cert_path = "not-set"
sasl_mechanism = "PLAIN"
sasl_username = "not-used"
sasl_password = "not-used"
topic = "platform.notifications.ingress" #provide in deployment env or as secret
timeout = "60s"
likelihood_threshold = 0
impact_threshold = 0
severity_threshold = 0
total_risk_threshold = 3
event_filter = "totalRisk >= totalRiskThreshold"
 
[service_log]
client_id = "a-service-id"
client_secret = "a-secret"
token_url = ""
enabled = false
url = "https://api.foo.bar.com/api/v1/logs/"
timeout = "15s"
likelihood_threshold = 0
impact_threshold = 0
severity_threshold = 0
total_risk_threshold = 0
event_filter = "totalRisk >= totalRiskThreshold"
rule_details_uri = "https://ui.foo.bar.com/page/{module}|{error_key}"
 
[storage]
db_driver = "postgres"
pg_username = "postgres" #provide in deployment env or as secret
pg_password = "postgres" #provide in deployment env or as secret
pg_host = "localhost" #provide in deployment env or as secret
pg_port = 5432 #provide in deployment env or as secret
pg_db_name = "notification" #provide in deployment env or as secret
pg_params = "sslmode=disable"
log_sql_queries = true
 
[dependencies]
content_server = "localhost:8082" #provide in deployment env or as secret
content_endpoint = "/api/v1/content" #provide in deployment env or as secret
template_renderer_server = "localhost:8083" #provide in deployment env or as secret
template_renderer_endpoint = "/v1/rendered_reports" #provide in deployment env or as secret
 
[notifications]
insights_advisor_url = "https://console.foo.bar.com/info/{object_id}"
cluster_details_uri = "https://console.foo.bar.com/details/{object_id}#insights"
rule_details_uri = "https://console.foo.bar.com/details/{object_id}/modules/{module}/{error_key}"
# valid units are SQL epoch time units: months days hours minutes seconds"
cooldown = "24 hours"
 
[metrics]
job_name = "notification_service"
# The metrics in Prometheus will be $namespace_$subsystem_$name
namespace = "notification_service"
subsystem = "notification_backend"
gateway_url = "localhost:9091"
gateway_auth_token = ""
retries = 3
# Valid time units are "ns", "us" (or "µs"), "ms", "s", "m", "h".
retry_after = "60s"
 
[cleaner]
# valid units are SQL epoch time units: months days hours minutes seconds"
max_age = "90 days"
 
[processing]
filter_allowed_clusters = false
allowed_clusters = []
filter_blocked_clusters = false
blocked_clusters = []

Jen pro zajímavost se podívejme na to, jak je tato konfigurace reflektována datovými strukturami jazyka Go a jak je zajištěno načtení konfigurace (což ovšem s problémem souvisí jen okrajově – takže tento kód můžete přeskočit, hodí se jen těm, kdo chtějí prozkoumat, jak lze spojit možnosti souborů TOML a konfigurace přes proměnné prostředí):

package conf
 
import (
        "bytes"
        "fmt"
        "net/url"
        "os"
        "path"
        "path/filepath"
        "strings"
        "time"
 
        "github.com/BurntSushi/toml"
 
        "github.com/rs/zerolog/log"
        "github.com/spf13/viper"
)
 
// Common constants used for logging and error reporting
const (
        filenameAttribute               = "filename"
        parsingConfigurationFileMessage = "parsing configuration file"
        noKafkaConfig                   = "no Kafka configuration available in Clowder, using default one"
        noBrokerConfig                  = "warning: no broker configurations found in clowder config"
        noSaslConfig                    = "warning: SASL configuration is missing"
        noTopicMapping                  = "warning: no kafka mapping found for topic %s"
        noStorage                       = "warning: no storage section in Clowder config"
)
 
// ConfigStruct is a structure holding the whole notification service
// configuration
type ConfigStruct struct {
        Logging       LoggingConfiguration       `mapstructure:"logging" toml:"logging"`
        Storage       StorageConfiguration       `mapstructure:"storage" toml:"storage"`
        Kafka         KafkaConfiguration         `mapstructure:"kafka_broker" toml:"kafka_broker"`
        ServiceLog    ServiceLogConfiguration    `mapstructure:"service_log" toml:"service_log"`
        Dependencies  DependenciesConfiguration  `mapstructure:"dependencies" toml:"dependencies"`
        Notifications NotificationsConfiguration `mapstructure:"notifications" toml:"notifications"`
        Metrics       MetricsConfiguration       `mapstructure:"metrics" toml:"metrics"`
        Cleaner       CleanerConfiguration       `mapstructure:"cleaner" toml:"cleaner"`
        Processing    ProcessingConfiguration    `mapstructure:"processing" toml:"processing"`
}
 
// LoggingConfiguration represents configuration for logging in general
type LoggingConfiguration struct {
        // Debug enables pretty colored logging
        Debug bool `mapstructure:"debug" toml:"debug"`
 
        // LogLevel sets logging level to show. Possible values are:
        // "debug"
        // "info"
        // "warn", "warning"
        // "error"
        // "fatal"
        //
        // logging level won't be changed if value is not one of listed above
        LogLevel string `mapstructure:"log_level" toml:"log_level"`
}
 
// StorageConfiguration represents configuration of postgresQSL data storage
type StorageConfiguration struct {
        Driver        string `mapstructure:"db_driver"       toml:"db_driver"`
        PGUsername    string `mapstructure:"pg_username"     toml:"pg_username"`
        PGPassword    string `mapstructure:"pg_password"     toml:"pg_password"`
        PGHost        string `mapstructure:"pg_host"         toml:"pg_host"`
        PGPort        int    `mapstructure:"pg_port"         toml:"pg_port"`
        PGDBName      string `mapstructure:"pg_db_name"      toml:"pg_db_name"`
        PGParams      string `mapstructure:"pg_params"       toml:"pg_params"`
        LogSQLQueries bool   `mapstructure:"log_sql_queries" toml:"log_sql_queries"`
}
 
// DependenciesConfiguration represents configuration of external services and other dependencies
type DependenciesConfiguration struct {
        ContentServiceServer     string `mapstructure:"content_server" toml:"content_server"`
        ContentServiceEndpoint   string `mapstructure:"content_endpoint" toml:"content_endpoint"`
        TemplateRendererServer   string `mapstructure:"template_renderer_server" toml:"template_renderer_server"`
        TemplateRendererEndpoint string `mapstructure:"template_renderer_endpoint" toml:"template_renderer_endpoint"`
        TemplateRendererURL      string
}
 
// CleanerConfiguration represents configuration for the main cleaner
type CleanerConfiguration struct {
        // MaxAge is specification of max age for records to be cleaned
        MaxAge string `mapstructure:"max_age" toml:"max_age"`
}
 
// KafkaConfiguration represents configuration of Kafka brokers and topics
type KafkaConfiguration struct {
        Enabled             bool          `mapstructure:"enabled" toml:"enabled"`
        Address             string        `mapstructure:"address" toml:"address"`
        SecurityProtocol    string        `mapstructure:"security_protocol" toml:"security_protocol"`
        CertPath            string        `mapstructure:"cert_path" toml:"cert_path"`
        SaslMechanism       string        `mapstructure:"sasl_mechanism" toml:"sasl_mechanism"`
        SaslUsername        string        `mapstructure:"sasl_username" toml:"sasl_username"`
        SaslPassword        string        `mapstructure:"sasl_password" toml:"sasl_password"`
        Topic               string        `mapstructure:"topic"   toml:"topic"`
        Timeout             time.Duration `mapstructure:"timeout" toml:"timeout"`
        LikelihoodThreshold int           `mapstructure:"likelihood_threshold" toml:"likelihood_threshold"`
        ImpactThreshold     int           `mapstructure:"impact_threshold" toml:"impact_threshold"`
        SeverityThreshold   int           `mapstructure:"severity_threshold" toml:"severity_threshold"`
        TotalRiskThreshold  int           `mapstructure:"total_risk_threshold" toml:"total_risk_threshold"`
        EventFilter         string        `mapstructure:"event_filter" toml:"event_filter"`
}
 
// ServiceLogConfiguration represents configuration of ServiceLog REST API
type ServiceLogConfiguration struct {
        Enabled             bool          `mapstructure:"enabled" toml:"enabled"`
        ClientID            string        `mapstructure:"client_id" toml:"client_id"`
        ClientSecret        string        `mapstructure:"client_secret" toml:"client_secret"`
        TokenURL            string        `mapstructure:"token_url" toml:"token_url"`
        URL                 string        `mapstructure:"url" toml:"url"`
        Timeout             time.Duration `mapstructure:"timeout" toml:"timeout"`
        LikelihoodThreshold int           `mapstructure:"likelihood_threshold" toml:"likelihood_threshold"`
        ImpactThreshold     int           `mapstructure:"impact_threshold" toml:"impact_threshold"`
        SeverityThreshold   int           `mapstructure:"severity_threshold" toml:"severity_threshold"`
        TotalRiskThreshold  int           `mapstructure:"total_risk_threshold" toml:"total_risk_threshold"`
        EventFilter         string        `mapstructure:"event_filter" toml:"event_filter"`
        RuleDetailsURI      string        `mapstructure:"rule_details_uri" toml:"rule_details_uri"`
}
 
// NotificationsConfiguration represents the configuration specific to the content of notifications
type NotificationsConfiguration struct {
        InsightsAdvisorURL string `mapstructure:"insights_advisor_url" toml:"insights_advisor_url"`
        ClusterDetailsURI  string `mapstructure:"cluster_details_uri" toml:"cluster_details_uri"`
        RuleDetailsURI     string `mapstructure:"rule_details_uri"    toml:"rule_details_uri"`
        Cooldown           string `mapstructure:"cooldown" toml:"cooldown"`
}
 
// MetricsConfiguration holds metrics related configuration
type MetricsConfiguration struct {
        Job              string        `mapstructure:"job_name" toml:"job_name"`
        Namespace        string        `mapstructure:"namespace" toml:"namespace"`
        Subsystem        string        `mapstructure:"subsystem" toml:"subsystem"`
        GatewayURL       string        `mapstructure:"gateway_url" toml:"gateway_url"`
        GatewayAuthToken string        `mapstructure:"gateway_auth_token" toml:"gateway_auth_token"`
        Retries          int           `mapstructure:"retries" toml:"retries"`
        RetryAfter       time.Duration `mapstructure:"retry_after" toml:"retry_after"`
}
 
// ProcessingConfiguration represents configuration for processing subsystem
type ProcessingConfiguration struct {
        FilterAllowedClusters bool     `mapstructure:"filter_allowed_clusters" toml:"filter_allowed_clusters"`
        AllowedClusters       []string `mapstructure:"allowed_clusters" toml:"allowed_clusters"`
        FilterBlockedClusters bool     `mapstructure:"filter_blocked_clusters" toml:"filter_blocked_clusters"`
        BlockedClusters       []string `mapstructure:"blocked_clusters" toml:"blocked_clusters"`
}
 
// LoadConfiguration loads configuration from defaultConfigFile, file set in
// configFileEnvVariableName or from env
func LoadConfiguration(configFileEnvVariableName, defaultConfigFile string) (ConfigStruct, error) {
        var configuration ConfigStruct
 
        // env. variable holding name of configuration file
        configFile, specified := os.LookupEnv(configFileEnvVariableName)
        if specified {
                log.Info().Str(filenameAttribute, configFile).Msg(parsingConfigurationFileMessage)
                // we need to separate the directory name and filename without
                // extension
                directory, basename := filepath.Split(configFile)
                file := strings.TrimSuffix(basename, filepath.Ext(basename))
                // parse the configuration
                viper.SetConfigName(file)
                viper.AddConfigPath(directory)
        } else {
                log.Info().Str(filenameAttribute, defaultConfigFile).Msg(parsingConfigurationFileMessage)
                // parse the configuration
                viper.SetConfigName(defaultConfigFile)
                viper.AddConfigPath(".")
        }
 
        // try to read the whole configuration
        err := viper.ReadInConfig()
        if _, isNotFoundError := err.(viper.ConfigFileNotFoundError); !specified && isNotFoundError {
                // If config file is not present (which might be correct in
                // some environment) we need to read configuration from
                // environment variables. The problem is that Viper is not
                // smart enough to understand the structure of config by
                // itself, so we need to read fake config file
                fakeTomlConfigWriter := new(bytes.Buffer)
 
                err := toml.NewEncoder(fakeTomlConfigWriter).Encode(configuration)
                if err != nil {
                        return configuration, err
                }
 
                fakeTomlConfig := fakeTomlConfigWriter.String()
 
                viper.SetConfigType("toml")
 
                err = viper.ReadConfig(strings.NewReader(fakeTomlConfig))
                if err != nil {
                        return configuration, err
                }
        } else if err != nil {
                // error is processed on caller side
                return configuration, fmt.Errorf("fatal error config file: %s", err)
        }
 
        // override configuration from env if there's variable in env
 
        const envPrefix = "MY_COOL_SERVICE_"
 
        viper.AutomaticEnv()
        viper.SetEnvPrefix(envPrefix)
        viper.SetEnvKeyReplacer(strings.NewReplacer("-", "_", ".", "__"))
 
        err = viper.Unmarshal(&configuration)
        if err != nil {
                return configuration, err
        }
 
        configuration.Dependencies.TemplateRendererURL, err = createURL(
                configuration.Dependencies.TemplateRendererServer,
                configuration.Dependencies.TemplateRendererEndpoint)
        if err != nil {
                fmt.Println("error creating content template renderer URL")
                return configuration, err
        }
 
        // everything's should be ok
        return configuration, nil
}
 
func createURL(server, endpoint string) (string, error) {
        u, err := url.Parse(server)
        if err != nil {
                return "", err
        }
        u.Path = path.Join(u.Path, endpoint)
        return u.String(), nil
}

Důležité je, že struktura nazvaná ConfigStruct obsahuje jako své prvky další struktury (a ty obsahují řetězce, pravdivostní hodnoty atd.) a její celková velikost je poměrně značná, což může způsobit problémy při předávání takové struktury hodnotou (a tedy i kopií celé struktury):

type ConfigStruct struct {
        Logging       LoggingConfiguration       `mapstructure:"logging" toml:"logging"`
        Storage       StorageConfiguration       `mapstructure:"storage" toml:"storage"`
        Kafka         KafkaConfiguration         `mapstructure:"kafka_broker" toml:"kafka_broker"`
        ServiceLog    ServiceLogConfiguration    `mapstructure:"service_log" toml:"service_log"`
        Dependencies  DependenciesConfiguration  `mapstructure:"dependencies" toml:"dependencies"`
        Notifications NotificationsConfiguration `mapstructure:"notifications" toml:"notifications"`
        Metrics       MetricsConfiguration       `mapstructure:"metrics" toml:"metrics"`
        Cleaner       CleanerConfiguration       `mapstructure:"cleaner" toml:"cleaner"`
        Processing    ProcessingConfiguration    `mapstructure:"processing" toml:"processing"`
}
Poznámka: na tomto místě je vhodné si uvědomit, že v Go se většina hodnot reprezentuje skutečně formou hodnoty a nikoli reference. To platí i pro struktury, takže struktura, která jako své prvky obsahuje další (pod)struktury, tyto podstruktury skutečně ve svém těle obsahuje – nejedná se o reference (adresy), na rozdíl od Javy, kde atribut typu nějaká třída je uložen formou reference. Tudíž v jazyce Go znamená předávání struktury hodnotou de facto hlubokou kopii celé struktury (výjimkou jsou řezy a do určité míry i řetězce, ovšem u řetězců nelze rozdíl poznat díky jejich neměnnosti).

10. Syntaxe pro předávání struktur do funkcí a metod hodnotou a odkazem, způsob překladu do assembleru

Zopakujme si, jak vlastně vypadají funkce a metody, do nichž se předává nějaká datová struktura hodnotou (tedy přes kopii) a odkazem (tedy přes ukazatel na původní strukturu). Syntaxe všech čtyř variant vypadá následovně:

; funkce s předáním struktury hodnotou
func GetStorageConfigurationByValue(configuration ConfigStruct) StorageConfiguration {
        return configuration.Storage
}
 
; funkce s předáním struktury referencí
func GetStorageConfigurationByReference(configuration *ConfigStruct) StorageConfiguration {
        return configuration.Storage
}
 
; metoda s příjemcem předaným hodnotou
func (configuration ConfigStruct) GetStorageConfigurationByValue() StorageConfiguration {
        return configuration.Storage
}
 
; metoda s příjemcem předaným referencí
func (configuration *ConfigStruct) GetStorageConfigurationByReference() StorageConfiguration {
        return configuration.Storage
}

Při volání funkcí (nikoli metod) je nutné při předání struktury odkazem ukazatel na danou strukturu získat operátorem &, který je v jazyce Go inspirován céčkem a má v obou jazycích podobný význam:

conf.GetStorageConfigurationByValue(configuration)
conf.GetStorageConfigurationByReference(&configuration)

Naproti tomu při volání metod žádný ukazatel získávat nemusíme, protože obě volání vypadají stejně, a to nezávisle na tom, zda je příjemce předáván hodnotou nebo odkazem:

configuration.GetStorageConfigurationByValue()
configuration.GetStorageConfigurationByReference()

A jak vlastně vypadá volání těchto funkcí a metod v assembleru? Ukažme si to pro nějakou lokální proměnnou obsahující konfiguraci:

func main() {
        configuration := ConfigStruct{}
        GetStorageConfigurationByValue(configuration)
        GetStorageConfigurationByReference(&configuration)
        configuration.GetStorageConfigurationByValue()
        configuration.GetStorageConfigurationByReference()
}

Překlad se zpětným převodem do assembleru:

$ go build -gcflags '-N -l' config.go
$ objdump -d config > config.asm

Překlad GetStorageConfigurationBy­Value(configuration):

  457358:       48 8b 84 24 78 03 00    mov    0x378(%rsp),%rax
  45735f:       00
  457360:       48 89 04 24             mov    %rax,(%rsp)
  457364:       48 8d 7c 24 08          lea    0x8(%rsp),%rdi
  457369:       48 8d b4 24 80 03 00    lea    0x380(%rsp),%rsi
  457370:       00
  457371:       66 0f 1f 84 00 00 00    nopw   0x0(%rax,%rax,1)
  457378:       00 00
  45737a:       66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
  457380:       48 89 6c 24 f0          mov    %rbp,-0x10(%rsp)
  457385:       48 8d 6c 24 f0          lea    -0x10(%rsp),%rbp
  45738a:       e8 51 c3 ff ff          callq  4536e0 <runtime.duffcopy+0xe0>
  45738f:       48 8b 6d 00             mov    0x0(%rbp),%rbp
  457393:       e8 88 fd ff ff          callq  457120 <main.GetStorageConfigurationByValue>

Překlad GetStorageConfigurationBy­Reference(&configuration):

  45739d:       48 8d 84 24 78 03 00    lea    0x378(%rsp),%rax
  4573a4:       00
  4573a5:       e8 d6 fd ff ff          callq  457180 <main.GetStorageConfigurationByReference>

Překlad configuration.GetStorageCon­figurationByValue():

  4573af:       48 8b 84 24 78 03 00    mov    0x378(%rsp),%rax
  4573b6:       00
  4573b7:       48 89 04 24             mov    %rax,(%rsp)
  4573bb:       48 8d 7c 24 08          lea    0x8(%rsp),%rdi
  4573c0:       48 8d b4 24 80 03 00    lea    0x380(%rsp),%rsi
  4573c7:       00
  4573c8:       48 89 6c 24 f0          mov    %rbp,-0x10(%rsp)
  4573cd:       48 8d 6c 24 f0          lea    -0x10(%rsp),%rbp
  4573d2:       e8 09 c3 ff ff          callq  4536e0 <runtime.duffcopy+0xe0>
  4573d7:       48 8b 6d 00             mov    0x0(%rbp),%rbp
  4573db:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
  4573e0:       e8 1b fe ff ff          callq  457200 <main.ConfigStruct.GetStorageConfigurationByValue>

Překlad configuration.GetStorageCon­figurationByReference():

  4573ea:       48 8d 84 24 78 03 00    lea    0x378(%rsp),%rax
  4573f1:       00
  4573f2:       e8 69 fe ff ff          callq  457260 <main.(*ConfigStruct).GetStorageConfigurationByReference>
Poznámka: už rozdíly v počtu instrukcí a ve volání funkce duffcopy naznačují, který způsob bude trvat déle a který kratší dobu.

11. Benchmark zjišťující rozdíly v rychlosti volání funkcí a metod s využitím hodnoty a reference na předávanou strukturu

Pro zjištění, jak moc (či jak vůbec) se budou lišit časy volání funkcí a metod s využitím hodnoty nebo reference na předávanou datovou strukturu, byl vytvořen následující jednoduchý benchmark, jenž otestuje všechny čtyři možnosti. Povšimněte si, že tento benchmark neměří čas nutný pro načtení konfigurace a její deserializaci knihovnou Viper. Měří se pouze čas volání funkce nebo metody s předáním deserializované konfigurace, a to buď hodnotou nebo odkazem (v benchmarcích je možné pozastavit a znovu rozběhnout časovač používaný pro výpočet doby trvání operací):

package conf_test
 
// Benchmark for config module
 
import (
        "os"
        "testing"
 
        "config-struct/conf"
)
 
const (
        configFileEnvVariableName = "SERVICE_CONFIG_FILE"
        defaultConfigFileName     = "./config"
)
 
// loadConfiguration function loads configuration prepared to be used by
// benchmarks
func loadConfiguration() (conf.ConfigStruct, error) {
        os.Clearenv()
 
        err := os.Setenv(configFileEnvVariableName, defaultConfigFileName)
        if err != nil {
                return conf.ConfigStruct{}, err
        }
 
        config, err := conf.LoadConfiguration(configFileEnvVariableName, defaultConfigFileName)
        if err != nil {
                return conf.ConfigStruct{}, err
        }
 
        return config, nil
}
 
func mustLoadBenchmarkConfiguration(b *testing.B) conf.ConfigStruct {
        configuration, err := loadConfiguration()
        if err != nil {
                b.Fatal(err)
        }
        return configuration
}
 
func BenchmarkGetStorageConfigurationFunctionByValue(b *testing.B) {
        b.StopTimer()
        configuration := mustLoadBenchmarkConfiguration(b)
        b.StartTimer()
 
        for i := 0; i < b.N; i++ {
                // call benchmarked function
                conf.GetStorageConfigurationByValue(configuration)
        }
 
}
 
func BenchmarkGetStorageConfigurationFunctionByReference(b *testing.B) {
        b.StopTimer()
        configuration := mustLoadBenchmarkConfiguration(b)
        b.StartTimer()
 
        for i := 0; i < b.N; i++ {
                // call benchmarked function
                conf.GetStorageConfigurationByReference(&configuration)
        }
 
}
 
func BenchmarkGetStorageConfigurationMethodByValue(b *testing.B) {
        b.StopTimer()
        configuration := mustLoadBenchmarkConfiguration(b)
        b.StartTimer()
 
        for i := 0; i < b.N; i++ {
                // call benchmarked function
                configuration.GetStorageConfigurationByValue()
        }
 
}
 
func BenchmarkGetStorageConfigurationMethodByReference(b *testing.B) {
        b.StopTimer()
        configuration := mustLoadBenchmarkConfiguration(b)
        b.StartTimer()
 
        for i := 0; i < b.N; i++ {
                // call benchmarked function
                configuration.GetStorageConfigurationByReference()
        }
 
}

12. Výsledky benchmarku i profileru

Podívejme se nyní na výsledky všech čtyř benchmarků, jejichž zdrojové kódy jsme si ukázali a popsali v předchozí kapitole. Celkem je provedeno 1000000000 volání všech testovaných funkcí a metod:

$ go test -bench=. -benchtime=1000000000x -cpuprofile profile.out -v config-struct/conf
 
goos: linux
goarch: amd64
pkg: config-struct/conf
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkGetStorageConfigurationFunctionByValue
BenchmarkGetStorageConfigurationFunctionByValue-8               1000000000              13.20 ns/op
BenchmarkGetStorageConfigurationFunctionByReference
BenchmarkGetStorageConfigurationFunctionByReference-8           1000000000               0.2405 ns/op
BenchmarkGetStorageConfigurationMethodByValue
BenchmarkGetStorageConfigurationMethodByValue-8                 1000000000              13.24 ns/op
BenchmarkGetStorageConfigurationMethodByReference
BenchmarkGetStorageConfigurationMethodByReference-8             1000000000               0.3596 ns/op
PASS
ok      config-struct/conf      27.166s
Poznámka: z výsledků benchmarků je patrné, že volání funkce s předáním reference je přibližně 55× rychlejší, než volání obdobné funkce, které se však předá přímo hodnota struktury. Podobně pro volání metod je použití reference jako příjemce (receiver) přibližně 36× rychlejší, než použití hodnoty jako příjemce. Samozřejmě se liší sémantika volání, ale obecně je použití reference mnohem rychlejší (a nebezpečnější kvůli nemožnosti použití modifikátoru const). Pro menší struktury (a naše testovaná struktura je skutečně velká) budou rozdíly v dosažených časech pochopitelně menší.

Profiler, konkrétně profiler zjišťující zatížení mikroprocesoru výpočty, se spustí následujícím příkazem:

$ go test -bench=. -benchtime=1000000000x -cpuprofile profile.out -v config-struct/conf

Výsledky v grafické podobě vypadají takto:

Obrázek 9: Z grafické podoby výsledků je patrné, že zdaleka nejvíce času se stráví v systémové funkci duffcopy.

Mimochodem – samotná funkce duffcopy se přeloží s rozbalenou smyčkou, takže se vlastně jedná pouze o sekvenci instrukcí pro přesuny dat:

    ...
    ...
    ...
    187        200ms      200ms             MOVUPS  (SI), X0
    188        120ms      120ms             ADDQ    $16, SI
    189        280ms      280ms             MOVUPS  X0, (DI)
    190         90ms       90ms             ADDQ    $16, DI
    191            .          .
    192        140ms      140ms             MOVUPS  (SI), X0
    193        120ms      120ms             ADDQ    $16, SI
    194        280ms      280ms             MOVUPS  X0, (DI)
    195         60ms       60ms             ADDQ    $16, DI
    196            .          .
    197        210ms      210ms             MOVUPS  (SI), X0
    198         70ms       70ms             ADDQ    $16, SI
    199        180ms      180ms             MOVUPS  X0, (DI)
    200         50ms       50ms             ADDQ    $16, DI
    201            .          .
    202        110ms      110ms             MOVUPS  (SI), X0
    203        140ms      140ms             ADDQ    $16, SI
    204        170ms      170ms             MOVUPS  X0, (DI)
    205         20ms       20ms             ADDQ    $16, DI
    206            .          .
    207         90ms       90ms             MOVUPS  (SI), X0
    208        130ms      130ms             ADDQ    $16, SI
    209        210ms      210ms             MOVUPS  X0, (DI)
    210         30ms       30ms             ADDQ    $16, DI
    ...
    ...
    ...

13. Mapy vs. řezy při implementaci jednoduché paměťové cache

Následující benchmark vznikl z toho důvodu, že jsme pro účely jednoho projektu zjišťovali, jakým způsobem se má implementovat jednoduchá paměťová cache, konkrétně cache pro prvky, jejichž klíče jsou typu int a hodnoty obsahují UUID a časové razítko (v samotné aplikaci je situace složitější, neboť se používá komplikovanější datová struktura). Poněkud neobvyklé ovšem bylo, že počet položek umístěných do paměťové cache je relativně malý – většinou v intervalu od 1 do 10 – a počet čtení o několik řádů přesahuje počet zápisů.

Vzhledem k tomu, že prvky v cache jsou určeny identifikátorem (typu int), mohlo by se zdát řešení triviální: použít mapu. Ovšem vzhledem k požadavku na co nejvyšší rychlost nalezení prvků byl vytvořen benchmark a navíc se kromě implementace cache přes mapu (což je řešení, které automaticky napadne každého vývojáře) vytvořilo i alternativní řešení založené na použití běžného řezu s lineárním (!!!) vyhledáváním. Z teoretického hlediska je to pochopitelně nesmysl, ovšem podívejme se na chování takové cache pro malý počet uložených prvků. Toto chování je otestováno v následujícím benchmarku:

package main
 
import (
        "testing"
        "time"
 
        "github.com/google/uuid"
)
 
type ID int
 
type Payload struct {
        uuid      string
        timestamp time.Time
}
 
type IdWithPayload struct {
        id        ID
        uuid      string
        timestamp time.Time
}
 
func genID(i int) ID {
        return ID(3*i + 1)
}
 
func fillInMap(b *testing.B, items int) map[ID]Payload {
        b.StopTimer()
 
        m := make(map[ID]Payload, items)
 
        for i := 0; i < items; i++ {
                id := genID(i)
                payload := Payload{
                        uuid:      uuid.New().String(),
                        timestamp: time.Now(),
                }
                m[id] = payload
        }
 
        b.StartTimer()
        return m
}
 
func fillInSlice(b *testing.B, items int) []IdWithPayload {
        b.StopTimer()
 
        s := make([]IdWithPayload, items)
 
        for i := 0; i < items; i++ {
                idWithPayload := IdWithPayload{
                        id:        genID(i),
                        uuid:      uuid.New().String(),
                        timestamp: time.Now(),
                }
                s[i] = idWithPayload
        }
 
        b.StartTimer()
        return s
}
 
func performBenchmarkFindInMap(b *testing.B, m map[ID]Payload) {
        items := len(m)
        for i := 0; i < b.N; i++ {
                _, found := m[genID(i%items)]
                if !found {
                        b.Fatal("not found")
                }
        }
}
 
func performBenchmarkFindInSlice(b *testing.B, s []IdWithPayload) {
        items := len(s)
        for i := 0; i < b.N; i++ {
                found := false
                id := genID(i % items)
                for _, p := range s {
                        if p.id == id {
                                found = true
                                break
                        }
                }
                if !found {
                        b.Fatal("not found")
                }
        }
}
 
func BenchmarkFindInMap1(b *testing.B) {
        m := fillInMap(b, 1)
        performBenchmarkFindInMap(b, m)
}
 
func BenchmarkFindInSlice1(b *testing.B) {
        m := fillInSlice(b, 1)
        performBenchmarkFindInSlice(b, m)
}
 
func BenchmarkFindInMap5(b *testing.B) {
        m := fillInMap(b, 5)
        performBenchmarkFindInMap(b, m)
}
 
func BenchmarkFindInSlice5(b *testing.B) {
        m := fillInSlice(b, 5)
        performBenchmarkFindInSlice(b, m)
}
 
func BenchmarkFindInMap10(b *testing.B) {
        m := fillInMap(b, 10)
        performBenchmarkFindInMap(b, m)
}
 
func BenchmarkFindInSlice10(b *testing.B) {
        m := fillInSlice(b, 10)
        performBenchmarkFindInSlice(b, m)
}
 
func BenchmarkFindInMap20(b *testing.B) {
        m := fillInMap(b, 20)
        performBenchmarkFindInMap(b, m)
}
 
func BenchmarkFindInSlice20(b *testing.B) {
        m := fillInSlice(b, 20)
        performBenchmarkFindInSlice(b, m)
}
 
func BenchmarkFindInMap100(b *testing.B) {
        m := fillInMap(b, 100)
        performBenchmarkFindInMap(b, m)
}
 
func BenchmarkFindInSlice100(b *testing.B) {
        m := fillInSlice(b, 100)
        performBenchmarkFindInSlice(b, m)
}
 
func BenchmarkFindInMap1000(b *testing.B) {
        m := fillInMap(b, 1000)
        performBenchmarkFindInMap(b, m)
}
 
func BenchmarkFindInSlice1000(b *testing.B) {
        m := fillInSlice(b, 1000)
        performBenchmarkFindInSlice(b, m)
}
Poznámka: ze zdrojového kódu je patrné, že benchmark voláme pro různé velikosti cache – od minimálního počtu prvků do 1000 prvků.

14. Výsledky benchmarků

Výsledky benchmarků budou v tomto případě zajímavé, protože již nebude zcela zřejmé, který algoritmus je výhodnější pro libovolná data. Ukazuje se totiž, že pro malý počet prvků je výhodnější (i když se nejedná o řádový rozdíl) použít řez a nikoli mapu:

$ go test -bench=. -benchtime=100000000x
 
goos: linux
goarch: amd64
pkg: slice-or-map
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkFindInMap1-8           100000000               12.13 ns/op
BenchmarkFindInSlice1-8         100000000                9.573 ns/op
BenchmarkFindInMap5-8           100000000               13.19 ns/op
BenchmarkFindInSlice5-8         100000000               10.78 ns/op
BenchmarkFindInMap10-8          100000000               15.82 ns/op
BenchmarkFindInSlice10-8        100000000               14.11 ns/op
BenchmarkFindInMap20-8          100000000               15.29 ns/op
BenchmarkFindInSlice20-8        100000000               17.80 ns/op
BenchmarkFindInMap100-8         100000000               17.07 ns/op
BenchmarkFindInSlice100-8       100000000               64.13 ns/op
BenchmarkFindInMap1000-8        100000000               23.96 ns/op
BenchmarkFindInSlice1000-8      100000000              611.9 ns/op
PASS
ok      slice-or-map    82.604s
Poznámka: v případě, že vás překvapuje, že je přístup do mapy (relativně) pomalý pro malý počet prvků, postačuje se podívat na implementaci mapy, konkrétně na funkce mapaccess1 a mapaccess2. Počet operací, které se při vyhledání prvku provádí, je skutečně velký v porovnání s triviálním lineárním průchodem prvky řezu, takže pro počet prvků do cca 15 je (což může znít paradoxně) mnohdy rychlejší použití řezů.

15. Grafické porovnání výsledků

Nejprve si porovnejme časy běhu pro benchmarku s počtem prvků pohybujícím se od 1 do 100:

Obrázek 10: Porovnání doby vyhledání prvku v mapě a v řezu pro kontejnery s počtem prvků do 100.

Povšimněte si, že pro skutečně malý počet prvků (do cca 15) je použití řezu výhodnější.

Pro větší počet prvků je však již patrné, že mapa je v naprosté většině případů lepším řešením a v nejhorším možném případě bude časová složitost stejná, jako složitost lineárního přístupu, tedy O(n). Viz též poslední sloupec:

Obrázek 11: Porovnání doby vyhledání prvku v mapě a v řezu pro kontejnery s počtem prvků do 1000.

Poznámka: samozřejmě je možné implementovat i sofistikovanější struktury typu strom. V našem konkrétním případě – o dva řády více vyhledání než zápisů – by se nejspíše jednalo o vyvážený strom. Užitečné je ovšem znovu provést benchmarky, aby se ověřilo, jak se bude datová struktura chovat v praxi, protože celý mechanismus běží na reálném HW s více jádry, lokální i globální cache atd. atd.

16. Mapy vs. řezy při implementaci množiny

Ještě naposledy se vraťme k problematice použití map nebo řezů, a to při implementaci množiny. Pokud je množina implementovaná řezem, je řešení zřejmé – vlastní hodnota uložená v řezu je hodnota prvku množiny, takže minimálně operace vkládání vyžaduje zjištění, zda prvek v množině již existuje či nikoli (operace s lineární složitostí!). V případě map se používají vlastně jen klíče prvků, protože hodnoty prvků jsou prázdnými strukturami (což je datový typ s teoreticky nulovou velikostí). Dopředu je nutné říci, že ani jeden z použitých způsobů není ani zdaleka ideální a pokud se má skutečně pracovat s rozsáhlými množinami, je lepší se poohlédnout po již hotových implementacích, například po knihovně Go18DS. Nicméně se podívejme na časovou složitost zjišťování, zda prvek v množině existuje či nikoli. Jedná se tedy o podobný problém, jaký jsme řešili v předchozích kapitolách:

package main
 
import (
        "testing"
)
 
type ID int
 
func genID(i int) ID {
        return ID(3*i + 1)
}
 
func fillInMap(b *testing.B, items int) map[ID]struct{} {
        b.StopTimer()
 
        m := make(map[ID]struct{}, items)
 
        for i := 0; i < items; i++ {
                id := genID(i)
                m[id] = struct{}{}
        }
 
        b.StartTimer()
        return m
}
 
func fillInSlice(b *testing.B, items int) []ID {
        b.StopTimer()
 
        s := make([]ID, items)
 
        for i := 0; i < items; i++ {
                id := genID(i)
                s[i] = id
        }
 
        b.StartTimer()
        return s
}
 
func performBenchmarkFindInMap(b *testing.B, m map[ID]struct{}) {
        items := len(m)
        for i := 0; i < b.N; i++ {
                _, found := m[genID(i%items)]
                if !found {
                        b.Fatal("not found")
                }
        }
}
 
func performBenchmarkFindInSlice(b *testing.B, s []ID) {
        items := len(s)
        for i := 0; i < b.N; i++ {
                found := false
                id := genID(i % items)
                for _, p := range s {
                        if p == id {
                                found = true
                                break
                        }
                }
                if !found {
                        b.Fatal("not found")
                }
        }
}
 
func BenchmarkFindInMap1(b *testing.B) {
        m := fillInMap(b, 1)
        performBenchmarkFindInMap(b, m)
}
 
func BenchmarkFindInSlice1(b *testing.B) {
        m := fillInSlice(b, 1)
        performBenchmarkFindInSlice(b, m)
}
 
func BenchmarkFindInMap5(b *testing.B) {
        m := fillInMap(b, 5)
        performBenchmarkFindInMap(b, m)
}
 
func BenchmarkFindInSlice5(b *testing.B) {
        m := fillInSlice(b, 5)
        performBenchmarkFindInSlice(b, m)
}
 
func BenchmarkFindInMap10(b *testing.B) {
        m := fillInMap(b, 10)
        performBenchmarkFindInMap(b, m)
}
 
func BenchmarkFindInSlice10(b *testing.B) {
        m := fillInSlice(b, 10)
        performBenchmarkFindInSlice(b, m)
}
 
func BenchmarkFindInMap20(b *testing.B) {
        m := fillInMap(b, 20)
        performBenchmarkFindInMap(b, m)
}
 
func BenchmarkFindInSlice20(b *testing.B) {
        m := fillInSlice(b, 20)
        performBenchmarkFindInSlice(b, m)
}
 
func BenchmarkFindInMap100(b *testing.B) {
        m := fillInMap(b, 100)
        performBenchmarkFindInMap(b, m)
}
 
func BenchmarkFindInSlice100(b *testing.B) {
        m := fillInSlice(b, 100)
        performBenchmarkFindInSlice(b, m)
}
 
func BenchmarkFindInMap1000(b *testing.B) {
        m := fillInMap(b, 1000)
        performBenchmarkFindInMap(b, m)
}
 
func BenchmarkFindInSlice1000(b *testing.B) {
        m := fillInSlice(b, 1000)
        performBenchmarkFindInSlice(b, m)
}

17. Výsledky benchmarku

Výsledky benchmarku by již pro nás neměly být překvapivé – pro velmi malý počet prvků „vyhrává“ jinak zcela nepoužitelný algoritmus založený na (lineárním) průchodu prvky, zatímco pro množiny mající více než přibližně 20 prvků je již lepší se spolehnout na interní hešovací algoritmus implementovaný pro mapy:

$ go test -bench=. -benchtime=100000000x
 
goos: linux
goarch: amd64
pkg: sets-slice-or-map
cpu: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz
BenchmarkFindInMap1-8           100000000               12.01 ns/op
BenchmarkFindInSlice1-8         100000000                7.208 ns/op
BenchmarkFindInMap5-8           100000000               12.61 ns/op
BenchmarkFindInSlice5-8         100000000                8.346 ns/op
BenchmarkFindInMap10-8          100000000               14.57 ns/op
BenchmarkFindInSlice10-8        100000000                9.498 ns/op
BenchmarkFindInMap20-8          100000000               14.28 ns/op
BenchmarkFindInSlice20-8        100000000               11.61 ns/op
BenchmarkFindInMap100-8         100000000               14.63 ns/op
BenchmarkFindInSlice100-8       100000000               35.57 ns/op
BenchmarkFindInMap1000-8        100000000               22.53 ns/op
BenchmarkFindInSlice1000-8      100000000              281.4 ns/op
PASS
ok      sets-slice-or-map       44.437s

Grafické zobrazení výsledků:

Obrázek 12: Při malém počtu prvků (což ale není typický případ) se vyplatí použít primitivní řezy.

Obrázek 13: Při větším počtu prvků je samozřejmě už výhodnější se spolehnout na sofistikovanější algoritmy, i když je nutné dát pozor na to, že mapy v nejhorším případě zaručují lineární složitost.

Obrázek 14: Praktický (ne teoretický!) rozdíl mezi použitím map a řezů pro implementaci množin je lépe patrný na tomto grafu, na němž je lineární časová složitost O(n) pro řezy jasně porovnatelná s obecně lepší časovou složitostí map pro větší počet prvků.

18. Závěrečné zhodnocení – triviální a přitom mnohdy důležité optimalizace

V dnešním článku jsme si ukázali velmi jednoduché optimalizace, které je možné provádět v aplikacích naprogramovaných v jazyku Go. Jak bylo z předchozích kapitol patrné, jedná se prakticky ve všech případech o zcela triviální operace, které však mohou být přesto užitečné a důležité. Prakticky vždy je však při výběru algoritmu určeného pro řešení určité úlohy užitečné si napsat benchmarky, spustit je a taktéž spustit profiler. Jen tak lze totiž „objevit“ některé zajímavé odchylky pro určitou velikost úlohy – viz například benchmark pro cache a benchmark pro implementaci množiny dvěma různými datovými strukturami.

UX DAy - tip 2

Někdy je taktéž užitečné (ale zde již skutečně záleží na citu programátora) vzdát se některé vlastnosti poskytované jazykem Go. Příkladem je předávání parametrů hodnotou, což je v mnoha ohledech „čistější“ řešení, než předávání odkazem (volaná funkce/metoda nemůže předávanou hodnotu modifikovat, protože má k dispozici její kopii – což je ale někdy jen iluze). Zde platíme strojovým časem a pamětí za fakt, že Go prozatím nedokáže zajistit neměnnost (immutability) datových struktur – neexistuje zde ani vhodná syntaxe, ale ani sémantika.

Poznámka: existují i další poněkud neintuitivní optimalizace, například při průchodu řezem, polem či mapou bez kopie hodnoty jednotlivých prvků. O této problematice (která mimochodem opět vede ke snížení počtu operace duffcopy) se zmíníme příště.

19. Repositář s demonstračními příklady

Zdrojové kódy všech 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:

# Příklad/soubor Stručný popis Cesta
1 maps/map1_test.go benchmark pro mapy, jejichž klíče jsou typu UUID a hodnoty jsou časovými razítky https://github.com/tisnik/go-root/blob/master/article98/map­s/map1_test.go
2 maps/map2_test.go benchmark pro mapy, jejichž klíče jsou typu int a i hodnoty jsou stejného typu https://github.com/tisnik/go-root/blob/master/article98/map­s/map2_test.go
3 maps/map3_test.go benchmark pro mapy, jejichž prvky jsou prázdnými strukturami https://github.com/tisnik/go-root/blob/master/article98/map­s/map3_test.go
4 maps/map4_test.go benchmark pro mapy, jejichž klíče mají velikost 100 bajtů https://github.com/tisnik/go-root/blob/master/article98/map­s/map4_test.go
5 maps/go.mod projektový soubor s definicí modulu https://github.com/tisnik/go-root/blob/master/article98/map­s/go.mod
6 maps/go.sum seznam všech přímých i nepřímých závislostí https://github.com/tisnik/go-root/blob/master/article98/map­s/go.sum
       
7 map_or_slice/map_or_slice_test.go benchmark porovnávající použití řezů a map pro podobné operace vyhledání hodnoty https://github.com/tisnik/go-root/blob/master/article98/map_or_sli­ce/map_or_slice_test.go
8 map_or_slice/go.mod projektový soubor s definicí modulu https://github.com/tisnik/go-root/blob/master/article98/map_or_sli­ce/go.mod
9 map_or_slice/go.sum seznam všech přímých i nepřímých závislostí https://github.com/tisnik/go-root/blob/master/article98/map_or_sli­ce/go.sum
       
10 sets/map_or_slice_test.go benchmark: je lepší použít mapu nebo řez pro implementaci množiny? https://github.com/tisnik/go-root/blob/master/article98/set­s/map_or_slice_test.go
11 sets/go.mod projektový soubor s definicí modulu https://github.com/tisnik/go-root/blob/master/article98/set­s/go.mod
       
12 parameter_value_reference/main.go předávání rozsáhlých parametrů: hlavní program https://github.com/tisnik/go-root/blob/master/article98/pa­rameter_value_reference/ma­in.go
13 parameter_value_reference/config.toml konfigurační soubor, který je načítán programem https://github.com/tisnik/go-root/blob/master/article98/pa­rameter_value_reference/con­fig.toml
14 parameter_value_reference/go.mod projektový soubor s definicí modulu https://github.com/tisnik/go-root/blob/master/article98/pa­rameter_value_reference/go­.mod
15 parameter_value_reference/go.sum seznam všech přímých i nepřímých závislostí https://github.com/tisnik/go-root/blob/master/article98/pa­rameter_value_reference/go­.sum
16 parameter_value_reference/con­f/config.go definice datové struktury s načítanou konfigurací https://github.com/tisnik/go-root/blob/master/article98/pa­rameter_value_reference/con­f/config.go
17 parameter_value_reference/con­f/config.toml konfigurační soubor, který je načítán benchmarkem https://github.com/tisnik/go-root/blob/master/article98/pa­rameter_value_reference/con­f/config.toml
18 parameter_value_reference/con­f/config_benchmark_test.go benchmark: předávání velké struktury hodnotou nebo referencí? https://github.com/tisnik/go-root/blob/master/article98/pa­rameter_value_reference/con­f/config_benchmark_test.go
       
19 config_to_asm.go soubor, jehož překlad do assembleru se použil v dnešním článku https://github.com/tisnik/go-root/blob/master/article98/con­fig_to_asm.go

20. Odkazy na Internetu

  1. An Introduction to Benchmarking Your Go Programs
    https://tutorialedge.net/go­lang/benchmarking-your-go-programs/
  2. 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
  3. Go18DS (Go 1.18+ Data Structures)
    https://github.com/daichi-m/go18ds
  4. TreeMap v2
    https://github.com/igrmk/treemap
  5. Go Data Structures: Binary Search Tree
    https://flaviocopes.com/golang-data-structure-binary-search-tree/
  6. Generics in Go
    https://bitfieldconsultin­g.com/golang/generics
  7. Tutorial: Getting started with generics
    https://go.dev/doc/tutorial/generics
  8. Gobs of data
    https://blog.golang.org/gobs-of-data
  9. 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/
  10. Benchmarking MinIO vs. AWS S3 for Apache Spark
    https://blog.min.io/benchmarking-apache-spark-vs-aws-s3/
  11. Know Go: Generics (Kniha)
    https://bitfieldconsultin­g.com/books/generics
  12. Go 1.18 Generics based slice package
    https://golangexample.com/go-1–18-generics-based-slice-package/

Byl pro vás článek přínosný?