Jak myślisz, czy te dwa warianty sprawdzania warunków w pętli są równoważne pod względem wydajności?
if a > b && c*2 > d {
....
}
// i
if a d {
....
}
Wszystko zaczęło się od "rozgrzewki dla mózgu", trzeba było podać przykład optymalnego wyszukiwania największej parzystej liczby w tablicy liczb całkowitych [-x….x]. Zastanowiło mnie, jak bardzo wydajność wzrośnie, jeśli do określenia, czy liczba jest parzysta, użyć mnożenia logicznego przez 1.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Moje doświadczenie w programowaniu w Go nie jest zbyt duże, to trochę ponad półtora roku, używałem go choć często, ale głównie w celach użytkowych (może poza jednym projektem związanym z wysokoobciążonym serwisem http), dlatego zaczynałem właśnie od niego. Otwieramy GoLand i piszemy 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
// Będziemy zmieniać zakres liczb od minimalnego
// do maksymalnego. Im mniejszy zakres, tym więcej
// czasu procesora będzie potrzebne na operację
// porównania bieżącej liczby, z wcześniej znalezioną i odwrotnie.
for maxValue = 128; maxValue Otrzymujemy wynik, na którym widać, że im większy threshold, tym częściej pojawiają się fluktuacje wydajności.
Porównajmaksymalny próg: 128
wynik maxEvenDividing: 126 czas trwania 116.0067ms
wynik maxEvenConjunction: 126 czas trwania 116.0066ms
max threshold: 16384
maxEvenDividing result: 16382 duration 115.0066ms
maxEvenConjunction result: 16382 duration 111.0064ms
......
max threshold: 8388608
maxEvenDividing wynik: 8388606 czas 109.0063ms
maxEvenConjunction wynik: 8388606 czas 109.0062ms
maksymalny próg: 16777216
maxEvenDividing wynik: 16777214 czas 108.0062ms
maxEvenConjunction wynik: 16777214 czas 109.0062ms
maksymalny próg: 33554432
maxEvenDividing wynik: 33554430 czas 114.0066ms
maxEvenConjunction wynik: 33554430 czas 110.0063ms
maksymalny próg: 67108864
maxEvenDividing wynik: 67108860 czas 111.0064ms
maxEvenConjunction wynik: 67108860 czas 109.0062ms
maksymalny próg: 134217728
maxEvenDividing wynik: 134217726 czas 108.0062ms
maxEvenConjunction wynik: 134217726 czas 109.0063ms
maksymalny próg: 268435456
maxEvenDividing wynik: 268435446 czas 111.0063ms
maxEvenConjunction wynik: 268435446 czas 110.0063ms
Jasne, ż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 okolicy 20-30%, pamięć zajmowana przez aplikację uruchomioną z GoLand wynosi średnio około 813MB - to również wpływa na wiarygodność wyników, trzeba zrealizować zapis zestawów testowych na dysku i przeprowadzić wszystkie testy dla każdego progu izolowały je od siebie.
I właśnie myśląc o tym, jak to wszystko zrealizować przy minimalnych kosztach, automatycznie poprawiam warunek sprawdzający
if value > current && value&1 == 0 {
current = value
}
na
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
uruchamiam testy jeszcze raz... i przestaję cokolwiek rozumieć 🙂
Czas wykonywania różni się już nie o procenty/ujednolicone, ale o 10-15%. Szybko dopisuję 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 i otrzymuję taki obrazek:początkowa pojemność tablicy: 100000000
maksymalny próg: 128
maxEvenDividing wynik: 126 czas 116.0066ms
maxEvenDividing2 wynik: 126 czas 79.0045ms
maxEvenConjunction wynik: 126 czas 114.0065ms
maxEvenConjunction2 wynik: 126 czas 83.0048ms
maksymalny próg: 256
maxEvenDividing wynik: 254 czas 111.0063ms
maxEvenDividing2 wynik: 254 czas 77.0044ms
maxEvenConjunction wynik: 254 czas 110.0063ms
maxEvenConjunction2 wynik: 254 czas 80.0046ms
maksymalny próg: 512
maxEvenDividing wynik: 510 czas 114.0066ms
maxEvenDividing2 wynik: 510 czas 80.0045ms
maxEvenConjunction wynik: 510 czas 110.0063ms
maxEvenConjunction2 wynik: 510 czas 80.0046ms
maksymalny próg: 1024
maxEvenDividing wynik: 1022 czas 109.0063ms
maxEvenDividing2 wynik: 1022 czas 77.0044ms
maxEvenConjunction wynik: 1022 czas 111.0063ms
maxEvenConjunction2 wynik: 1022 czas 81.0047ms
maksymalny próg: 2048
maxEvenDividing wynik: 2046 czas 114.0065ms
maxEvenDividing2 wynik: 2046 czas 79.0045ms
maxEvenConjunction wynik: 2046 czas 113.0065ms
maxEvenConjunction2 wynik: 2046 czas 81.0046ms
maksymalny próg: 4096
maxEvenDividing wynik: 4094 czas 114.0065ms
maxEvenDividing2 wynik: 4094 czas 80.0046ms
maxEvenConjunction wynik: 4094 czas 111.0063ms
maxEvenConjunction2 wynik: 4094 czas 78.0045ms
maksymalny próg: 8192
maxEvenDividing wynik: 8190 czas 107.0062ms
maxEvenDividing2 wynik: 8190 czas 77.0044ms
maxEvenConjunction wynik: 8190 czas 111.0063ms
maxEvenConjunction2 wynik: 8190 czas 77.0044ms
max threshold: 16384
maxEvenDividing wynik: 16382 czas 109.0063ms
maxEvenDividing2 wynik: 16382 czas 77.0044ms
maxEvenConjunction wynik: 16382 czas 108.0062ms
maxEvenConjunction2 wynik: 16382 czas 77.0044ms
maksymalny próg: 32768
maxEvenDividing wynik: 32766 czas 112.0064ms
maxEvenDividing2 wynik: 32766 czas 77.0044ms
maxEvenConjunction wynik: 32766 czas 109.0062ms
maxEvenConjunction2 wynik: 32766 czas 78.0045ms
maksymalny próg: 65536
maxEvenDividing wynik: 65534 czas 109.0062ms
maxEvenDividing2 wynik: 65534 czas 75.0043ms
maxEvenConjunction wynik: 65534 czas 109.0063ms
maxEvenConjunction2 wynik: 65534 czas 79.0045ms
maksymalny próg: 131072
maxEvenDividing wynik: 131070 czas 108.0061ms
maxEvenDividing2 wynik: 131070 czas 76.0044ms
maxEvenConjunction wynik: 131070 czas 110.0063ms
maxEvenConjunction2 wynik: 131070 czas 80.0046ms
maksymalny próg: 262144
maxEvenDividing wynik: 262142 czas 110.0063ms
maxEvenDividing2 wynik: 262142 czas 76.0044ms
maxEvenConjunction wynik: 262142 czas 107.0061ms
maxEvenConjunction2 wynik: 262142 czas 78.0044ms
maksymalny próg: 524288
maxEvenDividing wynik: 524286 czas 109.0062ms
maxEvenDividing2 wynik: 524286 czas 78.0045ms
maxEvenConjunction wynik: 524286 czas 109.0062ms
maxEvenConjunction2 wynik: 524286 czas 80.0046ms
maksymalny próg: 1048576
maxEvenDividing wynik: 1048574 czas 109.0063ms
maxEvenDividing2 wynik: 1048574 czas 80.0045ms
maxEvenConjunction wynik: 1048574 czas 114.0066ms
maxEvenConjunction2 wynik: 1048574 czas 78.0044ms
maksymalny próg: 2097152
maxEvenDividing wynik: 2097150 czas 111.0064ms
maxEvenDividing2 wynik: 2097150 czas 79.0045ms
maxEvenConjunction wynik: 2097150 czas 112.0064ms
maxEvenConjunction2 wynik: 2097150 czas 77.0044ms
maksymalny próg: 4194304
maxEvenDividing wynik: 4194302 czas 111.0063ms
maxEvenDividing2 wynik: 4194302 czas 78.0045ms
maxEvenConjunction wynik: 4194302 czas 111.0063ms
maxEvenConjunction2 wynik: 4194302 czas 77.0044ms
max threshold: 8388608
maxEvenDividing wynik: 8388606 czas 109.0062ms
maxEvenDividing2 wynik: 8388606 czas 78.0045ms
maxEvenConjunction wynik: 8388606 czas 114.0065ms
maxEvenConjunction2 wynik: 8388606 czas 78.0045ms
maksymalny próg: 16777216
maxEvenDividing wynik: 16777214 czas 109.0062ms
maxEvenDividing2 wynik: 16777214 czas 77.0044ms
maxEvenConjunction wynik: 16777214 czas 109.0063ms
maxEvenConjunction2 wynik: 16777214 czas 77.0044ms
maksymalny próg: 33554432
maxEvenDividing wynik: 33554430 czas 113.0065ms
maxEvenDividing2 wynik: 33554430 czas 78.0045ms
maxEvenConjunction wynik: 33554430 czas 110.0063ms
maxEvenConjunction2 wynik: 33554430 czas 80.0045ms
maksymalny próg: 67108864
maxEvenDividing wynik: 67108860 czas 112.0064ms
maxEvenDividing2 wynik: 67108860 czas 77.0044ms
maxEvenConjunction wynik: 67108860 czas 112.0064ms
maxEvenConjunction2 wynik: 67108860 czas 80.0046ms
maksymalny próg: 134217728
maxEvenDividing wynik: 134217726 czas 109.0063ms
maxEvenDividing2 wynik: 134217726 czas 78.0044ms
maxEvenConjunction wynik: 134217726 czas 114.0065ms
maxEvenConjunction2 wynik: 134217726 czas 81.0047ms
maksymalny próg: 268435456
maxEvenDividing wynik: 268435446 czas 111.0064ms
maxEvenDividing2 wynik: 268435446 czas 79.0045ms
maxEvenConjunction wynik: 268435446 czas 114.0065ms
maxEvenConjunction2 wynik: 268435446 czas 79.0045ms
maksymalny próg: 536870912
maxEvenDividing wynik: 536870910 czas 107.0062ms
maxEvenDividing2 wynik: 536870910 czas trwania 76.0043ms
maxEvenConjunction wynik: 536870910 czas trwania 109.0062ms
maxEvenConjunction2 wynik: 536870910 czas trwania 80.0046ms
Nie znalazłem sensownego wyjaśnienia, dlaczego kompilator Go nie optymalizuje kodu i zawsze sprawdza drugi warunek, nawet jeśli pierwszy jest fałszywy — może po prostu mi się „przymgliliło” i nie widzę jakiegoś oczywistego błędu? Czy może trzeba podać jakieś szczególne instrukcje kompilatorowi? Byłbym wdzięczny za rzeczowe komentarze.
PS: Tak, dla ciekawości, przeprowadziłem podobne testy w Java 5 oraz Java 7/8 — wszystko działa sprawnie, czas wykonania taki sam.
Źródło: habr.com
