BCE (إزالة فحص الحدود) | Go 101 بالعربية

Go لغة آمنة للذاكرة. ففي عمليات فهرسة عناصر المصفوفة/الشريحة/النص والعمليات الفرعية على الشرائح، سيتحقق وقت تشغيل Go مما إذا كانت الفهارس المعنية خارج النطاق أم لا. وإذا كان أحد الفهارس خارج النطاق، فسيُنشأ panic لمنع الفهرس غير الصالح من إحداث ضرر. ويسمى هذا فحص الحدود.

تجعل فحوص الحدود شيفرتنا تعمل بأمان، لكنها من ناحية أخرى تجعلها تعمل أبطأ قليلاً. وهذه مقايضة يجب أن تقبلها أي لغة آمنة.

منذ سلسلة أدوات Go v1.7، بدأ المصرِّف القياسي لـ Go يدعم BCE (إزالة فحص الحدود). ويستطيع BCE تجنّب بعض فحوص الحدود غير الضرورية، بحيث يستطيع المصرِّف القياسي لـ Go توليد برامج أكثر كفاءة.

وفيما يلي بعض الأمثلة التي توضّح الحالات التي يعمل فيها BCE والحالات التي لا يعمل فيها.

ويمكننا استخدام خيار المصرِّف -d=ssa/check_bce لإظهار أسطر الشيفرة التي تحتاج إلى فحوص حدود.

مثال 1

مثال بسيط:

// example1.go
package main

func f1a(s []struct{}, index int) {
	_ = s[index] // السطر 5: وُجد IsInBounds
	_ = s[index]
	_ = s[index:]
	_ = s[:index+1]
}

func f1b(s []byte, index int) {
	s[index-1] = 'a' // السطر 12: وُجد IsInBounds
	_ = s[:index]
}

func f1c(a [5]int) {
	_ = a[0]
	_ = a[4]
}

func f1d(s []int) {
	if len(s) > 2 {
	    _, _, _ = s[0], s[1], s[2]
	}
}

func f1g(s []int) {
	middle := len(s) / 2
	_ = s[:middle]
	_ = s[middle:]
}

func main() {}

لنشغّله مع خيار المصرِّف -d=ssa/check_bce:

$ go run -gcflags="-d=ssa/check_bce" example1.go
./example1.go:5:7: Found IsInBounds
./example1.go:12:3: Found IsInBounds

تُظهر المخرجات أن سطري شيفرة فقط يحتاجان إلى فحوص حدود في شيفرة المثال أعلاه.

لاحظ أن: سلاسل أدوات Go بإصدارات أقل من 1.21 فشلت في إزالة فحوص الحدود في الدالة f1g.

ولاحظ أنه حتى الآن (سلسلة أدوات Go v1.24.n)، لا يفحص المصرِّف القياسي الرسمي BCE لعملية في دالة عامة إذا كانت العملية تتضمن وسائط نوع ولم تُجسَّد الدالة العامة قط. مثلاً، لن يُبلّغ الأمر go run -gcflags=-d=ssa/check_bce bar.go عن أي شيء.

// bar.go
package bar

func foo[E any](s []E) {
	_ = s[0] // السطر 5
	_ = s[1] // السطر 6
	_ = s[2] // السطر 7
}

// var _ = foo[bool]

ومع ذلك، إذا فُعّل سطر تعريف المتغير، فسيُبلّغ المصرِّف عن:

./bar.go:5:7: Found IsInBounds
./bar.go:6:7: Found IsInBounds
./bar.go:7:7: Found IsInBounds
./bar.go:4:6: Found IsInBounds

مثال 2

تُزال جميع فحوص الحدود في عمليات فهرسة عناصر الشريحة والعمليات الفرعية على الشرائح الموضحة في المثال التالي.

// example2.go
package main

func f2a(s []int) {
	for i := range s {
		_ = s[i]
		_ = s[i:len(s)]
		_ = s[:i+1]
	}
}

func f2b(s []int) {
	for i := 0; i < len(s); i++ {
		_ = s[i]
		_ = s[i:len(s)]
		_ = s[:i+1]
	}
}

func f2c(s []int) {
	for i := len(s) - 1; i >= 0; i-- {
		_ = s[i]
		_ = s[i:len(s)]
		_ = s[:i+1]
	}
}

