Jak si myslíte, jsou tyto dva způsoby vyhodnocení podmínek uvnitř cyklu ekvivalentní z hlediska výkonu?
if a > b && c*2 > d {
....
}
// a
if a d {
....
}
Všechno to začalo jako "rozcvička pro mozek", bylo potřeba uvést příklad optimálního vyhledávání v poli celých čísel [-x….x] pro největší sudé číslo. Zajímalo mě, jak moc se zvýší výkon, pokud pro zjištění, zda je číslo sudé, použiju logické násobení jedničkou.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Moje zkušenost s programováním v Go není příliš velká, něco málo přes rok a půl, používal jsem ho sice často, ale čistě utilitárně (snad kromě jednoho projektu souvisejícího s vysoce zatíženým http servisem), proto jsem začal právě s ním. Otevřeme GoLand a napíšeme 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("počáteční kapacita pole: " + fmt.Sprint(size))
var maxValue int32
// Budeme měnit rozsah čísel od minimálního
// po maximální. Čím menší rozsah, tím více
// procesorového času se bude trávit na operaci
// porovnání aktuálního čísla s již nalezeným a naopak
for maxValue = 128; maxValue Dostáváme výsledek, na kterém je vidět, že čím vyšší je práh, tím častěji se objevují fluktuace výkonu.
Srovnejtemax prah: 128
maxEvenDividing výsledek: 126 trvání 116.0067ms
maxEvenConjunction výsledek: 126 trvání 116.0066ms
maximální práh: 16384
maxEvenDividing výsledek: 16382 trvání 115.0066ms
maxEvenConjunction výsledek: 16382 trvání 111.0064ms
......
maximální práh: 8388608
maxEvenDividing výsledek: 8388606 trvání 109.0063ms
maxEvenConjunction výsledek: 8388606 trvání 109.0062ms
max prah: 16777216
maxEvenDividing výsledek: 16777214 trvání 108.0062ms
maxEvenConjunction výsledek: 16777214 trvání 109.0062ms
max prah: 33554432
maxEvenDividing výsledek: 33554430 trvání 114.0066ms
maxEvenConjunction výsledek: 33554430 trvání 110.0063ms
max prah: 67108864
maxEvenDividing výsledek: 67108860 trvání 111.0064ms
maxEvenConjunction výsledek: 67108860 trvání 109.0062ms
max prah: 134217728
maxEvenDividing výsledek: 134217726 trvání 108.0062ms
maxEvenConjunction výsledek: 134217726 trvání 109.0063ms
max prah: 268435456
maxEvenDividing výsledek: 268435446 trvání 111.0063ms
maxEvenConjunction výsledek: 268435446 trvání 110.0063ms
Je jasné, že v tomto případě máme pro různé prahy různá data pro testování, zatížení procesoru (na mém notebooku i5-2540M) se pohybuje kolem 20..30%, paměť, kterou zabírá aplikace spuštěná z GoLand, je průměrně kolem 813 MB — to také ovlivňuje spolehlivost výsledku, je třeba realizovat ukládání testovacích dat na disk a spustit všechny testy pro každý práh izolovaně.
A přemýšlejíc o tom, jak to všechno realizovat s minimálními náklady, automaticky opravím podmínku kontroly.
if value > current && value&1 == 0 {
current = value
}
na
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
spouštím testy znovu... a přestávám cokoliv chápat 🙂
Čas potřebný k provedení začíná být odlišný ne už v procentech/dílech procenta, ale o 10..15%. Rychle dopisuji ještě 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
}
spouštím a dostávám takový obrázek:počáteční kapacita pole: 100000000
max prah: 128
maxEvenDividing výsledek: 126 trvání 116.0066ms
maxEvenDividing2 výsledek: 126 trvání 79.0045ms
maxEvenConjunction výsledek: 126 trvání 114.0065ms
maxEvenConjunction2 výsledek: 126 trvání 83.0048ms
max prah: 256
maxEvenDividing výsledek: 254 trvání 111.0063ms
maxEvenDividing2 výsledek: 254 trvání 77.0044ms
maxEvenConjunction výsledek: 254 trvání 110.0063ms
maxEvenConjunction2 výsledek: 254 trvání 80.0046ms
max prah: 512
maxEvenDividing výsledek: 510 trvání 114.0066ms
maxEvenDividing2 výsledek: 510 trvání 80.0045ms
maxEvenConjunction výsledek: 510 trvání 110.0063ms
maxEvenConjunction2 výsledek: 510 trvání 80.0046ms
max prah: 1024
maxEvenDividing výsledek: 1022 trvání 109.0063ms
maxEvenDividing2 výsledek: 1022 trvání 77.0044ms
maxEvenConjunction výsledek: 1022 trvání 111.0063ms
maxEvenConjunction2 výsledek: 1022 trvání 81.0047ms
max prah: 2048
maxEvenDividing výsledek: 2046 trvání 114.0065ms
maxEvenDividing2 výsledek: 2046 trvání 79.0045ms
maxEvenConjunction výsledek: 2046 trvání 113.0065ms
maxEvenConjunction2 výsledek: 2046 trvání 81.0046ms
max prah: 4096
maxEvenDividing výsledek: 4094 trvání 114.0065ms
maxEvenDividing2 výsledek: 4094 trvání 80.0046ms
maxEvenConjunction výsledek: 4094 trvání 111.0063ms
maxEvenConjunction2 výsledek: 4094 trvání 78.0045ms
max prah: 8192
maxEvenDividing výsledek: 8190 trvání 107.0062ms
maxEvenDividing2 výsledek: 8190 trvání 77.0044ms
maxEvenConjunction výsledek: 8190 trvání 111.0063ms
maxEvenConjunction2 výsledek: 8190 trvání 77.0044ms
maximální práh: 16384
maxEvenDividing výsledek: 16382 trvání 109.0063ms
maxEvenDividing2 výsledek: 16382 trvání 77.0044ms
maxEvenConjunction výsledek: 16382 trvání 108.0062ms
maxEvenConjunction2 výsledek: 16382 trvání 77.0044ms
max prah: 32768
maxEvenDividing výsledek: 32766 trvání 112.0064ms
maxEvenDividing2 výsledek: 32766 trvání 77.0044ms
maxEvenConjunction výsledek: 32766 trvání 109.0062ms
maxEvenConjunction2 výsledek: 32766 trvání 78.0045ms
max prah: 65536
maxEvenDividing výsledek: 65534 trvání 109.0062ms
maxEvenDividing2 výsledek: 65534 trvání 75.0043ms
maxEvenConjunction výsledek: 65534 trvání 109.0063ms
maxEvenConjunction2 výsledek: 65534 trvání 79.0045ms
max prah: 131072
maxEvenDividing výsledek: 131070 trvání 108.0061ms
maxEvenDividing2 výsledek: 131070 trvání 76.0044ms
maxEvenConjunction výsledek: 131070 trvání 110.0063ms
maxEvenConjunction2 výsledek: 131070 trvání 80.0046ms
max prah: 262144
maxEvenDividing výsledek: 262142 trvání 110.0063ms
maxEvenDividing2 výsledek: 262142 trvání 76.0044ms
maxEvenConjunction výsledek: 262142 trvání 107.0061ms
maxEvenConjunction2 výsledek: 262142 trvání 78.0044ms
max prah: 524288
maxEvenDividing výsledek: 524286 trvání 109.0062ms
maxEvenDividing2 výsledek: 524286 trvání 78.0045ms
maxEvenConjunction výsledek: 524286 trvání 109.0062ms
maxEvenConjunction2 výsledek: 524286 trvání 80.0046ms
max prah: 1048576
maxEvenDividing výsledek: 1048574 trvání 109.0063ms
maxEvenDividing2 výsledek: 1048574 trvání 80.0045ms
maxEvenConjunction výsledek: 1048574 trvání 114.0066ms
maxEvenConjunction2 výsledek: 1048574 trvání 78.0044ms
max prah: 2097152
maxEvenDividing výsledek: 2097150 trvání 111.0064ms
maxEvenDividing2 výsledek: 2097150 trvání 79.0045ms
maxEvenConjunction výsledek: 2097150 trvání 112.0064ms
maxEvenConjunction2 výsledek: 2097150 trvání 77.0044ms
max prah: 4194304
maxEvenDividing výsledek: 4194302 trvání 111.0063ms
maxEvenDividing2 výsledek: 4194302 trvání 78.0045ms
maxEvenConjunction výsledek: 4194302 trvání 111.0063ms
maxEvenConjunction2 výsledek: 4194302 trvání 77.0044ms
maximální práh: 8388608
maxEvenDividing výsledek: 8388606 trvání 109.0062ms
maxEvenDividing2 výsledek: 8388606 trvání 78.0045ms
maxEvenConjunction výsledek: 8388606 trvání 114.0065ms
maxEvenConjunction2 výsledek: 8388606 trvání 78.0045ms
max prah: 16777216
maxEvenDividing výsledek: 16777214 trvání 109.0062ms
maxEvenDividing2 výsledek: 16777214 trvání 77.0044ms
maxEvenConjunction výsledek: 16777214 trvání 109.0063ms
maxEvenConjunction2 výsledek: 16777214 trvání 77.0044ms
max prah: 33554432
maxEvenDividing výsledek: 33554430 trvání 113.0065ms
maxEvenDividing2 výsledek: 33554430 trvání 78.0045ms
maxEvenConjunction výsledek: 33554430 trvání 110.0063ms
maxEvenConjunction2 výsledek: 33554430 trvání 80.0045ms
max prah: 67108864
maxEvenDividing výsledek: 67108860 trvání 112.0064ms
maxEvenDividing2 výsledek: 67108860 trvání 77.0044ms
maxEvenConjunction výsledek: 67108860 trvání 112.0064ms
maxEvenConjunction2 výsledek: 67108860 trvání 80.0046ms
max prah: 134217728
maxEvenDividing výsledek: 134217726 trvání 109.0063ms
maxEvenDividing2 výsledek: 134217726 trvání 78.0044ms
maxEvenConjunction výsledek: 134217726 trvání 114.0065ms
maxEvenConjunction2 výsledek: 134217726 trvání 81.0047ms
max prah: 268435456
maxEvenDividing výsledek: 268435446 trvání 111.0064ms
maxEvenDividing2 výsledek: 268435446 trvání 79.0045ms
maxEvenConjunction výsledek: 268435446 trvání 114.0065ms
maxEvenConjunction2 výsledek: 268435446 trvání 79.0045ms
max prah: 536870912
maxEvenDividing výsledek: 536870910 trvání 107.0062ms
maxEvenDividing2 výsledek: 536870910 trvání 76.0043ms
maxEvenConjunction výsledek: 536870910 doba trvání 109.0062ms
maxEvenConjunction2 výsledek: 536870910 doba trvání 80.0046ms
Až dosud jsem nenašel jasné vysvětlení, proč kompilátor Go neoptimalizuje kód a vždy kontroluje druhou podmínku, i když je první falešná — možná mi prostě "zakrylo oči" a nevidím nějakou zřejmou chybu? Nebo je potřeba kompilátorovi uvádět nějaké zvláštní pokyny? Byl bych vděčný za smysluplné komentáře.
PS: Ano, pro zajímavost jsem provedl podobné testy na Java 5 a Java 7/8 — všechno jasné, čas provedení je stejný.
Zdroj: habr.com
