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?
12. Výsledky benchmarku i profileru
13. Mapy vs. řezy při implementaci jednoduché paměťové cache
15. Grafické porovnání výsledků
16. Mapy vs. řezy při implementaci množiny
18. Závěrečné zhodnocení – triviální a přitom mnohdy důležité optimalizace
19. Repositář s demonstračními příklady
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.
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.
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]
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
}
}
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
}
}
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{}
}
}
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{}
}
}
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"`
}
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 GetStorageConfigurationByValue(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 GetStorageConfigurationByReference(&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.GetStorageConfigurationByValue():
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.GetStorageConfigurationByReference():
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>
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
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)
}
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
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.
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.
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.
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/maps/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/maps/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/maps/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/maps/map4_test.go |
| 5 | maps/go.mod | projektový soubor s definicí modulu | https://github.com/tisnik/go-root/blob/master/article98/maps/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/maps/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_slice/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_slice/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_slice/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/sets/map_or_slice_test.go |
| 11 | sets/go.mod | projektový soubor s definicí modulu | https://github.com/tisnik/go-root/blob/master/article98/sets/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/parameter_value_reference/main.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/parameter_value_reference/config.toml |
| 14 | parameter_value_reference/go.mod | projektový soubor s definicí modulu | https://github.com/tisnik/go-root/blob/master/article98/parameter_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/parameter_value_reference/go.sum |
| 16 | parameter_value_reference/conf/config.go | definice datové struktury s načítanou konfigurací | https://github.com/tisnik/go-root/blob/master/article98/parameter_value_reference/conf/config.go |
| 17 | parameter_value_reference/conf/config.toml | konfigurační soubor, který je načítán benchmarkem | https://github.com/tisnik/go-root/blob/master/article98/parameter_value_reference/conf/config.toml |
| 18 | parameter_value_reference/conf/config_benchmark_test.go | benchmark: předávání velké struktury hodnotou nebo referencí? | https://github.com/tisnik/go-root/blob/master/article98/parameter_value_reference/conf/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/config_to_asm.go |
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/
ČLÁNKY DO MAILU