func f2d(s []int) {
	for i := len(s); i > 0; {
		i--
		_ = s[i]
		_ = s[i:len(s)]
		_ = s[:i+1]
	}
}

func f2e(s []int) {
	for i := 0; i < len(s) - 1; i += 2 {
		_ = s[i]
		_ = s[i:len(s)]
		_ = s[:i+1]
	}
}

func main() {}

إذا شغّلناه، سنجد أنه لا يُطبع أي شيء. نعم، المصرِّف القياسي الرسمي لـ Go ذكي جداً بحيث يجد أن جميع فحوص الحدود يمكن إزالتها في شيفرة المثال أعلاه.

$ go run -gcflags="-d=ssa/check_bce" example2.go

ملاحظة: قبل الإصدار 1.24، فشل المصرِّف القياسي لـ Go في إزالة فحوص الحدود في الحلقتين التاليتين.

func f2g(s []int) {
	for i := len(s) - 1; i >= 0; i-- {
		_ = s[:i+1]
	}
}

func f2h(s []int) {
	for i := 0; i <= len(s) - 1; i++ {
		_ = s[:i+1]
	}
}

مثال 3

ينبغي أن نحاول تقييم عملية فهرسة العنصر أو العملية الفرعية على الشريحة ذات أكبر فهرس في أقرب وقت ممكن لتقليل عدد فحوص الحدود.

في المثال التالي، إذا قُيّم التعبير s[3] دون حدوث panic، فيمكن إزالة فحوص الحدود الخاصة بـ s[0] وs[1] وs[2].

// example3.go
package main

func f3a(s []int32) int32 {
	return s[0] | // وُجد IsInBounds (السطر 5)
		s[1] | // وُجد IsInBounds
		s[2] | // وُجد IsInBounds
		s[3]   // وُجد IsInBounds
}

func f3b(s []int32) int32 {
	return s[3] | // وُجد IsInBounds (السطر 12)
		s[0] |
		s[1] |
		s[2]
}

func main() {
}

نشغّله، فنحصل على:

./example3.go:5:10: Found IsInBounds
./example3.go:6:4: Found IsInBounds
./example3.go:7:4: Found IsInBounds
./example3.go:8:4: Found IsInBounds
./example3.go:12:10: Found IsInBounds

من المخرجات، نعلم أن في الدالة f3a أربعة فحوص حدود، لكن في الدالة f3b فحصاً واحداً فقط.

مثال 4

منذ سلسلة أدوات Go v1.19، أُزيل فحص الحدود في الدالة f5a بنجاح،

func f5a(isa []int, isb []int) {
	if len(isa) > 0xFFF {
		for _, n := range isb {
			_ = isa[n & 0xFFF]
		}
	}
}

ومع ذلك، قبل سلسلة أدوات Go v1.19، لم يكن الفحص يُزال. وكانت المصرِّفات قبل الإصدار 1.19 تحتاج إلى تلميح لإزالته، كما هو موضح في الدالة f5b:

func f5b(isa []int, isb []int) {
	if len(isa) > 0xFFF {
		// تلميح ناجح (لمصرِّفات v1.18 وما قبلها)
		isa = isa[:0xFFF+1]
		for _, n := range isb {
			_ = isa[n & 0xFFF] // أُزيل فحص الحدود!
		}
	}
}

func f5c(isa []int, isb []int) {
	if len(isa) > 0xFFF {
		// تلميح غير فعّال (لمصرِّفات v1.18 وما قبلها)
		_ = isa[:0xFFF+1]
		for _, n := range isb {
			_ = isa[n & 0xFFF] // وُجد IsInBounds
		}
	}
}

func f5d(isa []int, isb []int) {
	if len(isa) > 0xFFF {
		// تلميح غير فعّال (لمصرِّفات v1.18 وما قبلها)
		_ = isa[0xFFF]
		for _, n := range isb {
			_ = isa[n & 0xFFF] // وُجد IsInBounds
		}
	}
}

يعرض القسم التالي حالات أخرى تحتاج إلى تلميحات المصرِّف لتجنّب بعض فحوص الحدود غير الضرورية.

مثال 5

قبل سلسلة أدوات Go v1.24، كانت هناك بعض فحوص الحدود غير الضرورية في الشيفرة التالية:

