Bạn có nghĩ rằng hai tùy chọn này để kiểm tra các điều kiện bên trong một vòng lặp có hiệu suất tương đương nhau không?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Tất cả bắt đầu bằng việc “khởi động trí não”; tôi phải đưa ra một ví dụ về cách tìm kiếm tối ưu số chẵn lớn nhất trong mảng số nguyên [-x....x]. Tôi đang tự hỏi hiệu suất sẽ tốt hơn bao nhiêu nếu tôi sử dụng phép nhân logic với 1 để tìm hiểu xem một số có phải là số chẵn hay không.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Kinh nghiệm lập trình Go của tôi không sâu rộng lắm, chỉ hơn một năm rưỡi, tôi đã sử dụng nó, mặc dù thường xuyên, nhưng hoàn toàn vì mục đích thực dụng (à, có thể ngoại trừ một dự án liên quan đến dịch vụ http tải cao), vì vậy tôi bắt đầu với nó. Mở GoLand và viết một bài kiểm tra đơn giản
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
}
Chúng tôi nhận được một kết quả cho thấy rằng ngưỡng càng cao thì hiệu suất càng xuất hiện nhiều biến động.
So sánhmax 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
Rõ ràng là trong trường hợp này, đối với các ngưỡng khác nhau, chúng tôi có các bộ dữ liệu thử nghiệm khác nhau, tải bộ xử lý (trên máy tính xách tay i5-2540M của tôi) thay đổi khoảng 20..30%, trung bình bộ nhớ bị chiếm bởi ứng dụng chạy từ GoLand khoảng 813 MB - điều này cũng ảnh hưởng đến độ tin cậy của kết quả, bạn cần lưu các trường hợp kiểm thử vào đĩa và chạy tất cả các kiểm thử cho từng ngưỡng một cách tách biệt với nhau.
Và bây giờ, khi nghĩ về cách thực hiện tất cả những điều này với chi phí tối thiểu, tôi tự động sửa lỗi kiểm tra điều kiện
if value > current && value&1 == 0 {
current = value
}
trên
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Tôi chạy lại bài kiểm tra... và tôi không hiểu gì cả :)
Thời gian dành cho việc thực hiện bắt đầu không còn khác nhau theo tỷ lệ phần trăm/phân số của phần trăm mà là 10..15%.Tôi nhanh chóng thêm 2 bài kiểm tra nữa:
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
}
Tôi chạy nó và nhận được hình ảnh này:dung lượng mảng ban đầu: 100000000
ngưỡng tối đa: 128
Kết quả maxEvenDividing: 126 thời lượng 116.0066ms
Kết quả maxEvenDividing2: 126 thời lượng 79.0045ms
Kết quả maxEvenConjunction: 126 thời lượng 114.0065ms
Kết quả maxEvenConjunction2: 126 thời lượng 83.0048ms
ngưỡng tối đa: 256
Kết quả maxEvenDividing: 254 thời lượng 111.0063ms
Kết quả maxEvenDividing2: 254 thời lượng 77.0044ms
Kết quả maxEvenConjunction: 254 thời lượng 110.0063ms
Kết quả maxEvenConjunction2: 254 thời lượng 80.0046ms
ngưỡng tối đa: 512
Kết quả maxEvenDividing: 510 thời lượng 114.0066ms
Kết quả maxEvenDividing2: 510 thời lượng 80.0045ms
Kết quả maxEvenConjunction: 510 thời lượng 110.0063ms
Kết quả maxEvenConjunction2: 510 thời lượng 80.0046ms
ngưỡng tối đa: 1024
Kết quả maxEvenDividing: 1022 thời lượng 109.0063ms
Kết quả maxEvenDividing2: 1022 thời lượng 77.0044ms
Kết quả maxEvenConjunction: 1022 thời lượng 111.0063ms
Kết quả maxEvenConjunction2: 1022 thời lượng 81.0047ms
ngưỡng tối đa: 2048
Kết quả maxEvenDividing: 2046 thời lượng 114.0065ms
Kết quả maxEvenDividing2: 2046 thời lượng 79.0045ms
Kết quả maxEvenConjunction: 2046 thời lượng 113.0065ms
Kết quả maxEvenConjunction2: 2046 thời lượng 81.0046ms
ngưỡng tối đa: 4096
Kết quả maxEvenDividing: 4094 thời lượng 114.0065ms
Kết quả maxEvenDividing2: 4094 thời lượng 80.0046ms
Kết quả maxEvenConjunction: 4094 thời lượng 111.0063ms
Kết quả maxEvenConjunction2: 4094 thời lượng 78.0045ms
ngưỡng tối đa: 8192
Kết quả maxEvenDividing: 8190 thời lượng 107.0062ms
Kết quả maxEvenDividing2: 8190 thời lượng 77.0044ms
Kết quả maxEvenConjunction: 8190 thời lượng 111.0063ms
Kết quả maxEvenConjunction2: 8190 thời lượng 77.0044ms
ngưỡng tối đa: 16384
Kết quả maxEvenDividing: 16382 thời lượng 109.0063ms
Kết quả maxEvenDividing2: 16382 thời lượng 77.0044ms
Kết quả maxEvenConjunction: 16382 thời lượng 108.0062ms
Kết quả maxEvenConjunction2: 16382 thời lượng 77.0044ms
ngưỡng tối đa: 32768
Kết quả maxEvenDividing: 32766 thời lượng 112.0064ms
Kết quả maxEvenDividing2: 32766 thời lượng 77.0044ms
Kết quả maxEvenConjunction: 32766 thời lượng 109.0062ms
Kết quả maxEvenConjunction2: 32766 thời lượng 78.0045ms
ngưỡng tối đa: 65536
Kết quả maxEvenDividing: 65534 thời lượng 109.0062ms
Kết quả maxEvenDividing2: 65534 thời lượng 75.0043ms
Kết quả maxEvenConjunction: 65534 thời lượng 109.0063ms
Kết quả maxEvenConjunction2: 65534 thời lượng 79.0045ms
ngưỡng tối đa: 131072
Kết quả maxEvenDividing: 131070 thời lượng 108.0061ms
Kết quả maxEvenDividing2: 131070 thời lượng 76.0044ms
Kết quả maxEvenConjunction: 131070 thời lượng 110.0063ms
Kết quả maxEvenConjunction2: 131070 thời lượng 80.0046ms
ngưỡng tối đa: 262144
Kết quả maxEvenDividing: 262142 thời lượng 110.0063ms
Kết quả maxEvenDividing2: 262142 thời lượng 76.0044ms
Kết quả maxEvenConjunction: 262142 thời lượng 107.0061ms
Kết quả maxEvenConjunction2: 262142 thời lượng 78.0044ms
ngưỡng tối đa: 524288
Kết quả maxEvenDividing: 524286 thời lượng 109.0062ms
Kết quả maxEvenDividing2: 524286 thời lượng 78.0045ms
Kết quả maxEvenConjunction: 524286 thời lượng 109.0062ms
Kết quả maxEvenConjunction2: 524286 thời lượng 80.0046ms
ngưỡng tối đa: 1048576
Kết quả maxEvenDividing: 1048574 thời lượng 109.0063ms
Kết quả maxEvenDividing2: 1048574 thời lượng 80.0045ms
Kết quả maxEvenConjunction: 1048574 thời lượng 114.0066ms
Kết quả maxEvenConjunction2: 1048574 thời lượng 78.0044ms
ngưỡng tối đa: 2097152
Kết quả maxEvenDividing: 2097150 thời lượng 111.0064ms
Kết quả maxEvenDividing2: 2097150 thời lượng 79.0045ms
Kết quả maxEvenConjunction: 2097150 thời lượng 112.0064ms
Kết quả maxEvenConjunction2: 2097150 thời lượng 77.0044ms
ngưỡng tối đa: 4194304
Kết quả maxEvenDividing: 4194302 thời lượng 111.0063ms
Kết quả maxEvenDividing2: 4194302 thời lượng 78.0045ms
Kết quả maxEvenConjunction: 4194302 thời lượng 111.0063ms
Kết quả maxEvenConjunction2: 4194302 thời lượng 77.0044ms
ngưỡng tối đa: 8388608
Kết quả maxEvenDividing: 8388606 thời lượng 109.0062ms
Kết quả maxEvenDividing2: 8388606 thời lượng 78.0045ms
Kết quả maxEvenConjunction: 8388606 thời lượng 114.0065ms
Kết quả maxEvenConjunction2: 8388606 thời lượng 78.0045ms
ngưỡng tối đa: 16777216
Kết quả maxEvenDividing: 16777214 thời lượng 109.0062ms
Kết quả maxEvenDividing2: 16777214 thời lượng 77.0044ms
Kết quả maxEvenConjunction: 16777214 thời lượng 109.0063ms
Kết quả maxEvenConjunction2: 16777214 thời lượng 77.0044ms
ngưỡng tối đa: 33554432
Kết quả maxEvenDividing: 33554430 thời lượng 113.0065ms
Kết quả maxEvenDividing2: 33554430 thời lượng 78.0045ms
Kết quả maxEvenConjunction: 33554430 thời lượng 110.0063ms
Kết quả maxEvenConjunction2: 33554430 thời lượng 80.0045ms
ngưỡng tối đa: 67108864
Kết quả maxEvenDividing: 67108860 thời lượng 112.0064ms
Kết quả maxEvenDividing2: 67108860 thời lượng 77.0044ms
Kết quả maxEvenConjunction: 67108860 thời lượng 112.0064ms
Kết quả maxEvenConjunction2: 67108860 thời lượng 80.0046ms
ngưỡng tối đa: 134217728
Kết quả maxEvenDividing: 134217726 thời lượng 109.0063ms
Kết quả maxEvenDividing2: 134217726 thời lượng 78.0044ms
Kết quả maxEvenConjunction: 134217726 thời lượng 114.0065ms
Kết quả maxEvenConjunction2: 134217726 thời lượng 81.0047ms
ngưỡng tối đa: 268435456
Kết quả maxEvenDividing: 268435446 thời lượng 111.0064ms
Kết quả maxEvenDividing2: 268435446 thời lượng 79.0045ms
Kết quả maxEvenConjunction: 268435446 thời lượng 114.0065ms
Kết quả maxEvenConjunction2: 268435446 thời lượng 79.0045ms
ngưỡng tối đa: 536870912
Kết quả maxEvenDividing: 536870910 thời lượng 107.0062ms
Kết quả maxEvenDividing2: 536870910 thời lượng 76.0043ms
Kết quả maxEvenConjunction: 536870910 thời lượng 109.0062ms
Kết quả maxEvenConjunction2: 536870910 thời lượng 80.0046ms
Tôi không thể tìm thấy lời giải thích rõ ràng tại sao trình biên dịch Go không tối ưu hóa mã và luôn kiểm tra điều kiện thứ hai, ngay cả khi điều kiện đầu tiên sai. Hoặc có thể mắt tôi chỉ mờ và tôi không nhìn thấy lỗi nào rõ ràng? Hay bạn cần cung cấp một số hướng dẫn đặc biệt cho trình biên dịch? Tôi sẽ vui mừng cho ý kiến hợp lý.
PS: Có, chỉ để giải trí, tôi đã chạy thử nghiệm tương tự trên Java 5 và Java 7/8 - mọi thứ đều rõ ràng, thời gian thực hiện là như nhau.
Nguồn: www.habr.com