Pull to refresh

Comments 41

Есть этому внятное объяснение. Называется «приоритеты операторов».
Разве в Go не так?
Logical AND (&&): Left to right
До выполнения && будут выполнены все операции с обеих его сторон так как их приоритет выше.
UFO just landed and posted this here
UFO just landed and posted this here
Вы это серьезно?

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

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

А вообще, код нужно тестировать. Хотя бы минимально, руками. Вы гоняете код, но не проверили правильность выдаваемого этим кодом результата ;)
идею понял, поправил
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

UFO just landed and posted this here
Кто-то из основных разрабов Go писал: приоритет скорости компиляции, а не оптимизациям. Т.е. оптимизации тоже запиливаются, но не ценой скорости компиляции.
Тут речь не только об оптимизации. Если правая операция имеет побочные эффекты, то будет вообще разный результат.
upd: впрочем, вероятность такого сценария кажется крайне малой. Скорее всего дело в чём-то другом.
UFO just landed and posted this here
UFO just landed and posted this here
по 2 пункту — совершенно верно. Важно понять какое получается распределение чисел. Я давно хочу сравнить реализацию рандомайзера у go (пакет rand) и у пары реализаций в яве

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


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

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

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

Я поэкспериментировал с вашим кодом. Получился любопытный результат.
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 непонятно как и непонятно что оптимизирует :)
Надо за памятью и CPU смотреть. Я поэтому и упомянул про следующий шаг — запуск всех тестов изолированно.

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

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

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

вот там просто поле непаханное для размышлений :)
Такое ощущение, что мы видим работу предсказателя переходов CPU.
Технически, эквивалент
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
}
Насколько я понимаю, тест можно было свести к такому виду: 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)

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

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

Так если бы я не перебирал бы эти пороги, я бы и не узнал бы, что время выполнения от них не сильно зависит. Это штатный рандомайзер вносит свою лепту. В этом примере, мы имеем равномерный закон распределения, но рандомайзер же можно взять и другой, да и пороги снизу и сверху тоже сделать несимметричными.
UPD: и потом, мне было интересно сравнить реальное время вычисления например 16%2 и 1073741822%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

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

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

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

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

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

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

Articles