func fz(s, x, y []byte) {
	n := copy(s, x)
	copy(s[n:], y) // وُجد IsSliceInBounds (1.24-)
	_ = x[n:]      // وُجد IsSliceInBounds (1.24-)
}

func fy(a, b []byte) {
    for i := range min(len(a), len(b)) {
        _ = a[i] // وُجد IsInBounds (1.24-)
        _ = b[i] // وُجد IsInBounds (1.24-)
    }
}

func fx(a [256]byte) {
	for i := 0; i < 128; i++ {
		_ = a[2*i] // وُجد IsInBounds (1.24-)
	}
}

func f4a(is []int, bs []byte) {
	if len(is) >= 256 {
		for _, n := range bs {
			_ = is[n] // وُجد IsInBounds (1.24-)
		}
	}
}

ومنذ الإصدار 1.24، أُزيلت جميعها.

وقبل الإصدار 1.24، كان علينا إضافة سطر تلميح لإزالة فحص الحدود في الدالة f4a:

func f4a(is []int, bs []byte) {
	if len(is) >= 256 {
		is = is[:256] // تلميح ناجح
		for _, n := range bs {
			_ = is[n] // أُزيل فحص الحدود!
		}
	}
}

ومنذ الإصدار 1.24، أصبح سطر التلميح غير ضروري.

أحياناً، يحتاج المصرِّف إلى بعض التلميحات لإزالة بعض فحوص الحدود

لا يزال المصرِّف القياسي الرسمي لـ Go غير ذكي بما يكفي لإزالة جميع فحوص الحدود غير الضرورية. وأحياناً، يحتاج المصرِّف إلى إعطائه بعض التلميحات لإزالة بعض فحوص الحدود.

في المثال التالي، بإضافة كتلة شيفرة if زائدة في الدالة NumSameBytes_2، تُزال جميع فحوص الحدود في الحلقة.

type T = string

func NumSameBytes_1(x, y T) int {
	if len(x) > len(y) {
		x, y = y, x
	}
	for i := 0; i < len(x); i++ {
		if x[i] !=
			y[i] { // وُجد IsInBounds
			return i
		}
	}
	return len(x)
}

func NumSameBytes_2(x, y T) int {
	if len(x) > len(y) {
		x, y = y, x
	}

	// تلميح ناجح
	if len(x) > len(y) {
		panic("unreachable")
	}

	for i := 0; i < len(x); i++ {
		if x[i] != y[i] { // أُزيل فحص الحدود!
			return i
		}
	}
	return len(x)
}

يعمل التلميح أعلاه عندما يكون T نوع نص أو نوع شريحة، بينما يعمل كل من التلميحين التاليين لحالة واحدة فقط (اعتباراً من سلسلة أدوات Go v1.24.n).

func NumSameBytes_3(x, y T) int {
	if len(x) > len(y) {
		x, y = y, x
	}

	y = y[:len(x)] // تلميح، يعمل فقط إذا كان T نوع شريحة
	for i := 0; i < len(x); i++ {
		if x[i] != y[i] {
			return i
		}
	}
	return len(x)
}

func NumSameBytes_4(x, y T) int {
	if len(x) > len(y) {
		x, y = y, x
	}

	_ = y[:len(x)] // تلميح، يعمل فقط إذا كان T نوع نص
	for i := 0; i < len(x); i++ {
		if x[i] != y[i] {
			return i
		}
	}
	return len(x)
}

لاحظ أن الإصدارات المستقبلية من المصرِّف القياسي الرسمي لـ Go ستصبح أذكى بحيث تصبح التلميحات أعلاه غير ضرورية لاحقاً.

اكتب شيفرة صديقة لـ BCE

في المثال التالي، تُجري الدالتان f7b وf7c ثلاثة فحوص حدود أقل من f7a.

func f7a(s []byte, i int) {
	_ = s[i+3] // وُجد IsInBounds
	_ = s[i+2] // وُجد IsInBounds
	_ = s[i+1] // وُجد IsInBounds
	_ = s[i]   // وُجد IsInBounds
}

func f7b(s []byte, i int) {
	s = s[i:i+4] // وُجد IsSliceInBounds
	_ = s[3]
	_ = s[2]
	_ = s[1]
	_ = s[0]
}

