Mislite li da su ove dvije opcije za testiranje uslova unutar petlje ekvivalentne u performansama?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Sve je počelo „zagrevanjem mozga“; morao sam da dam primer optimalne pretrage za najvećim parnim brojem u nizu celih brojeva [-x....x]. Pitao sam se koliko bi bolje performanse bilo kada bih koristio logičko množenje sa 1 da utvrdim da li je broj paran ili ne.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Moje iskustvo u programiranju u Gou nije mnogo, nešto više od godinu i po, koristio sam ga, doduše često, ali čisto u utilitarne svrhe (pa, možda osim jednog projekta koji se odnosi na http servis visokog opterećenja), pa sam počeo s tim. Otvorite GoLand i napišite jednostavan test
package main
import (
"fmt"
"log"
"math"
"math/rand"
"time"
)
const size = 100000000 //math.MaxInt32*2
type Result struct {
Name string
Duration time.Duration
Value int32
}
func main() {
log.Println("initial array capacity: " + fmt.Sprint(size))
var maxValue int32
// Будем варьировать диапазон чисел от минимального
// до максимального. Чем меньше диапазон, тем больше
// процессорного времени будет уходить на операцию
// сравнения текущего числа, с ранее найденным и наоборот
for maxValue = 128; maxValue < math.MaxInt32/2+1; maxValue = maxValue * 2 {
test(maxValue)
}
}
func test(maxValue int32) {
log.Println("max threshold: " + fmt.Sprint(maxValue))
arr := make([]int32, size)
for i := range arr {
arr[i] = rand.Int31n(maxValue)
// в тестовых данных нам нужны и отрицательные числа
sign := rand.Intn(2)
if sign == 1 {
arr[i] = -arr[i]
}
}
// запускаем тест "деление с остатком"
result := maxEvenDividing("maxEvenDividing", arr)
log.Printf(result.Name+"t result: "+fmt.Sprint(result.Value)+"ttduration %s", result.Duration)
// запускаем тест "конъюнкции"
result = maxEvenConjunction("maxEvenConjunction", arr)
log.Printf(result.Name+"t result: "+fmt.Sprint(result.Value)+"ttduration %s", result.Duration)
}
func maxEvenDividing(name string, arr []int32) Result {
start := time.Now()
var current int32 = math.MinInt32
for _, value := range arr {
if value > current && value%2 == 0 {
current = value
}
}
duration := time.Since(start)
result := Result{name, duration, current}
return result
}
func maxEvenConjunction(name string, arr []int32) Result {
start := time.Now()
var current int32 = math.MinInt32
for _, value := range arr {
if value > current && value&1 == 0 {
current = value
}
}
duration := time.Since(start)
result := Result{name, duration, current}
return result
}
Dobijamo rezultat koji pokazuje da što je prag veći, to se češće pojavljuju fluktuacije u performansama.
Uporeditemax threshold: 128
maxEvenDividing result: 126 duration 116.0067ms
maxEvenConjunction result: 126 duration 116.0066ms
max threshold: 16384
maxEvenDividing result: 16382 duration 115.0066ms
maxEvenConjunction result: 16382 duration 111.0064ms
......
max threshold: 8388608
maxEvenDividing result: 8388606 duration 109.0063ms
maxEvenConjunction result: 8388606 duration 109.0062ms
max threshold: 16777216
maxEvenDividing result: 16777214 duration 108.0062ms
maxEvenConjunction result: 16777214 duration 109.0062ms
max threshold: 33554432
maxEvenDividing result: 33554430 duration 114.0066ms
maxEvenConjunction result: 33554430 duration 110.0063ms
max threshold: 67108864
maxEvenDividing result: 67108860 duration 111.0064ms
maxEvenConjunction result: 67108860 duration 109.0062ms
max threshold: 134217728
maxEvenDividing result: 134217726 duration 108.0062ms
maxEvenConjunction result: 134217726 duration 109.0063ms
max threshold: 268435456
maxEvenDividing result: 268435446 duration 111.0063ms
maxEvenConjunction result: 268435446 duration 110.0063ms
Jasno je da u ovom slučaju, za različite pragove imamo različite skupove testnih podataka, opterećenje procesora (na mom i5-2540M laptopu) varira oko 20..30%, memorija koju zauzima aplikacija koja radi sa GoLand-a je u prosjeku oko 813MB - ovo takođe utiče na pouzdanost rezultata, potrebno je da sačuvate test slučajeve na disku i da pokrenete sve testove za svaki prag izolovano jedan od drugog.
I sada, razmišljajući o tome kako sve to implementirati uz minimalne troškove, automatski ispravljam provjeru stanja
if value > current && value&1 == 0 {
current = value
}
na
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Ponovo radim testove... i prestajem da razumijem bilo šta :)
Vrijeme utrošeno na izvršenje počinje da se razlikuje više ne za procente/djeliće procenta, već za 10..15%.Brzo dodajem još 2 testa:
func maxEvenDividing2(name string, arr []int32) Result {
start := time.Now()
var current int32 = math.MinInt32
for _, value := range arr {
if value <= current {
continue
}
if value%2 == 0 {
current = value
}
}
duration := time.Since(start)
result := Result{name, duration, current}
return result
}
func maxEvenConjunction2(name string, arr []int32) Result {
start := time.Now()
var current int32 = math.MinInt32
for _, value := range arr {
if value <= current {
continue
}
if value&1 == 0 {
current = value
}
}
duration := time.Since(start)
result := Result{name, duration, current}
return result
}
Pokrenem ga i dobijem ovu sliku:početni kapacitet niza: 100000000
maksimalni prag: 128
maxEvenDividing rezultat: 126 trajanje 116.0066ms
maxEvenDividing2 rezultat: 126 trajanje 79.0045ms
maxEvenConnjunction rezultat: 126 trajanje 114.0065ms
maxEvenConnjunction2 rezultat: 126 trajanje 83.0048ms
maksimalni prag: 256
maxEvenDividing rezultat: 254 trajanje 111.0063ms
maxEvenDividing2 rezultat: 254 trajanje 77.0044ms
maxEvenConnjunction rezultat: 254 trajanje 110.0063ms
maxEvenConnjunction2 rezultat: 254 trajanje 80.0046ms
maksimalni prag: 512
maxEvenDividing rezultat: 510 trajanje 114.0066ms
maxEvenDividing2 rezultat: 510 trajanje 80.0045ms
maxEvenConnjunction rezultat: 510 trajanje 110.0063ms
maxEvenConnjunction2 rezultat: 510 trajanje 80.0046ms
maksimalni prag: 1024
maxEvenDividing rezultat: 1022 trajanje 109.0063ms
maxEvenDividing2 rezultat: 1022 trajanje 77.0044ms
maxEvenConnjunction rezultat: 1022 trajanje 111.0063ms
maxEvenConnjunction2 rezultat: 1022 trajanje 81.0047ms
maksimalni prag: 2048
maxEvenDividing rezultat: 2046 trajanje 114.0065ms
maxEvenDividing2 rezultat: 2046 trajanje 79.0045ms
maxEvenConnjunction rezultat: 2046 trajanje 113.0065ms
maxEvenConnjunction2 rezultat: 2046 trajanje 81.0046ms
maksimalni prag: 4096
maxEvenDividing rezultat: 4094 trajanje 114.0065ms
maxEvenDividing2 rezultat: 4094 trajanje 80.0046ms
maxEvenConnjunction rezultat: 4094 trajanje 111.0063ms
maxEvenConnjunction2 rezultat: 4094 trajanje 78.0045ms
maksimalni prag: 8192
maxEvenDividing rezultat: 8190 trajanje 107.0062ms
maxEvenDividing2 rezultat: 8190 trajanje 77.0044ms
maxEvenConnjunction rezultat: 8190 trajanje 111.0063ms
maxEvenConnjunction2 rezultat: 8190 trajanje 77.0044ms
maksimalni prag: 16384
maxEvenDividing rezultat: 16382 trajanje 109.0063ms
maxEvenDividing2 rezultat: 16382 trajanje 77.0044ms
maxEvenConnjunction rezultat: 16382 trajanje 108.0062ms
maxEvenConnjunction2 rezultat: 16382 trajanje 77.0044ms
maksimalni prag: 32768
maxEvenDividing rezultat: 32766 trajanje 112.0064ms
maxEvenDividing2 rezultat: 32766 trajanje 77.0044ms
maxEvenConnjunction rezultat: 32766 trajanje 109.0062ms
maxEvenConnjunction2 rezultat: 32766 trajanje 78.0045ms
maksimalni prag: 65536
maxEvenDividing rezultat: 65534 trajanje 109.0062ms
maxEvenDividing2 rezultat: 65534 trajanje 75.0043ms
maxEvenConnjunction rezultat: 65534 trajanje 109.0063ms
maxEvenConnjunction2 rezultat: 65534 trajanje 79.0045ms
maksimalni prag: 131072
maxEvenDividing rezultat: 131070 trajanje 108.0061ms
maxEvenDividing2 rezultat: 131070 trajanje 76.0044ms
maxEvenConnjunction rezultat: 131070 trajanje 110.0063ms
maxEvenConnjunction2 rezultat: 131070 trajanje 80.0046ms
maksimalni prag: 262144
maxEvenDividing rezultat: 262142 trajanje 110.0063ms
maxEvenDividing2 rezultat: 262142 trajanje 76.0044ms
maxEvenConnjunction rezultat: 262142 trajanje 107.0061ms
maxEvenConnjunction2 rezultat: 262142 trajanje 78.0044ms
maksimalni prag: 524288
maxEvenDividing rezultat: 524286 trajanje 109.0062ms
maxEvenDividing2 rezultat: 524286 trajanje 78.0045ms
maxEvenConnjunction rezultat: 524286 trajanje 109.0062ms
maxEvenConnjunction2 rezultat: 524286 trajanje 80.0046ms
maksimalni prag: 1048576
maxEvenDividing rezultat: 1048574 trajanje 109.0063ms
maxEvenDividing2 rezultat: 1048574 trajanje 80.0045ms
maxEvenConnjunction rezultat: 1048574 trajanje 114.0066ms
maxEvenConnjunction2 rezultat: 1048574 trajanje 78.0044ms
maksimalni prag: 2097152
maxEvenDividing rezultat: 2097150 trajanje 111.0064ms
maxEvenDividing2 rezultat: 2097150 trajanje 79.0045ms
maxEvenConnjunction rezultat: 2097150 trajanje 112.0064ms
maxEvenConnjunction2 rezultat: 2097150 trajanje 77.0044ms
maksimalni prag: 4194304
maxEvenDividing rezultat: 4194302 trajanje 111.0063ms
maxEvenDividing2 rezultat: 4194302 trajanje 78.0045ms
maxEvenConnjunction rezultat: 4194302 trajanje 111.0063ms
maxEvenConnjunction2 rezultat: 4194302 trajanje 77.0044ms
maksimalni prag: 8388608
maxEvenDividing rezultat: 8388606 trajanje 109.0062ms
maxEvenDividing2 rezultat: 8388606 trajanje 78.0045ms
maxEvenConnjunction rezultat: 8388606 trajanje 114.0065ms
maxEvenConnjunction2 rezultat: 8388606 trajanje 78.0045ms
maksimalni prag: 16777216
maxEvenDividing rezultat: 16777214 trajanje 109.0062ms
maxEvenDividing2 rezultat: 16777214 trajanje 77.0044ms
maxEvenConnjunction rezultat: 16777214 trajanje 109.0063ms
maxEvenConnjunction2 rezultat: 16777214 trajanje 77.0044ms
maksimalni prag: 33554432
maxEvenDividing rezultat: 33554430 trajanje 113.0065ms
maxEvenDividing2 rezultat: 33554430 trajanje 78.0045ms
maxEvenConnjunction rezultat: 33554430 trajanje 110.0063ms
maxEvenConnjunction2 rezultat: 33554430 trajanje 80.0045ms
maksimalni prag: 67108864
maxEvenDividing rezultat: 67108860 trajanje 112.0064ms
maxEvenDividing2 rezultat: 67108860 trajanje 77.0044ms
maxEvenConnjunction rezultat: 67108860 trajanje 112.0064ms
maxEvenConnjunction2 rezultat: 67108860 trajanje 80.0046ms
maksimalni prag: 134217728
maxEvenDividing rezultat: 134217726 trajanje 109.0063ms
maxEvenDividing2 rezultat: 134217726 trajanje 78.0044ms
maxEvenConnjunction rezultat: 134217726 trajanje 114.0065ms
maxEvenConnjunction2 rezultat: 134217726 trajanje 81.0047ms
maksimalni prag: 268435456
maxEvenDividing rezultat: 268435446 trajanje 111.0064ms
maxEvenDividing2 rezultat: 268435446 trajanje 79.0045ms
maxEvenConnjunction rezultat: 268435446 trajanje 114.0065ms
maxEvenConnjunction2 rezultat: 268435446 trajanje 79.0045ms
maksimalni prag: 536870912
maxEvenDividing rezultat: 536870910 trajanje 107.0062ms
maxEvenDividing2 rezultat: 536870910 trajanje 76.0043ms
maxEvenConnjunction rezultat: 536870910 trajanje 109.0062ms
maxEvenConnjunction2 rezultat: 536870910 trajanje 80.0046ms
Nisam mogao da nađem jasno objašnjenje zašto Go kompajler ne optimizuje kod i uvek proverava drugi uslov, čak i ako je prvi netačan. Ili su mi možda oči samo zamagljene i ne vidim nikakvu očitu grešku? Ili trebate dati neka posebna uputstva kompajleru? Bilo bi mi drago za razumne komentare.
PS: Da, iz zabave, radio sam slične testove na Javi 5 i Javi 7/8 - sve je jasno, vrijeme izvršavanja je isto.
izvor: www.habr.com