Πιστεύετε ότι αυτές οι δύο επιλογές για τη δοκιμή συνθηκών εντός ενός βρόχου είναι ισοδύναμες σε απόδοση;
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Όλα ξεκίνησαν με μια «προθέρμανση εγκεφάλου»· έπρεπε να δώσω ένα παράδειγμα βέλτιστης αναζήτησης για τον μεγαλύτερο ζυγό αριθμό σε έναν πίνακα ακεραίων [-x....x]. Αναρωτιόμουν πόσο καλύτερη απόδοση θα ήταν αν χρησιμοποιούσα λογικό πολλαπλασιασμό με το 1 για να καταλάβω αν ένας αριθμός είναι ζυγός ή όχι.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Η εμπειρία μου στον προγραμματισμό στο Go δεν είναι πολύ μεγάλη, λίγο περισσότερο από ενάμιση χρόνο, το χρησιμοποίησα, αν και συχνά, αλλά καθαρά για χρηστικούς σκοπούς (καλά, ίσως εκτός από ένα έργο που σχετίζεται με μια υπηρεσία http υψηλού φορτίου), οπότε ξεκίνησε με αυτό. Ανοίξτε το GoLand και γράψτε ένα απλό τεστ
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
}
Παίρνουμε ένα αποτέλεσμα που δείχνει ότι όσο υψηλότερο είναι το όριο, τόσο πιο συχνά εμφανίζονται διακυμάνσεις στην απόδοση.
Συγκρίνετεmax 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
Είναι σαφές ότι σε αυτήν την περίπτωση, για διαφορετικά όρια έχουμε διαφορετικά σύνολα δεδομένων δοκιμής, το φορτίο του επεξεργαστή (στο φορητό υπολογιστή i5-2540M μου) κυμαίνεται γύρω στο 20..30%, η μνήμη που καταλαμβάνει η εφαρμογή που εκτελείται από το GoLand είναι κατά μέσο όρο περίπου 813MB - αυτό επηρεάζει επίσης την αξιοπιστία του αποτελέσματος, πρέπει να αποθηκεύσετε τις περιπτώσεις δοκιμών στο δίσκο και να εκτελέσετε όλες τις δοκιμές για κάθε όριο χωριστά το ένα από το άλλο.
Και τώρα, σκεπτόμενος πώς θα τα εφαρμόσω όλα αυτά με ελάχιστο κόστος, διορθώνω αυτόματα τον έλεγχο κατάστασης
if value > current && value&1 == 0 {
current = value
}
επί
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Ξανακάνω τα τεστ... και δεν καταλαβαίνω τίποτα :)
Ο χρόνος που δαπανάται για την εκτέλεση αρχίζει να διαφέρει όχι πλέον κατά ποσοστά/κλάσματα του ποσοστού, αλλά κατά 10..15%. Προσθέτω γρήγορα 2 ακόμη τεστ:
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
}
Το τρέχω και βγάζω αυτή την εικόνα:αρχική χωρητικότητα συστοιχίας: 100000000
μέγιστο όριο: 128
maxEvenDividing αποτέλεσμα: 126 διάρκεια 116.0066ms
maxEvenDividing2 αποτέλεσμα: 126 διάρκεια 79.0045ms
maxEvenConjunction αποτέλεσμα: 126 διάρκεια 114.0065ms
maxEvenConjunction2 αποτέλεσμα: 126 διάρκεια 83.0048ms
μέγιστο όριο: 256
maxEvenDividing αποτέλεσμα: 254 διάρκεια 111.0063ms
maxEvenDividing2 αποτέλεσμα: 254 διάρκεια 77.0044ms
maxEvenConjunction αποτέλεσμα: 254 διάρκεια 110.0063ms
maxEvenConjunction2 αποτέλεσμα: 254 διάρκεια 80.0046ms
μέγιστο όριο: 512
maxEvenDividing αποτέλεσμα: 510 διάρκεια 114.0066ms
maxEvenDividing2 αποτέλεσμα: 510 διάρκεια 80.0045ms
maxEvenConjunction αποτέλεσμα: 510 διάρκεια 110.0063ms
maxEvenConjunction2 αποτέλεσμα: 510 διάρκεια 80.0046ms
μέγιστο όριο: 1024
maxEvenDividing αποτέλεσμα: 1022 διάρκεια 109.0063ms
maxEvenDividing2 αποτέλεσμα: 1022 διάρκεια 77.0044ms
maxEvenConjunction αποτέλεσμα: 1022 διάρκεια 111.0063ms
maxEvenConjunction2 αποτέλεσμα: 1022 διάρκεια 81.0047ms
μέγιστο όριο: 2048
maxEvenDividing αποτέλεσμα: 2046 διάρκεια 114.0065ms
maxEvenDividing2 αποτέλεσμα: 2046 διάρκεια 79.0045ms
maxEvenConjunction αποτέλεσμα: 2046 διάρκεια 113.0065ms
maxEvenConjunction2 αποτέλεσμα: 2046 διάρκεια 81.0046ms
μέγιστο όριο: 4096
maxEvenDividing αποτέλεσμα: 4094 διάρκεια 114.0065ms
maxEvenDividing2 αποτέλεσμα: 4094 διάρκεια 80.0046ms
maxEvenConjunction αποτέλεσμα: 4094 διάρκεια 111.0063ms
maxEvenConjunction2 αποτέλεσμα: 4094 διάρκεια 78.0045ms
μέγιστο όριο: 8192
maxEvenDividing αποτέλεσμα: 8190 διάρκεια 107.0062ms
maxEvenDividing2 αποτέλεσμα: 8190 διάρκεια 77.0044ms
maxEvenConjunction αποτέλεσμα: 8190 διάρκεια 111.0063ms
maxEvenConjunction2 αποτέλεσμα: 8190 διάρκεια 77.0044ms
μέγιστο όριο: 16384
maxEvenDividing αποτέλεσμα: 16382 διάρκεια 109.0063ms
maxEvenDividing2 αποτέλεσμα: 16382 διάρκεια 77.0044ms
maxEvenConjunction αποτέλεσμα: 16382 διάρκεια 108.0062ms
maxEvenConjunction2 αποτέλεσμα: 16382 διάρκεια 77.0044ms
μέγιστο όριο: 32768
maxEvenDividing αποτέλεσμα: 32766 διάρκεια 112.0064ms
maxEvenDividing2 αποτέλεσμα: 32766 διάρκεια 77.0044ms
maxEvenConjunction αποτέλεσμα: 32766 διάρκεια 109.0062ms
maxEvenConjunction2 αποτέλεσμα: 32766 διάρκεια 78.0045ms
μέγιστο όριο: 65536
maxEvenDividing αποτέλεσμα: 65534 διάρκεια 109.0062ms
maxEvenDividing2 αποτέλεσμα: 65534 διάρκεια 75.0043ms
maxEvenConjunction αποτέλεσμα: 65534 διάρκεια 109.0063ms
maxEvenConjunction2 αποτέλεσμα: 65534 διάρκεια 79.0045ms
μέγιστο όριο: 131072
maxEvenDividing αποτέλεσμα: 131070 διάρκεια 108.0061ms
maxEvenDividing2 αποτέλεσμα: 131070 διάρκεια 76.0044ms
maxEvenConjunction αποτέλεσμα: 131070 διάρκεια 110.0063ms
maxEvenConjunction2 αποτέλεσμα: 131070 διάρκεια 80.0046ms
μέγιστο όριο: 262144
maxEvenDividing αποτέλεσμα: 262142 διάρκεια 110.0063ms
maxEvenDividing2 αποτέλεσμα: 262142 διάρκεια 76.0044ms
maxEvenConjunction αποτέλεσμα: 262142 διάρκεια 107.0061ms
maxEvenConjunction2 αποτέλεσμα: 262142 διάρκεια 78.0044ms
μέγιστο όριο: 524288
maxEvenDividing αποτέλεσμα: 524286 διάρκεια 109.0062ms
maxEvenDividing2 αποτέλεσμα: 524286 διάρκεια 78.0045ms
maxEvenConjunction αποτέλεσμα: 524286 διάρκεια 109.0062ms
maxEvenConjunction2 αποτέλεσμα: 524286 διάρκεια 80.0046ms
μέγιστο όριο: 1048576
maxEvenDividing αποτέλεσμα: 1048574 διάρκεια 109.0063ms
maxEvenDividing2 αποτέλεσμα: 1048574 διάρκεια 80.0045ms
maxEvenConjunction αποτέλεσμα: 1048574 διάρκεια 114.0066ms
maxEvenConjunction2 αποτέλεσμα: 1048574 διάρκεια 78.0044ms
μέγιστο όριο: 2097152
maxEvenDividing αποτέλεσμα: 2097150 διάρκεια 111.0064ms
maxEvenDividing2 αποτέλεσμα: 2097150 διάρκεια 79.0045ms
maxEvenConjunction αποτέλεσμα: 2097150 διάρκεια 112.0064ms
maxEvenConjunction2 αποτέλεσμα: 2097150 διάρκεια 77.0044ms
μέγιστο όριο: 4194304
maxEvenDividing αποτέλεσμα: 4194302 διάρκεια 111.0063ms
maxEvenDividing2 αποτέλεσμα: 4194302 διάρκεια 78.0045ms
maxEvenConjunction αποτέλεσμα: 4194302 διάρκεια 111.0063ms
maxEvenConjunction2 αποτέλεσμα: 4194302 διάρκεια 77.0044ms
μέγιστο όριο: 8388608
maxEvenDividing αποτέλεσμα: 8388606 διάρκεια 109.0062ms
maxEvenDividing2 αποτέλεσμα: 8388606 διάρκεια 78.0045ms
maxEvenConjunction αποτέλεσμα: 8388606 διάρκεια 114.0065ms
maxEvenConjunction2 αποτέλεσμα: 8388606 διάρκεια 78.0045ms
μέγιστο όριο: 16777216
maxEvenDividing αποτέλεσμα: 16777214 διάρκεια 109.0062ms
maxEvenDividing2 αποτέλεσμα: 16777214 διάρκεια 77.0044ms
maxEvenConjunction αποτέλεσμα: 16777214 διάρκεια 109.0063ms
maxEvenConjunction2 αποτέλεσμα: 16777214 διάρκεια 77.0044ms
μέγιστο όριο: 33554432
maxEvenDividing αποτέλεσμα: 33554430 διάρκεια 113.0065ms
maxEvenDividing2 αποτέλεσμα: 33554430 διάρκεια 78.0045ms
maxEvenConjunction αποτέλεσμα: 33554430 διάρκεια 110.0063ms
maxEvenConjunction2 αποτέλεσμα: 33554430 διάρκεια 80.0045ms
μέγιστο όριο: 67108864
maxEvenDividing αποτέλεσμα: 67108860 διάρκεια 112.0064ms
maxEvenDividing2 αποτέλεσμα: 67108860 διάρκεια 77.0044ms
maxEvenConjunction αποτέλεσμα: 67108860 διάρκεια 112.0064ms
maxEvenConjunction2 αποτέλεσμα: 67108860 διάρκεια 80.0046ms
μέγιστο όριο: 134217728
maxEvenDividing αποτέλεσμα: 134217726 διάρκεια 109.0063ms
maxEvenDividing2 αποτέλεσμα: 134217726 διάρκεια 78.0044ms
maxEvenConjunction αποτέλεσμα: 134217726 διάρκεια 114.0065ms
maxEvenConjunction2 αποτέλεσμα: 134217726 διάρκεια 81.0047ms
μέγιστο όριο: 268435456
maxEvenDividing αποτέλεσμα: 268435446 διάρκεια 111.0064ms
maxEvenDividing2 αποτέλεσμα: 268435446 διάρκεια 79.0045ms
maxEvenConjunction αποτέλεσμα: 268435446 διάρκεια 114.0065ms
maxEvenConjunction2 αποτέλεσμα: 268435446 διάρκεια 79.0045ms
μέγιστο όριο: 536870912
maxEvenDividing αποτέλεσμα: 536870910 διάρκεια 107.0062ms
maxEvenDividing2 αποτέλεσμα: 536870910 διάρκεια 76.0043ms
maxEvenConjunction αποτέλεσμα: 536870910 διάρκεια 109.0062ms
maxEvenConjunction2 αποτέλεσμα: 536870910 διάρκεια 80.0046ms
Δεν μπορούσα να βρω μια σαφή εξήγηση γιατί ο μεταγλωττιστής Go δεν βελτιστοποιεί τον κώδικα και ελέγχει πάντα τη δεύτερη συνθήκη, ακόμα κι αν η πρώτη είναι ψευδής. Ή μήπως τα μάτια μου είναι απλά θολά και δεν βλέπω κάποιο προφανές λάθος; Ή πρέπει να δώσετε κάποιες ειδικές οδηγίες στον μεταγλωττιστή; Θα χαρώ για λογικά σχόλια.
PS: Ναι, για πλάκα, έτρεξα παρόμοιες δοκιμές σε Java 5 και Java 7/8 - όλα είναι ξεκάθαρα, ο χρόνος εκτέλεσης είναι ίδιος.
Πηγή: www.habr.com