func f7c(s []byte, i int) {
	s = s[i:i+4:i+4] // وُجد IsSliceInBounds
	_ = s[3]
	_ = s[2]
	_ = s[1]
	_ = s[0]
}

ومع ذلك، لاحظ أنه قد توجد بعض العوامل الأخرى التي تؤثر في أداء البرنامج. وعلى جهازي (Intel i5-4210U CPU @ 1.70GHz، Linux/amd64)، فإن الدالة f7b هي الأقل أداءً فعلاً بين الدوال الثلاث أعلاه.

Benchmark_f7a-4  3861 ns/op
Benchmark_f7b-4  4223 ns/op
Benchmark_f7c-4  3477 ns/op

عملياً، يُستحسن استخدام صيغة الشريحة الفرعية ثلاثية الفهارس (f7c).

في المثال التالي، تُظهر نتائج قياس الأداء أن

الدالة f8z هي الأعلى أداءً (كما هو متوقع)
لكن الدالة f8y تضاهي الدالة f8x في الأداء (وهو أمر غير متوقع).

func f8x(s []byte) {
	var n = len(s)
	s = s[:n]
	for i := 0; i <= n - 4; i += 4 {
		_ = s[i+3] // وُجد IsInBounds
		_ = s[i+2] // وُجد IsInBounds
		_ = s[i+1] // وُجد IsInBounds
		_ = s[i]
	}
}

func f8y(s []byte) {
	for i := 0; i <= len(s) - 4; i += 4 {
		s2 := s[i:]
		_ = s2[3] // وُجد IsInBounds
		_ = s2[2]
		_ = s2[1]
		_ = s2[0]
	}
}

func f8z(s []byte) {
	for i := 0; len(s) >= 4; i += 4 {
		_ = s[3]
		_ = s[2]
		_ = s[1]
		_ = s[0]
		s = s[4:]
	}
}

في الواقع، تُظهر نتائج قياس الأداء أيضاً أن الدالة f8y3 التالية تضاهي الدالة f8z في الأداء، وأن أداء الدالة f8y2 يوازي أداء الدالة f8y. لذا يُستحسن عملياً استخدام صيغ الشريحة الفرعية ثلاثية الفهارس في مثل هذه الحالات.

func f8y2(s []byte) {
	for i := 0; i < len(s) - 3; i += 4 {
		s2 := s[i:i+4] // وُجد IsInBounds
		_ = s2[3]
		_ = s2[2]
		_ = s2[1]
		_ = s2[0]
	}
}

func f8y3(s []byte) {
	for i := 0; i < len(s) - 3; i += 4 {
		s2 := s[i:i+4:i+4] // وُجد IsInBounds
		_ = s2[3]
		_ = s2[2]
		_ = s2[1]
		_ = s2[0]
	}
}

في المثال التالي، لا توجد فحوص حدود في الدالتين f9b وf9c، لكن يوجد فحص واحد في الدالة f9a.

func f9a(n int) []int {
	buf := make([]int, n+1)
	k := 0
	for i := 0; i <= n; i++ {
		buf[i] = k // وُجد IsInBounds
		k++
	}
	return buf
}

func f9b(n int) []int {
	buf := make([]int, n+1)
	k := 0
	for i := 0; i < len(buf); i++ {
		buf[i] = k
		k++
	}
	return buf
}

func f9c(n int) []int {
	buf := make([]int, n+1)
	k := 0
	for i := 0; i < n+1; i++ {
		buf[i] = k
		k++
	}
	return buf
}

في الشيفرة التالية، الدالة f6b أعلى أداءً من f6a، لكن كلتيهما أقل أداءً بكثير من f6c.

const N = 3

func f6a(s []byte) {
	for i := 0; i < len(s)-(N-1); i += N {
		_ = s[i+N-1] // وُجد IsInBounds
	}
}

func f6b(s []byte) {
	for i := N-1; i < len(s); i += N {
		_ = s[i] // وُجد IsInBounds
	}
}

func f6c(s []byte) {
	for i := uint(N-1); i < uint(len(s)); i += N {
		_ = s[i]
	}
}

