Як ви вважаєте, чи еквіваленти за продуктивністю ці два варіанти перевірки умов усередині циклу?
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
}
Отримуємо результат, на якому видно, що тим більше threshold, тим все частіше з'являються флуктуації щодо продуктивності.
Порівняйте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
Зрозуміло, що в даному випадку, для різних threshold ми маємо різні набори тестових даних, завантаження процесора (на моєму ноутбуці i5-2540M) варіюється в районі 20...30%, пам'ять займається додатком запущеним з-під GoLand в середньому близько 813Мб - це теж Впливає на достовірність результату, потрібно реалізувати збереження тестових наборів на диску і прогнати всі тести для кожного трехhold ізольовано один від одного.
І ось роздумуючи над тим, як би з мінімальними витратами все це реалізувати, я машинально виправляю перевірку умови.
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
}
запускаю і отримую ось таку картинку:initial array capacity: 100000000
max threshold: 128
maxEvenDividing result: 126 тривалість 116.0066ms
maxEvenDividing2 result: 126 duration 79.0045ms
maxEvenConjunction result: 126 duration 114.0065ms
maxEvenConjunction2 result: 126 duration 83.0048ms
max threshold: 256
maxEvenDividing result: 254 тривалість 111.0063ms
maxEvenDividing2 result: 254 duration 77.0044ms
maxEvenConjunction result: 254 duration 110.0063ms
maxEvenConjunction2 result: 254 duration 80.0046ms
max threshold: 512
maxEvenDividing result: 510 тривалість 114.0066ms
maxEvenDividing2 result: 510 duration 80.0045ms
maxEvenConjunction result: 510 duration 110.0063ms
maxEvenConjunction2 result: 510 duration 80.0046ms
max threshold: 1024
maxEvenDividing result: 1022 тривалість 109.0063ms
maxEvenDividing2 result: 1022 duration 77.0044ms
maxEvenConjunction result: 1022 duration 111.0063ms
maxEvenConjunction2 result: 1022 duration 81.0047ms
max threshold: 2048
maxEvenDividing result: 2046 тривалість 114.0065ms
maxEvenDividing2 result: 2046 duration 79.0045ms
maxEvenConjunction result: 2046 duration 113.0065ms
maxEvenConjunction2 result: 2046 duration 81.0046ms
max threshold: 4096
maxEvenDividing result: 4094 тривалість 114.0065ms
maxEvenDividing2 result: 4094 duration 80.0046ms
maxEvenConjunction result: 4094 duration 111.0063ms
maxEvenConjunction2 result: 4094 duration 78.0045ms
max threshold: 8192
maxEvenDividing result: 8190 тривалість 107.0062ms
maxEvenDividing2 result: 8190 duration 77.0044ms
maxEvenConjunction result: 8190 duration 111.0063ms
maxEvenConjunction2 result: 8190 duration 77.0044ms
max threshold: 16384
maxEvenDividing result: 16382 тривалість 109.0063ms
maxEvenDividing2 result: 16382 duration 77.0044ms
maxEvenConjunction result: 16382 duration 108.0062ms
maxEvenConjunction2 result: 16382 duration 77.0044ms
max threshold: 32768
maxEvenDividing result: 32766 тривалість 112.0064ms
maxEvenDividing2 result: 32766 duration 77.0044ms
maxEvenConjunction result: 32766 duration 109.0062ms
maxEvenConjunction2 result: 32766 duration 78.0045ms
max threshold: 65536
maxEvenDividing result: 65534 тривалість 109.0062ms
maxEvenDividing2 result: 65534 duration 75.0043ms
maxEvenConjunction result: 65534 duration 109.0063ms
maxEvenConjunction2 result: 65534 duration 79.0045ms
max threshold: 131072
maxEvenDividing result: 131070 тривалість 108.0061ms
maxEvenDividing2 result: 131070 duration 76.0044ms
maxEvenConjunction result: 131070 duration 110.0063ms
maxEvenConjunction2 result: 131070 duration 80.0046ms
max threshold: 262144
maxEvenDividing result: 262142 тривалість 110.0063ms
maxEvenDividing2 result: 262142 duration 76.0044ms
maxEvenConjunction result: 262142 duration 107.0061ms
maxEvenConjunction2 result: 262142 duration 78.0044ms
max threshold: 524288
maxEvenDividing result: 524286 тривалість 109.0062ms
maxEvenDividing2 result: 524286 duration 78.0045ms
maxEvenConjunction result: 524286 duration 109.0062ms
maxEvenConjunction2 result: 524286 duration 80.0046ms
max threshold: 1048576
maxEvenDividing result: 1048574 тривалість 109.0063ms
maxEvenDividing2 result: 1048574 duration 80.0045ms
maxEvenConjunction result: 1048574 duration 114.0066ms
maxEvenConjunction2 result: 1048574 duration 78.0044ms
max threshold: 2097152
maxEvenDividing result: 2097150 тривалість 111.0064ms
maxEvenDividing2 result: 2097150 duration 79.0045ms
maxEvenConjunction result: 2097150 duration 112.0064ms
maxEvenConjunction2 result: 2097150 duration 77.0044ms
max threshold: 4194304
maxEvenDividing result: 4194302 тривалість 111.0063ms
maxEvenDividing2 result: 4194302 duration 78.0045ms
maxEvenConjunction result: 4194302 duration 111.0063ms
maxEvenConjunction2 result: 4194302 duration 77.0044ms
max threshold: 8388608
maxEvenDividing result: 8388606 тривалість 109.0062ms
maxEvenDividing2 result: 8388606 duration 78.0045ms
maxEvenConjunction result: 8388606 duration 114.0065ms
maxEvenConjunction2 result: 8388606 duration 78.0045ms
max threshold: 16777216
maxEvenDividing result: 16777214 тривалість 109.0062ms
maxEvenDividing2 result: 16777214 duration 77.0044ms
maxEvenConjunction result: 16777214 duration 109.0063ms
maxEvenConjunction2 result: 16777214 duration 77.0044ms
max threshold: 33554432
maxEvenDividing result: 33554430 тривалість 113.0065ms
maxEvenDividing2 result: 33554430 duration 78.0045ms
maxEvenConjunction result: 33554430 duration 110.0063ms
maxEvenConjunction2 result: 33554430 duration 80.0045ms
max threshold: 67108864
maxEvenDividing result: 67108860 тривалість 112.0064ms
maxEvenDividing2 result: 67108860 duration 77.0044ms
maxEvenConjunction result: 67108860 duration 112.0064ms
maxEvenConjunction2 result: 67108860 duration 80.0046ms
max threshold: 134217728
maxEvenDividing result: 134217726 тривалість 109.0063ms
maxEvenDividing2 result: 134217726 duration 78.0044ms
maxEvenConjunction result: 134217726 duration 114.0065ms
maxEvenConjunction2 result: 134217726 duration 81.0047ms
max threshold: 268435456
maxEvenDividing result: 268435446 тривалість 111.0064ms
maxEvenDividing2 result: 268435446 duration 79.0045ms
maxEvenConjunction result: 268435446 duration 114.0065ms
maxEvenConjunction2 result: 268435446 duration 79.0045ms
max threshold: 536870912
maxEvenDividing result: 536870910 тривалість 107.0062ms
maxEvenDividing2 result: 536870910 duration 76.0043ms
maxEvenConjunction result: 536870910 duration 109.0062ms
maxEvenConjunction2 result: 536870910 duration 80.0046ms
Виразного пояснення, чому компілятор Go не оптимізує код і завжди перевіряє другу умову, навіть якщо перша помилкова - я не знайшов. А може у мене просто око «замилилося» і я не бачу якоїсь очевидної помилки? Або треба вказувати якісь особливі інструкції компілятору? Був би радий тямущим коментарям.
PS: Так, для інтересу, прогнав аналогічні тести на Java 5 і Java 7/8 - все чітко, час виконання однаковий.
Джерело: habr.com