Creus que aquestes dues opcions per provar les condicions dins d'un bucle són equivalents en rendiment?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Tot va començar amb un "escalfament del cervell"; vaig haver de donar un exemple d'una cerca òptima del nombre parell més gran en una matriu d'enters [-x....x]. Em preguntava quant seria millor el rendiment si utilitzés la multiplicació lògica per 1 per esbrinar si un nombre és parell o no.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
La meva experiència de programació a Go no és gaire extensa, poc més d'un any i mig, la vaig utilitzar, encara que sovint, però només amb finalitats utilitaries (bé, potser excepte un projecte relacionat amb un servei http d'alta càrrega), així que vaig va començar amb ell. Obriu GoLand i escriviu una prova senzilla
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
}
Obtenim un resultat que mostra que com més alt és el llindar, més sovint apareixen les fluctuacions del rendiment.
Comparamax 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
És evident que en aquest cas, per a diferents llindars tenim diferents conjunts de dades de prova, la càrrega del processador (al meu portàtil i5-2540M) varia al voltant del 20..30%, la memòria ocupada per l'aplicació que s'executa des de GoLand és de mitjana uns 813 MB: això també afecta la fiabilitat del resultat, cal desar casos de prova al disc i executar totes les proves per a cada llindar de manera aïllada.
I ara, pensant en com implementar tot això amb uns costos mínims, corregeixo automàticament la comprovació de l'estat
if value > current && value&1 == 0 {
current = value
}
en
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Torno a fer les proves... i deixo d'entendre res :)
El temps dedicat a l'execució comença a diferir ja no en percentatges/fraccions d'un percentatge, sinó en un 10..15%. Ràpidament afegeixo 2 proves més:
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
}
L'executo i tinc aquesta foto:Capacitat inicial de la matriu: 100000000
Llindar màxim: 128
Resultat maxEvenDividing: 126 durada 116.0066 ms
Resultat maxEvenDividing2: 126 durada 79.0045 ms
Resultat maxEvenConjunction: 126 durada 114.0065 ms
Resultat maxEvenConjunction2: 126 durada 83.0048 ms
Llindar màxim: 256
Resultat maxEvenDividing: 254 durada 111.0063 ms
Resultat maxEvenDividing2: 254 durada 77.0044 ms
Resultat maxEvenConjunction: 254 durada 110.0063 ms
Resultat maxEvenConjunction2: 254 durada 80.0046 ms
Llindar màxim: 512
Resultat maxEvenDividing: 510 durada 114.0066 ms
Resultat maxEvenDividing2: 510 durada 80.0045 ms
Resultat maxEvenConjunction: 510 durada 110.0063 ms
Resultat maxEvenConjunction2: 510 durada 80.0046 ms
Llindar màxim: 1024
Resultat maxEvenDividing: 1022 durada 109.0063 ms
Resultat maxEvenDividing2: 1022 durada 77.0044 ms
Resultat maxEvenConjunction: 1022 durada 111.0063 ms
Resultat maxEvenConjunction2: 1022 durada 81.0047 ms
Llindar màxim: 2048
Resultat maxEvenDividing: 2046 durada 114.0065 ms
Resultat maxEvenDividing2: 2046 durada 79.0045 ms
Resultat maxEvenConjunction: 2046 durada 113.0065 ms
Resultat maxEvenConjunction2: 2046 durada 81.0046 ms
Llindar màxim: 4096
Resultat maxEvenDividing: 4094 durada 114.0065 ms
Resultat maxEvenDividing2: 4094 durada 80.0046 ms
Resultat maxEvenConjunction: 4094 durada 111.0063 ms
Resultat maxEvenConjunction2: 4094 durada 78.0045 ms
Llindar màxim: 8192
Resultat maxEvenDividing: 8190 durada 107.0062 ms
Resultat maxEvenDividing2: 8190 durada 77.0044 ms
Resultat maxEvenConjunction: 8190 durada 111.0063 ms
Resultat maxEvenConjunction2: 8190 durada 77.0044 ms
Llindar màxim: 16384
Resultat maxEvenDividing: 16382 durada 109.0063 ms
Resultat maxEvenDividing2: 16382 durada 77.0044 ms
Resultat maxEvenConjunction: 16382 durada 108.0062 ms
Resultat maxEvenConjunction2: 16382 durada 77.0044 ms
Llindar màxim: 32768
Resultat maxEvenDividing: 32766 durada 112.0064 ms
Resultat maxEvenDividing2: 32766 durada 77.0044 ms
Resultat maxEvenConjunction: 32766 durada 109.0062 ms
Resultat maxEvenConjunction2: 32766 durada 78.0045 ms
Llindar màxim: 65536
Resultat maxEvenDividing: 65534 durada 109.0062 ms
Resultat maxEvenDividing2: 65534 durada 75.0043 ms
Resultat maxEvenConjunction: 65534 durada 109.0063 ms
Resultat maxEvenConjunction2: 65534 durada 79.0045 ms
Llindar màxim: 131072
Resultat maxEvenDividing: 131070 durada 108.0061 ms
Resultat maxEvenDividing2: 131070 durada 76.0044 ms
Resultat maxEvenConjunction: 131070 durada 110.0063 ms
Resultat maxEvenConjunction2: 131070 durada 80.0046 ms
Llindar màxim: 262144
Resultat maxEvenDividing: 262142 durada 110.0063 ms
Resultat maxEvenDividing2: 262142 durada 76.0044 ms
Resultat maxEvenConjunction: 262142 durada 107.0061 ms
Resultat maxEvenConjunction2: 262142 durada 78.0044 ms
Llindar màxim: 524288
Resultat maxEvenDividing: 524286 durada 109.0062 ms
Resultat maxEvenDividing2: 524286 durada 78.0045 ms
Resultat maxEvenConjunction: 524286 durada 109.0062 ms
Resultat maxEvenConjunction2: 524286 durada 80.0046 ms
Llindar màxim: 1048576
Resultat maxEvenDividing: 1048574 durada 109.0063 ms
Resultat maxEvenDividing2: 1048574 durada 80.0045 ms
Resultat maxEvenConjunction: 1048574 durada 114.0066 ms
Resultat maxEvenConjunction2: 1048574 durada 78.0044 ms
Llindar màxim: 2097152
Resultat maxEvenDividing: 2097150 durada 111.0064 ms
Resultat maxEvenDividing2: 2097150 durada 79.0045 ms
Resultat maxEvenConjunction: 2097150 durada 112.0064 ms
Resultat maxEvenConjunction2: 2097150 durada 77.0044 ms
Llindar màxim: 4194304
Resultat maxEvenDividing: 4194302 durada 111.0063 ms
Resultat maxEvenDividing2: 4194302 durada 78.0045 ms
Resultat maxEvenConjunction: 4194302 durada 111.0063 ms
Resultat maxEvenConjunction2: 4194302 durada 77.0044 ms
Llindar màxim: 8388608
Resultat maxEvenDividing: 8388606 durada 109.0062 ms
Resultat maxEvenDividing2: 8388606 durada 78.0045 ms
Resultat maxEvenConjunction: 8388606 durada 114.0065 ms
Resultat maxEvenConjunction2: 8388606 durada 78.0045 ms
Llindar màxim: 16777216
Resultat maxEvenDividing: 16777214 durada 109.0062 ms
Resultat maxEvenDividing2: 16777214 durada 77.0044 ms
Resultat maxEvenConjunction: 16777214 durada 109.0063 ms
Resultat maxEvenConjunction2: 16777214 durada 77.0044 ms
Llindar màxim: 33554432
Resultat maxEvenDividing: 33554430 durada 113.0065 ms
Resultat maxEvenDividing2: 33554430 durada 78.0045 ms
Resultat maxEvenConjunction: 33554430 durada 110.0063 ms
Resultat maxEvenConjunction2: 33554430 durada 80.0045 ms
Llindar màxim: 67108864
Resultat maxEvenDividing: 67108860 durada 112.0064 ms
Resultat maxEvenDividing2: 67108860 durada 77.0044 ms
Resultat maxEvenConjunction: 67108860 durada 112.0064 ms
Resultat maxEvenConjunction2: 67108860 durada 80.0046 ms
Llindar màxim: 134217728
Resultat maxEvenDividing: 134217726 durada 109.0063 ms
Resultat maxEvenDividing2: 134217726 durada 78.0044 ms
Resultat maxEvenConjunction: 134217726 durada 114.0065 ms
Resultat maxEvenConjunction2: 134217726 durada 81.0047 ms
Llindar màxim: 268435456
Resultat maxEvenDividing: 268435446 durada 111.0064 ms
Resultat maxEvenDividing2: 268435446 durada 79.0045 ms
Resultat maxEvenConjunction: 268435446 durada 114.0065 ms
Resultat maxEvenConjunction2: 268435446 durada 79.0045 ms
Llindar màxim: 536870912
Resultat maxEvenDividing: 536870910 durada 107.0062 ms
Resultat maxEvenDividing2: 536870910 durada 76.0043 ms
Resultat maxEvenConjunction: 536870910 durada 109.0062 ms
Resultat maxEvenConjunction2: 536870910 durada 80.0046 ms
No he trobat una explicació clara per què el compilador Go no optimitza el codi i sempre comprova la segona condició, encara que la primera sigui falsa. O potser els meus ulls estan borrosos i no veig cap error evident? O necessites proporcionar algunes instruccions especials al compilador? M'agradaria tenir comentaris sensats.
PS: Sí, només per diversió, vaig fer proves similars a Java 5 i Java 7/8: tot està clar, el temps d'execució és el mateix.
Font: www.habr.com