كثيراً ما تكون الشرائح العامة (على مستوى الحزمة) غير صديقة لـ BCE، لذا ينبغي أن نحاول إسنادها إلى شرائح محلية لإزالة بعض فحوص الحدود غير الضرورية. مثلاً، في الشيفرة التالية، تُجري الدالة fa0 فحص حدود واحداً أكثر من الدالتين fa1 وfa2، لذا فإن نداءي الدالتين fa1() وfa2(s) أعلى أداءً من fa0().

var s = make([]int, 5)

func fa0() {
	for i := range s {
		s[i] = i // وُجد IsInBounds
	}
}

func fa1() {
	s := s
	for i := range s {
		s[i] = i
	}
}

func fa2(x []int) {
	for i := range x {
		x[i] = i
	}
}

كثيراً ما تكون المصفوفات أكثر ملاءمة لـ BCE من الشرائح. في الشيفرة التالية، لا تحتاج دالتا نسخة المصفوفة (fb2 وfc2) إلى فحوص حدود.

var s = make([]int, 256)
var a = [256]int{}

func fb1() int {
    return s[100] // وُجد IsInBounds
}

func fb2() int {
    return a[100]
}

func fc1(n byte) int {
    return s[n] // وُجد IsInBounds
}

func fc2(n byte) int {
    return a[n]
}

قبل سلسلة أدوات Go v1.24، كانت الدالة f0b في الشيفرة التالية أعلى أداءً بكثير من f0a، لأن في الدالة f0a بعض فحوص الحدود غير الضرورية. ومنذ سلسلة أدوات Go v1.24، أُزيلت جميع فحوص الحدود غير الضرورية في الدالة f0a، فتحسّن أداء الدالة f0a كثيراً (رغم أنها لا تزال أبطأ قليلاً من f0b).

func f0a(x [16]byte) (r [4]byte){
	for i := 0; i < 4; i++ {
		r[i] =
			x[i*4+3] ^
			x[i*4+2] ^
			x[i*4+1] ^
			x[i*4]
	}
	return
}

func f0b(x [16]byte) (r [4]byte){
	r[0] = x[3] ^ x[2] ^ x[1] ^ x[0]
	r[1] = x[7] ^ x[6] ^ x[5] ^ x[4]
	r[2] = x[11] ^ x[10] ^ x[9] ^ x[8]
	r[3] = x[15] ^ x[14] ^ x[13] ^ x[12]
	return
}

لاحظ أن الإصدارات المستقبلية من المصرِّف القياسي الرسمي لـ Go ستصبح أذكى بحيث قد تصبح شيفرة أكثر غير صديقة لـ BCE صديقة له لاحقاً.

المصرِّف القياسي الرسمي الحالي لـ Go يفشل في إزالة بعض فحوص الحدود غير الضرورية

اعتباراً من سلسلة أدوات Go v1.24.n، لا يزيل المصرِّف القياسي الرسمي لـ Go فحوص الحدود غير الضرورية التالية.

func fd(data []int, check func(int) bool) []int {
	var k = 0
	for _, v := range data {
		if check(v) {
			data[k] = v // وُجد IsInBounds
			k++
		}
	}
	return data[:k] // وُجد IsSliceInBounds
}

// بالنسبة إلى فحص الحدود الوحيد في الدالة التالية،
// * إذا كان N == 1، فسيُزال دائماً.
// * إذا كان N قوة للعدد 2، فتستطيع سلسلة أدوات Go 1.19+ إزالته.
// * في الحالات الأخرى، تفشل سلسلة أدوات Go في إزالته.
func fe(s []byte) {
	const N = 3
	if len(s) >= N {
		r := len(s) % N
		_ = s[r] // وُجد IsInBounds
	}
}

func ff(s []byte) {
	for i := 0; i < len(s); i++ {
		_ = s[i/2] // وُجد IsInBounds
		_ = s[i/3] // وُجد IsInBounds
	}
}

func fg(src, dst []byte) {
	dst = dst[:len(src)]
	for len(src) >= 4 {
		dst[1] = // وُجد IsInBounds
			src[0]
		dst[0] = src[1]
		src = src[4:]
		dst = dst[4:] // وُجد IsSliceInBounds
	}
}

ستصبح الإصدارات المستقبلية من المصرِّف القياسي الرسمي لـ Go أذكى بحيث تُزال فحوص الحدود غير الضرورية أعلاه لاحقاً.