الخرائط

في Go، سعة الخريطة غير محدودة نظرياً، ولا يحدّها إلا الذاكرة المتاحة. ولهذا لا تنطبق الدالة المدمجة cap على الخرائط.

في تطبيق وقت التشغيل القياسي الرسمي لـ Go، تُطبَّق الخرائط داخلياً كجداول تجزئة (hashtables). ويحتفظ كل جدول تجزئة (خريطة) بمصفوفة داعمة (backing array) لتخزين مدخلات الخريطة (أزواج المفتاح-القيمة). وبإضافة المزيد والمزيد من المدخلات إلى خريطة، قد يُرى أن حجم المصفوفة الداعمة صغير جداً لتخزين مزيد من المدخلات، فتُخصَّص مصفوفة داعمة جديدة أكبر وتُنقل المدخلات الحالية (في المصفوفة الداعمة القديمة) إليها، ثم تُهمل المصفوفة الداعمة القديمة.

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

تفريغ مدخلات الخريطة

يمكننا استخدام الحلقة التالية لتفريغ جميع مدخلات خريطة:

	for key := range aMap {
		delete(aMap, key)
	}

الحلقة مُحسَّنة تحسيناً خاصاً (إلا إذا وُجدت مدخلات بمفاتيح NaN) بحيث يكون تنفيذها سريعاً جداً. ولكن لاحظ أنه، كما ذُكر أعلاه، لا تتقلّص المصفوفة الداعمة للخريطة المفرَّغة بعد الحلقة. فكيف نحرّر المصفوفة الداعمة للخريطة؟ هناك طريقتان:

	aMap = nil
	// أو
	aMap = make(map[K]V)

إذا لم تُشِر أي جهة أخرى إلى المصفوفة الداعمة للخريطة، فستُجمع المصفوفة الداعمة في النهاية بعد تحريرها.

إذا كانت ستُضاف مدخلات جديدة كثيرة إلى الخريطة بعد تفريغها، فتُفضَّل الطريقة الأولى؛ وإلا، فتُفضَّل الطريقة الثانية (طريقة التحرير).

منذ Go 1.21، توجد طريقة أفضل لإنجاز هذه المهمة. فقد قدّم Go 1.21 دالة مدمجة جديدة، clear، يمكن استخدامها لتفريغ جميع مدخلات خريطة، بما فيها المدخلات ذات المفاتيح NaN.

ملاحظة: حالياً (سلسلة أدوات Go 1.24)، يستغرق استخدام الدالة المدمجة clear لتفريغ خريطة فيها مدخل واحد على الأقل وقتاً يتناسب مع حجم المصفوفة الداعمة للخريطة.

aMap[key]++ أكثر كفاءة من aMap[key] = aMap[key] + 1

في الجملة aMap[key] = aMap[key] + 1، تُحسب تجزئة key مرتين، لكن في الجملة aMap[key]++، تُحسب تجزئته مرة واحدة فقط.

وبالمثل، aMap[key] += value أكثر كفاءة من aMap[key] = aMap[key] + value.

ويمكن إثبات ذلك بشيفرة قياس الأداء التالية:

package maps

import "testing"

var m = map[int]int{}

func Benchmark_increment(b *testing.B) {
	for i := 0; i < b.N; i++ {
		m[99]++
	}
}

func Benchmark_plusone(b *testing.B) {
	for i := 0; i < b.N; i++ {
		m[99] += 1
	}
}

func Benchmark_addition(b *testing.B) {
	for i := 0; i < b.N; i++ {
		m[99] = m[99] + 1
	}
}

نتائج قياس الأداء:

Benchmark_increment-4  11.31 ns/op
Benchmark_plusone-4    11.21 ns/op
Benchmark_addition-4   16.10 ns/op

المؤشرات في الخرائط

إذا لم يحتوي نوع مفتاح خريطة ونوع عناصرها على مؤشرات، فلن يفحص جامع النفايات مدخلات الخريطة في مرحلة المسح من دورة GC. وقد يوفّر هذا وقتاً كثيراً.

وتنطبق هذه النصيحة أيضاً على أنواع الحاويات الأخرى في Go، مثل الشرائح والمصفوفات والقنوات.

استخدام مصفوفات byte بدلاً من النصوص القصيرة كمفاتيح

يحتوي كل نص داخلياً على مؤشر يشير إلى البايتات الكامنة لذلك النص. لذا إذا كان نوع مفتاح خريطة أو نوع عناصرها نوع نص، فيجب فحص جميع مدخلات الخريطة في دورات GC.

إذا استطعنا ضمان أن لقيم النصوص المستخدمة في مدخلات خريطة طولاً أقصى، وأن هذا الطول الأقصى صغير، فيمكننا استخدام نوع المصفوفة [N]byte بدلاً من أنواع النصوص (حيث N هو الطول الأقصى للنص). وسيوفّر فعل ذلك وقتاً كثيراً من مسح جمع النفايات إذا كان عدد مدخلات الخريطة كبيراً جداً.

مثلاً، في الشيفرة التالية، لا تحتوي مدخلات mapB على مؤشرات، لكن مفاتيح mapA (النصية) تحتوي على مؤشرات. لذا سيتخطى جامع النفايات mapB في مرحلة المسح من دورة GC.

	var mapA = make(map[string]int, 1 << 16)
	var mapB = make(map[[32]byte]int, 1 << 16)

ولاحظ أن المصرِّف القياسي الرسمي يُجري تحسينات خاصة على تجزئة مفاتيح الخرائط التي أحجامها 4 أو 8 بايت. لذا، من وجهة نظر توفير CPU، من الأفضل استخدام map[[8]byte]V بدلاً من map[[5]byte]V، ومن الأفضل استخدام map[int32]V بدلاً من map[int16]V.

تقليل تكرار تعديل عناصر الخريطة

ذُكر في فصل «النصوص وشرائح البايت» السابق أن تحويل شريحة byte إلى نص يظهر كمفتاح فهرس في تعبير استرجاع عنصر خريطة لا يُجري تخصيصاً، لكن مثل هذه التحويلات في تعبيرات فهرس عنصر خريطة قيمة وجهة تُجري تخصيصات.

لذا يمكننا أحياناً تقليل تكرار استخدام مثل هذه التحويلات في تعبيرات فهرس عنصر خريطة قيمة وجهة لتحسين أداء البرنامج.

في المثال التالي، الطريقة B (طريقة العناصر المؤشرة) أعلى أداءً من الطريقة A. والسبب أن الطريقة B نادراً ما تعدّل قيم العناصر. فالعناصر في الطريقة B مؤشرات، وبمجرد إنشائها لا تتغير أبداً.

package maps

import "testing"

var wordCounterA = make(map[string]int)
var wordCounterB = make(map[string]*int)
var key = make([]byte, 64)

func IncA(w []byte) {
	wordCounterA[string(w)]++
}

func IncB(w []byte) {
	p := wordCounterB[string(w)]
	if p == nil {
		p = new(int)
		wordCounterB[string(w)] = p
	}
	*p++
}

func Benchmark_A(b *testing.B) {
	for i := 0; i < b.N; i++ {
		for i := range key {
			IncA(key[:i])
		}
	}
}

func Benchmark_B(b *testing.B) {
	for i := 0; i < b.N; i++ {
		for i := range key {
			IncB(key[:i])
		}
	}
}

نتائج قياس الأداء:

Benchmark_A-4  11600 ns/op  2336 B/op  62 allocs/op
Benchmark_B-4   1543 ns/op     0 B/op   0 allocs/op

رغم أن الطريقة B (طريقة العناصر المؤشرة) تستهلك CPU أقل، فإنها تنشئ مؤشرات كثيرة، ما يزيد عبء مسح المؤشرات في دورة GC. لكن الطريقة B أكثر كفاءة عموماً.

ويمكننا استخدام جدول عدّادات إضافي (شريحة) وجعل الخريطة تسجّل فهارس إلى الجدول، لتجنّب إجراء تخصيصات كثيرة وإنشاء مؤشرات كثيرة، كما توضّح الشيفرة التالية:

var wordIndexes = make(map[string]int)
var wordCounters []int

func IncC(w []byte) {
	if i, ok := wordIndexes[string(w)]; ok {
		wordCounters[i]++
	} else {
		wordIndexes[string(w)] = len(wordCounters)
		wordCounters = append(wordCounters, 1)
	}
}

func Benchmark_C(b *testing.B) {
	for i := 0; i < b.N; i++ {
		for i := range key {
			IncC(key[:i])
		}
	}
}

نتائج قياس الأداء:

Benchmark_A-4  11600 ns/op  2336 B/op  62 allocs/op
Benchmark_B-4   1543 ns/op     0 B/op   0 allocs/op
Benchmark_C-4   1609 ns/op     0 B/op   0 allocs/op

من منظور قصير المدى، تكاد الطريقة C تضاهي الطريقة B في الأداء، لكنها، لأنها تستخدم مؤشرات أقل بكثير، أكثر كفاءة فعلاً من الطريقة B من منظور طويل المدى.

