Czy uważasz, że te dwie opcje testowania warunków w pętli są równoważne pod względem wydajności?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Wszystko zaczęło się od „rozgrzewki mózgu”, miałem podać przykład optymalnego wyszukiwania największej liczby parzystej w tablicy liczb całkowitych [-x...x]. Zastanawiałem się, o ile lepsza byłaby wydajność, gdybym użył logicznego mnożenia przez 1, aby dowiedzieć się, czy liczba jest parzysta, czy nie.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Moje doświadczenie w programowaniu w Go nie jest zbyt rozległe, nieco ponad półtora roku, używałem go, choć często, ale wyłącznie w celach utylitarnych (no, może z wyjątkiem jednego projektu związanego z usługą HTTP o dużym obciążeniu), więc zaczął od tego. Otwórz GoLand i napisz prosty 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
}
Otrzymujemy wynik, który pokazuje, że im wyższy próg, tym częściej pojawiają się wahania w wydajności.
Porównajmax 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
Widać, że w tym przypadku dla różnych progów mamy różne zestawy danych testowych, obciążenie procesora (na moim laptopie i5-2540M) waha się w granicach 20..30%, pamięć zajmowana przez aplikację uruchamianą z GoLanda jest średnio około 813MB - to też wpływa na wiarygodność wyniku, należy zapisać przypadki testowe na dysku i uruchomić wszystkie testy dla każdego progu w oderwaniu od siebie.
A teraz, myśląc o tym, jak to wszystko wdrożyć przy minimalnych kosztach, automatycznie poprawiam kontrolę stanu
if value > current && value&1 == 0 {
current = value
}
na
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Robię testy jeszcze raz... i przestaję cokolwiek rozumieć :)
Czas poświęcony na wykonanie zaczyna się różnić nie procentami/ułamkami procenta, ale 10..15%. Szybko dodaję jeszcze 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
}
Uruchamiam go i otrzymuję taki obrazek:początkowa pojemność tablicy: 100000000
maksymalny próg: 128
maxEvenWynik dzielenia: 126 czas trwania 116.0066 ms
wynik maxEvenDividing2: 126 czasu trwania 79.0045 ms
wynik maxEvenConjunction: 126 czasu trwania 114.0065 ms
wynik maxEvenConjunction2: 126 czasu trwania 83.0048 ms
maksymalny próg: 256
maxEvenWynik dzielenia: 254 czas trwania 111.0063 ms
wynik maxEvenDividing2: 254 czasu trwania 77.0044 ms
wynik maxEvenConjunction: 254 czasu trwania 110.0063 ms
wynik maxEvenConjunction2: 254 czasu trwania 80.0046 ms
maksymalny próg: 512
maxEvenWynik dzielenia: 510 czas trwania 114.0066 ms
wynik maxEvenDividing2: 510 czasu trwania 80.0045 ms
wynik maxEvenConjunction: 510 czasu trwania 110.0063 ms
wynik maxEvenConjunction2: 510 czasu trwania 80.0046 ms
maksymalny próg: 1024
maxEvenWynik dzielenia: 1022 czas trwania 109.0063 ms
wynik maxEvenDividing2: 1022 czasu trwania 77.0044 ms
wynik maxEvenConjunction: 1022 czasu trwania 111.0063 ms
wynik maxEvenConjunction2: 1022 czasu trwania 81.0047 ms
maksymalny próg: 2048
maxEvenWynik dzielenia: 2046 czas trwania 114.0065 ms
wynik maxEvenDividing2: 2046 czasu trwania 79.0045 ms
wynik maxEvenConjunction: 2046 czasu trwania 113.0065 ms
wynik maxEvenConjunction2: 2046 czasu trwania 81.0046 ms
maksymalny próg: 4096
maxEvenWynik dzielenia: 4094 czas trwania 114.0065 ms
wynik maxEvenDividing2: 4094 czasu trwania 80.0046 ms
wynik maxEvenConjunction: 4094 czasu trwania 111.0063 ms
wynik maxEvenConjunction2: 4094 czasu trwania 78.0045 ms
maksymalny próg: 8192
maxEvenWynik dzielenia: 8190 czas trwania 107.0062 ms
wynik maxEvenDividing2: 8190 czasu trwania 77.0044 ms
wynik maxEvenConjunction: 8190 czasu trwania 111.0063 ms
wynik maxEvenConjunction2: 8190 czasu trwania 77.0044 ms
maksymalny próg: 16384
maxEvenWynik dzielenia: 16382 czas trwania 109.0063 ms
wynik maxEvenDividing2: 16382 czasu trwania 77.0044 ms
wynik maxEvenConjunction: 16382 czasu trwania 108.0062 ms
wynik maxEvenConjunction2: 16382 czasu trwania 77.0044 ms
maksymalny próg: 32768
maxEvenWynik dzielenia: 32766 czas trwania 112.0064 ms
wynik maxEvenDividing2: 32766 czasu trwania 77.0044 ms
wynik maxEvenConjunction: 32766 czasu trwania 109.0062 ms
wynik maxEvenConjunction2: 32766 czasu trwania 78.0045 ms
maksymalny próg: 65536
maxEvenWynik dzielenia: 65534 czas trwania 109.0062 ms
wynik maxEvenDividing2: 65534 czasu trwania 75.0043 ms
wynik maxEvenConjunction: 65534 czasu trwania 109.0063 ms
wynik maxEvenConjunction2: 65534 czasu trwania 79.0045 ms
maksymalny próg: 131072
maxEvenWynik dzielenia: 131070 czas trwania 108.0061 ms
wynik maxEvenDividing2: 131070 czasu trwania 76.0044 ms
wynik maxEvenConjunction: 131070 czasu trwania 110.0063 ms
wynik maxEvenConjunction2: 131070 czasu trwania 80.0046 ms
maksymalny próg: 262144
maxEvenWynik dzielenia: 262142 czas trwania 110.0063 ms
wynik maxEvenDividing2: 262142 czasu trwania 76.0044 ms
wynik maxEvenConjunction: 262142 czasu trwania 107.0061 ms
wynik maxEvenConjunction2: 262142 czasu trwania 78.0044 ms
maksymalny próg: 524288
maxEvenWynik dzielenia: 524286 czas trwania 109.0062 ms
wynik maxEvenDividing2: 524286 czasu trwania 78.0045 ms
wynik maxEvenConjunction: 524286 czasu trwania 109.0062 ms
wynik maxEvenConjunction2: 524286 czasu trwania 80.0046 ms
maksymalny próg: 1048576
maxEvenWynik dzielenia: 1048574 czas trwania 109.0063 ms
wynik maxEvenDividing2: 1048574 czasu trwania 80.0045 ms
wynik maxEvenConjunction: 1048574 czasu trwania 114.0066 ms
wynik maxEvenConjunction2: 1048574 czasu trwania 78.0044 ms
maksymalny próg: 2097152
maxEvenWynik dzielenia: 2097150 czas trwania 111.0064 ms
wynik maxEvenDividing2: 2097150 czasu trwania 79.0045 ms
wynik maxEvenConjunction: 2097150 czasu trwania 112.0064 ms
wynik maxEvenConjunction2: 2097150 czasu trwania 77.0044 ms
maksymalny próg: 4194304
maxEvenWynik dzielenia: 4194302 czas trwania 111.0063 ms
wynik maxEvenDividing2: 4194302 czasu trwania 78.0045 ms
wynik maxEvenConjunction: 4194302 czasu trwania 111.0063 ms
wynik maxEvenConjunction2: 4194302 czasu trwania 77.0044 ms
maksymalny próg: 8388608
maxEvenWynik dzielenia: 8388606 czas trwania 109.0062 ms
wynik maxEvenDividing2: 8388606 czasu trwania 78.0045 ms
wynik maxEvenConjunction: 8388606 czasu trwania 114.0065 ms
wynik maxEvenConjunction2: 8388606 czasu trwania 78.0045 ms
maksymalny próg: 16777216
maxEvenWynik dzielenia: 16777214 czas trwania 109.0062 ms
wynik maxEvenDividing2: 16777214 czasu trwania 77.0044 ms
wynik maxEvenConjunction: 16777214 czasu trwania 109.0063 ms
wynik maxEvenConjunction2: 16777214 czasu trwania 77.0044 ms
maksymalny próg: 33554432
maxEvenWynik dzielenia: 33554430 czas trwania 113.0065 ms
wynik maxEvenDividing2: 33554430 czasu trwania 78.0045 ms
wynik maxEvenConjunction: 33554430 czasu trwania 110.0063 ms
wynik maxEvenConjunction2: 33554430 czasu trwania 80.0045 ms
maksymalny próg: 67108864
maxEvenWynik dzielenia: 67108860 czas trwania 112.0064 ms
wynik maxEvenDividing2: 67108860 czasu trwania 77.0044 ms
wynik maxEvenConjunction: 67108860 czasu trwania 112.0064 ms
wynik maxEvenConjunction2: 67108860 czasu trwania 80.0046 ms
maksymalny próg: 134217728
maxEvenWynik dzielenia: 134217726 czas trwania 109.0063 ms
wynik maxEvenDividing2: 134217726 czasu trwania 78.0044 ms
wynik maxEvenConjunction: 134217726 czasu trwania 114.0065 ms
wynik maxEvenConjunction2: 134217726 czasu trwania 81.0047 ms
maksymalny próg: 268435456
maxEvenWynik dzielenia: 268435446 czas trwania 111.0064 ms
wynik maxEvenDividing2: 268435446 czasu trwania 79.0045 ms
wynik maxEvenConjunction: 268435446 czasu trwania 114.0065 ms
wynik maxEvenConjunction2: 268435446 czasu trwania 79.0045 ms
maksymalny próg: 536870912
maxEvenWynik dzielenia: 536870910 czas trwania 107.0062 ms
wynik maxEvenDividing2: 536870910 czasu trwania 76.0043 ms
wynik maxEvenConjunction: 536870910 czasu trwania 109.0062 ms
wynik maxEvenConjunction2: 536870910 czasu trwania 80.0046 ms
Nie udało mi się znaleźć jasnego wyjaśnienia, dlaczego kompilator Go nie optymalizuje kodu i zawsze sprawdza drugi warunek, nawet jeśli pierwszy jest fałszywy. A może po prostu mam zamglone oczy i nie widzę żadnego oczywistego błędu? A może potrzebujesz przekazać kompilatorowi jakieś specjalne instrukcje? Chętnie wysłucham rozsądnych komentarzy.
PS: Tak, dla zabawy, podobne testy przeprowadziłem na Javie 5 i Javie 7/8 - wszystko jest jasne, czas wykonania jest taki sam.
Źródło: www.habr.com