Você acha que essas duas opções para testar condições dentro de um loop são equivalentes em desempenho?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Tudo começou com um “aquecimento cerebral”; tive que dar um exemplo de busca ótima pelo maior número par em um array de inteiros [-x....x]. Fiquei me perguntando quão melhor seria o desempenho se usasse a multiplicação lógica por 1 para descobrir se um número é par ou não.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Minha experiência de programação em Go não é muito extensa, pouco mais de um ano e meio, usei-o, embora com frequência, mas puramente para fins utilitários (bem, talvez exceto para um projeto relacionado a um serviço http de alta carga), então eu começou com isso. Abra o GoLand e escreva um teste simples
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
}
Obtemos um resultado que mostra que quanto maior o limite, mais frequentemente aparecem flutuações no desempenho.
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
É claro que neste caso, para diferentes limites temos diferentes conjuntos de dados de teste, a carga do processador (no meu laptop i5-2540M) varia em torno de 20..30%, a memória ocupada pelo aplicativo rodando do GoLand é em média cerca de 813 MB - isso também afeta a confiabilidade do resultado, você precisa salvar os casos de teste no disco e executar todos os testes para cada limite isoladamente uns dos outros.
E agora, pensando em como implementar tudo isso com custos mínimos, corrijo automaticamente a verificação da condição
if value > current && value&1 == 0 {
current = value
}
em
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Faço os testes novamente... e não consigo entender nada :)
O tempo gasto na execução começa a diferir não mais em porcentagens/frações de percentual, mas em 10 a 15%.Acrescento rapidamente mais 2 testes:
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
}
Eu corro e recebo esta foto:capacidade inicial da matriz: 100000000
limite máximo: 128
Resultado maxEvenDividing: 126 duração 116.0066ms
Resultado maxEvenDividing2: 126 duração 79.0045ms
Resultado maxEvenConjunction: 126 duração 114.0065ms
Resultado maxEvenConjunction2: 126 duração 83.0048ms
limite máximo: 256
Resultado maxEvenDividing: 254 duração 111.0063ms
Resultado maxEvenDividing2: 254 duração 77.0044ms
Resultado maxEvenConjunction: 254 duração 110.0063ms
Resultado maxEvenConjunction2: 254 duração 80.0046ms
limite máximo: 512
Resultado maxEvenDividing: 510 duração 114.0066ms
Resultado maxEvenDividing2: 510 duração 80.0045ms
Resultado maxEvenConjunction: 510 duração 110.0063ms
Resultado maxEvenConjunction2: 510 duração 80.0046ms
limite máximo: 1024
Resultado maxEvenDividing: 1022 duração 109.0063ms
Resultado maxEvenDividing2: 1022 duração 77.0044ms
Resultado maxEvenConjunction: 1022 duração 111.0063ms
Resultado maxEvenConjunction2: 1022 duração 81.0047ms
limite máximo: 2048
Resultado maxEvenDividing: 2046 duração 114.0065ms
Resultado maxEvenDividing2: 2046 duração 79.0045ms
Resultado maxEvenConjunction: 2046 duração 113.0065ms
Resultado maxEvenConjunction2: 2046 duração 81.0046ms
limite máximo: 4096
Resultado maxEvenDividing: 4094 duração 114.0065ms
Resultado maxEvenDividing2: 4094 duração 80.0046ms
Resultado maxEvenConjunction: 4094 duração 111.0063ms
Resultado maxEvenConjunction2: 4094 duração 78.0045ms
limite máximo: 8192
Resultado maxEvenDividing: 8190 duração 107.0062ms
Resultado maxEvenDividing2: 8190 duração 77.0044ms
Resultado maxEvenConjunction: 8190 duração 111.0063ms
Resultado maxEvenConjunction2: 8190 duração 77.0044ms
limite máximo: 16384
Resultado maxEvenDividing: 16382 duração 109.0063ms
Resultado maxEvenDividing2: 16382 duração 77.0044ms
Resultado maxEvenConjunction: 16382 duração 108.0062ms
Resultado maxEvenConjunction2: 16382 duração 77.0044ms
limite máximo: 32768
Resultado maxEvenDividing: 32766 duração 112.0064ms
Resultado maxEvenDividing2: 32766 duração 77.0044ms
Resultado maxEvenConjunction: 32766 duração 109.0062ms
Resultado maxEvenConjunction2: 32766 duração 78.0045ms
limite máximo: 65536
Resultado maxEvenDividing: 65534 duração 109.0062ms
Resultado maxEvenDividing2: 65534 duração 75.0043ms
Resultado maxEvenConjunction: 65534 duração 109.0063ms
Resultado maxEvenConjunction2: 65534 duração 79.0045ms
limite máximo: 131072
Resultado maxEvenDividing: 131070 duração 108.0061ms
Resultado maxEvenDividing2: 131070 duração 76.0044ms
Resultado maxEvenConjunction: 131070 duração 110.0063ms
Resultado maxEvenConjunction2: 131070 duração 80.0046ms
limite máximo: 262144
Resultado maxEvenDividing: 262142 duração 110.0063ms
Resultado maxEvenDividing2: 262142 duração 76.0044ms
Resultado maxEvenConjunction: 262142 duração 107.0061ms
Resultado maxEvenConjunction2: 262142 duração 78.0044ms
limite máximo: 524288
Resultado maxEvenDividing: 524286 duração 109.0062ms
Resultado maxEvenDividing2: 524286 duração 78.0045ms
Resultado maxEvenConjunction: 524286 duração 109.0062ms
Resultado maxEvenConjunction2: 524286 duração 80.0046ms
limite máximo: 1048576
Resultado maxEvenDividing: 1048574 duração 109.0063ms
Resultado maxEvenDividing2: 1048574 duração 80.0045ms
Resultado maxEvenConjunction: 1048574 duração 114.0066ms
Resultado maxEvenConjunction2: 1048574 duração 78.0044ms
limite máximo: 2097152
Resultado maxEvenDividing: 2097150 duração 111.0064ms
Resultado maxEvenDividing2: 2097150 duração 79.0045ms
Resultado maxEvenConjunction: 2097150 duração 112.0064ms
Resultado maxEvenConjunction2: 2097150 duração 77.0044ms
limite máximo: 4194304
Resultado maxEvenDividing: 4194302 duração 111.0063ms
Resultado maxEvenDividing2: 4194302 duração 78.0045ms
Resultado maxEvenConjunction: 4194302 duração 111.0063ms
Resultado maxEvenConjunction2: 4194302 duração 77.0044ms
limite máximo: 8388608
Resultado maxEvenDividing: 8388606 duração 109.0062ms
Resultado maxEvenDividing2: 8388606 duração 78.0045ms
Resultado maxEvenConjunction: 8388606 duração 114.0065ms
Resultado maxEvenConjunction2: 8388606 duração 78.0045ms
limite máximo: 16777216
Resultado maxEvenDividing: 16777214 duração 109.0062ms
Resultado maxEvenDividing2: 16777214 duração 77.0044ms
Resultado maxEvenConjunction: 16777214 duração 109.0063ms
Resultado maxEvenConjunction2: 16777214 duração 77.0044ms
limite máximo: 33554432
Resultado maxEvenDividing: 33554430 duração 113.0065ms
Resultado maxEvenDividing2: 33554430 duração 78.0045ms
Resultado maxEvenConjunction: 33554430 duração 110.0063ms
Resultado maxEvenConjunction2: 33554430 duração 80.0045ms
limite máximo: 67108864
Resultado maxEvenDividing: 67108860 duração 112.0064ms
Resultado maxEvenDividing2: 67108860 duração 77.0044ms
Resultado maxEvenConjunction: 67108860 duração 112.0064ms
Resultado maxEvenConjunction2: 67108860 duração 80.0046ms
limite máximo: 134217728
Resultado maxEvenDividing: 134217726 duração 109.0063ms
Resultado maxEvenDividing2: 134217726 duração 78.0044ms
Resultado maxEvenConjunction: 134217726 duração 114.0065ms
Resultado maxEvenConjunction2: 134217726 duração 81.0047ms
limite máximo: 268435456
Resultado maxEvenDividing: 268435446 duração 111.0064ms
Resultado maxEvenDividing2: 268435446 duração 79.0045ms
Resultado maxEvenConjunction: 268435446 duração 114.0065ms
Resultado maxEvenConjunction2: 268435446 duração 79.0045ms
limite máximo: 536870912
Resultado maxEvenDividing: 536870910 duração 107.0062ms
Resultado maxEvenDividing2: 536870910 duração 76.0043ms
Resultado maxEvenConjunction: 536870910 duração 109.0062ms
Resultado maxEvenConjunction2: 536870910 duração 80.0046ms
Não consegui encontrar uma explicação clara de por que o compilador Go não otimiza o código e sempre verifica a segunda condição, mesmo que a primeira seja falsa. Ou talvez meus olhos estejam embaçados e não vejo nenhum erro óbvio? Ou você precisa fornecer algumas instruções especiais ao compilador? Eu ficaria feliz em receber comentários sensatos.
PS: Sim, só por diversão, executei testes semelhantes em Java 5 e Java 7/8 - está tudo claro, o tempo de execução é o mesmo.
Fonte: habr.com