Условия в 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 — все четко, время выполнения одинаковое.
    Поделиться публикацией

    Комментарии 39

      –1
      Есть этому внятное объяснение. Называется «приоритеты операторов».
        0
        Разве в Go не так?
        Logical AND (&&): Left to right
          0
          Посмотрите на "&" и "==".
            –3
            До выполнения && будут выполнены все операции с обеих его сторон так как их приоритет выше.
              0
              Ясно. Спасибо за объяснение
              • НЛО прилетело и опубликовало эту надпись здесь
                  0
                  Это в случае если операнд не выражение.
                  • НЛО прилетело и опубликовало эту надпись здесь
                    +2
                    Простите, я днище. Был не прав, всё так и есть
                    +2
                    Вы это серьезно?

                    То есть стандартное:
                    if(i<arr.length && arr[i]>0)
                    будет кидать исключения?
                • НЛО прилетело и опубликовало эту надпись здесь
                    0
                    Да, java например не вычисляет второе значение если первое ложно. Это меня и «погубило» в смысле и заставило написать эту заметку.
                    UPD: Поторопился я. Надо было прогнать на всем диапазоне тестов. Тоже есть разница. «Век живи, век учись»
                      0
                      Странно. Решил проверить: play.golang.org/p/fjXUB-4em4q
                      Выполняет только первую часть условия, вторая сразу отбрасывается.
                        0
                        go1.11.2 под win7 64
                    0
                    "if value > current && value&1 == 0 {"

                    А этот код точно делает то, что нужно?
                    Я про порядок операций. У "==" приоритет выше, чем у "&", есть такое мнение.

                    А вообще, код нужно тестировать. Хотя бы минимально, руками. Вы гоняете код, но не проверили правильность выдаваемого этим кодом результата ;)
                      +1
                      идею понял, поправил
                      if value > current && (value&1) == 0 {
                      if (value&1) == 0 {
                      и
                      if value > current && (value%2) == 0 {
                      if (value%2) == 0 {
                      

                      но увы все осталось
                      max threshold: 65536
                      maxEvenDividing result: 65534 duration 112.0064ms
                      maxEvenDividing2 result: 65534 duration 79.0045ms
                      maxEvenConjunction result: 65534 duration 109.0062ms
                      maxEvenConjunction2 result: 65534 duration 79.0046ms

                      max threshold: 131072
                      maxEvenDividing result: 131070 duration 110.0063ms
                      maxEvenDividing2 result: 131070 duration 77.0044ms
                      maxEvenConjunction result: 131070 duration 109.0062ms
                      maxEvenConjunction2 result: 131070 duration 82.0047ms

                    • НЛО прилетело и опубликовало эту надпись здесь
                        +1
                        Кто-то из основных разрабов Go писал: приоритет скорости компиляции, а не оптимизациям. Т.е. оптимизации тоже запиливаются, но не ценой скорости компиляции.
                          0
                          Тут речь не только об оптимизации. Если правая операция имеет побочные эффекты, то будет вообще разный результат.
                          upd: впрочем, вероятность такого сценария кажется крайне малой. Скорее всего дело в чём-то другом.
                        • НЛО прилетело и опубликовало эту надпись здесь
                          • НЛО прилетело и опубликовало эту надпись здесь
                              0
                              по 2 пункту — совершенно верно. Важно понять какое получается распределение чисел. Я давно хочу сравнить реализацию рандомайзера у go (пакет rand) и у пары реализаций в яве
                              0

                              То есть ветка с continue всегда будет быстрее и нужно стараться делать её основной? Тогда что насчет такого варианта?


                                  for _, value := range arr {
                                      if value <= current || value%2 == 1 {
                                          continue
                                      }
                                      current = value
                                  }

                              Он по идее должен быть так же быстр, как с двумя ифами.

                                0

                                Проверил, по скорости такой же, как с двумя ифами.

                                  0
                                  Да, так и есть.
                                +1
                                Я поэкспериментировал с вашим кодом. Получился любопытный результат.
                                go version go1.11.2 linux/amd64
                                Для начала, ваша изначальная версия:
                                Вывод
                                2019/03/18 16:09:47 initial array capacity: 100000000
                                2019/03/18 16:09:47 max threshold: 128
                                2019/03/18 16:09:51 maxEvenDividing result: 126 duration 89.412503ms
                                2019/03/18 16:09:52 maxEvenConjunction result: 126 duration 91.088461ms
                                2019/03/18 16:09:52 max threshold: 256
                                2019/03/18 16:09:57 maxEvenDividing result: 254 duration 89.081515ms
                                2019/03/18 16:09:57 maxEvenConjunction result: 254 duration 89.547376ms
                                2019/03/18 16:09:57 max threshold: 512
                                2019/03/18 16:10:02 maxEvenDividing result: 510 duration 88.149262ms
                                2019/03/18 16:10:02 maxEvenConjunction result: 510 duration 88.361855ms
                                2019/03/18 16:10:02 max threshold: 1024
                                2019/03/18 16:10:07 maxEvenDividing result: 1022 duration 91.8891ms
                                2019/03/18 16:10:07 maxEvenConjunction result: 1022 duration 89.751739ms
                                2019/03/18 16:10:07 max threshold: 2048
                                2019/03/18 16:10:11 maxEvenDividing result: 2046 duration 88.284615ms
                                2019/03/18 16:10:12 maxEvenConjunction result: 2046 duration 88.519161ms
                                2019/03/18 16:10:12 max threshold: 4096


                                Числа практически одинаковые. А теперь просто увеличим число тестов в два раза…
                                Вот так
                                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)
                                
                                        // запускаем тест "деление с остатком"
                                        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)
                                }


                                И получаем… в принципе то, что у вас в статье.
                                Вывод
                                2019/03/18 16:11:38 initial array capacity: 100000000
                                2019/03/18 16:11:38 max threshold: 128
                                2019/03/18 16:11:43 maxEvenDividing result: 126 duration 58.024607ms
                                2019/03/18 16:11:43 maxEvenConjunction result: 126 duration 89.166074ms
                                2019/03/18 16:11:43 maxEvenDividing result: 126 duration 59.46789ms
                                2019/03/18 16:11:43 maxEvenConjunction result: 126 duration 89.592731ms
                                2019/03/18 16:11:43 max threshold: 256
                                2019/03/18 16:11:48 maxEvenDividing result: 254 duration 55.982769ms
                                2019/03/18 16:11:48 maxEvenConjunction result: 254 duration 90.445492ms
                                2019/03/18 16:11:48 maxEvenDividing result: 254 duration 57.619549ms
                                2019/03/18 16:11:48 maxEvenConjunction result: 254 duration 86.687485ms
                                2019/03/18 16:11:48 max threshold: 512
                                2019/03/18 16:11:53 maxEvenDividing result: 510 duration 55.006077ms
                                2019/03/18 16:11:53 maxEvenConjunction result: 510 duration 84.614818ms
                                2019/03/18 16:11:53 maxEvenDividing result: 510 duration 55.419376ms
                                2019/03/18 16:11:53 maxEvenConjunction result: 510 duration 90.981786ms
                                2019/03/18 16:11:53 max threshold: 1024
                                2019/03/18 16:11:58 maxEvenDividing result: 1022 duration 54.55514ms
                                2019/03/18 16:11:58 maxEvenConjunction result: 1022 duration 87.052763ms
                                2019/03/18 16:11:58 maxEvenDividing result: 1022 duration 58.450258ms
                                2019/03/18 16:11:58 maxEvenConjunction result: 1022 duration 99.431524ms
                                2019/03/18 16:11:58 max threshold: 2048
                                2019/03/18 16:12:03 maxEvenDividing result: 2046 duration 55.037655ms
                                2019/03/18 16:12:03 maxEvenConjunction result: 2046 duration 87.676236ms
                                2019/03/18 16:12:03 maxEvenDividing result: 2046 duration 55.551481ms
                                2019/03/18 16:12:03 maxEvenConjunction result: 2046 duration 90.076374ms


                                Видимо происходит некая оптимизация, но что именно — не берусь сказать.
                                Но! Берем ваш изначальный пример и модифицируем его вот так:
                                Код
                                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)
                                
                                	// запускаем тест "деление с остатком через 2 if"
                                	result = maxEvenDividing2("maxEvenDividing2", 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 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
                                }
                                
                                


                                Т. е. оставляем 2 одинаковые функции, но во второй делаем 2 if'а. Результат интересный:
                                Вывод
                                2019/03/18 16:17:55 initial array capacity: 100000000
                                2019/03/18 16:17:55 max threshold: 128
                                2019/03/18 16:18:00 maxEvenDividing result: 126 duration 89.261734ms
                                2019/03/18 16:18:00 maxEvenDividing2 result: 126 duration 34.88396ms
                                2019/03/18 16:18:00 max threshold: 256
                                2019/03/18 16:18:05 maxEvenDividing result: 254 duration 88.500843ms
                                2019/03/18 16:18:05 maxEvenDividing2 result: 254 duration 33.392775ms
                                2019/03/18 16:18:05 max threshold: 512
                                2019/03/18 16:18:10 maxEvenDividing result: 510 duration 89.431299ms
                                2019/03/18 16:18:10 maxEvenDividing2 result: 510 duration 32.631082ms
                                2019/03/18 16:18:10 max threshold: 1024
                                2019/03/18 16:18:15 maxEvenDividing result: 1022 duration 88.952642ms
                                2019/03/18 16:18:15 maxEvenDividing2 result: 1022 duration 31.930767ms
                                2019/03/18 16:18:15 max threshold: 2048
                                2019/03/18 16:18:20 maxEvenDividing result: 2046 duration 88.147315ms
                                2019/03/18 16:18:20 maxEvenDividing2 result: 2046 duration 32.349729ms


                                Ок, ладно. Меняем во второй функции условие:
                                Заголовок спойлера
                                	for _, value := range arr {
                                		if value <= current || value%2 != 0 {
                                			continue
                                		}
                                		current = value
                                	}


                                Вывод
                                2019/03/18 16:22:33 initial array capacity: 100000000
                                2019/03/18 16:22:33 max threshold: 128
                                2019/03/18 16:22:38 maxEvenDividing result: 126 duration 89.277911ms
                                2019/03/18 16:22:38 maxEvenDividing2 result: 126 duration 35.701745ms
                                2019/03/18 16:22:38 max threshold: 256
                                2019/03/18 16:22:43 maxEvenDividing result: 254 duration 88.572809ms
                                2019/03/18 16:22:43 maxEvenDividing2 result: 254 duration 33.28079ms
                                2019/03/18 16:22:43 max threshold: 512
                                2019/03/18 16:22:47 maxEvenDividing result: 510 duration 91.273419ms
                                2019/03/18 16:22:47 maxEvenDividing2 result: 510 duration 34.338536ms
                                2019/03/18 16:22:47 max threshold: 1024
                                2019/03/18 16:22:52 maxEvenDividing result: 1022 duration 88.363171ms
                                2019/03/18 16:22:52 maxEvenDividing2 result: 1022 duration 34.153742ms
                                2019/03/18 16:22:52 max threshold: 2048
                                2019/03/18 16:22:58 maxEvenDividing result: 2046 duration 89.752329ms
                                2019/03/18 16:22:58 maxEvenDividing2 result: 2046 duration 32.016185ms


                                Ладно, а теперь — самое интересное :) Оставляем только maxEvenDividing:
                                Код
                                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 = maxEvenDividing("maxEvenDividing", 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
                                }
                                


                                Результаты примерно одинаковые для обоих вызовов:
                                Вывод
                                2019/03/18 16:26:35 initial array capacity: 100000000
                                2019/03/18 16:26:35 max threshold: 128
                                2019/03/18 16:26:40 maxEvenDividing result: 126 duration 89.268756ms
                                2019/03/18 16:26:40 maxEvenDividing result: 126 duration 90.170882ms
                                2019/03/18 16:26:40 max threshold: 256
                                2019/03/18 16:26:45 maxEvenDividing result: 254 duration 88.172275ms
                                2019/03/18 16:26:45 maxEvenDividing result: 254 duration 89.698248ms
                                2019/03/18 16:26:45 max threshold: 512
                                2019/03/18 16:26:50 maxEvenDividing result: 510 duration 87.865053ms
                                2019/03/18 16:26:50 maxEvenDividing result: 510 duration 89.035878ms
                                2019/03/18 16:26:50 max threshold: 1024
                                2019/03/18 16:26:55 maxEvenDividing result: 1022 duration 88.126932ms
                                2019/03/18 16:26:55 maxEvenDividing result: 1022 duration 89.817568ms
                                2019/03/18 16:26:55 max threshold: 2048
                                2019/03/18 16:27:00 maxEvenDividing result: 2046 duration 88.188604ms
                                2019/03/18 16:27:00 maxEvenDividing result: 2046 duration 89.596681ms


                                А теперь копируем функцию maxEvenDividing, без каких-либо изменений:
                                Код
                                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 = maxEvenDividing2("maxEvenDividing2", 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 maxEvenDividing2(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
                                }
                                


                                Иии…
                                Вывод
                                2019/03/18 16:30:02 initial array capacity: 100000000
                                2019/03/18 16:30:02 max threshold: 128
                                2019/03/18 16:30:07 maxEvenDividing result: 126 duration 89.38445ms
                                2019/03/18 16:30:07 maxEvenDividing2 result: 126 duration 59.310151ms
                                2019/03/18 16:30:07 max threshold: 256
                                2019/03/18 16:30:12 maxEvenDividing result: 254 duration 88.565655ms
                                2019/03/18 16:30:12 maxEvenDividing2 result: 254 duration 58.531543ms
                                2019/03/18 16:30:12 max threshold: 512
                                2019/03/18 16:30:17 maxEvenDividing result: 510 duration 89.049685ms
                                2019/03/18 16:30:17 maxEvenDividing2 result: 510 duration 57.656563ms
                                2019/03/18 16:30:17 max threshold: 1024
                                2019/03/18 16:30:22 maxEvenDividing result: 1022 duration 88.74683ms
                                2019/03/18 16:30:22 maxEvenDividing2 result: 1022 duration 57.928491ms
                                2019/03/18 16:30:22 max threshold: 2048
                                2019/03/18 16:30:27 maxEvenDividing result: 2046 duration 88.483885ms
                                2019/03/18 16:30:27 maxEvenDividing2 result: 2046 duration 55.760495ms



                                Короче говоря, проблема не в if'ах. Вообще не в них. Проблема в том, что Go непонятно как и непонятно что оптимизирует :)
                                  0
                                  Надо за памятью и CPU смотреть. Я поэтому и упомянул про следующий шаг — запуск всех тестов изолированно.

                                  Еще пример где много интересных цифр вылезает: массив для передачи в функцию например можно было обьявить так
                                  type numbers [size]int32
                                  ....
                                  var arr = new(numbers)

                                  там тоже много чего интересного можно накопать

                                  еще я смотрел на конкуренцию за ресурсы запуская горутины и отдавая результаты через каналы

                                  вот там просто поле непаханное для размышлений :)
                                  +2
                                  Такое ощущение, что мы видим работу предсказателя переходов CPU.
                                    +1
                                    Технически, эквивалент
                                    if value > current && value&1 == 0 {
                                    	current = value
                                    }

                                    Это
                                    if value > current {
                                        if  value&1 == 0 {
                                          current = value
                                       }
                                    }
                                    

                                    а не ваше

                                    if value <= current {
                                            continue;
                                    }
                                    if value&1 == 0 {
                                    	current = value
                                    }
                                      0
                                      В контексте кол-ва операций внутри цикла, я обычно в работе использую паттерн с continue. Такой код прилично легче читается спустя какое то время, да и вложенность со скобками меньше.
                                      Ну и как выяснили выше, разница все же есть
                                      +1
                                      Насколько я понимаю, тест можно было свести к такому виду: https://play.golang.org/p/zn-NaV8XE8k

                                      offtop
                                      Предлагаю вместо
                                      log.Println("initial array capacity: " + fmt.Sprint(size))

                                      log.Printf("initial array capacity: %d\n", size)

                                      Ну и вместо
                                      log.Printf(result.Name+"\t result: "+fmt.Sprint(result.Value)+"\t\tduration %s", result.Duration)

                                      log.Printf("%s\t result: %d\t\tduration %s\n", result.Name, result.Value, result.Duration)

                                        0
                                        Получаем результат, на котором видно, что тем больше threshold, тем все чаще появляются флуктуации по части производительности.

                                        Вообще не видно. И вообще не понятно, зачем вы тестируете на разных threshold, видно же что время от них почти не зависит. Это только уводит от поиска ответа

                                          0
                                          Так если бы я не перебирал бы эти пороги, я бы и не узнал бы, что время выполнения от них не сильно зависит. Это штатный рандомайзер вносит свою лепту. В этом примере, мы имеем равномерный закон распределения, но рандомайзер же можно взять и другой, да и пороги снизу и сверху тоже сделать несимметричными.
                                          UPD: и потом, мне было интересно сравнить реальное время вычисления например 16%2 и 1073741822%2
                                          +2

                                          А зачем такой сложный тест? Мне кажется было бы нагляднее, если упростить его до максимума. Тем более, что Golang предоставляет такой замечательный инструмент для тестирования из коробки.


                                          package main
                                          
                                          import (
                                              "testing"
                                              "time"
                                          )
                                          
                                          var val1 = 10
                                          var val2 = 1000
                                          
                                          func longComparison(val int) bool  {
                                              time.Sleep(100 * time.Millisecond)
                                              return true
                                          }
                                          
                                          func BenchmarkComplexIfDiv(b *testing.B) {
                                              for i := 0; i < b.N; i++ {
                                                  if val1 > val2 && val1%2 == 0 {
                                                  }
                                              }
                                          }
                                          
                                          func BenchmarkComplexIfConj(b *testing.B) {
                                              for i := 0; i < b.N; i++ {
                                                  if val1 > val2 && val1&1 == 0 {
                                                  }
                                              }
                                          }
                                          
                                          func BenchmarkComplexLong(b *testing.B) {
                                              for i := 0; i < b.N; i++ {
                                                  if val1 > val2 && longComparison(val1) {
                                                  }
                                              }
                                          }
                                          
                                          func BenchmarkTwoSimpleIf(b *testing.B) {
                                              for i := 0; i < b.N; i++ {
                                                  if val1 <= val2 {
                                                      continue
                                                  }
                                          
                                                  if val1%2 == 0 {
                                                  }
                                              }
                                          }
                                          
                                          // $ go test -bench .
                                          // BenchmarkComplexIfDiv-8      2000000000           0.85 ns/op
                                          // BenchmarkComplexIfConj-8     2000000000           0.85 ns/op
                                          // BenchmarkComplexLong-8       2000000000           0.57 ns/op
                                          // BenchmarkTwoSimpleIf-8       2000000000           0.58 ns/op

                                          Кстати, забавно, но BenchmarkComplexLong такой же быстрый как и вариант с continue

                                            0
                                            Что-то мне всегда казалось, что нормальный компилятор все эти пустые условия с пустыми циклами должен изничтожить под корень, кроме BenchmarkComplexLong
                                              +1
                                              Возможно он так и делает. В данном случае я больше хотел показать, что в Golang уже все необходимое для измерения производительности есть: golang.org/pkg/testing Так что нету необходимости придумывать велосипеды.
                                              0
                                              Опередил.

                                              Я вот тоже не понял зачем нужен этот велосипед, когда есть go test -bench.
                                                0

                                                Да не было цели изобрести велосипед, была цель проверить несколько предположений: скорость деления, равномерность распределения рандомайзера и тп. Я же не весь код показал, а только часть, которая вызвала вопросы.

                                                  0
                                                  go test -bench — и есть инструмент для проверки вопросов производительности кода/предположений о производительности.

                                                  Вот есть у меня функция, и кажется мне что можно сделать оптимальнее — пишу новую версию и два бенча (для старой и новой) и go test -bench мне четко говорит — прав я был или нет.
                                                  Если еще профилировщик подключить (test -bench -benchmem -cpuprofile cpu.out -memprofile mem.out), то там вам еще скажут «почему»/где именно тормозит/память жрет.

                                                  Так что не сами ваши эксперименты, но инструменты которые вы использовали для их проверки и есть самый настоящий велосипед с треугольными колесами. :)

                                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                            Самое читаемое