Tror du disse to alternativene for å teste forhold inne i en sløyfe er like i ytelse?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Det hele startet med en "hjerneoppvarming"; jeg måtte gi et eksempel på et optimalt søk etter det største partall i en rekke heltall [-x....x]. Jeg lurte på hvor mye bedre ytelsen ville vært hvis jeg brukte logisk multiplikasjon med 1 for å finne ut om et tall er partall eller ikke.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Min programmeringserfaring i Go er ikke særlig omfattende, litt over halvannet år, jeg brukte den, men ofte, men rent for utilitaristiske formål (vel, kanskje bortsett fra ett prosjekt relatert til en høybelastnings http-tjeneste), så jeg startet med det. Åpne GoLand og skriv en enkel 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
}
Vi får et resultat som viser at jo høyere terskelen er, jo oftere dukker det opp svingninger i ytelsen.
Sammenlignemax 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
Det er klart at i dette tilfellet, for forskjellige terskler har vi forskjellige sett med testdata, prosessorbelastningen (på min bærbare i5-2540M) varierer rundt 20..30%, minnet som er okkupert av applikasjonen som kjører fra GoLand er i gjennomsnitt ca 813MB - dette påvirker også påliteligheten til resultatet, du må lagre testtilfeller på disk og kjøre alle tester for hver terskel isolert fra hverandre.
Og nå, når jeg tenker på hvordan jeg skal implementere alt dette med minimale kostnader, retter jeg automatisk tilstandskontrollen
if value > current && value&1 == 0 {
current = value
}
på
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Jeg kjører testene igjen... og jeg slutter å forstå noe :)
Tiden brukt på utførelse begynner å variere ikke med prosenter/brøkdeler av en prosent, men med 10..15%. Jeg legger raskt til 2 tester til:
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
}
Jeg kjører den og får dette bildet:innledende matrisekapasitet: 100000000
maks terskel: 128
maxEvenDividing resultat: 126 varighet 116.0066ms
maxEvenDividing2 resultat: 126 varighet 79.0045ms
maxEvenConjunction resultat: 126 varighet 114.0065ms
maxEvenConjunction2 resultat: 126 varighet 83.0048ms
maks terskel: 256
maxEvenDividing resultat: 254 varighet 111.0063ms
maxEvenDividing2 resultat: 254 varighet 77.0044ms
maxEvenConjunction resultat: 254 varighet 110.0063ms
maxEvenConjunction2 resultat: 254 varighet 80.0046ms
maks terskel: 512
maxEvenDividing resultat: 510 varighet 114.0066ms
maxEvenDividing2 resultat: 510 varighet 80.0045ms
maxEvenConjunction resultat: 510 varighet 110.0063ms
maxEvenConjunction2 resultat: 510 varighet 80.0046ms
maks terskel: 1024
maxEvenDividing resultat: 1022 varighet 109.0063ms
maxEvenDividing2 resultat: 1022 varighet 77.0044ms
maxEvenConjunction resultat: 1022 varighet 111.0063ms
maxEvenConjunction2 resultat: 1022 varighet 81.0047ms
maks terskel: 2048
maxEvenDividing resultat: 2046 varighet 114.0065ms
maxEvenDividing2 resultat: 2046 varighet 79.0045ms
maxEvenConjunction resultat: 2046 varighet 113.0065ms
maxEvenConjunction2 resultat: 2046 varighet 81.0046ms
maks terskel: 4096
maxEvenDividing resultat: 4094 varighet 114.0065ms
maxEvenDividing2 resultat: 4094 varighet 80.0046ms
maxEvenConjunction resultat: 4094 varighet 111.0063ms
maxEvenConjunction2 resultat: 4094 varighet 78.0045ms
maks terskel: 8192
maxEvenDividing resultat: 8190 varighet 107.0062ms
maxEvenDividing2 resultat: 8190 varighet 77.0044ms
maxEvenConjunction resultat: 8190 varighet 111.0063ms
maxEvenConjunction2 resultat: 8190 varighet 77.0044ms
maks terskel: 16384
maxEvenDividing resultat: 16382 varighet 109.0063ms
maxEvenDividing2 resultat: 16382 varighet 77.0044ms
maxEvenConjunction resultat: 16382 varighet 108.0062ms
maxEvenConjunction2 resultat: 16382 varighet 77.0044ms
maks terskel: 32768
maxEvenDividing resultat: 32766 varighet 112.0064ms
maxEvenDividing2 resultat: 32766 varighet 77.0044ms
maxEvenConjunction resultat: 32766 varighet 109.0062ms
maxEvenConjunction2 resultat: 32766 varighet 78.0045ms
maks terskel: 65536
maxEvenDividing resultat: 65534 varighet 109.0062ms
maxEvenDividing2 resultat: 65534 varighet 75.0043ms
maxEvenConjunction resultat: 65534 varighet 109.0063ms
maxEvenConjunction2 resultat: 65534 varighet 79.0045ms
maks terskel: 131072
maxEvenDividing resultat: 131070 varighet 108.0061ms
maxEvenDividing2 resultat: 131070 varighet 76.0044ms
maxEvenConjunction resultat: 131070 varighet 110.0063ms
maxEvenConjunction2 resultat: 131070 varighet 80.0046ms
maks terskel: 262144
maxEvenDividing resultat: 262142 varighet 110.0063ms
maxEvenDividing2 resultat: 262142 varighet 76.0044ms
maxEvenConjunction resultat: 262142 varighet 107.0061ms
maxEvenConjunction2 resultat: 262142 varighet 78.0044ms
maks terskel: 524288
maxEvenDividing resultat: 524286 varighet 109.0062ms
maxEvenDividing2 resultat: 524286 varighet 78.0045ms
maxEvenConjunction resultat: 524286 varighet 109.0062ms
maxEvenConjunction2 resultat: 524286 varighet 80.0046ms
maks terskel: 1048576
maxEvenDividing resultat: 1048574 varighet 109.0063ms
maxEvenDividing2 resultat: 1048574 varighet 80.0045ms
maxEvenConjunction resultat: 1048574 varighet 114.0066ms
maxEvenConjunction2 resultat: 1048574 varighet 78.0044ms
maks terskel: 2097152
maxEvenDividing resultat: 2097150 varighet 111.0064ms
maxEvenDividing2 resultat: 2097150 varighet 79.0045ms
maxEvenConjunction resultat: 2097150 varighet 112.0064ms
maxEvenConjunction2 resultat: 2097150 varighet 77.0044ms
maks terskel: 4194304
maxEvenDividing resultat: 4194302 varighet 111.0063ms
maxEvenDividing2 resultat: 4194302 varighet 78.0045ms
maxEvenConjunction resultat: 4194302 varighet 111.0063ms
maxEvenConjunction2 resultat: 4194302 varighet 77.0044ms
maks terskel: 8388608
maxEvenDividing resultat: 8388606 varighet 109.0062ms
maxEvenDividing2 resultat: 8388606 varighet 78.0045ms
maxEvenConjunction resultat: 8388606 varighet 114.0065ms
maxEvenConjunction2 resultat: 8388606 varighet 78.0045ms
maks terskel: 16777216
maxEvenDividing resultat: 16777214 varighet 109.0062ms
maxEvenDividing2 resultat: 16777214 varighet 77.0044ms
maxEvenConjunction resultat: 16777214 varighet 109.0063ms
maxEvenConjunction2 resultat: 16777214 varighet 77.0044ms
maks terskel: 33554432
maxEvenDividing resultat: 33554430 varighet 113.0065ms
maxEvenDividing2 resultat: 33554430 varighet 78.0045ms
maxEvenConjunction resultat: 33554430 varighet 110.0063ms
maxEvenConjunction2 resultat: 33554430 varighet 80.0045ms
maks terskel: 67108864
maxEvenDividing resultat: 67108860 varighet 112.0064ms
maxEvenDividing2 resultat: 67108860 varighet 77.0044ms
maxEvenConjunction resultat: 67108860 varighet 112.0064ms
maxEvenConjunction2 resultat: 67108860 varighet 80.0046ms
maks terskel: 134217728
maxEvenDividing resultat: 134217726 varighet 109.0063ms
maxEvenDividing2 resultat: 134217726 varighet 78.0044ms
maxEvenConjunction resultat: 134217726 varighet 114.0065ms
maxEvenConjunction2 resultat: 134217726 varighet 81.0047ms
maks terskel: 268435456
maxEvenDividing resultat: 268435446 varighet 111.0064ms
maxEvenDividing2 resultat: 268435446 varighet 79.0045ms
maxEvenConjunction resultat: 268435446 varighet 114.0065ms
maxEvenConjunction2 resultat: 268435446 varighet 79.0045ms
maks terskel: 536870912
maxEvenDividing resultat: 536870910 varighet 107.0062ms
maxEvenDividing2 resultat: 536870910 varighet 76.0043ms
maxEvenConjunction resultat: 536870910 varighet 109.0062ms
maxEvenConjunction2 resultat: 536870910 varighet 80.0046ms
Jeg kunne ikke finne en klar forklaring på hvorfor Go-kompilatoren ikke optimaliserer koden og alltid sjekker den andre betingelsen, selv om den første er falsk. Eller kanskje øynene mine bare er uklare og jeg ser ingen åpenbar feil? Eller trenger du å gi noen spesielle instruksjoner til kompilatoren? Jeg blir glad for fornuftige kommentarer.
PS: Ja, bare for moro skyld kjørte jeg lignende tester på Java 5 og Java 7/8 - alt er klart, utførelsestiden er den samme.
Kilde: www.habr.com