Kas arvate, et need kaks võimalust ahela sees tingimuste testimiseks on jõudluses samaväärsed?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Kõik algas "aju soojendamisega"; pidin tooma näite täisarvude massiivi [-x....x] suurima paarisarvu optimaalse otsimise kohta. Mõtlesin, kui palju parem jõudlus oleks, kui kasutaksin loogilist korrutamist 1-ga, et välja selgitada, kas arv on paaris või mitte.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Minu programmeerimiskogemus Go-s pole kuigi ulatuslik, veidi üle pooleteise aasta, kasutasin seda, kuigi sageli, kuid puhtalt utilitaarsetel eesmärkidel (no võib-olla välja arvatud üks suure koormusega http-teenusega seotud projekt), nii et alustas sellega. Avage GoLand ja kirjutage lihtne 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
}
Saame tulemuse, mis näitab, et mida kõrgem on lävi, seda sagedamini ilmnevad jõudluse kõikumised.
Võrdlemax 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
Selge on see, et antud juhul on meil erinevate lävede puhul erinevad testiandmete komplektid, protsessori koormus (minu i5-2540M sülearvutil) varieerub 20...30% ringis, GoLandist töötava rakenduse mälu hõivab keskmiselt. umbes 813 MB - see mõjutab ka tulemuse usaldusväärsust, peate salvestama testjuhtumid kettale ja käivitama kõik testid iga läve jaoks üksteisest eraldi.
Ja nüüd, mõeldes, kuidas seda kõike minimaalsete kuludega rakendada, parandan automaatselt seisukorra kontrolli
if value > current && value&1 == 0 {
current = value
}
edasi
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Teen uuesti testid... ja ei saa enam millestki aru :)
Täitmisele kuluv aeg hakkab erinema mitte enam protsentide/protsenti murdosa, vaid 10...15% võrra.. Lisan kiirelt veel 2 testi:
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
}
Käivitan selle ja saan selle pildi:esialgne massiivi maht: 100000000
maksimaalne lävi: 128
maxEvenJagamise tulemus: 126 kestus 116.0066 ms
maxEvenDividing2 tulemus: 126 kestus 79.0045 ms
maxEvenConjunction tulemus: 126 kestus 114.0065 ms
maxEvenConjunction2 tulemus: 126 kestus 83.0048 ms
maksimaalne lävi: 256
maxEvenJagamise tulemus: 254 kestus 111.0063 ms
maxEvenDividing2 tulemus: 254 kestus 77.0044 ms
maxEvenConjunction tulemus: 254 kestus 110.0063 ms
maxEvenConjunction2 tulemus: 254 kestus 80.0046 ms
maksimaalne lävi: 512
maxEvenJagamise tulemus: 510 kestus 114.0066 ms
maxEvenDividing2 tulemus: 510 kestus 80.0045 ms
maxEvenConjunction tulemus: 510 kestus 110.0063 ms
maxEvenConjunction2 tulemus: 510 kestus 80.0046 ms
maksimaalne lävi: 1024
maxEvenJagamise tulemus: 1022 kestus 109.0063 ms
maxEvenDividing2 tulemus: 1022 kestus 77.0044 ms
maxEvenConjunction tulemus: 1022 kestus 111.0063 ms
maxEvenConjunction2 tulemus: 1022 kestus 81.0047 ms
maksimaalne lävi: 2048
maxEvenJagamise tulemus: 2046 kestus 114.0065 ms
maxEvenDividing2 tulemus: 2046 kestus 79.0045 ms
maxEvenConjunction tulemus: 2046 kestus 113.0065 ms
maxEvenConjunction2 tulemus: 2046 kestus 81.0046 ms
maksimaalne lävi: 4096
maxEvenJagamise tulemus: 4094 kestus 114.0065 ms
maxEvenDividing2 tulemus: 4094 kestus 80.0046 ms
maxEvenConjunction tulemus: 4094 kestus 111.0063 ms
maxEvenConjunction2 tulemus: 4094 kestus 78.0045 ms
maksimaalne lävi: 8192
maxEvenJagamise tulemus: 8190 kestus 107.0062 ms
maxEvenDividing2 tulemus: 8190 kestus 77.0044 ms
maxEvenConjunction tulemus: 8190 kestus 111.0063 ms
maxEvenConjunction2 tulemus: 8190 kestus 77.0044 ms
maksimaalne lävi: 16384
maxEvenJagamise tulemus: 16382 kestus 109.0063 ms
maxEvenDividing2 tulemus: 16382 kestus 77.0044 ms
maxEvenConjunction tulemus: 16382 kestus 108.0062 ms
maxEvenConjunction2 tulemus: 16382 kestus 77.0044 ms
maksimaalne lävi: 32768
maxEvenJagamise tulemus: 32766 kestus 112.0064 ms
maxEvenDividing2 tulemus: 32766 kestus 77.0044 ms
maxEvenConjunction tulemus: 32766 kestus 109.0062 ms
maxEvenConjunction2 tulemus: 32766 kestus 78.0045 ms
maksimaalne lävi: 65536
maxEvenJagamise tulemus: 65534 kestus 109.0062 ms
maxEvenDividing2 tulemus: 65534 kestus 75.0043 ms
maxEvenConjunction tulemus: 65534 kestus 109.0063 ms
maxEvenConjunction2 tulemus: 65534 kestus 79.0045 ms
maksimaalne lävi: 131072
maxEvenJagamise tulemus: 131070 kestus 108.0061 ms
maxEvenDividing2 tulemus: 131070 kestus 76.0044 ms
maxEvenConjunction tulemus: 131070 kestus 110.0063 ms
maxEvenConjunction2 tulemus: 131070 kestus 80.0046 ms
maksimaalne lävi: 262144
maxEvenJagamise tulemus: 262142 kestus 110.0063 ms
maxEvenDividing2 tulemus: 262142 kestus 76.0044 ms
maxEvenConjunction tulemus: 262142 kestus 107.0061 ms
maxEvenConjunction2 tulemus: 262142 kestus 78.0044 ms
maksimaalne lävi: 524288
maxEvenJagamise tulemus: 524286 kestus 109.0062 ms
maxEvenDividing2 tulemus: 524286 kestus 78.0045 ms
maxEvenConjunction tulemus: 524286 kestus 109.0062 ms
maxEvenConjunction2 tulemus: 524286 kestus 80.0046 ms
maksimaalne lävi: 1048576
maxEvenJagamise tulemus: 1048574 kestus 109.0063 ms
maxEvenDividing2 tulemus: 1048574 kestus 80.0045 ms
maxEvenConjunction tulemus: 1048574 kestus 114.0066 ms
maxEvenConjunction2 tulemus: 1048574 kestus 78.0044 ms
maksimaalne lävi: 2097152
maxEvenJagamise tulemus: 2097150 kestus 111.0064 ms
maxEvenDividing2 tulemus: 2097150 kestus 79.0045 ms
maxEvenConjunction tulemus: 2097150 kestus 112.0064 ms
maxEvenConjunction2 tulemus: 2097150 kestus 77.0044 ms
maksimaalne lävi: 4194304
maxEvenJagamise tulemus: 4194302 kestus 111.0063 ms
maxEvenDividing2 tulemus: 4194302 kestus 78.0045 ms
maxEvenConjunction tulemus: 4194302 kestus 111.0063 ms
maxEvenConjunction2 tulemus: 4194302 kestus 77.0044 ms
maksimaalne lävi: 8388608
maxEvenJagamise tulemus: 8388606 kestus 109.0062 ms
maxEvenDividing2 tulemus: 8388606 kestus 78.0045 ms
maxEvenConjunction tulemus: 8388606 kestus 114.0065 ms
maxEvenConjunction2 tulemus: 8388606 kestus 78.0045 ms
maksimaalne lävi: 16777216
maxEvenJagamise tulemus: 16777214 kestus 109.0062 ms
maxEvenDividing2 tulemus: 16777214 kestus 77.0044 ms
maxEvenConjunction tulemus: 16777214 kestus 109.0063 ms
maxEvenConjunction2 tulemus: 16777214 kestus 77.0044 ms
maksimaalne lävi: 33554432
maxEvenJagamise tulemus: 33554430 kestus 113.0065 ms
maxEvenDividing2 tulemus: 33554430 kestus 78.0045 ms
maxEvenConjunction tulemus: 33554430 kestus 110.0063 ms
maxEvenConjunction2 tulemus: 33554430 kestus 80.0045 ms
maksimaalne lävi: 67108864
maxEvenJagamise tulemus: 67108860 kestus 112.0064 ms
maxEvenDividing2 tulemus: 67108860 kestus 77.0044 ms
maxEvenConjunction tulemus: 67108860 kestus 112.0064 ms
maxEvenConjunction2 tulemus: 67108860 kestus 80.0046 ms
maksimaalne lävi: 134217728
maxEvenJagamise tulemus: 134217726 kestus 109.0063 ms
maxEvenDividing2 tulemus: 134217726 kestus 78.0044 ms
maxEvenConjunction tulemus: 134217726 kestus 114.0065 ms
maxEvenConjunction2 tulemus: 134217726 kestus 81.0047 ms
maksimaalne lävi: 268435456
maxEvenJagamise tulemus: 268435446 kestus 111.0064 ms
maxEvenDividing2 tulemus: 268435446 kestus 79.0045 ms
maxEvenConjunction tulemus: 268435446 kestus 114.0065 ms
maxEvenConjunction2 tulemus: 268435446 kestus 79.0045 ms
maksimaalne lävi: 536870912
maxEvenJagamise tulemus: 536870910 kestus 107.0062 ms
maxEvenDividing2 tulemus: 536870910 kestus 76.0043 ms
maxEvenConjunction tulemus: 536870910 kestus 109.0062 ms
maxEvenConjunction2 tulemus: 536870910 kestus 80.0046 ms
Ma ei leidnud selget selgitust, miks Go-kompilaator ei optimeeri koodi ja kontrollib alati teist tingimust, isegi kui esimene on vale. Või äkki on mu silmad lihtsalt udused ja ma ei näe ilmset viga? Või peate koostajale andma erijuhised? Mul oleks hea meel mõistlike kommentaaride üle.
PS: Jah, nalja pärast tegin sarnaseid teste Java 5 ja Java 7/8 peal - kõik on selge, täitmisaeg on sama.
Allikas: www.habr.com