¿Crees que estas dos opciones para probar las condiciones dentro de un bucle son equivalentes en rendimiento?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Todo empezó con un “calentamiento cerebral”; tuve que dar un ejemplo de búsqueda óptima del número par más grande en una matriz de números enteros [-x....x]. Me preguntaba cuánto mejor sería el rendimiento si usara la multiplicación lógica por 1 para determinar si un número es par o no.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Mi experiencia en programación en Go no es muy extensa, poco más de un año y medio, lo usé, aunque a menudo, pero puramente con fines utilitarios (bueno, tal vez excepto para un proyecto relacionado con un servicio http de alta carga), así que empezó con ello. Abra GoLand y escriba una prueba sencilla
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
}
Obtenemos un resultado que muestra que cuanto más alto es el umbral, más a menudo aparecen fluctuaciones en el rendimiento.
Compararmax 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
Está claro que en este caso, para diferentes umbrales tenemos diferentes conjuntos de datos de prueba, la carga del procesador (en mi computadora portátil i5-2540M) varía alrededor del 20..30%, la memoria ocupada por la aplicación que se ejecuta desde GoLand es en promedio aproximadamente 813 MB; esto también afecta la confiabilidad del resultado; debe guardar los casos de prueba en el disco y ejecutar todas las pruebas para cada umbral de forma aislada entre sí.
Y ahora, pensando en cómo implementar todo esto con costos mínimos, corrijo automáticamente la verificación de condición.
if value > current && value&1 == 0 {
current = value
}
en
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Vuelvo a realizar las pruebas... y dejo de entender nada :)
El tiempo dedicado a la ejecución comienza a diferir no en porcentajes/fracciones de porcentaje, sino en 10...15%. Rápidamente agrego 2 pruebas 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
}
Lo ejecuto y obtengo esta imagen:capacidad de matriz inicial: 100000000
umbral máximo: 128
resultado maxEvenDividing: 126 duración 116.0066ms
Resultado maxEvenDividing2: 126 duración 79.0045 ms
Resultado maxEvenConjunction: 126 duración 114.0065 ms
Resultado de maxEvenConjunction2: 126 duración 83.0048 ms
umbral máximo: 256
resultado maxEvenDividing: 254 duración 111.0063ms
Resultado maxEvenDividing2: 254 duración 77.0044 ms
Resultado maxEvenConjunction: 254 duración 110.0063 ms
Resultado de maxEvenConjunction2: 254 duración 80.0046 ms
umbral máximo: 512
resultado maxEvenDividing: 510 duración 114.0066ms
Resultado maxEvenDividing2: 510 duración 80.0045 ms
Resultado maxEvenConjunction: 510 duración 110.0063 ms
Resultado de maxEvenConjunction2: 510 duración 80.0046 ms
umbral máximo: 1024
resultado maxEvenDividing: 1022 duración 109.0063ms
Resultado maxEvenDividing2: 1022 duración 77.0044 ms
Resultado maxEvenConjunction: 1022 duración 111.0063 ms
Resultado de maxEvenConjunction2: 1022 duración 81.0047 ms
umbral máximo: 2048
resultado maxEvenDividing: 2046 duración 114.0065ms
Resultado maxEvenDividing2: 2046 duración 79.0045 ms
Resultado maxEvenConjunction: 2046 duración 113.0065 ms
Resultado de maxEvenConjunction2: 2046 duración 81.0046 ms
umbral máximo: 4096
resultado maxEvenDividing: 4094 duración 114.0065ms
Resultado maxEvenDividing2: 4094 duración 80.0046 ms
Resultado maxEvenConjunction: 4094 duración 111.0063 ms
Resultado de maxEvenConjunction2: 4094 duración 78.0045 ms
umbral máximo: 8192
resultado maxEvenDividing: 8190 duración 107.0062ms
Resultado maxEvenDividing2: 8190 duración 77.0044 ms
Resultado maxEvenConjunction: 8190 duración 111.0063 ms
Resultado de maxEvenConjunction2: 8190 duración 77.0044 ms
umbral máximo: 16384
resultado maxEvenDividing: 16382 duración 109.0063ms
Resultado maxEvenDividing2: 16382 duración 77.0044 ms
Resultado maxEvenConjunction: 16382 duración 108.0062 ms
Resultado de maxEvenConjunction2: 16382 duración 77.0044 ms
umbral máximo: 32768
resultado maxEvenDividing: 32766 duración 112.0064ms
Resultado maxEvenDividing2: 32766 duración 77.0044 ms
Resultado maxEvenConjunction: 32766 duración 109.0062 ms
Resultado de maxEvenConjunction2: 32766 duración 78.0045 ms
umbral máximo: 65536
resultado maxEvenDividing: 65534 duración 109.0062ms
Resultado maxEvenDividing2: 65534 duración 75.0043 ms
Resultado maxEvenConjunction: 65534 duración 109.0063 ms
Resultado de maxEvenConjunction2: 65534 duración 79.0045 ms
umbral máximo: 131072
resultado maxEvenDividing: 131070 duración 108.0061ms
Resultado maxEvenDividing2: 131070 duración 76.0044 ms
Resultado maxEvenConjunction: 131070 duración 110.0063 ms
Resultado de maxEvenConjunction2: 131070 duración 80.0046 ms
umbral máximo: 262144
resultado maxEvenDividing: 262142 duración 110.0063ms
Resultado maxEvenDividing2: 262142 duración 76.0044 ms
Resultado maxEvenConjunction: 262142 duración 107.0061 ms
Resultado de maxEvenConjunction2: 262142 duración 78.0044 ms
umbral máximo: 524288
resultado maxEvenDividing: 524286 duración 109.0062ms
Resultado maxEvenDividing2: 524286 duración 78.0045 ms
Resultado maxEvenConjunction: 524286 duración 109.0062 ms
Resultado de maxEvenConjunction2: 524286 duración 80.0046 ms
umbral máximo: 1048576
resultado maxEvenDividing: 1048574 duración 109.0063ms
Resultado maxEvenDividing2: 1048574 duración 80.0045 ms
Resultado maxEvenConjunction: 1048574 duración 114.0066 ms
Resultado de maxEvenConjunction2: 1048574 duración 78.0044 ms
umbral máximo: 2097152
resultado maxEvenDividing: 2097150 duración 111.0064ms
Resultado maxEvenDividing2: 2097150 duración 79.0045 ms
Resultado maxEvenConjunction: 2097150 duración 112.0064 ms
Resultado de maxEvenConjunction2: 2097150 duración 77.0044 ms
umbral máximo: 4194304
resultado maxEvenDividing: 4194302 duración 111.0063ms
Resultado maxEvenDividing2: 4194302 duración 78.0045 ms
Resultado maxEvenConjunction: 4194302 duración 111.0063 ms
Resultado de maxEvenConjunction2: 4194302 duración 77.0044 ms
umbral máximo: 8388608
resultado maxEvenDividing: 8388606 duración 109.0062ms
Resultado maxEvenDividing2: 8388606 duración 78.0045 ms
Resultado maxEvenConjunction: 8388606 duración 114.0065 ms
Resultado de maxEvenConjunction2: 8388606 duración 78.0045 ms
umbral máximo: 16777216
resultado maxEvenDividing: 16777214 duración 109.0062ms
Resultado maxEvenDividing2: 16777214 duración 77.0044 ms
Resultado maxEvenConjunction: 16777214 duración 109.0063 ms
Resultado de maxEvenConjunction2: 16777214 duración 77.0044 ms
umbral máximo: 33554432
resultado maxEvenDividing: 33554430 duración 113.0065ms
Resultado maxEvenDividing2: 33554430 duración 78.0045 ms
Resultado maxEvenConjunction: 33554430 duración 110.0063 ms
Resultado de maxEvenConjunction2: 33554430 duración 80.0045 ms
umbral máximo: 67108864
resultado maxEvenDividing: 67108860 duración 112.0064ms
Resultado maxEvenDividing2: 67108860 duración 77.0044 ms
Resultado maxEvenConjunction: 67108860 duración 112.0064 ms
Resultado de maxEvenConjunction2: 67108860 duración 80.0046 ms
umbral máximo: 134217728
resultado maxEvenDividing: 134217726 duración 109.0063ms
Resultado maxEvenDividing2: 134217726 duración 78.0044 ms
Resultado maxEvenConjunction: 134217726 duración 114.0065 ms
Resultado de maxEvenConjunction2: 134217726 duración 81.0047 ms
umbral máximo: 268435456
resultado maxEvenDividing: 268435446 duración 111.0064ms
Resultado maxEvenDividing2: 268435446 duración 79.0045 ms
Resultado maxEvenConjunction: 268435446 duración 114.0065 ms
Resultado de maxEvenConjunction2: 268435446 duración 79.0045 ms
umbral máximo: 536870912
resultado maxEvenDividing: 536870910 duración 107.0062ms
Resultado maxEvenDividing2: 536870910 duración 76.0043 ms
Resultado maxEvenConjunction: 536870910 duración 109.0062 ms
Resultado de maxEvenConjunction2: 536870910 duración 80.0046 ms
No pude encontrar una explicación clara de por qué el compilador de Go no optimiza el código y siempre verifica la segunda condición, incluso si la primera es falsa. ¿O tal vez mis ojos simplemente están borrosos y no veo ningún error obvio? ¿O necesita proporcionar algunas instrucciones especiales al compilador? Me encantaría recibir comentarios sensatos.
PS: Sí, solo por diversión, realicé pruebas similares en Java 5 y Java 7/8; todo está claro, el tiempo de ejecución es el mismo.
Fuente: habr.com