Comments 41
Logical AND (&&): Left to right
Выполняет только первую часть условия, вторая сразу отбрасывается.
"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 {
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
То есть ветка с 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 непонятно как и непонятно что оптимизирует :)
Еще пример где много интересных цифр вылезает: массив для передачи в функцию например можно было обьявить так
type numbers [size]int32
....
var arr = new(numbers)
там тоже много чего интересного можно накопать
еще я смотрел на конкуренцию за ресурсы запуская горутины и отдавая результаты через каналы
вот там просто поле непаханное для размышлений :)
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
}
Ну и как выяснили выше, разница все же есть
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
Я вот тоже не понял зачем нужен этот велосипед, когда есть go test -bench.
Да не было цели изобрести велосипед, была цель проверить несколько предположений: скорость деления, равномерность распределения рандомайзера и тп. Я же не весь код показал, а только часть, которая вызвала вопросы.
Вот есть у меня функция, и кажется мне что можно сделать оптимальнее — пишу новую версию и два бенча (для старой и новой) и go test -bench мне четко говорит — прав я был или нет.
Если еще профилировщик подключить (test -bench -benchmem -cpuprofile cpu.out -memprofile mem.out), то там вам еще скажут «почему»/где именно тормозит/память жрет.
Так что не сами ваши эксперименты, но инструменты которые вы использовали для их проверки и есть самый настоящий велосипед с треугольными колесами. :)
Условия в Go и их странности