Myslíte si, že tieto dve možnosti testovania podmienok vo vnútri slučky sú ekvivalentné vo výkone?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Všetko to začalo „zahrievaním mozgu“, musel som uviesť príklad optimálneho hľadania najväčšieho párneho čísla v poli celých čísel [-x....x]. Zaujímalo by ma, o koľko lepší by bol výkon, keby som použil logické násobenie 1, aby som zistil, či je číslo párne alebo nie.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Moje programátorské skúsenosti v Go nie sú príliš rozsiahle, len niečo vyše roka a pol som ho používal síce často, ale čisto na utilitárne účely (dobre, možno až na jeden projekt súvisiaci s vysoko zaťaženou http službou), takže začal s tým. Otvorte GoLand a napíšte jednoduchý 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
}
Dostaneme výsledok, ktorý ukazuje, že čím je prah vyšší, tým častejšie sa objavujú výkyvy výkonu.
porovnať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
Je jasné, že v tomto prípade máme pre rôzne prahové hodnoty rôzne sady testovacích údajov, zaťaženie procesora (na mojom notebooku i5-2540M) kolíše okolo 20..30%, pamäť obsadená aplikáciou spustenou z GoLand je v priemere asi 813 MB - to tiež ovplyvňuje spoľahlivosť výsledku, musíte uložiť testovacie prípady na disk a spustiť všetky testy pre každý prah izolovane od seba.
A teraz, keď rozmýšľam, ako to všetko zrealizovať s minimálnymi nákladmi, automaticky opravujem kontrolu stavu
if value > current && value&1 == 0 {
current = value
}
na
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Znova robím testy... a prestávam ničomu rozumieť :)
Čas strávený vykonaním sa už začína líšiť nie o percentá/zlomky percenta, ale o 10..15%. Rýchlo pridávam ďalšie 2 testy:
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
}
Spustím to a dostanem tento obrázok:počiatočná kapacita poľa: 100000000
maximálny prah: 128
maxEvenVýsledok delenia: 126 trvanie 116.0066ms
maxEvenDividing2 výsledok: 126 trvanie 79.0045 ms
maxEvenConjunction výsledok: 126 trvanie 114.0065 ms
maxEvenConjunction2 výsledok: 126 trvanie 83.0048 ms
maximálny prah: 256
maxEvenVýsledok delenia: 254 trvanie 111.0063ms
maxEvenDividing2 výsledok: 254 trvanie 77.0044 ms
maxEvenConjunction výsledok: 254 trvanie 110.0063 ms
maxEvenConjunction2 výsledok: 254 trvanie 80.0046 ms
maximálny prah: 512
maxEvenVýsledok delenia: 510 trvanie 114.0066ms
maxEvenDividing2 výsledok: 510 trvanie 80.0045 ms
maxEvenConjunction výsledok: 510 trvanie 110.0063 ms
maxEvenConjunction2 výsledok: 510 trvanie 80.0046 ms
maximálny prah: 1024
maxEvenVýsledok delenia: 1022 trvanie 109.0063ms
maxEvenDividing2 výsledok: 1022 trvanie 77.0044 ms
maxEvenConjunction výsledok: 1022 trvanie 111.0063 ms
maxEvenConjunction2 výsledok: 1022 trvanie 81.0047 ms
maximálny prah: 2048
maxEvenVýsledok delenia: 2046 trvanie 114.0065ms
maxEvenDividing2 výsledok: 2046 trvanie 79.0045 ms
maxEvenConjunction výsledok: 2046 trvanie 113.0065 ms
maxEvenConjunction2 výsledok: 2046 trvanie 81.0046 ms
maximálny prah: 4096
maxEvenVýsledok delenia: 4094 trvanie 114.0065ms
maxEvenDividing2 výsledok: 4094 trvanie 80.0046 ms
maxEvenConjunction výsledok: 4094 trvanie 111.0063 ms
maxEvenConjunction2 výsledok: 4094 trvanie 78.0045 ms
maximálny prah: 8192
maxEvenVýsledok delenia: 8190 trvanie 107.0062ms
maxEvenDividing2 výsledok: 8190 trvanie 77.0044 ms
maxEvenConjunction výsledok: 8190 trvanie 111.0063 ms
maxEvenConjunction2 výsledok: 8190 trvanie 77.0044 ms
maximálny prah: 16384
maxEvenVýsledok delenia: 16382 trvanie 109.0063ms
maxEvenDividing2 výsledok: 16382 trvanie 77.0044 ms
maxEvenConjunction výsledok: 16382 trvanie 108.0062 ms
maxEvenConjunction2 výsledok: 16382 trvanie 77.0044 ms
maximálny prah: 32768
maxEvenVýsledok delenia: 32766 trvanie 112.0064ms
maxEvenDividing2 výsledok: 32766 trvanie 77.0044 ms
maxEvenConjunction výsledok: 32766 trvanie 109.0062 ms
maxEvenConjunction2 výsledok: 32766 trvanie 78.0045 ms
maximálny prah: 65536
maxEvenVýsledok delenia: 65534 trvanie 109.0062ms
maxEvenDividing2 výsledok: 65534 trvanie 75.0043 ms
maxEvenConjunction výsledok: 65534 trvanie 109.0063 ms
maxEvenConjunction2 výsledok: 65534 trvanie 79.0045 ms
maximálny prah: 131072
maxEvenVýsledok delenia: 131070 trvanie 108.0061ms
maxEvenDividing2 výsledok: 131070 trvanie 76.0044 ms
maxEvenConjunction výsledok: 131070 trvanie 110.0063 ms
maxEvenConjunction2 výsledok: 131070 trvanie 80.0046 ms
maximálny prah: 262144
maxEvenVýsledok delenia: 262142 trvanie 110.0063ms
maxEvenDividing2 výsledok: 262142 trvanie 76.0044 ms
maxEvenConjunction výsledok: 262142 trvanie 107.0061 ms
maxEvenConjunction2 výsledok: 262142 trvanie 78.0044 ms
maximálny prah: 524288
maxEvenVýsledok delenia: 524286 trvanie 109.0062ms
maxEvenDividing2 výsledok: 524286 trvanie 78.0045 ms
maxEvenConjunction výsledok: 524286 trvanie 109.0062 ms
maxEvenConjunction2 výsledok: 524286 trvanie 80.0046 ms
maximálny prah: 1048576
maxEvenVýsledok delenia: 1048574 trvanie 109.0063ms
maxEvenDividing2 výsledok: 1048574 trvanie 80.0045 ms
maxEvenConjunction výsledok: 1048574 trvanie 114.0066 ms
maxEvenConjunction2 výsledok: 1048574 trvanie 78.0044 ms
maximálny prah: 2097152
maxEvenVýsledok delenia: 2097150 trvanie 111.0064ms
maxEvenDividing2 výsledok: 2097150 trvanie 79.0045 ms
maxEvenConjunction výsledok: 2097150 trvanie 112.0064 ms
maxEvenConjunction2 výsledok: 2097150 trvanie 77.0044 ms
maximálny prah: 4194304
maxEvenVýsledok delenia: 4194302 trvanie 111.0063ms
maxEvenDividing2 výsledok: 4194302 trvanie 78.0045 ms
maxEvenConjunction výsledok: 4194302 trvanie 111.0063 ms
maxEvenConjunction2 výsledok: 4194302 trvanie 77.0044 ms
maximálny prah: 8388608
maxEvenVýsledok delenia: 8388606 trvanie 109.0062ms
maxEvenDividing2 výsledok: 8388606 trvanie 78.0045 ms
maxEvenConjunction výsledok: 8388606 trvanie 114.0065 ms
maxEvenConjunction2 výsledok: 8388606 trvanie 78.0045 ms
maximálny prah: 16777216
maxEvenVýsledok delenia: 16777214 trvanie 109.0062ms
maxEvenDividing2 výsledok: 16777214 trvanie 77.0044 ms
maxEvenConjunction výsledok: 16777214 trvanie 109.0063 ms
maxEvenConjunction2 výsledok: 16777214 trvanie 77.0044 ms
maximálny prah: 33554432
maxEvenVýsledok delenia: 33554430 trvanie 113.0065ms
maxEvenDividing2 výsledok: 33554430 trvanie 78.0045 ms
maxEvenConjunction výsledok: 33554430 trvanie 110.0063 ms
maxEvenConjunction2 výsledok: 33554430 trvanie 80.0045 ms
maximálny prah: 67108864
maxEvenVýsledok delenia: 67108860 trvanie 112.0064ms
maxEvenDividing2 výsledok: 67108860 trvanie 77.0044 ms
maxEvenConjunction výsledok: 67108860 trvanie 112.0064 ms
maxEvenConjunction2 výsledok: 67108860 trvanie 80.0046 ms
maximálny prah: 134217728
maxEvenVýsledok delenia: 134217726 trvanie 109.0063ms
maxEvenDividing2 výsledok: 134217726 trvanie 78.0044 ms
maxEvenConjunction výsledok: 134217726 trvanie 114.0065 ms
maxEvenConjunction2 výsledok: 134217726 trvanie 81.0047 ms
maximálny prah: 268435456
maxEvenVýsledok delenia: 268435446 trvanie 111.0064ms
maxEvenDividing2 výsledok: 268435446 trvanie 79.0045 ms
maxEvenConjunction výsledok: 268435446 trvanie 114.0065 ms
maxEvenConjunction2 výsledok: 268435446 trvanie 79.0045 ms
maximálny prah: 536870912
maxEvenVýsledok delenia: 536870910 trvanie 107.0062ms
maxEvenDividing2 výsledok: 536870910 trvanie 76.0043 ms
maxEvenConjunction výsledok: 536870910 trvanie 109.0062 ms
maxEvenConjunction2 výsledok: 536870910 trvanie 80.0046 ms
Nenašiel som jasné vysvetlenie, prečo kompilátor Go neoptimalizuje kód a vždy kontroluje druhú podmienku, aj keď je prvá nepravdivá. Alebo možno mám len rozmazané oči a nevidím žiadnu zjavnú chybu? Alebo potrebujete poskytnúť nejaké špeciálne pokyny pre kompilátor? Budem rád za rozumné komentáre.
PS: Áno, len pre zaujímavosť, spustil som podobné testy na Java 5 a Java 7/8 - všetko je jasné, čas vykonania je rovnaký.
Zdroj: hab.com