Baldintzak Go-n eta haien bitxikeriak

Begizta baten barruan baldintzak probatzeko bi aukera hauek errendimenduan baliokideak direla uste duzu?

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

Dena "garunaren beroketa" batekin hasi zen; zenbaki bikoiti handienaren bilaketa optimoaren adibide bat eman behar nuen [-x....x] zenbaki osoen multzo batean. Zenbaki bat bikoitia den ala ez jakiteko biderketa logikoa 1ez erabiliko balu zenbat errendimendu hobea izango litzatekeen galdetzen ari nintzen.

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

Go-n programatzen dudan esperientzia ez da oso zabala, urte eta erdi pasatxo, erabili nuen, nahiz eta askotan, baina helburu utilitarioetarako soilik (beno, agian karga handiko http zerbitzuarekin lotutako proiektu bat izan ezik), beraz horrekin hasi zen. Ireki GoLand eta idatzi proba sinple bat

package main
import (
	"fmt"
	"log"
	"math"
	"math/rand"
	"time"
)
const size = 100000000 //math.MaxInt32*2
type Result struct {
	Name     string
	Duration time.Duration
	Value    int32
}

func main() {
	log.Println("initial array capacity: " + fmt.Sprint(size))
	var maxValue int32
        // Будем варьировать диапазон чисел от минимального 
        // до максимального. Чем меньше диапазон, тем больше 
        // процессорного времени будет уходить на операцию 
        // сравнения текущего числа, с ранее найденным и наоборот
	for maxValue = 128; maxValue < math.MaxInt32/2+1; maxValue = maxValue * 2 {
		test(maxValue)
	}
}

func test(maxValue int32) {
	log.Println("max threshold: " + fmt.Sprint(maxValue))
	arr := make([]int32, size)
	for i := range arr {
		arr[i] = rand.Int31n(maxValue)
                // в тестовых данных нам нужны и отрицательные числа 
		sign := rand.Intn(2)
		if sign == 1 {
			arr[i] = -arr[i]
		}
	}

        // запускаем тест "деление с остатком"
	result := maxEvenDividing("maxEvenDividing", arr)
	log.Printf(result.Name+"t result: "+fmt.Sprint(result.Value)+"ttduration %s", result.Duration)

        // запускаем тест "конъюнкции"
	result = maxEvenConjunction("maxEvenConjunction", arr)
	log.Printf(result.Name+"t result: "+fmt.Sprint(result.Value)+"ttduration %s", result.Duration)
}

func maxEvenDividing(name string, arr []int32) Result {
	start := time.Now()
	var current int32 = math.MinInt32
	for _, value := range arr {
		if value > current && value%2 == 0 {
			current = value
		}
	}
	duration := time.Since(start)
	result := Result{name, duration, current}
	return result
}

func maxEvenConjunction(name string, arr []int32) Result {
	start := time.Now()
	var current int32 = math.MinInt32
	for _, value := range arr {
		if value > current && value&1 == 0 {
			current = value
		}
	}
	duration := time.Since(start)
	result := Result{name, duration, current}
	return result
}

Atalasea zenbat eta altuagoa izan, errendimenduaren gorabeherak maizago agertzen direla erakusten duen emaitza lortzen dugu.

konparatumax 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

Argi dago kasu honetan, atalase desberdinetarako proba-datu multzo desberdinak ditugula, prozesadorearen karga (nire i5-2540M ordenagailu eramangarrian) %20..30 inguruan aldatzen dela, GoLand-etik exekutatzen den aplikazioak okupatzen duen memoria batez bestekoa da. 813 MB inguru - honek emaitzaren fidagarritasunari ere eragiten dio, proba kasuak diskoan gorde behar dituzu eta atalase bakoitzeko proba guztiak elkarrengandik isolatuta exekutatu behar dituzu.

Eta orain, hau guztia kostu minimoekin nola inplementatu pentsatzen, automatikoki zuzentzen dut egoera egiaztatzea

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

on

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

Berriro probak egiten ditut... eta ezer ulertzeari uzten diot :)

Exekuzioan emandako denbora ez da ehuneko ehuneko/frakzioen arabera aldatzen, % 10..15 baizik eta 2 proba gehiago gehitzen ditut azkar:

		
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
}

Exekutatu eta argazki hau lortzen dut:hasierako array-ahalmena: 100000000

