Denkt u dat deze twee opties voor het testen van omstandigheden binnen een lus qua prestaties gelijkwaardig zijn?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Het begon allemaal met een “brain warming-up”; ik moest een voorbeeld geven van een optimale zoektocht naar het grootste even getal in een array van gehele getallen [-x....x]. Ik vroeg me af hoeveel betere prestaties zouden zijn als ik logische vermenigvuldiging met 1 zou gebruiken om erachter te komen of een getal even is of niet.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Mijn programmeerervaring in Go is niet erg uitgebreid, iets meer dan anderhalf jaar. Ik gebruikte het, hoewel vaak, maar puur voor utilitaire doeleinden (nou ja, misschien behalve één project gerelateerd aan een http-service met hoge belasting), dus ik begon ermee. Open GoLand en schrijf een eenvoudige 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
}
We krijgen een resultaat dat aantoont dat hoe hoger de drempel, hoe vaker er schommelingen in de prestaties optreden.
Vergelijkenmax 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
Het is duidelijk dat we in dit geval voor verschillende drempels verschillende sets testgegevens hebben, de processorbelasting (op mijn i5-2540M-laptop) varieert rond de 20..30%, het geheugen dat wordt ingenomen door de applicatie die draait vanaf GoLand is gemiddeld ongeveer 813 MB - dit heeft ook invloed op de betrouwbaarheid van het resultaat, u moet testgevallen op schijf opslaan en alle tests voor elke drempel afzonderlijk van elkaar uitvoeren.
En nu ik erover nadenk hoe ik dit allemaal met minimale kosten kan implementeren, corrigeer ik automatisch de conditiecontrole
if value > current && value&1 == 0 {
current = value
}
op
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Ik voer de tests opnieuw uit... en ik begrijp niets meer :)
De tijd die aan de uitvoering wordt besteed, begint niet langer te verschillen met percentages/fracties van een procent, maar met 10..15%. Ik voeg snel nog twee tests toe:
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
}
Ik voer het uit en krijg dit beeld:initiële arraycapaciteit: 100000000
maximale drempel: 128
maxEvenDividing resultaat: 126 duur 116.0066ms
maxEvenDividing2 resultaat: 126 duur 79.0045ms
maxEvenConjunction-resultaat: 126 duur 114.0065 ms
maxEvenConjunction2 resultaat: 126 duur 83.0048 ms
maximale drempel: 256
maxEvenDividing resultaat: 254 duur 111.0063ms
maxEvenDividing2 resultaat: 254 duur 77.0044ms
maxEvenConjunction-resultaat: 254 duur 110.0063 ms
maxEvenConjunction2 resultaat: 254 duur 80.0046 ms
maximale drempel: 512
maxEvenDividing resultaat: 510 duur 114.0066ms
maxEvenDividing2 resultaat: 510 duur 80.0045ms
maxEvenConjunction-resultaat: 510 duur 110.0063 ms
maxEvenConjunction2 resultaat: 510 duur 80.0046 ms
maximale drempel: 1024
maxEvenDividing resultaat: 1022 duur 109.0063ms
maxEvenDividing2 resultaat: 1022 duur 77.0044ms
maxEvenConjunction-resultaat: 1022 duur 111.0063 ms
maxEvenConjunction2 resultaat: 1022 duur 81.0047 ms
maximale drempel: 2048
maxEvenDividing resultaat: 2046 duur 114.0065ms
maxEvenDividing2 resultaat: 2046 duur 79.0045ms
maxEvenConjunction-resultaat: 2046 duur 113.0065 ms
maxEvenConjunction2 resultaat: 2046 duur 81.0046 ms
maximale drempel: 4096
maxEvenDividing resultaat: 4094 duur 114.0065ms
maxEvenDividing2 resultaat: 4094 duur 80.0046ms
maxEvenConjunction-resultaat: 4094 duur 111.0063 ms
maxEvenConjunction2 resultaat: 4094 duur 78.0045 ms
maximale drempel: 8192
maxEvenDividing resultaat: 8190 duur 107.0062ms
maxEvenDividing2 resultaat: 8190 duur 77.0044ms
maxEvenConjunction-resultaat: 8190 duur 111.0063 ms
maxEvenConjunction2 resultaat: 8190 duur 77.0044 ms
maximale drempel: 16384
maxEvenDividing resultaat: 16382 duur 109.0063ms
maxEvenDividing2 resultaat: 16382 duur 77.0044ms
maxEvenConjunction-resultaat: 16382 duur 108.0062 ms
maxEvenConjunction2 resultaat: 16382 duur 77.0044 ms
maximale drempel: 32768
maxEvenDividing resultaat: 32766 duur 112.0064ms
maxEvenDividing2 resultaat: 32766 duur 77.0044ms
maxEvenConjunction-resultaat: 32766 duur 109.0062 ms
maxEvenConjunction2 resultaat: 32766 duur 78.0045 ms
maximale drempel: 65536
maxEvenDividing resultaat: 65534 duur 109.0062ms
maxEvenDividing2 resultaat: 65534 duur 75.0043ms
maxEvenConjunction-resultaat: 65534 duur 109.0063 ms
maxEvenConjunction2 resultaat: 65534 duur 79.0045 ms
maximale drempel: 131072
maxEvenDividing resultaat: 131070 duur 108.0061ms
maxEvenDividing2 resultaat: 131070 duur 76.0044ms
maxEvenConjunction-resultaat: 131070 duur 110.0063 ms
maxEvenConjunction2 resultaat: 131070 duur 80.0046 ms
maximale drempel: 262144
maxEvenDividing resultaat: 262142 duur 110.0063ms
maxEvenDividing2 resultaat: 262142 duur 76.0044ms
maxEvenConjunction-resultaat: 262142 duur 107.0061 ms
maxEvenConjunction2 resultaat: 262142 duur 78.0044 ms
maximale drempel: 524288
maxEvenDividing resultaat: 524286 duur 109.0062ms
maxEvenDividing2 resultaat: 524286 duur 78.0045ms
maxEvenConjunction-resultaat: 524286 duur 109.0062 ms
maxEvenConjunction2 resultaat: 524286 duur 80.0046 ms
maximale drempel: 1048576
maxEvenDividing resultaat: 1048574 duur 109.0063ms
maxEvenDividing2 resultaat: 1048574 duur 80.0045ms
maxEvenConjunction-resultaat: 1048574 duur 114.0066 ms
maxEvenConjunction2 resultaat: 1048574 duur 78.0044 ms
maximale drempel: 2097152
maxEvenDividing resultaat: 2097150 duur 111.0064ms
maxEvenDividing2 resultaat: 2097150 duur 79.0045ms
maxEvenConjunction-resultaat: 2097150 duur 112.0064 ms
maxEvenConjunction2 resultaat: 2097150 duur 77.0044 ms
maximale drempel: 4194304
maxEvenDividing resultaat: 4194302 duur 111.0063ms
maxEvenDividing2 resultaat: 4194302 duur 78.0045ms
maxEvenConjunction-resultaat: 4194302 duur 111.0063 ms
maxEvenConjunction2 resultaat: 4194302 duur 77.0044 ms
maximale drempel: 8388608
maxEvenDividing resultaat: 8388606 duur 109.0062ms
maxEvenDividing2 resultaat: 8388606 duur 78.0045ms
maxEvenConjunction-resultaat: 8388606 duur 114.0065 ms
maxEvenConjunction2 resultaat: 8388606 duur 78.0045 ms
maximale drempel: 16777216
maxEvenDividing resultaat: 16777214 duur 109.0062ms
maxEvenDividing2 resultaat: 16777214 duur 77.0044ms
maxEvenConjunction-resultaat: 16777214 duur 109.0063 ms
maxEvenConjunction2 resultaat: 16777214 duur 77.0044 ms
maximale drempel: 33554432
maxEvenDividing resultaat: 33554430 duur 113.0065ms
maxEvenDividing2 resultaat: 33554430 duur 78.0045ms
maxEvenConjunction-resultaat: 33554430 duur 110.0063 ms
maxEvenConjunction2 resultaat: 33554430 duur 80.0045 ms
maximale drempel: 67108864
maxEvenDividing resultaat: 67108860 duur 112.0064ms
maxEvenDividing2 resultaat: 67108860 duur 77.0044ms
maxEvenConjunction-resultaat: 67108860 duur 112.0064 ms
maxEvenConjunction2 resultaat: 67108860 duur 80.0046 ms
maximale drempel: 134217728
maxEvenDividing resultaat: 134217726 duur 109.0063ms
maxEvenDividing2 resultaat: 134217726 duur 78.0044ms
maxEvenConjunction-resultaat: 134217726 duur 114.0065 ms
maxEvenConjunction2 resultaat: 134217726 duur 81.0047 ms
maximale drempel: 268435456
maxEvenDividing resultaat: 268435446 duur 111.0064ms
maxEvenDividing2 resultaat: 268435446 duur 79.0045ms
maxEvenConjunction-resultaat: 268435446 duur 114.0065 ms
maxEvenConjunction2 resultaat: 268435446 duur 79.0045 ms
maximale drempel: 536870912
maxEvenDividing resultaat: 536870910 duur 107.0062ms
maxEvenDividing2 resultaat: 536870910 duur 76.0043ms
maxEvenConjunction-resultaat: 536870910 duur 109.0062 ms
maxEvenConjunction2 resultaat: 536870910 duur 80.0046 ms
Ik kon geen duidelijke verklaring vinden waarom de Go-compiler de code niet optimaliseert en altijd de tweede voorwaarde controleert, zelfs als de eerste onwaar is. Of misschien zijn mijn ogen gewoon wazig en zie ik geen duidelijke fout? Of moet u speciale instructies aan de compiler geven? Ik zou blij zijn met zinnige opmerkingen.
PS: Ja, voor de lol heb ik soortgelijke tests uitgevoerd op Java 5 en Java 7/8 - alles is duidelijk, de uitvoeringstijd is hetzelfde.
Bron: www.habr.com