المخصصات وأحواض الذاكرة

كل عقدة قائمة أو عقدة شجرة أو أمر ينشئه برنامج يأتي من مخصص والمخصص هو من يقرر عناوينها. يبعثر malloc العام الغرض الكائنات الصغيرة برؤوس وبالكائنات المؤقتة التي ينشئها البرنامج نفسه؛ أما الحوض فيرصّها. يضع هذا الدرس نموذجًا للاثنين ويعبر القائمة نفسها بإخفاقات ذاكرة مخبئية أقل بـ3.3 مرة من حوض.

حين يطلب برنامج ذاكرة لكائن يعطيه المخصص كتلة ويعيد العنوان. يجب على المخصص العام أن يتذكر حجم كل كتلة فيحتفظ بـرأس صغير أمامها ويقرّب الكتل إلى مضاعف 16 بايت ليتسع أي نوع من القيم. أبسط نموذج لذلك لا يعيد استعمال الذاكرة أبدًا: كل طلب يأخذ كتلة بعد السابقة مباشرة ويحصل البرنامج على العنوان الذي يلي الرأس مباشرة.

def round_up(n, align):    return -(-n // align) * aligndef malloc_addresses(sizes, header=HEADER_BYTES, align=ALIGN):    addresses = []    start = 0    for size in sizes:        addresses.append(start + header)1        start += round_up(size + header, align)    return addressesprint(malloc_addresses([24, 100, 24]))print([round_up(size + 16, 16) for size in (24, 100)])

[16, 64, 192]
[48, 128]

1. 1الكتلة هي الطلب زائد الرأس مقرّبًا إلى مضاعف 16: 24 بايت تحتاج كتلة من 48 بايت و100 بايت تحتاج 128.

تحصل عقدة من 24 بايت (إغلاق وحجم ومؤشر تالٍ 8 بايت لكل منها) على كتلة من 48 بايت أي ضعف حاجتها ويحصل كائن مؤقت من 100 بايت على 128. العناوين الثلاثة 16 و64 و192: يبدأ الطلب الثاني بعد كتلة الأول ذات 48 بايت ويبدأ الثالث بعد كتلة الثاني ذات 128 بايت.

لا تبني الشيفرة الحقيقية قائمة في الفراغ. بين عقدتين تنسّق رسالة أو تبني مفتاحًا أو تحلل سطرًا وهذه الكائنات المؤقتة تُخصَّص أيضًا. ومع مخصص بسيط لا يعيد استعمال الذاكرة أبدًا تجلس بين العقد. تبني الدالة الأولى أدناه خطة الطلبات: عقدة تليها ثلاثة كائنات مؤقتة من 100 بايت وتخدم الثانية الخطة وتحتفظ بعناوين العقد فقط. وللمقارنة نكتب أيضًا حوضًا يوزّع فتحات ثابتة واحدة بعد الأخرى مباشرة.

def alloc_plan(n_nodes, garbage_per_node, garbage_bytes, node_bytes):    sizes = []    node_index = []    for _ in range(n_nodes):        node_index.append(len(sizes))        sizes.append(node_bytes)        sizes.extend([garbage_bytes] * garbage_per_node)    return sizes, node_indexdef node_addresses(n_nodes, garbage_per_node, garbage_bytes, node_bytes):    sizes, node_index = alloc_plan(n_nodes, garbage_per_node, garbage_bytes, node_bytes)    addresses = malloc_addresses(sizes)    return [addresses[i] for i in node_index]def pool_addresses(n, slot_bytes, base=0):    return [base + i * slot_bytes for i in range(n)]print(node_addresses(3, 3, 100, 24))print(node_addresses(3, 0, 100, 24))print(pool_addresses(3, 24))

[16, 448, 880]
[16, 64, 112]
[0, 24, 48]

مع ثلاثة كائنات مؤقتة لكل عقدة تتباعد العقد 432 بايت: 48 للعقدة و3 × 128 للمهملات. وبلا مؤقتات تتباعد 48 بايت. وفي الحوض تتباعد 24 بايت أي حجم العقدة بالضبط بلا رأس ولا مهملات. يحوي سطر من 64 بايت عقدة واحدة مبعثرة و1.3 عقدة مع الرؤوس فقط و2.7 عقدة في الحوض. نعبر الآن 3000 عقدة نقرأ أول بايت وآخر بايت من كل منها عبر ذاكرة الموضوعات السابقة.

def traversal_misses(addresses, node_bytes):    cache = Cache()    for address in addresses:        cache.access(address)        cache.access(address + node_bytes - 1)    return cache.missesn = 3000for name, addresses in (("scattered", node_addresses(n, 3, 100, 24)), ("headers only", node_addresses(n, 0, 100, 24)), ("pool", pool_addresses(n, 24))):    print(name, traversal_misses(addresses, 24), "misses, last node at", addresses[-1] // 1024, "KB")

scattered 3750 misses, last node at 1265 KB
headers only 2250 misses, last node at 140 KB
pool 1125 misses, last node at 70 KB

تكلّف القائمة المبعثرة 3750 إخفاقًا وتمتد على 1265 كيلوبايت. أما الحوض الذي يحوي العقد الـ3000 نفسها فيكلّف 1125 إخفاقًا على 70 كيلوبايت: أقل بـ3.3 مرة وقد تتسع العقد حتى في ذاكرة مخبئية من المستوى الثاني. البرنامج والبيانات وترتيب العبور هي نفسها؛ تغيّرت العناوين فقط.

يتبع المختبر الدرس: التقريب والمخصص العام البسيط والحوض وخطة الطلبات مع المؤقتات وعناوين العقد وعدّ إخفاقات عبور والدراسة على قائمة أيام SPY.

• الدالة · السؤالتعتمد على
• round_up(n, align)كم يساوي n مقرّبًا إلى مضاعف؟حساب بسيط
• malloc_addresses(sizes)أين يضع المخصص العام كل كتلة؟round_up
• pool_addresses(n, slot_bytes)والحوض؟حساب بسيط
• alloc_plan(...)ما الطلبات التي يجريها البرنامج؟حساب بسيط
• node_addresses(...)أين ينتهي المطاف بالعقد؟alloc_planmalloc_addresses
• traversal_misses(addresses, node_bytes)كم إخفاقًا يكلّف عبور؟Cache
• study(bars)كم يوفّر الحوض في قائمة SPY؟node_addressespool_addressestraversal_misses

الموضوع التالي: جاءت كل كلفة حتى الآن من الذاكرة. وآخر أثر عتادي في هذه المهارة يأتي من تخمينات المعالج. في التنبؤ بالتفرعات تنمذج متنبئًا وتعدّ أخطاءه في حلقة فيها if وترى لماذا تكون الحلقة نفسها أسرع على بيانات مرتبة.