Crezi că aceste două opțiuni pentru testarea condițiilor în interiorul unei bucle sunt echivalente ca performanță?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Totul a început cu o „încălzire a creierului”; a trebuit să dau un exemplu de căutare optimă pentru cel mai mare număr par dintr-o matrice de numere întregi [-x....x]. Mă întrebam cât de mult ar fi performanța mai bună dacă aș folosi înmulțirea logică cu 1 pentru a-mi da seama dacă un număr este par sau nu.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Experiența mea de programare în Go nu este foarte extinsă, puțin peste un an și jumătate, l-am folosit, deși des, dar pur în scopuri utilitare (bine, poate cu excepția unui proiect legat de un serviciu http de încărcare mare), așa că am a inceput cu ea. Deschideți GoLand și scrieți un test simplu
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
}
Obținem un rezultat care arată că cu cât pragul este mai mare, cu atât mai des apar fluctuații ale performanței.
Сравнитеmax 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
Este clar că în acest caz, pentru diferite praguri avem seturi diferite de date de testare, sarcina procesorului (pe laptopul meu i5-2540M) variază în jur de 20..30%, memoria ocupată de aplicația care rulează de pe GoLand este în medie. aproximativ 813MB - acest lucru afectează și fiabilitatea rezultatului, trebuie să salvați cazurile de testare pe disc și să rulați toate testele pentru fiecare prag izolat unul de celălalt.
Și acum, gândindu-mă la cum să implementez toate acestea cu costuri minime, corectez automat verificarea stării
if value > current && value&1 == 0 {
current = value
}
pe
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Dau din nou testele... si nu mai inteleg nimic :)
Timpul petrecut la executie incepe sa difere nu mai in procente/fractii de procent, ci cu 10..15%.Adaug rapid inca 2 teste:
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
}
Îl rulez și iau această poză:capacitatea inițială a matricei: 100000000
prag maxim: 128
maxEvenDividing rezultat: 126 durată 116.0066ms
rezultat maxEvenDividing2: 126 durată 79.0045 ms
maxEvenConjunction rezultat: 126 durată 114.0065ms
rezultat maxEvenConjunction2: 126 durată 83.0048ms
prag maxim: 256
maxEvenDividing rezultat: 254 durată 111.0063ms
rezultat maxEvenDividing2: 254 durată 77.0044 ms
maxEvenConjunction rezultat: 254 durată 110.0063ms
rezultat maxEvenConjunction2: 254 durată 80.0046ms
prag maxim: 512
maxEvenDividing rezultat: 510 durată 114.0066ms
rezultat maxEvenDividing2: 510 durată 80.0045 ms
maxEvenConjunction rezultat: 510 durată 110.0063ms
rezultat maxEvenConjunction2: 510 durată 80.0046ms
prag maxim: 1024
maxEvenDividing rezultat: 1022 durată 109.0063ms
rezultat maxEvenDividing2: 1022 durată 77.0044 ms
maxEvenConjunction rezultat: 1022 durată 111.0063ms
rezultat maxEvenConjunction2: 1022 durată 81.0047ms
prag maxim: 2048
maxEvenDividing rezultat: 2046 durată 114.0065ms
rezultat maxEvenDividing2: 2046 durată 79.0045 ms
maxEvenConjunction rezultat: 2046 durată 113.0065ms
rezultat maxEvenConjunction2: 2046 durată 81.0046ms
prag maxim: 4096
maxEvenDividing rezultat: 4094 durată 114.0065ms
rezultat maxEvenDividing2: 4094 durată 80.0046 ms
maxEvenConjunction rezultat: 4094 durată 111.0063ms
rezultat maxEvenConjunction2: 4094 durată 78.0045ms
prag maxim: 8192
maxEvenDividing rezultat: 8190 durată 107.0062ms
rezultat maxEvenDividing2: 8190 durată 77.0044 ms
maxEvenConjunction rezultat: 8190 durată 111.0063ms
rezultat maxEvenConjunction2: 8190 durată 77.0044ms
prag maxim: 16384
maxEvenDividing rezultat: 16382 durată 109.0063ms
rezultat maxEvenDividing2: 16382 durată 77.0044 ms
maxEvenConjunction rezultat: 16382 durată 108.0062ms
rezultat maxEvenConjunction2: 16382 durată 77.0044ms
prag maxim: 32768
maxEvenDividing rezultat: 32766 durată 112.0064ms
rezultat maxEvenDividing2: 32766 durată 77.0044 ms
maxEvenConjunction rezultat: 32766 durată 109.0062ms
rezultat maxEvenConjunction2: 32766 durată 78.0045ms
prag maxim: 65536
maxEvenDividing rezultat: 65534 durată 109.0062ms
rezultat maxEvenDividing2: 65534 durată 75.0043 ms
maxEvenConjunction rezultat: 65534 durată 109.0063ms
rezultat maxEvenConjunction2: 65534 durată 79.0045ms
prag maxim: 131072
maxEvenDividing rezultat: 131070 durată 108.0061ms
rezultat maxEvenDividing2: 131070 durată 76.0044 ms
maxEvenConjunction rezultat: 131070 durată 110.0063ms
rezultat maxEvenConjunction2: 131070 durată 80.0046ms
prag maxim: 262144
maxEvenDividing rezultat: 262142 durată 110.0063ms
rezultat maxEvenDividing2: 262142 durată 76.0044 ms
maxEvenConjunction rezultat: 262142 durată 107.0061ms
rezultat maxEvenConjunction2: 262142 durată 78.0044ms
prag maxim: 524288
maxEvenDividing rezultat: 524286 durată 109.0062ms
rezultat maxEvenDividing2: 524286 durată 78.0045 ms
maxEvenConjunction rezultat: 524286 durată 109.0062ms
rezultat maxEvenConjunction2: 524286 durată 80.0046ms
prag maxim: 1048576
maxEvenDividing rezultat: 1048574 durată 109.0063ms
rezultat maxEvenDividing2: 1048574 durată 80.0045 ms
maxEvenConjunction rezultat: 1048574 durată 114.0066ms
rezultat maxEvenConjunction2: 1048574 durată 78.0044ms
prag maxim: 2097152
maxEvenDividing rezultat: 2097150 durată 111.0064ms
rezultat maxEvenDividing2: 2097150 durată 79.0045 ms
maxEvenConjunction rezultat: 2097150 durată 112.0064ms
rezultat maxEvenConjunction2: 2097150 durată 77.0044ms
prag maxim: 4194304
maxEvenDividing rezultat: 4194302 durată 111.0063ms
rezultat maxEvenDividing2: 4194302 durată 78.0045 ms
maxEvenConjunction rezultat: 4194302 durată 111.0063ms
rezultat maxEvenConjunction2: 4194302 durată 77.0044ms
prag maxim: 8388608
maxEvenDividing rezultat: 8388606 durată 109.0062ms
rezultat maxEvenDividing2: 8388606 durată 78.0045 ms
maxEvenConjunction rezultat: 8388606 durată 114.0065ms
rezultat maxEvenConjunction2: 8388606 durată 78.0045ms
prag maxim: 16777216
maxEvenDividing rezultat: 16777214 durată 109.0062ms
rezultat maxEvenDividing2: 16777214 durată 77.0044 ms
maxEvenConjunction rezultat: 16777214 durată 109.0063ms
rezultat maxEvenConjunction2: 16777214 durată 77.0044ms
prag maxim: 33554432
maxEvenDividing rezultat: 33554430 durată 113.0065ms
rezultat maxEvenDividing2: 33554430 durată 78.0045 ms
maxEvenConjunction rezultat: 33554430 durată 110.0063ms
rezultat maxEvenConjunction2: 33554430 durată 80.0045ms
prag maxim: 67108864
maxEvenDividing rezultat: 67108860 durată 112.0064ms
rezultat maxEvenDividing2: 67108860 durată 77.0044 ms
maxEvenConjunction rezultat: 67108860 durată 112.0064ms
rezultat maxEvenConjunction2: 67108860 durată 80.0046ms
prag maxim: 134217728
maxEvenDividing rezultat: 134217726 durată 109.0063ms
rezultat maxEvenDividing2: 134217726 durată 78.0044 ms
maxEvenConjunction rezultat: 134217726 durată 114.0065ms
rezultat maxEvenConjunction2: 134217726 durată 81.0047ms
prag maxim: 268435456
maxEvenDividing rezultat: 268435446 durată 111.0064ms
rezultat maxEvenDividing2: 268435446 durată 79.0045 ms
maxEvenConjunction rezultat: 268435446 durată 114.0065ms
rezultat maxEvenConjunction2: 268435446 durată 79.0045ms
prag maxim: 536870912
maxEvenDividing rezultat: 536870910 durată 107.0062ms
rezultat maxEvenDividing2: 536870910 durată 76.0043 ms
maxEvenConjunction rezultat: 536870910 durată 109.0062ms
rezultat maxEvenConjunction2: 536870910 durată 80.0046ms
Nu am putut găsi o explicație clară de ce compilatorul Go nu optimizează codul și verifică întotdeauna a doua condiție, chiar dacă prima este falsă. Sau poate că ochii mei sunt încețoșați și nu văd nicio greșeală evidentă? Sau trebuie să oferiți niște instrucțiuni speciale compilatorului? Mi-ar face plăcere comentarii sensibile.
PS: Da, doar pentru distracție, am rulat teste similare pe Java 5 și Java 7/8 - totul este clar, timpul de execuție este același.
Sursa: www.habr.com