Mit úgy gondolja, hogy ezek a két feltételvizsgálati lehetőség teljesítményben egyenértékűek a cikluson belül?
if a > b && c*2 > d {
....
}
// és
if a d {
....
}
Minden az "agyserkentéssel" kezdődött, példát kellett hozni az optimális keresésre egy egész számokból álló tömbben [-x….x] a legnagyobb páros számra. Érdekes volt számomra, hogy mennyivel nő a teljesítmény, ha a páros szám meghatározásához logikai szorzást használnak 1-gyel.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
A Go programozásban szerzett tapasztalatom nem túl nagy, kicsivel több mint másfél év, bár gyakran használtam, de főleg hasznos célokra (talán egy kivételével, ami nagy terhelésű http szolgáltatással kapcsolatos), ezért kezdtem ezzel. Nyissuk meg a GoLandot, és írjunk egy egyszerű tesztet.
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("kezdeti tömb kapacitás: " + fmt.Sprint(size))
var maxValue int32
// Változtatni fogjuk a számok tartományát a minimálistól
// a maximálisig. Minél kisebb a tartomány, annál több
// processzort időt fog eltölteni a művelet
// összehasonlításával az aktuális számmal, az előzőleg találtal.
for maxValue = 128; maxValue A kapott eredményből látható, hogy minél nagyobb a küszöb, annál gyakrabban lépnek fel ingadozások a teljesítmény terén.
Hasonlítsa összemax küszöb: 128
maxEvenDividing eredmény: 126 időtartam 116.0067ms
maxEvenConjunction eredmény: 126 időtartam 116.0066ms
max küszöb: 16384
maxEvenDividing result: 16382 duration 115.0066ms
maxEvenConjunction result: 16382 duration 111.0064ms
......
max küszöb: 8388608
maxEvenDividing result: 8388606 duration 109.0063ms
maxEvenConjunction eredmény: 8388606 időtartam 109.0062ms
max küszöb: 16777216
maxEvenDividing eredmény: 16777214 időtartam 108.0062ms
maxEvenConjunction eredmény: 16777214 időtartam 109.0062ms
max küszöb: 33554432
maxEvenDividing eredmény: 33554430 időtartam 114.0066ms
maxEvenConjunction eredmény: 33554430 időtartam 110.0063ms
max küszöb: 67108864
maxEvenDividing eredmény: 67108860 időtartam 111.0064ms
maxEvenConjunction eredmény: 67108860 időtartam 109.0062ms
max küszöb: 134217728
maxEvenDividing eredmény: 134217726 időtartam 108.0062ms
maxEvenConjunction eredmény: 134217726 időtartam 109.0063ms
max küszöb: 268435456
maxEvenDividing eredmény: 268435446 időtartam 111.0063ms
maxEvenConjunction eredmény: 268435446 időtartam 110.0063ms
Nyilvánvaló, hogy ebben az esetben a különböző küszöbértékekhez eltérő tesztadatok tartoznak, a processzor terhelése (az én i5-2540M laptopomon) 20–30% körül változik, a GoLand alatt futó alkalmazás által használt memória átlagosan körülbelül 813MB, ami szintén befolyásolja az eredmény hitelességét, szükséges a teszthalmazonként való mentés megvalósítása, és minden tesztet külön-külön futtatni minden küszöbértéknél.
Így gondolkodva arról, hogyan lehetne mindezt minimális költséggel megvalósítani, gépiesen javítom a feltétel ellenőrzését.
if value > current && value&1 == 0 {
current = value
}
Gyorsan emlékezzünk vissza, hogyan működik a moduláris aritmetika. Az óra már egy ismert koncepció. Az órák használata
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Futtatom a teszteket még egyszer… és nem értek semmit 🙂
Az végrehajtásra fordított idő már nem százalékos arányokban különbözik, hanem 10–15%-kal. Gyorsan írok még 2 tesztet:
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
}
Futtatom és egy ilyen képet kapok:kezdeti tömbkapacitás: 100000000
max küszöb: 128
maxEvenDividing eredmény: 126 időtartam 116.0066ms
maxEvenDividing2 eredmény: 126 időtartam 79.0045ms
maxEvenConjunction eredmény: 126 időtartam 114.0065ms
maxEvenConjunction2 eredmény: 126 időtartam 83.0048ms
max küszöb: 256
maxEvenDividing eredmény: 254 időtartam 111.0063ms
maxEvenDividing2 eredmény: 254 időtartam 77.0044ms
maxEvenConjunction eredmény: 254 időtartam 110.0063ms
maxEvenConjunction2 eredmény: 254 időtartam 80.0046ms
max küszöb: 512
maxEvenDividing eredmény: 510 időtartam 114.0066ms
maxEvenDividing2 eredmény: 510 időtartam 80.0045ms
maxEvenConjunction eredmény: 510 időtartam 110.0063ms
maxEvenConjunction2 eredmény: 510 időtartam 80.0046ms
max küszöb: 1024
maxEvenDividing eredmény: 1022 időtartam 109.0063ms
maxEvenDividing2 eredmény: 1022 időtartam 77.0044ms
maxEvenConjunction eredmény: 1022 időtartam 111.0063ms
maxEvenConjunction2 eredmény: 1022 időtartam 81.0047ms
max küszöb: 2048
maxEvenDividing eredmény: 2046 időtartam 114.0065ms
maxEvenDividing2 eredmény: 2046 időtartam 79.0045ms
maxEvenConjunction eredmény: 2046 időtartam 113.0065ms
maxEvenConjunction2 eredmény: 2046 időtartam 81.0046ms
max küszöb: 4096
maxEvenDividing eredmény: 4094 időtartam 114.0065ms
maxEvenDividing2 eredmény: 4094 időtartam 80.0046ms
maxEvenConjunction eredmény: 4094 időtartam 111.0063ms
maxEvenConjunction2 eredmény: 4094 időtartam 78.0045ms
max küszöb: 8192
maxEvenDividing eredmény: 8190 időtartam 107.0062ms
maxEvenDividing2 eredmény: 8190 időtartam 77.0044ms
maxEvenConjunction eredmény: 8190 időtartam 111.0063ms
maxEvenConjunction2 eredmény: 8190 időtartam 77.0044ms
max küszöb: 16384
maxEvenDividing eredmény: 16382 időtartam 109.0063ms
maxEvenDividing2 eredmény: 16382 időtartam 77.0044ms
maxEvenConjunction eredmény: 16382 időtartam 108.0062ms
maxEvenConjunction2 eredmény: 16382 időtartam 77.0044ms
max küszöb: 32768
maxEvenDividing eredmény: 32766 időtartam 112.0064ms
maxEvenDividing2 eredmény: 32766 időtartam 77.0044ms
maxEvenConjunction eredmény: 32766 időtartam 109.0062ms
maxEvenConjunction2 eredmény: 32766 időtartam 78.0045ms
max küszöb: 65536
maxEvenDividing eredmény: 65534 időtartam 109.0062ms
maxEvenDividing2 eredmény: 65534 időtartam 75.0043ms
maxEvenConjunction eredmény: 65534 időtartam 109.0063ms
maxEvenConjunction2 eredmény: 65534 időtartam 79.0045ms
max küszöb: 131072
maxEvenDividing eredmény: 131070 időtartam 108.0061ms
maxEvenDividing2 eredmény: 131070 időtartam 76.0044ms
maxEvenConjunction eredmény: 131070 időtartam 110.0063ms
maxEvenConjunction2 eredmény: 131070 időtartam 80.0046ms
max küszöb: 262144
maxEvenDividing eredmény: 262142 időtartam 110.0063ms
maxEvenDividing2 eredmény: 262142 időtartam 76.0044ms
maxEvenConjunction eredmény: 262142 időtartam 107.0061ms
maxEvenConjunction2 eredmény: 262142 időtartam 78.0044ms
max küszöb: 524288
maxEvenDividing eredmény: 524286 időtartam 109.0062ms
maxEvenDividing2 eredmény: 524286 időtartam 78.0045ms
maxEvenConjunction eredmény: 524286 időtartam 109.0062ms
maxEvenConjunction2 eredmény: 524286 időtartam 80.0046ms
max küszöb: 1048576
maxEvenDividing eredmény: 1048574 időtartam 109.0063ms
maxEvenDividing2 eredmény: 1048574 időtartam 80.0045ms
maxEvenConjunction eredmény: 1048574 időtartam 114.0066ms
maxEvenConjunction2 eredmény: 1048574 időtartam 78.0044ms
max küszöb: 2097152
maxEvenDividing eredmény: 2097150 időtartam 111.0064ms
maxEvenDividing2 eredmény: 2097150 időtartam 79.0045ms
maxEvenConjunction eredmény: 2097150 időtartam 112.0064ms
maxEvenConjunction2 eredmény: 2097150 időtartam 77.0044ms
max küszöb: 4194304
maxEvenDividing eredmény: 4194302 időtartam 111.0063ms
maxEvenDividing2 eredmény: 4194302 időtartam 78.0045ms
maxEvenConjunction eredmény: 4194302 időtartam 111.0063ms
maxEvenConjunction2 eredmény: 4194302 időtartam 77.0044ms
max küszöb: 8388608
maxEvenDividing eredmény: 8388606 időtartam 109.0062ms
maxEvenDividing2 eredmény: 8388606 időtartam 78.0045ms
maxEvenConjunction eredmény: 8388606 időtartam 114.0065ms
maxEvenConjunction2 eredmény: 8388606 időtartam 78.0045ms
max küszöb: 16777216
maxEvenDividing eredmény: 16777214 időtartam 109.0062ms
maxEvenDividing2 eredmény: 16777214 időtartam 77.0044ms
maxEvenConjunction eredmény: 16777214 időtartam 109.0063ms
maxEvenConjunction2 eredmény: 16777214 időtartam 77.0044ms
max küszöb: 33554432
maxEvenDividing eredmény: 33554430 időtartam 113.0065ms
maxEvenDividing2 eredmény: 33554430 időtartam 78.0045ms
maxEvenConjunction eredmény: 33554430 időtartam 110.0063ms
maxEvenConjunction2 eredmény: 33554430 időtartam 80.0045ms
max küszöb: 67108864
maxEvenDividing eredmény: 67108860 időtartam 112.0064ms
maxEvenDividing2 eredmény: 67108860 időtartam 77.0044ms
maxEvenConjunction eredmény: 67108860 időtartam 112.0064ms
maxEvenConjunction2 eredmény: 67108860 időtartam 80.0046ms
max küszöb: 134217728
maxEvenDividing eredmény: 134217726 időtartam 109.0063ms
maxEvenDividing2 eredmény: 134217726 időtartam 78.0044ms
maxEvenConjunction eredmény: 134217726 időtartam 114.0065ms
maxEvenConjunction2 eredmény: 134217726 időtartam 81.0047ms
max küszöb: 268435456
maxEvenDividing eredmény: 268435446 időtartam 111.0064ms
maxEvenDividing2 eredmény: 268435446 időtartam 79.0045ms
maxEvenConjunction eredmény: 268435446 időtartam 114.0065ms
maxEvenConjunction2 eredmény: 268435446 időtartam 79.0045ms
max küszöb: 536870912
maxEvenDividing eredmény: 536870910 időtartam 107.0062ms
maxEvenDividing2 eredmény: 536870910 időtartam 76.0043ms
maxEvenConjunction eredmény: 536870910 időtartam 109.0062ms
maxEvenConjunction2 eredmény: 536870910 időtartam 80.0046ms
Nem találtam világos magyarázatot arra, hogy miért nem optimalizálja a Go fordító a kódot, és mindig ellenőrzi a második feltételt, még akkor is, ha az első hamis. Vagy talán csak "elhomályosult" a szemem, és nem látom a nyilvánvaló hibát? Vagy szükség van valamilyen különleges utasításra a fordító számára? Örülnék bármilyen értelmes megjegyzésnek.
PS: Igen, érdekességképpen hasonló teszteket futtattam Java 5 és Java 7/8 alatt – minden rendben, a futási idő azonos.
Forrás: habr.com
