Смятате ли, че тези две опции за тестване на условията вътре в цикъл са еквивалентни по отношение на производителността?
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