Go conditions and their oddities

    Do you think these two options for checking conditions inside a loop are equivalent in performance?

    		
    if a > b && c*2 > d {
    	....
    }
    // и
    if a <= b  { 
      continue;
    }
    if c*2 > d {
     ....
    }
    

    It all started with a “warm-up for the brain”, it was necessary to give an example of an optimal search for an array of integers [-x .... x] of the largest even number. I was wondering how much higher performance would be if, to figure out an even number or not, use logical multiplication by 1.

    
    //у четных чисел последний бит всегда равен 0
    value & 1 == 0
    //vs классический метод
    value % 2 == 0
    

    My experience of programming on Go is not very large, just over a year and a half, I used it, though often, but for purely utilitarian purposes (well, maybe except for one project related to a highly loaded http service), so I started with it. Open GoLand and write a simple test

    
    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
    }
    

    We get a result that shows that the higher the threshold, the more often fluctuations in terms of performance appear.

    Compare
    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

    It is clear that in this case, for different thresholds we have different test data sets, the processor load (on my i5-2540M laptop) varies around 20..30%, the memory occupied by the application running from under GoLand averages about 813 MB - this is also affects the reliability of the result, you need to implement the preservation of test suites on disk and run all the tests for each threshold in isolation from each other.

    And thinking about how to implement all this at a minimal cost, I automatically correct the condition check

    		
    if value > current && value&1 == 0 {
    	current = value
    }
    

    on the

    		
    if value <= current {
            continue;
    }
    if value&1 == 0 {
    	current = value
    }
    

    I start the tests again ... and stop understanding something :) The

    time spent on execution starts to differ not by percent / percentage of a percent, but by 10..15% I quickly add 2 more tests:

    		
    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
    }
    

    I launch and get this picture:
    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 : 254 duration 77.0044ms
    maxEvenConjunction result: 510 duration 80.0045ms maxEvenConjunction result: 510 duration 80.0045ms maxEvenConjunction result: 510 duration 110.0063ms maximum result: 254 duration 110.0063ms
    maxEvenConjunction2 result: 254 duration 80.0046ms

    max threshold: 512 max



    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
    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
    maxEvenConjunction2 result: 4094 duration 78.0045ms

    max threshold:
    16384 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
    maxEvenDimal
    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 109.0062ms duration
    maxEvenConjunction2 of result: 32766 78.0045ms duration

    max threshold: 65536
    maxEvenDividing result: 65534 109.0062ms duration
    maxEvenDividing2 of result: 65534 75.0043ms duration
    maxEvenConjunction result: 65534 109.0063ms duration
    maxEvenConjunction2 of result: 65534 79.0045ms duration

    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.002unction duration 5.0024function
    5.0024function 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: 2,097,150 111.0064ms duration
    maxEvenDividing2 of result: 2,097,150 79.0045ms duration
    maxEvenConjunction of result: 2,097,150 112.0064ms duration
    maxEvenConjunction2 of result: 2,097,150 77.0044ms duration

    max threshold: 4194304
    maxEvenDividing result: 4,194,302 111.0063ms duration
    maxEvenDividing2 of result: 4,194,302 78.0045ms duration
    maxEvenConjunction of 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: 8,388,606 78.0045ms duration

    max threshold: 16777216
    maxEvenDividing result: 16,777,214 109.0062ms duration
    maxEvenDividing2 of result: 16777214 77.0044ms duration
    maxEvenConjunction of result: 16777214 109.0063ms duration
    maxEvenConjunction2 result: 16,777,214 77.0044ms duration

    max threshold: 33554432
    maxEvenDividing result: 33,554,430 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: 67,108,860 112.0064ms duration
    maxEvenConjunction2 of result: 67108860 80.0046ms duration

    max threshold: 134217728
    maxEvenDividing result: 134 217 726 109.0063ms duration
    maxEvenDividing2 of result: 134 217 726 78.0044ms duration
    maxEvenConjunction result: 134 217 726 114.0065ms duration
    maxEvenConjunction2 of result: 134 217 726 81.0047ms duration

    max threshold: 268 435 456
    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

    A clear explanation of why the Go compiler does not optimize the code and always checks the second condition, even if the first is false, I did not find. Or maybe my eye just “blurred” and I don’t see any obvious mistake? Or do you need to specify some special instructions to the compiler? I would be happy with sensible comments.

    PS: Yes, for fun, I ran similar tests on Java 5 and Java 7/8 - everything is clear, the execution time is the same.

    Also popular now: