Условия в Go и их странности

Как вы думаете, эквиваленты ли по производительности эти два варианта проверки условий внутри цикла?

		
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

Внятного обьяснения, почему компилятор Go не оптимизирует код и всегда проверяет второе условие, даже если первое ложно — я не нашел. А может у меня просто глаз «замылился» и я не вижу какой то очевидной ошибки? Или надо указывать какие то особенные инструкции компилятору? Был бы рад толковым комментариям.

PS: Да, для интереса, прогнал аналогичные тесты на Java 5 и Java 7/8 — все четко, время выполнения одинаковое.
@
18.03.2019 14:45 UTC
Первоисточник