Šta mislite, da li su ova dva uslova unutar petlje ekvivalentna po performansama?
if a > b && c*2 > d {
....
}
// i
if a d {
....
}
Sve je počelo kao "zagrijavanje za mozak", trebalo je dati primjer optimalne pretrage u nizu celih brojeva [-x….x] najvećeg parnog broja. Zainteresovalo me je koliko će performanse rasti ako se kod utvrđivanja da li je broj paran ili nije, koristi logičko množenje s 1.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Moje iskustvo programiranja u Go-u nije previše veliko, malo više od godinu i po dana, koristio sam ga i često, ali isključivo u utilitarnim svrhama (možda osim jednog projekta vezanog za visoko opterećeni http servis), zato sam i počeo upravo s njim. Otvaramo GoLand i pišemo 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("početni kapacitet niza: " + fmt.Sprint(size))
var maxValue int32
// Variraćemo opseg brojeva od minimalnog
// do maksimalnog. Što je opseg manji, to će više
// procesorskog vremena ići na operaciju
// poređenja trenutnog broja sa prethodno pronađenim i obrnuto
for maxValue = 128; maxValue Dobijamo rezultat koji pokazuje da što je viši prag, to se češće javljaju fluktuacije u pogledu performansi.
Poredimaksimalni prag: 128
maksimalni rezultatEvenDividing: 126 trajanje 116.0067ms
maksimalni rezultatEvenConjunction: 126 trajanje 116.0066ms
maksimalni prag: 16384
maxEvenDividing rezultat: 16382 trajanje 115.0066ms
maxEvenConjunction rezultat: 16382 trajanje 111.0064ms
......
maksimalni prag: 8388608
maxEvenDividing rezultat: 8388606 trajanje 109.0063ms
maxEvenConjunction rezultat: 8388606 trajanje 109.0062ms
maksimalni prag: 16777216
maxEvenDividing rezultat: 16777214 trajanje 108.0062ms
maxEvenConjunction rezultat: 16777214 trajanje 109.0062ms
maksimalni prag: 33554432
maxEvenDividing rezultat: 33554430 trajanje 114.0066ms
maxEvenConjunction rezultat: 33554430 trajanje 110.0063ms
maksimalni prag: 67108864
maxEvenDividing rezultat: 67108860 trajanje 111.0064ms
maxEvenConjunction rezultat: 67108860 trajanje 109.0062ms
maksimalni prag: 134217728
maxEvenDividing rezultat: 134217726 trajanje 108.0062ms
maxEvenConjunction rezultat: 134217726 trajanje 109.0063ms
maksimalni prag: 268435456
maxEvenDividing rezultat: 268435446 trajanje 111.0063ms
maxEvenConjunction rezultat: 268435446 trajanje 110.0063ms
Jasno je da u ovom slučaju imamo različite skupove testnih podataka za različite pragove, opterećenje procesora (na mom laptopu i5-2540M) varira u rasponu od 20..30%, dok aplikacija pokrenuta iz GoLand zauzima oko 813MB — to također utiče na tačnost rezultata, potrebno je implementirati čuvanje testnih skupova na disku i izvršiti sve testove za svaki prag izolovano.
I tako razmišljajući o tome kako sve to realizovati uz minimalne troškove, instinktivno ispravljam proveru uslova
if value > current && value&1 == 0 {
current = value
}
na
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
ponovo pokrećem testove... i prestajem da razumem 🙂
Vreme koje se troši na izvršenje se sada razlikuje ne samo za procente, 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
}
pokrećem i dobijam ovakvu sliku:početni kapacitet niza: 100000000
maksimalni prag: 128
maxEvenDividing rezultat: 126 trajanje 116.0066ms
maxEvenDividing2 rezultat: 126 trajanje 79.0045ms
maxEvenConjunction rezultat: 126 trajanje 114.0065ms
maxEvenConjunction2 rezultat: 126 trajanje 83.0048ms
maksimalni prag: 256
maxEvenDividing rezultat: 254 trajanje 111.0063ms
maxEvenDividing2 rezultat: 254 trajanje 77.0044ms
maxEvenConjunction rezultat: 254 trajanje 110.0063ms
maxEvenConjunction2 rezultat: 254 trajanje 80.0046ms
maksimalni prag: 512
maxEvenDividing rezultat: 510 trajanje 114.0066ms
maxEvenDividing2 rezultat: 510 trajanje 80.0045ms
maxEvenConjunction rezultat: 510 trajanje 110.0063ms
maxEvenConjunction2 rezultat: 510 trajanje 80.0046ms
maksimalni prag: 1024
maxEvenDividing rezultat: 1022 trajanje 109.0063ms
maxEvenDividing2 rezultat: 1022 trajanje 77.0044ms
maxEvenConjunction rezultat: 1022 trajanje 111.0063ms
maxEvenConjunction2 rezultat: 1022 trajanje 81.0047ms
maksimalni prag: 2048
maxEvenDividing rezultat: 2046 trajanje 114.0065ms
maxEvenDividing2 rezultat: 2046 trajanje 79.0045ms
maxEvenConjunction rezultat: 2046 trajanje 113.0065ms
maxEvenConjunction2 rezultat: 2046 trajanje 81.0046ms
maksimalni prag: 4096
maxEvenDividing rezultat: 4094 trajanje 114.0065ms
maxEvenDividing2 rezultat: 4094 trajanje 80.0046ms
maxEvenConjunction rezultat: 4094 trajanje 111.0063ms
maxEvenConjunction2 rezultat: 4094 trajanje 78.0045ms
maksimalni prag: 8192
maxEvenDividing rezultat: 8190 trajanje 107.0062ms
maxEvenDividing2 rezultat: 8190 trajanje 77.0044ms
maxEvenConjunction rezultat: 8190 trajanje 111.0063ms
maxEvenConjunction2 rezultat: 8190 trajanje 77.0044ms
maksimalni prag: 16384
maxEvenDividing rezultat: 16382 trajanje 109.0063ms
maxEvenDividing2 rezultat: 16382 trajanje 77.0044ms
maxEvenConjunction rezultat: 16382 trajanje 108.0062ms
maxEvenConjunction2 rezultat: 16382 trajanje 77.0044ms
maksimalni prag: 32768
maxEvenDividing rezultat: 32766 trajanje 112.0064ms
maxEvenDividing2 rezultat: 32766 trajanje 77.0044ms
maxEvenConjunction rezultat: 32766 trajanje 109.0062ms
maxEvenConjunction2 rezultat: 32766 trajanje 78.0045ms
maksimalni prag: 65536
maxEvenDividing rezultat: 65534 trajanje 109.0062ms
maxEvenDividing2 rezultat: 65534 trajanje 75.0043ms
maxEvenConjunction rezultat: 65534 trajanje 109.0063ms
maxEvenConjunction2 rezultat: 65534 trajanje 79.0045ms
maksimalni prag: 131072
maxEvenDividing rezultat: 131070 trajanje 108.0061ms
maxEvenDividing2 rezultat: 131070 trajanje 76.0044ms
maxEvenConjunction rezultat: 131070 trajanje 110.0063ms
maxEvenConjunction2 rezultat: 131070 trajanje 80.0046ms
maksimalni prag: 262144
maxEvenDividing rezultat: 262142 trajanje 110.0063ms
maxEvenDividing2 rezultat: 262142 trajanje 76.0044ms
maxEvenConjunction rezultat: 262142 trajanje 107.0061ms
maxEvenConjunction2 rezultat: 262142 trajanje 78.0044ms
maksimalni prag: 524288
maxEvenDividing rezultat: 524286 trajanje 109.0062ms
maxEvenDividing2 rezultat: 524286 trajanje 78.0045ms
maxEvenConjunction rezultat: 524286 trajanje 109.0062ms
maxEvenConjunction2 rezultat: 524286 trajanje 80.0046ms
maksimalni prag: 1048576
maxEvenDividing rezultat: 1048574 trajanje 109.0063ms
maxEvenDividing2 rezultat: 1048574 trajanje 80.0045ms
maxEvenConjunction rezultat: 1048574 trajanje 114.0066ms
maxEvenConjunction2 rezultat: 1048574 trajanje 78.0044ms
maksimalni prag: 2097152
maxEvenDividing rezultat: 2097150 trajanje 111.0064ms
maxEvenDividing2 rezultat: 2097150 trajanje 79.0045ms
maxEvenConjunction rezultat: 2097150 trajanje 112.0064ms
maxEvenConjunction2 rezultat: 2097150 trajanje 77.0044ms
maksimalni prag: 4194304
maxEvenDividing rezultat: 4194302 trajanje 111.0063ms
maxEvenDividing2 rezultat: 4194302 trajanje 78.0045ms
maxEvenConjunction rezultat: 4194302 trajanje 111.0063ms
maxEvenConjunction2 rezultat: 4194302 trajanje 77.0044ms
maksimalni prag: 8388608
maxEvenDividing rezultat: 8388606 trajanje 109.0062ms
maxEvenDividing2 rezultat: 8388606 trajanje 78.0045ms
maxEvenConjunction rezultat: 8388606 trajanje 114.0065ms
maxEvenConjunction2 rezultat: 8388606 trajanje 78.0045ms
maksimalni prag: 16777216
maxEvenDividing rezultat: 16777214 trajanje 109.0062ms
maxEvenDividing2 rezultat: 16777214 trajanje 77.0044ms
maxEvenConjunction rezultat: 16777214 trajanje 109.0063ms
maxEvenConjunction2 rezultat: 16777214 trajanje 77.0044ms
maksimalni prag: 33554432
maxEvenDividing rezultat: 33554430 trajanje 113.0065ms
maxEvenDividing2 rezultat: 33554430 trajanje 78.0045ms
maxEvenConjunction rezultat: 33554430 trajanje 110.0063ms
maxEvenConjunction2 rezultat: 33554430 trajanje 80.0045ms
maksimalni prag: 67108864
maxEvenDividing rezultat: 67108860 trajanje 112.0064ms
maxEvenDividing2 rezultat: 67108860 trajanje 77.0044ms
maxEvenConjunction rezultat: 67108860 trajanje 112.0064ms
maxEvenConjunction2 rezultat: 67108860 trajanje 80.0046ms
maksimalni prag: 134217728
maxEvenDividing rezultat: 134217726 trajanje 109.0063ms
maxEvenDividing2 rezultat: 134217726 trajanje 78.0044ms
maxEvenConjunction rezultat: 134217726 trajanje 114.0065ms
maxEvenConjunction2 rezultat: 134217726 trajanje 81.0047ms
maksimalni prag: 268435456
maxEvenDividing rezultat: 268435446 trajanje 111.0064ms
maxEvenDividing2 rezultat: 268435446 trajanje 79.0045ms
maxEvenConjunction rezultat: 268435446 trajanje 114.0065ms
maxEvenConjunction2 rezultat: 268435446 trajanje 79.0045ms
maksimalni prag: 536870912
maxEvenDividing rezultat: 536870910 trajanje 107.0062ms
maxEvenDividing2 rezultat: 536870910 trajanje 76.0043ms
maxEvenConjunction rezultat: 536870910 trajanje 109.0062ms
maxEvenConjunction2 rezultat: 536870910 trajanje 80.0046ms
Nisam našao jasnog objašnjenja zašto Go kompajler ne optimizira kod i uvijek provjerava drugo stanje, čak i ako je prvo lažno — možda jednostavno ne primjećujem neku očiglednu grešku? Ili trebam dati posebne instrukcije kompajleru? Bio bih zahvalan na korisnim komentarima.
PS: Da, iz znatiželje, izveo sam slične testove na Java 5 i Java 7/8 — sve je jasno, vrijeme izvođenja je isto.
Izvor: habr.com
