Как вы думаете, эквиваленты ли по производительности эти два варианта проверки условий внутри цикла?
Все началось с «разминки для мозгов», надо было привести пример оптимального поиска по массиву целых чисел [-x....x] наибольшего четного числа. Мне стало интересно, насколько будет выше производительность, если для выяснения четное число или нет, использовать логическое умножение на 1.
Мой опыт программирования на Go не очень большой, чуть более полутора лет, использовал я его хоть и часто, но чисто в утилитарных целях (ну может быть кроме одного проекта связанного с высоконагруженным http сервисом), поэтому начал я именно с него. Открываем GoLand и пишем простенький тест
Получаем результат, на котором видно, что тем больше threshold, тем все чаще появляются флуктуации по части производительности.
Понятно, что в данном случае, для разных threshold мы имеем разные наборы тестовых данных, загрузка процессора (на моем ноутбуке i5-2540M) варьируется в районе 20..30%, память занимаемая приложением запущенным из под GoLand в среднем около 813Мб — это тоже влияет на достоверность результата, нужно реализовать сохранение тестовых наборов на диске и прогнать все тесты для каждого threshold изолировано друг от друга.
И вот раздумывая над тем как бы с минимальными затратами все это реализовать, я машинально исправляю проверку условия
на
запускаю тесты еще раз… и перестаю что либо понимать :)
Время затрачиваемое на выполнение начинает отличаться уже не на проценты/доли процента, а на 10..15% Быстро дописываю еще 2 теста:
Внятного обьяснения, почему компилятор Go не оптимизирует код и всегда проверяет второе условие, даже если первое ложно — я не нашел. А может у меня просто глаз «замылился» и я не вижу какой то очевидной ошибки? Или надо указывать какие то особенные инструкции компилятору? Был бы рад толковым комментариям.
PS: Да, для интереса, прогнал аналогичные тесты на Java 5 и Java 7/8 — все четко, время выполнения одинаковое.
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)+"\t\tduration %s", result.Duration)
// запускаем тест "конъюнкции"
result = maxEvenConjunction("maxEvenConjunction", arr)
log.Printf(result.Name+"\t result: "+fmt.Sprint(result.Value)+"\t\tduration %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Мб — это тоже влияет на достоверность результата, нужно реализовать сохранение тестовых наборов на диске и прогнать все тесты для каждого threshold изолировано друг от друга.
И вот раздумывая над тем как бы с минимальными затратами все это реализовать, я машинально исправляю проверку условия
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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 107.0062ms
maxEvenDividing2 result: 536870910 duration 76.0043ms
maxEvenConjunction result: 536870910 duration 109.0062ms
maxEvenConjunction2 result: 536870910 duration 80.0046ms
max threshold: 128
maxEvenDividing result: 126 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 duration 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 — все четко, время выполнения одинаковое.