Glauben Sie, dass diese beiden Optionen zum Testen von Bedingungen innerhalb einer Schleife hinsichtlich der Leistung gleichwertig sind?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Alles begann mit einem „Aufwärmen des Gehirns“; ich musste ein Beispiel für eine optimale Suche nach der größten geraden Zahl in einem Array von ganzen Zahlen [-x....x] geben. Ich habe mich gefragt, wie viel besser die Leistung wäre, wenn ich die logische Multiplikation mit 1 verwenden würde, um herauszufinden, ob eine Zahl gerade ist oder nicht.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Meine Programmiererfahrung in Go ist nicht sehr umfangreich, etwas mehr als eineinhalb Jahre, ich habe es zwar oft, aber rein aus praktischen Gründen genutzt (na ja, vielleicht mit Ausnahme eines Projekts im Zusammenhang mit einem stark ausgelasteten http-Dienst), also habe ich habe damit angefangen. Öffnen Sie GoLand und schreiben Sie einen einfachen 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
}
Wir erhalten ein Ergebnis, das zeigt: Je höher der Schwellenwert, desto häufiger treten Leistungsschwankungen auf.
Vergleichenmax 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
Es ist klar, dass wir in diesem Fall für unterschiedliche Schwellenwerte unterschiedliche Sätze von Testdaten haben, die Prozessorlast (auf meinem i5-2540M-Laptop) um etwa 20 bis 30 % schwankt und der von der von GoLand ausgeführten Anwendung belegte Speicher im Durchschnitt liegt ca. 813 MB – dies wirkt sich auch auf die Zuverlässigkeit des Ergebnisses aus. Sie müssen Testfälle auf der Festplatte speichern und alle Tests für jeden Schwellenwert isoliert voneinander ausführen.
Und wenn ich jetzt darüber nachdenke, wie ich das alles mit minimalen Kosten umsetzen kann, korrigiere ich automatisch die Zustandsprüfung
if value > current && value&1 == 0 {
current = value
}
auf
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Ich führe die Tests noch einmal durch... und ich verstehe nichts mehr :)
Die für die Ausführung aufgewendete Zeit beginnt sich nicht mehr um Prozente/Bruchteile eines Prozents, sondern um 10..15 % zu unterscheiden. Ich füge schnell noch zwei weitere Tests hinzu:
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
}
Ich führe es aus und erhalte dieses Bild:anfängliche Array-Kapazität: 100000000
Maximaler Schwellenwert: 128
maxEvenDividing Ergebnis: 126 Dauer 116.0066 ms
maxEvenDividing2 Ergebnis: 126 Dauer 79.0045 ms
maxEvenConjunction-Ergebnis: 126 Dauer 114.0065 ms
maxEvenConjunction2 Ergebnis: 126 Dauer 83.0048 ms
Maximaler Schwellenwert: 256
maxEvenDividing Ergebnis: 254 Dauer 111.0063 ms
maxEvenDividing2 Ergebnis: 254 Dauer 77.0044 ms
maxEvenConjunction-Ergebnis: 254 Dauer 110.0063 ms
maxEvenConjunction2 Ergebnis: 254 Dauer 80.0046 ms
Maximaler Schwellenwert: 512
maxEvenDividing Ergebnis: 510 Dauer 114.0066 ms
maxEvenDividing2 Ergebnis: 510 Dauer 80.0045 ms
maxEvenConjunction-Ergebnis: 510 Dauer 110.0063 ms
maxEvenConjunction2 Ergebnis: 510 Dauer 80.0046 ms
Maximaler Schwellenwert: 1024
maxEvenDividing Ergebnis: 1022 Dauer 109.0063 ms
maxEvenDividing2 Ergebnis: 1022 Dauer 77.0044 ms
maxEvenConjunction-Ergebnis: 1022 Dauer 111.0063 ms
maxEvenConjunction2 Ergebnis: 1022 Dauer 81.0047 ms
Maximaler Schwellenwert: 2048
maxEvenDividing Ergebnis: 2046 Dauer 114.0065 ms
maxEvenDividing2 Ergebnis: 2046 Dauer 79.0045 ms
maxEvenConjunction-Ergebnis: 2046 Dauer 113.0065 ms
maxEvenConjunction2 Ergebnis: 2046 Dauer 81.0046 ms
Maximaler Schwellenwert: 4096
maxEvenDividing Ergebnis: 4094 Dauer 114.0065 ms
maxEvenDividing2 Ergebnis: 4094 Dauer 80.0046 ms
maxEvenConjunction-Ergebnis: 4094 Dauer 111.0063 ms
maxEvenConjunction2 Ergebnis: 4094 Dauer 78.0045 ms
Maximaler Schwellenwert: 8192
maxEvenDividing Ergebnis: 8190 Dauer 107.0062 ms
maxEvenDividing2 Ergebnis: 8190 Dauer 77.0044 ms
maxEvenConjunction-Ergebnis: 8190 Dauer 111.0063 ms
maxEvenConjunction2 Ergebnis: 8190 Dauer 77.0044 ms
Maximaler Schwellenwert: 16384
maxEvenDividing Ergebnis: 16382 Dauer 109.0063 ms
maxEvenDividing2 Ergebnis: 16382 Dauer 77.0044 ms
maxEvenConjunction-Ergebnis: 16382 Dauer 108.0062 ms
maxEvenConjunction2 Ergebnis: 16382 Dauer 77.0044 ms
Maximaler Schwellenwert: 32768
maxEvenDividing Ergebnis: 32766 Dauer 112.0064 ms
maxEvenDividing2 Ergebnis: 32766 Dauer 77.0044 ms
maxEvenConjunction-Ergebnis: 32766 Dauer 109.0062 ms
maxEvenConjunction2 Ergebnis: 32766 Dauer 78.0045 ms
Maximaler Schwellenwert: 65536
maxEvenDividing Ergebnis: 65534 Dauer 109.0062 ms
maxEvenDividing2 Ergebnis: 65534 Dauer 75.0043 ms
maxEvenConjunction-Ergebnis: 65534 Dauer 109.0063 ms
maxEvenConjunction2 Ergebnis: 65534 Dauer 79.0045 ms
Maximaler Schwellenwert: 131072
maxEvenDividing Ergebnis: 131070 Dauer 108.0061 ms
maxEvenDividing2 Ergebnis: 131070 Dauer 76.0044 ms
maxEvenConjunction-Ergebnis: 131070 Dauer 110.0063 ms
maxEvenConjunction2 Ergebnis: 131070 Dauer 80.0046 ms
Maximaler Schwellenwert: 262144
maxEvenDividing Ergebnis: 262142 Dauer 110.0063 ms
maxEvenDividing2 Ergebnis: 262142 Dauer 76.0044 ms
maxEvenConjunction-Ergebnis: 262142 Dauer 107.0061 ms
maxEvenConjunction2 Ergebnis: 262142 Dauer 78.0044 ms
Maximaler Schwellenwert: 524288
maxEvenDividing Ergebnis: 524286 Dauer 109.0062 ms
maxEvenDividing2 Ergebnis: 524286 Dauer 78.0045 ms
maxEvenConjunction-Ergebnis: 524286 Dauer 109.0062 ms
maxEvenConjunction2 Ergebnis: 524286 Dauer 80.0046 ms
Maximaler Schwellenwert: 1048576
maxEvenDividing Ergebnis: 1048574 Dauer 109.0063 ms
maxEvenDividing2 Ergebnis: 1048574 Dauer 80.0045 ms
maxEvenConjunction-Ergebnis: 1048574 Dauer 114.0066 ms
maxEvenConjunction2 Ergebnis: 1048574 Dauer 78.0044 ms
Maximaler Schwellenwert: 2097152
maxEvenDividing Ergebnis: 2097150 Dauer 111.0064 ms
maxEvenDividing2 Ergebnis: 2097150 Dauer 79.0045 ms
maxEvenConjunction-Ergebnis: 2097150 Dauer 112.0064 ms
maxEvenConjunction2 Ergebnis: 2097150 Dauer 77.0044 ms
Maximaler Schwellenwert: 4194304
maxEvenDividing Ergebnis: 4194302 Dauer 111.0063 ms
maxEvenDividing2 Ergebnis: 4194302 Dauer 78.0045 ms
maxEvenConjunction-Ergebnis: 4194302 Dauer 111.0063 ms
maxEvenConjunction2 Ergebnis: 4194302 Dauer 77.0044 ms
Maximaler Schwellenwert: 8388608
maxEvenDividing Ergebnis: 8388606 Dauer 109.0062 ms
maxEvenDividing2 Ergebnis: 8388606 Dauer 78.0045 ms
maxEvenConjunction-Ergebnis: 8388606 Dauer 114.0065 ms
maxEvenConjunction2 Ergebnis: 8388606 Dauer 78.0045 ms
Maximaler Schwellenwert: 16777216
maxEvenDividing Ergebnis: 16777214 Dauer 109.0062 ms
maxEvenDividing2 Ergebnis: 16777214 Dauer 77.0044 ms
maxEvenConjunction-Ergebnis: 16777214 Dauer 109.0063 ms
maxEvenConjunction2 Ergebnis: 16777214 Dauer 77.0044 ms
Maximaler Schwellenwert: 33554432
maxEvenDividing Ergebnis: 33554430 Dauer 113.0065 ms
maxEvenDividing2 Ergebnis: 33554430 Dauer 78.0045 ms
maxEvenConjunction-Ergebnis: 33554430 Dauer 110.0063 ms
maxEvenConjunction2 Ergebnis: 33554430 Dauer 80.0045 ms
Maximaler Schwellenwert: 67108864
maxEvenDividing Ergebnis: 67108860 Dauer 112.0064 ms
maxEvenDividing2 Ergebnis: 67108860 Dauer 77.0044 ms
maxEvenConjunction-Ergebnis: 67108860 Dauer 112.0064 ms
maxEvenConjunction2 Ergebnis: 67108860 Dauer 80.0046 ms
Maximaler Schwellenwert: 134217728
maxEvenDividing Ergebnis: 134217726 Dauer 109.0063 ms
maxEvenDividing2 Ergebnis: 134217726 Dauer 78.0044 ms
maxEvenConjunction-Ergebnis: 134217726 Dauer 114.0065 ms
maxEvenConjunction2 Ergebnis: 134217726 Dauer 81.0047 ms
Maximaler Schwellenwert: 268435456
maxEvenDividing Ergebnis: 268435446 Dauer 111.0064 ms
maxEvenDividing2 Ergebnis: 268435446 Dauer 79.0045 ms
maxEvenConjunction-Ergebnis: 268435446 Dauer 114.0065 ms
maxEvenConjunction2 Ergebnis: 268435446 Dauer 79.0045 ms
Maximaler Schwellenwert: 536870912
maxEvenDividing Ergebnis: 536870910 Dauer 107.0062 ms
maxEvenDividing2 Ergebnis: 536870910 Dauer 76.0043 ms
maxEvenConjunction-Ergebnis: 536870910 Dauer 109.0062 ms
maxEvenConjunction2 Ergebnis: 536870910 Dauer 80.0046 ms
Ich konnte keine klare Erklärung dafür finden, warum der Go-Compiler den Code nicht optimiert und immer die zweite Bedingung prüft, auch wenn die erste falsch ist. Oder sind meine Augen vielleicht nur verschwommen und ich sehe keinen offensichtlichen Fehler? Oder müssen Sie dem Compiler spezielle Anweisungen geben? Über sinnvolle Kommentare würde ich mich freuen.
PS: Ja, nur zum Spaß habe ich ähnliche Tests auf Java 5 und Java 7/8 durchgeführt – alles ist klar, die Ausführungszeit ist gleich.
Source: habr.com