لاحظ أن نتائج قياس الأداء أعلاه تُظهر أن الطريقتين الأخيرتين تُجريان صفر تخصيصات. وهذا غير صحيح في الواقع. فالأمر مجرد أن كل تشغيل من تشغيلي قياس الأداء الأخيرين يُجري أقل من تخصيص واحد في المتوسط، وقد قُطعت النتيجة إلى صفر. وهذا تصميم متعمَّد لتقارير قياس الأداء في الحزم القياسية.

حاول تنمية الخريطة في خطوة واحدة

إذا استطعنا التنبؤ بالعدد الأقصى للمدخلات التي ستُضاف إلى خريطة وقت كتابة الشيفرة، فينبغي إنشاء الخريطة بالدالة make وتمرير العدد الأقصى كمعطى size لنداء make، لتجنّب تنمية الخريطة على عدة خطوات لاحقاً.

استخدام جداول الفهارس بدلاً من الخرائط التي لا تملك أنواع مفاتيحها إلا مجموعة صغيرة من القيم الممكنة

يحب بعض المبرمجين استخدام خريطة بمفتاح منطقي لتقليل استخدام كتل شيفرة if-else المطوَّلة. مثلاً، الشيفرة التالية

	// داخل دالة ...
	var condition bool
	condition = evaluateCondition()
	...
	if condition {
		counter++
	} else {
		counter--
	}
	...
	if condition {
		f()
	} else {
		g()
	}
	...

يمكن استبدالها بـ

// خرائط على مستوى الحزمة.
var boolToInt = map[bool]int{true: 1, false: 0}
var boolToFunc = map[bool]func(){true: f, false: g}

	// داخل دالة ...
	var condition bool
	condition = evaluateCondition()
	...
	counter += boolToInt[condition]
	...
	boolToFunc[condition]()
	...

إذا كانت هناك كتل if-else متطابقة كثيرة مستخدمة في الشيفرة، فإن استخدام خرائط بمفاتيح منطقية سيقلّل كثيراً من الشيفرة المتكررة ويجعل الشيفرة تبدو أنظف بكثير. وهذا جيد عموماً في معظم حالات الاستخدام. ومع ذلك، اعتباراً من سلسلة أدوات Go v1.24.n، طريقة الخرائط ليست عالية الكفاءة من وجهة نظر أداء تنفيذ الشيفرة. وتُظهر قياسات الأداء التالية فروق الأداء.

package maps

import "testing"

//go:noiline
func f() {}

//go:noiline
func g() {}

func IfElse(x bool) func() {
	if x {
		return f
	} else {
		return g
	}
}

var m = map[bool]func() {true: f, false: g}
func MapSwitch(x bool) func() {
	return m[x]
}

func Benchmark_IfElse(b *testing.B) {
	for i := 0; i < b.N; i++ {
		IfElse(true)()
		IfElse(false)()
	}
}

func Benchmark_MapSwitch(b *testing.B) {
	for i := 0; i < b.N; i++ {
		MapSwitch(true)()
		MapSwitch(false)()
	}
}

نتائج قياس الأداء:

Benchmark_IfElse-4      4.155 ns/op
Benchmark_MapSwitch-4  47.46 ns/op

من نتائج قياس الأداء، يمكننا أن نستنتج أن طريقة كتل if-else أعلى أداءً بكثير من طريقة تبديل الخريطة.

في حالات الاستخدام التي تتطلب أداءً عالياً للشيفرة، يمكننا محاكاة خريطة بمفتاح منطقي باستخدام جدول فهارس لتقليل شيفرة if-else المتكررة، مع الحفاظ على بساطة طريقة تبديل الخريطة، بمساعدة دالة تحوّل المنطقي إلى عدد صحيح. وتُظهر قياسات الأداء التالية كيفية استخدام طريقة جدول الفهارس.

func b2i(b bool) (r int) {
	if b {
		r = 1
	}
	return
}

var boolMap = [2]func(){g, f}

func Benchmark_BoolMap(b *testing.B) {
	for i := 0; i < b.N; i++ {
		boolMap[b2i(true)]()
		boolMap[b2i(false)]()
	}
}

من الشيفرة أعلاه، يمكننا أن نجد أن استخدامات طريقة جدول الفهارس تكاد تكون بنظافة طريقة تبديل الخريطة، وإن كانت تحتاج إلى دالة b2i صغيرة إضافية. ومن نتائج قياس الأداء التالية، نعلم أن طريقة جدول الفهارس تضاهي طريقة كتل if-else في الأداء.

Benchmark_IfElse-4      4.155 ns/op
Benchmark_MapSwitch-4  47.46 ns/op
Benchmark_BoolMap-4     4.135 ns/op