Да ли мислите да су ове две опције за тестирање услова унутар петље еквивалентне у перформансама?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Све је почело са „загревањем мозга“; морао сам да дам пример оптималне претраге највећег парног броја у низу целих бројева [-к....к]. Питао сам се колико би боље перформансе било када бих користио логичко множење са 1 да утврдим да ли је број паран или не.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Моје програмско искуство у Го-у није много, нешто више од годину и по дана, користио сам га, додуше често, али чисто у утилитарне сврхе (па, можда осим једног пројекта који се односи на хттп сервис високог оптерећења), па сам почео с тим. Отворите ГоЛанд и напишите једноставан тест
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
Јасно је да у овом случају, за различите прагове имамо различите скупове тестних података, оптерећење процесора (на мом и5-2540М лаптопу) варира око 20..30%, меморија коју заузима апликација која ради са ГоЛанд-а је у просеку око 813МБ - ово такође утиче на поузданост резултата, потребно је да сачувате тест случајеве на диску и да покренете све тестове за сваки праг изоловано један од другог.
И сада, размишљајући о томе како све ово имплементирати уз минималне трошкове, аутоматски исправљам проверу стања
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
макЕвенДивидинг резултат: 126 трајање 116.0066мс
макЕвенДивидинг2 резултат: 126 трајање 79.0045мс
макЕвенЦонњунцтион резултат: 126 трајање 114.0065мс
макЕвенЦоњунцтион2 резултат: 126 трајање 83.0048мс
максимални праг: 256
макЕвенДивидинг резултат: 254 трајање 111.0063мс
макЕвенДивидинг2 резултат: 254 трајање 77.0044мс
макЕвенЦонњунцтион резултат: 254 трајање 110.0063мс
макЕвенЦоњунцтион2 резултат: 254 трајање 80.0046мс
максимални праг: 512
макЕвенДивидинг резултат: 510 трајање 114.0066мс
макЕвенДивидинг2 резултат: 510 трајање 80.0045мс
макЕвенЦонњунцтион резултат: 510 трајање 110.0063мс
макЕвенЦоњунцтион2 резултат: 510 трајање 80.0046мс
максимални праг: 1024
макЕвенДивидинг резултат: 1022 трајање 109.0063мс
макЕвенДивидинг2 резултат: 1022 трајање 77.0044мс
макЕвенЦонњунцтион резултат: 1022 трајање 111.0063мс
макЕвенЦоњунцтион2 резултат: 1022 трајање 81.0047мс
максимални праг: 2048
макЕвенДивидинг резултат: 2046 трајање 114.0065мс
макЕвенДивидинг2 резултат: 2046 трајање 79.0045мс
макЕвенЦонњунцтион резултат: 2046 трајање 113.0065мс
макЕвенЦоњунцтион2 резултат: 2046 трајање 81.0046мс
максимални праг: 4096
макЕвенДивидинг резултат: 4094 трајање 114.0065мс
макЕвенДивидинг2 резултат: 4094 трајање 80.0046мс
макЕвенЦонњунцтион резултат: 4094 трајање 111.0063мс
макЕвенЦоњунцтион2 резултат: 4094 трајање 78.0045мс
максимални праг: 8192
макЕвенДивидинг резултат: 8190 трајање 107.0062мс
макЕвенДивидинг2 резултат: 8190 трајање 77.0044мс
макЕвенЦонњунцтион резултат: 8190 трајање 111.0063мс
макЕвенЦоњунцтион2 резултат: 8190 трајање 77.0044мс
максимални праг: 16384
макЕвенДивидинг резултат: 16382 трајање 109.0063мс
макЕвенДивидинг2 резултат: 16382 трајање 77.0044мс
макЕвенЦонњунцтион резултат: 16382 трајање 108.0062мс
макЕвенЦоњунцтион2 резултат: 16382 трајање 77.0044мс
максимални праг: 32768
макЕвенДивидинг резултат: 32766 трајање 112.0064мс
макЕвенДивидинг2 резултат: 32766 трајање 77.0044мс
макЕвенЦонњунцтион резултат: 32766 трајање 109.0062мс
макЕвенЦоњунцтион2 резултат: 32766 трајање 78.0045мс
максимални праг: 65536
макЕвенДивидинг резултат: 65534 трајање 109.0062мс
макЕвенДивидинг2 резултат: 65534 трајање 75.0043мс
макЕвенЦонњунцтион резултат: 65534 трајање 109.0063мс
макЕвенЦоњунцтион2 резултат: 65534 трајање 79.0045мс
максимални праг: 131072
макЕвенДивидинг резултат: 131070 трајање 108.0061мс
макЕвенДивидинг2 резултат: 131070 трајање 76.0044мс
макЕвенЦонњунцтион резултат: 131070 трајање 110.0063мс
макЕвенЦоњунцтион2 резултат: 131070 трајање 80.0046мс
максимални праг: 262144
макЕвенДивидинг резултат: 262142 трајање 110.0063мс
макЕвенДивидинг2 резултат: 262142 трајање 76.0044мс
макЕвенЦонњунцтион резултат: 262142 трајање 107.0061мс
макЕвенЦоњунцтион2 резултат: 262142 трајање 78.0044мс
максимални праг: 524288
макЕвенДивидинг резултат: 524286 трајање 109.0062мс
макЕвенДивидинг2 резултат: 524286 трајање 78.0045мс
макЕвенЦонњунцтион резултат: 524286 трајање 109.0062мс
макЕвенЦоњунцтион2 резултат: 524286 трајање 80.0046мс
максимални праг: 1048576
макЕвенДивидинг резултат: 1048574 трајање 109.0063мс
макЕвенДивидинг2 резултат: 1048574 трајање 80.0045мс
макЕвенЦонњунцтион резултат: 1048574 трајање 114.0066мс
макЕвенЦоњунцтион2 резултат: 1048574 трајање 78.0044мс
максимални праг: 2097152
макЕвенДивидинг резултат: 2097150 трајање 111.0064мс
макЕвенДивидинг2 резултат: 2097150 трајање 79.0045мс
макЕвенЦонњунцтион резултат: 2097150 трајање 112.0064мс
макЕвенЦоњунцтион2 резултат: 2097150 трајање 77.0044мс
максимални праг: 4194304
макЕвенДивидинг резултат: 4194302 трајање 111.0063мс
макЕвенДивидинг2 резултат: 4194302 трајање 78.0045мс
макЕвенЦонњунцтион резултат: 4194302 трајање 111.0063мс
макЕвенЦоњунцтион2 резултат: 4194302 трајање 77.0044мс
максимални праг: 8388608
макЕвенДивидинг резултат: 8388606 трајање 109.0062мс
макЕвенДивидинг2 резултат: 8388606 трајање 78.0045мс
макЕвенЦонњунцтион резултат: 8388606 трајање 114.0065мс
макЕвенЦоњунцтион2 резултат: 8388606 трајање 78.0045мс
максимални праг: 16777216
макЕвенДивидинг резултат: 16777214 трајање 109.0062мс
макЕвенДивидинг2 резултат: 16777214 трајање 77.0044мс
макЕвенЦонњунцтион резултат: 16777214 трајање 109.0063мс
макЕвенЦоњунцтион2 резултат: 16777214 трајање 77.0044мс
максимални праг: 33554432
макЕвенДивидинг резултат: 33554430 трајање 113.0065мс
макЕвенДивидинг2 резултат: 33554430 трајање 78.0045мс
макЕвенЦонњунцтион резултат: 33554430 трајање 110.0063мс
макЕвенЦоњунцтион2 резултат: 33554430 трајање 80.0045мс
максимални праг: 67108864
макЕвенДивидинг резултат: 67108860 трајање 112.0064мс
макЕвенДивидинг2 резултат: 67108860 трајање 77.0044мс
макЕвенЦонњунцтион резултат: 67108860 трајање 112.0064мс
макЕвенЦоњунцтион2 резултат: 67108860 трајање 80.0046мс
максимални праг: 134217728
макЕвенДивидинг резултат: 134217726 трајање 109.0063мс
макЕвенДивидинг2 резултат: 134217726 трајање 78.0044мс
макЕвенЦонњунцтион резултат: 134217726 трајање 114.0065мс
макЕвенЦоњунцтион2 резултат: 134217726 трајање 81.0047мс
максимални праг: 268435456
макЕвенДивидинг резултат: 268435446 трајање 111.0064мс
макЕвенДивидинг2 резултат: 268435446 трајање 79.0045мс
макЕвенЦонњунцтион резултат: 268435446 трајање 114.0065мс
макЕвенЦоњунцтион2 резултат: 268435446 трајање 79.0045мс
максимални праг: 536870912
макЕвенДивидинг резултат: 536870910 трајање 107.0062мс
макЕвенДивидинг2 резултат: 536870910 трајање 76.0043мс
макЕвенЦонњунцтион резултат: 536870910 трајање 109.0062мс
макЕвенЦоњунцтион2 резултат: 536870910 трајање 80.0046мс
Нисам могао да нађем јасно објашњење зашто Го компајлер не оптимизује код и увек проверава други услов, чак и ако је први нетачан. Или су ми можда очи само замагљене и не видим никакву очигледну грешку? Или треба да дате нека посебна упутства компајлеру? Било би ми драго за разумне коментаре.
ПС: Да, из забаве, радио сам сличне тестове на Јави 5 и Јави 7/8 - све је јасно, време извршења је исто.
Извор: ввв.хабр.цом