gehienezko atalasea: 128
maxEvenDividing emaitza: 126 iraupena 116.0066 ms
maxEvenDividing2 emaitza: 126 iraupena 79.0045 ms
maxEvenConjunction emaitza: 126 iraupena 114.0065 ms
maxEvenConjunction2 emaitza: 126 iraupena 83.0048 ms

gehienezko atalasea: 256
maxEvenDividing emaitza: 254 iraupena 111.0063 ms
maxEvenDividing2 emaitza: 254 iraupena 77.0044 ms
maxEvenConjunction emaitza: 254 iraupena 110.0063 ms
maxEvenConjunction2 emaitza: 254 iraupena 80.0046 ms

gehienezko atalasea: 512
maxEvenDividing emaitza: 510 iraupena 114.0066 ms
maxEvenDividing2 emaitza: 510 iraupena 80.0045 ms
maxEvenConjunction emaitza: 510 iraupena 110.0063 ms
maxEvenConjunction2 emaitza: 510 iraupena 80.0046 ms

gehienezko atalasea: 1024
maxEvenDividing emaitza: 1022 iraupena 109.0063 ms
maxEvenDividing2 emaitza: 1022 iraupena 77.0044 ms
maxEvenConjunction emaitza: 1022 iraupena 111.0063 ms
maxEvenConjunction2 emaitza: 1022 iraupena 81.0047 ms

gehienezko atalasea: 2048
maxEvenDividing emaitza: 2046 iraupena 114.0065 ms
maxEvenDividing2 emaitza: 2046 iraupena 79.0045 ms
maxEvenConjunction emaitza: 2046 iraupena 113.0065 ms
maxEvenConjunction2 emaitza: 2046 iraupena 81.0046 ms

gehienezko atalasea: 4096
maxEvenDividing emaitza: 4094 iraupena 114.0065 ms
maxEvenDividing2 emaitza: 4094 iraupena 80.0046 ms
maxEvenConjunction emaitza: 4094 iraupena 111.0063 ms
maxEvenConjunction2 emaitza: 4094 iraupena 78.0045 ms

gehienezko atalasea: 8192
maxEvenDividing emaitza: 8190 iraupena 107.0062 ms
maxEvenDividing2 emaitza: 8190 iraupena 77.0044 ms
maxEvenConjunction emaitza: 8190 iraupena 111.0063 ms
maxEvenConjunction2 emaitza: 8190 iraupena 77.0044 ms

gehienezko atalasea: 16384
maxEvenDividing emaitza: 16382 iraupena 109.0063 ms
maxEvenDividing2 emaitza: 16382 iraupena 77.0044 ms
maxEvenConjunction emaitza: 16382 iraupena 108.0062 ms
maxEvenConjunction2 emaitza: 16382 iraupena 77.0044 ms

gehienezko atalasea: 32768
maxEvenDividing emaitza: 32766 iraupena 112.0064 ms
maxEvenDividing2 emaitza: 32766 iraupena 77.0044 ms
maxEvenConjunction emaitza: 32766 iraupena 109.0062 ms
maxEvenConjunction2 emaitza: 32766 iraupena 78.0045 ms

gehienezko atalasea: 65536
maxEvenDividing emaitza: 65534 iraupena 109.0062 ms
maxEvenDividing2 emaitza: 65534 iraupena 75.0043 ms
maxEvenConjunction emaitza: 65534 iraupena 109.0063 ms
maxEvenConjunction2 emaitza: 65534 iraupena 79.0045 ms

gehienezko atalasea: 131072
maxEvenDividing emaitza: 131070 iraupena 108.0061 ms
maxEvenDividing2 emaitza: 131070 iraupena 76.0044 ms
maxEvenConjunction emaitza: 131070 iraupena 110.0063 ms
maxEvenConjunction2 emaitza: 131070 iraupena 80.0046 ms

gehienezko atalasea: 262144
maxEvenDividing emaitza: 262142 iraupena 110.0063 ms
maxEvenDividing2 emaitza: 262142 iraupena 76.0044 ms
maxEvenConjunction emaitza: 262142 iraupena 107.0061 ms
maxEvenConjunction2 emaitza: 262142 iraupena 78.0044 ms

gehienezko atalasea: 524288
maxEvenDividing emaitza: 524286 iraupena 109.0062 ms
maxEvenDividing2 emaitza: 524286 iraupena 78.0045 ms
maxEvenConjunction emaitza: 524286 iraupena 109.0062 ms
maxEvenConjunction2 emaitza: 524286 iraupena 80.0046 ms

