Tror du, at disse to muligheder for at teste forhold inde i en loop er ækvivalente i ydeevne?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Det hele startede med en "hjerneopvarmning"; jeg skulle give et eksempel på en optimal søgning efter det største lige tal i en række heltal [-x....x]. Jeg spekulerede på, hvor meget bedre ydeevne ville være, hvis jeg brugte logisk multiplikation med 1 for at finde ud af, om et tal er lige eller ej.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Min programmeringserfaring i Go er ikke særlig omfattende, lidt over halvandet år, jeg brugte den, dog ofte, men udelukkende til utilitaristiske formål (nå, måske bortset fra et projekt relateret til en http-tjeneste med høj belastning), så jeg startede med det. Åbn GoLand og skriv en simpel 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, der viser, at jo højere tærsklen er, jo oftere opstår udsving i ydeevnen.
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 tilfælde, for forskellige tærskler, har vi forskellige sæt af testdata, processorbelastningen (på min i5-2540M bærbare computer) varierer omkring 20..30%, hukommelsen optaget af applikationen, der kører fra GoLand, er i gennemsnit omkring 813MB - dette påvirker også pålideligheden af resultatet, du skal gemme testcases på disken og køre alle tests for hver tærskel isoleret fra hinanden.
Og nu, når jeg tænker på, hvordan man implementerer alt dette med minimale omkostninger, retter jeg automatisk tilstandskontrollen
if value > current && value&1 == 0 {
current = value
}
på
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Jeg kører testene igen... og jeg holder op med at forstå noget :)
Tiden brugt på udførelse begynder ikke længere at variere med procenter/brøkdele af en procent, men med 10..15 %. Jeg tilføjer hurtigt 2 test mere:
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 kører det og får dette billede:indledende array kapacitet: 100000000
max tærskel: 128
maxEvenDividing resultat: 126 varighed 116.0066ms
maxEvenDividing2 resultat: 126 varighed 79.0045ms
maxEvenConjunction resultat: 126 varighed 114.0065ms
maxEvenConjunction2 resultat: 126 varighed 83.0048ms
max tærskel: 256
maxEvenDividing resultat: 254 varighed 111.0063ms
maxEvenDividing2 resultat: 254 varighed 77.0044ms
maxEvenConjunction resultat: 254 varighed 110.0063ms
maxEvenConjunction2 resultat: 254 varighed 80.0046ms
max tærskel: 512
maxEvenDividing resultat: 510 varighed 114.0066ms
maxEvenDividing2 resultat: 510 varighed 80.0045ms
maxEvenConjunction resultat: 510 varighed 110.0063ms
maxEvenConjunction2 resultat: 510 varighed 80.0046ms
max tærskel: 1024
maxEvenDividing resultat: 1022 varighed 109.0063ms
maxEvenDividing2 resultat: 1022 varighed 77.0044ms
maxEvenConjunction resultat: 1022 varighed 111.0063ms
maxEvenConjunction2 resultat: 1022 varighed 81.0047ms
max tærskel: 2048
maxEvenDividing resultat: 2046 varighed 114.0065ms
maxEvenDividing2 resultat: 2046 varighed 79.0045ms
maxEvenConjunction resultat: 2046 varighed 113.0065ms
maxEvenConjunction2 resultat: 2046 varighed 81.0046ms
max tærskel: 4096
maxEvenDividing resultat: 4094 varighed 114.0065ms
maxEvenDividing2 resultat: 4094 varighed 80.0046ms
maxEvenConjunction resultat: 4094 varighed 111.0063ms
maxEvenConjunction2 resultat: 4094 varighed 78.0045ms
max tærskel: 8192
maxEvenDividing resultat: 8190 varighed 107.0062ms
maxEvenDividing2 resultat: 8190 varighed 77.0044ms
maxEvenConjunction resultat: 8190 varighed 111.0063ms
maxEvenConjunction2 resultat: 8190 varighed 77.0044ms
max tærskel: 16384
maxEvenDividing resultat: 16382 varighed 109.0063ms
maxEvenDividing2 resultat: 16382 varighed 77.0044ms
maxEvenConjunction resultat: 16382 varighed 108.0062ms
maxEvenConjunction2 resultat: 16382 varighed 77.0044ms
max tærskel: 32768
maxEvenDividing resultat: 32766 varighed 112.0064ms
maxEvenDividing2 resultat: 32766 varighed 77.0044ms
maxEvenConjunction resultat: 32766 varighed 109.0062ms
maxEvenConjunction2 resultat: 32766 varighed 78.0045ms
max tærskel: 65536
maxEvenDividing resultat: 65534 varighed 109.0062ms
maxEvenDividing2 resultat: 65534 varighed 75.0043ms
maxEvenConjunction resultat: 65534 varighed 109.0063ms
maxEvenConjunction2 resultat: 65534 varighed 79.0045ms
max tærskel: 131072
maxEvenDividing resultat: 131070 varighed 108.0061ms
maxEvenDividing2 resultat: 131070 varighed 76.0044ms
maxEvenConjunction resultat: 131070 varighed 110.0063ms
maxEvenConjunction2 resultat: 131070 varighed 80.0046ms
max tærskel: 262144
maxEvenDividing resultat: 262142 varighed 110.0063ms
maxEvenDividing2 resultat: 262142 varighed 76.0044ms
maxEvenConjunction resultat: 262142 varighed 107.0061ms
maxEvenConjunction2 resultat: 262142 varighed 78.0044ms
max tærskel: 524288
maxEvenDividing resultat: 524286 varighed 109.0062ms
maxEvenDividing2 resultat: 524286 varighed 78.0045ms
maxEvenConjunction resultat: 524286 varighed 109.0062ms
maxEvenConjunction2 resultat: 524286 varighed 80.0046ms
max tærskel: 1048576
maxEvenDividing resultat: 1048574 varighed 109.0063ms
maxEvenDividing2 resultat: 1048574 varighed 80.0045ms
maxEvenConjunction resultat: 1048574 varighed 114.0066ms
maxEvenConjunction2 resultat: 1048574 varighed 78.0044ms
max tærskel: 2097152
maxEvenDividing resultat: 2097150 varighed 111.0064ms
maxEvenDividing2 resultat: 2097150 varighed 79.0045ms
maxEvenConjunction resultat: 2097150 varighed 112.0064ms
maxEvenConjunction2 resultat: 2097150 varighed 77.0044ms
max tærskel: 4194304
maxEvenDividing resultat: 4194302 varighed 111.0063ms
maxEvenDividing2 resultat: 4194302 varighed 78.0045ms
maxEvenConjunction resultat: 4194302 varighed 111.0063ms
maxEvenConjunction2 resultat: 4194302 varighed 77.0044ms
max tærskel: 8388608
maxEvenDividing resultat: 8388606 varighed 109.0062ms
maxEvenDividing2 resultat: 8388606 varighed 78.0045ms
maxEvenConjunction resultat: 8388606 varighed 114.0065ms
maxEvenConjunction2 resultat: 8388606 varighed 78.0045ms
max tærskel: 16777216
maxEvenDividing resultat: 16777214 varighed 109.0062ms
maxEvenDividing2 resultat: 16777214 varighed 77.0044ms
maxEvenConjunction resultat: 16777214 varighed 109.0063ms
maxEvenConjunction2 resultat: 16777214 varighed 77.0044ms
max tærskel: 33554432
maxEvenDividing resultat: 33554430 varighed 113.0065ms
maxEvenDividing2 resultat: 33554430 varighed 78.0045ms
maxEvenConjunction resultat: 33554430 varighed 110.0063ms
maxEvenConjunction2 resultat: 33554430 varighed 80.0045ms
max tærskel: 67108864
maxEvenDividing resultat: 67108860 varighed 112.0064ms
maxEvenDividing2 resultat: 67108860 varighed 77.0044ms
maxEvenConjunction resultat: 67108860 varighed 112.0064ms
maxEvenConjunction2 resultat: 67108860 varighed 80.0046ms
max tærskel: 134217728
maxEvenDividing resultat: 134217726 varighed 109.0063ms
maxEvenDividing2 resultat: 134217726 varighed 78.0044ms
maxEvenConjunction resultat: 134217726 varighed 114.0065ms
maxEvenConjunction2 resultat: 134217726 varighed 81.0047ms
max tærskel: 268435456
maxEvenDividing resultat: 268435446 varighed 111.0064ms
maxEvenDividing2 resultat: 268435446 varighed 79.0045ms
maxEvenConjunction resultat: 268435446 varighed 114.0065ms
maxEvenConjunction2 resultat: 268435446 varighed 79.0045ms
max tærskel: 536870912
maxEvenDividing resultat: 536870910 varighed 107.0062ms
maxEvenDividing2 resultat: 536870910 varighed 76.0043ms
maxEvenConjunction resultat: 536870910 varighed 109.0062ms
maxEvenConjunction2 resultat: 536870910 varighed 80.0046ms
Jeg kunne ikke finde en klar forklaring på, hvorfor Go-kompileren ikke optimerer koden og altid tjekker den anden betingelse, selvom den første er falsk. Eller måske er mine øjne bare slørede, og jeg kan ikke se nogen åbenlys fejl? Eller skal du give nogle specielle instruktioner til compileren? Jeg ville blive glad for fornuftige kommentarer.
PS: Ja, bare for sjov, kørte jeg lignende test på Java 5 og Java 7/8 - alt er klart, udførelsestiden er den samme.
Kilde: www.habr.com