Myslíte si, že tyto dvě možnosti testování podmínek uvnitř smyčky jsou ekvivalentní ve výkonu?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Všechno to začalo „zahříváním mozku“, musel jsem uvést příklad optimálního hledání největšího sudého čísla v poli celých čísel [-x....x]. Zajímalo by mě, o kolik lepší výkon by bylo, kdybych použil logické násobení 1, abych zjistil, zda je číslo sudé nebo ne.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Moje zkušenosti s programováním v Go nejsou příliš rozsáhlé, něco přes rok a půl, používal jsem ho sice často, ale čistě pro utilitární účely (no, možná až na jeden projekt související s vysokozatíženou http službou), takže začal s tím. Otevřete GoLand a napiš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ýsledek, který ukazuje, že čím vyšší je práh, tím častěji se objevují výkyvy ve výkonu.
Porovnejtemax 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 případě máme pro různé prahy různé sady testovacích dat, zatížení procesoru (na mém notebooku i5-2540M) se pohybuje kolem 20..30 %, paměť zabraná aplikací běžící z GoLandu je v průměru asi 813 MB - to také ovlivňuje spolehlivost výsledku, je třeba uložit testovací případy na disk a spustit všechny testy pro každý práh izolovaně od sebe.
A nyní, když přemýšlím, jak to vše realizovat s minimálními náklady, automaticky opravuji kontrolu stavu
if value > current && value&1 == 0 {
current = value
}
na
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Provádím testy znovu... a přestávám ničemu rozumět :)
Čas strávený prováděním se již začíná lišit ne o procenta/zlomky procenta, ale o 10..15 %. Rychle přidávám další 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 získám tento obrázek:počáteční kapacita pole: 100000000
maximální práh: 128
maxEvenDividing výsledek: 126 trvání 116.0066ms
maxEvenDividing2 výsledek: 126 trvání 79.0045 ms
maxEvenConjunction výsledek: 126 trvání 114.0065 ms
maxEvenConjunction2 výsledek: 126 trvání 83.0048 ms
maximální práh: 256
maxEvenDividing výsledek: 254 trvání 111.0063ms
maxEvenDividing2 výsledek: 254 trvání 77.0044 ms
maxEvenConjunction výsledek: 254 trvání 110.0063 ms
maxEvenConjunction2 výsledek: 254 trvání 80.0046 ms
maximální práh: 512
maxEvenDividing výsledek: 510 trvání 114.0066ms
maxEvenDividing2 výsledek: 510 trvání 80.0045 ms
maxEvenConjunction výsledek: 510 trvání 110.0063 ms
maxEvenConjunction2 výsledek: 510 trvání 80.0046 ms
maximální práh: 1024
maxEvenDividing výsledek: 1022 trvání 109.0063ms
maxEvenDividing2 výsledek: 1022 trvání 77.0044 ms
maxEvenConjunction výsledek: 1022 trvání 111.0063 ms
maxEvenConjunction2 výsledek: 1022 trvání 81.0047 ms
maximální práh: 2048
maxEvenDividing výsledek: 2046 trvání 114.0065ms
maxEvenDividing2 výsledek: 2046 trvání 79.0045 ms
maxEvenConjunction výsledek: 2046 trvání 113.0065 ms
maxEvenConjunction2 výsledek: 2046 trvání 81.0046 ms
maximální práh: 4096
maxEvenDividing výsledek: 4094 trvání 114.0065ms
maxEvenDividing2 výsledek: 4094 trvání 80.0046 ms
maxEvenConjunction výsledek: 4094 trvání 111.0063 ms
maxEvenConjunction2 výsledek: 4094 trvání 78.0045 ms
maximální práh: 8192
maxEvenDividing výsledek: 8190 trvání 107.0062ms
maxEvenDividing2 výsledek: 8190 trvání 77.0044 ms
maxEvenConjunction výsledek: 8190 trvání 111.0063 ms
maxEvenConjunction2 výsledek: 8190 trvání 77.0044 ms
maximální práh: 16384
maxEvenDividing výsledek: 16382 trvání 109.0063ms
maxEvenDividing2 výsledek: 16382 trvání 77.0044 ms
maxEvenConjunction výsledek: 16382 trvání 108.0062 ms
maxEvenConjunction2 výsledek: 16382 trvání 77.0044 ms
maximální práh: 32768
maxEvenDividing výsledek: 32766 trvání 112.0064ms
maxEvenDividing2 výsledek: 32766 trvání 77.0044 ms
maxEvenConjunction výsledek: 32766 trvání 109.0062 ms
maxEvenConjunction2 výsledek: 32766 trvání 78.0045 ms
maximální práh: 65536
maxEvenDividing výsledek: 65534 trvání 109.0062ms
maxEvenDividing2 výsledek: 65534 trvání 75.0043 ms
maxEvenConjunction výsledek: 65534 trvání 109.0063 ms
maxEvenConjunction2 výsledek: 65534 trvání 79.0045 ms
maximální práh: 131072
maxEvenDividing výsledek: 131070 trvání 108.0061ms
maxEvenDividing2 výsledek: 131070 trvání 76.0044 ms
maxEvenConjunction výsledek: 131070 trvání 110.0063 ms
maxEvenConjunction2 výsledek: 131070 trvání 80.0046 ms
maximální práh: 262144
maxEvenDividing výsledek: 262142 trvání 110.0063ms
maxEvenDividing2 výsledek: 262142 trvání 76.0044 ms
maxEvenConjunction výsledek: 262142 trvání 107.0061 ms
maxEvenConjunction2 výsledek: 262142 trvání 78.0044 ms
maximální práh: 524288
maxEvenDividing výsledek: 524286 trvání 109.0062ms
maxEvenDividing2 výsledek: 524286 trvání 78.0045 ms
maxEvenConjunction výsledek: 524286 trvání 109.0062 ms
maxEvenConjunction2 výsledek: 524286 trvání 80.0046 ms
maximální práh: 1048576
maxEvenDividing výsledek: 1048574 trvání 109.0063ms
maxEvenDividing2 výsledek: 1048574 trvání 80.0045 ms
maxEvenConjunction výsledek: 1048574 trvání 114.0066 ms
maxEvenConjunction2 výsledek: 1048574 trvání 78.0044 ms
maximální práh: 2097152
maxEvenDividing výsledek: 2097150 trvání 111.0064ms
maxEvenDividing2 výsledek: 2097150 trvání 79.0045 ms
maxEvenConjunction výsledek: 2097150 trvání 112.0064 ms
maxEvenConjunction2 výsledek: 2097150 trvání 77.0044 ms
maximální práh: 4194304
maxEvenDividing výsledek: 4194302 trvání 111.0063ms
maxEvenDividing2 výsledek: 4194302 trvání 78.0045 ms
maxEvenConjunction výsledek: 4194302 trvání 111.0063 ms
maxEvenConjunction2 výsledek: 4194302 trvání 77.0044 ms
maximální práh: 8388608
maxEvenDividing výsledek: 8388606 trvání 109.0062ms
maxEvenDividing2 výsledek: 8388606 trvání 78.0045 ms
maxEvenConjunction výsledek: 8388606 trvání 114.0065 ms
maxEvenConjunction2 výsledek: 8388606 trvání 78.0045 ms
maximální práh: 16777216
maxEvenDividing výsledek: 16777214 trvání 109.0062ms
maxEvenDividing2 výsledek: 16777214 trvání 77.0044 ms
maxEvenConjunction výsledek: 16777214 trvání 109.0063 ms
maxEvenConjunction2 výsledek: 16777214 trvání 77.0044 ms
maximální práh: 33554432
maxEvenDividing výsledek: 33554430 trvání 113.0065ms
maxEvenDividing2 výsledek: 33554430 trvání 78.0045 ms
maxEvenConjunction výsledek: 33554430 trvání 110.0063 ms
maxEvenConjunction2 výsledek: 33554430 trvání 80.0045 ms
maximální práh: 67108864
maxEvenDividing výsledek: 67108860 trvání 112.0064ms
maxEvenDividing2 výsledek: 67108860 trvání 77.0044 ms
maxEvenConjunction výsledek: 67108860 trvání 112.0064 ms
maxEvenConjunction2 výsledek: 67108860 trvání 80.0046 ms
maximální práh: 134217728
maxEvenDividing výsledek: 134217726 trvání 109.0063ms
maxEvenDividing2 výsledek: 134217726 trvání 78.0044 ms
maxEvenConjunction výsledek: 134217726 trvání 114.0065 ms
maxEvenConjunction2 výsledek: 134217726 trvání 81.0047 ms
maximální práh: 268435456
maxEvenDividing výsledek: 268435446 trvání 111.0064ms
maxEvenDividing2 výsledek: 268435446 trvání 79.0045 ms
maxEvenConjunction výsledek: 268435446 trvání 114.0065 ms
maxEvenConjunction2 výsledek: 268435446 trvání 79.0045 ms
maximální práh: 536870912
maxEvenDividing výsledek: 536870910 trvání 107.0062ms
maxEvenDividing2 výsledek: 536870910 trvání 76.0043 ms
maxEvenConjunction výsledek: 536870910 trvání 109.0062 ms
maxEvenConjunction2 výsledek: 536870910 trvání 80.0046 ms
Nemohl jsem najít jasné vysvětlení, proč kompilátor Go neoptimalizuje kód a vždy kontroluje druhou podmínku, i když je první nepravdivá. Nebo mám možná jen rozmazané oči a nevidím žádnou zjevnou chybu? Nebo potřebujete kompilátoru poskytnout nějaké speciální instrukce? Budu rád za rozumné komentáře.
PS: Ano, jen pro zajímavost, podobné testy jsem provedl na Javě 5 a Javě 7/8 - vše je jasné, doba provádění je stejná.
Zdroj: www.habr.com