gehienezko atalasea: 1048576
maxEvenDividing emaitza: 1048574 iraupena 109.0063 ms
maxEvenDividing2 emaitza: 1048574 iraupena 80.0045 ms
maxEvenConjunction emaitza: 1048574 iraupena 114.0066 ms
maxEvenConjunction2 emaitza: 1048574 iraupena 78.0044 ms

gehienezko atalasea: 2097152
maxEvenDividing emaitza: 2097150 iraupena 111.0064 ms
maxEvenDividing2 emaitza: 2097150 iraupena 79.0045 ms
maxEvenConjunction emaitza: 2097150 iraupena 112.0064 ms
maxEvenConjunction2 emaitza: 2097150 iraupena 77.0044 ms

gehienezko atalasea: 4194304
maxEvenDividing emaitza: 4194302 iraupena 111.0063 ms
maxEvenDividing2 emaitza: 4194302 iraupena 78.0045 ms
maxEvenConjunction emaitza: 4194302 iraupena 111.0063 ms
maxEvenConjunction2 emaitza: 4194302 iraupena 77.0044 ms

gehienezko atalasea: 8388608
maxEvenDividing emaitza: 8388606 iraupena 109.0062 ms
maxEvenDividing2 emaitza: 8388606 iraupena 78.0045 ms
maxEvenConjunction emaitza: 8388606 iraupena 114.0065 ms
maxEvenConjunction2 emaitza: 8388606 iraupena 78.0045 ms

gehienezko atalasea: 16777216
maxEvenDividing emaitza: 16777214 iraupena 109.0062 ms
maxEvenDividing2 emaitza: 16777214 iraupena 77.0044 ms
maxEvenConjunction emaitza: 16777214 iraupena 109.0063 ms
maxEvenConjunction2 emaitza: 16777214 iraupena 77.0044 ms

gehienezko atalasea: 33554432
maxEvenDividing emaitza: 33554430 iraupena 113.0065 ms
maxEvenDividing2 emaitza: 33554430 iraupena 78.0045 ms
maxEvenConjunction emaitza: 33554430 iraupena 110.0063 ms
maxEvenConjunction2 emaitza: 33554430 iraupena 80.0045 ms

gehienezko atalasea: 67108864
maxEvenDividing emaitza: 67108860 iraupena 112.0064 ms
maxEvenDividing2 emaitza: 67108860 iraupena 77.0044 ms
maxEvenConjunction emaitza: 67108860 iraupena 112.0064 ms
maxEvenConjunction2 emaitza: 67108860 iraupena 80.0046 ms

gehienezko atalasea: 134217728
maxEvenDividing emaitza: 134217726 iraupena 109.0063 ms
maxEvenDividing2 emaitza: 134217726 iraupena 78.0044 ms
maxEvenConjunction emaitza: 134217726 iraupena 114.0065 ms
maxEvenConjunction2 emaitza: 134217726 iraupena 81.0047 ms

gehienezko atalasea: 268435456
maxEvenDividing emaitza: 268435446 iraupena 111.0064 ms
maxEvenDividing2 emaitza: 268435446 iraupena 79.0045 ms
maxEvenConjunction emaitza: 268435446 iraupena 114.0065 ms
maxEvenConjunction2 emaitza: 268435446 iraupena 79.0045 ms

gehienezko atalasea: 536870912
maxEvenDividing emaitza: 536870910 iraupena 107.0062 ms
maxEvenDividing2 emaitza: 536870910 iraupena 76.0043 ms
maxEvenConjunction emaitza: 536870910 iraupena 109.0062 ms
maxEvenConjunction2 emaitza: 536870910 iraupena 80.0046 ms

Ezin izan dut azalpen argirik aurkitu Go konpilatzaileak ez duen kodea optimizatzen eta beti bigarren baldintza egiaztatzen duen, nahiz eta lehenengoa faltsua izan. Edo agian nire begiak lausotuta daude eta ez dut akats nabaririk ikusten? Edo konpilatzaileari argibide berezi batzuk eman behar dizkiozu? Pozik egongo nintzateke zentzuzko iruzkinak.

PS: Bai, ondo pasatzeko, antzeko probak egin nituen Java 5 eta Java 7/8-n - dena argi dago, exekuzio denbora berdina da.

Iturria: www.habr.com