المحلية الزمنية ومجموعات العمل

لا تفيد الذاكرة المخبئية إلا في البيانات التي تعيد قراءتها، والمهم هو مدى سرعة ذلك. يقيس هذا الدرس ذلك برقم واحد هو مسافة إعادة الاستعمال ويستعمله للتنبؤ دفعة واحدة بمعدل الإصابة لكل أحجام الذاكرة المخبئية بما فيها الهاوية التي تكون فيها حلقة أكبر قليلًا من أن تتسع.

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

قراءة السطر 5 مرتين متتاليتين تعطي مسافة 0. وفي المتتالية 1، 2، 3، 1 تكون مسافة آخر قراءة 2 لأن السطرين 2 و3 جاءا بينهما. وقراءة السطر 2 عشر مرات بين قراءتين للسطر 1 تُحسب سطرًا واحدًا فقط. يحتفظ الكود بقائمة للأسطر بترتيب آخر استعمال لها، الأحدث في النهاية. وحين يعود سطر تكون الأسطر التي بعده في القائمة هي بالضبط ما استُعمل منذئذٍ.

def reuse_distances(lines):    stack = []    out = []    for line in lines:        if line in stack:            position = stack.index(line)            out.append(len(stack) - 1 - position)1            stack.pop(position)        else:            out.append(None)        stack.append(line)    return outprint(reuse_distances([1, 2, 3, 1, 2, 1, 1]))

[None, None, None, 2, 2, 1, 0]

1. 1الأسطر التي تلي هذا السطر في القائمة هي بالضبط الأسطر المستعملة منذ آخر قراءة له: عددها هو المسافة.

هذه هي الحقيقة المفيدة. خذ ذاكرة مخبئية تحمل C سطرًا وتطرد الأقل استعمالًا مؤخرًا أيًّا كانت أرقام الأسطر. تحتفظ في كل لحظة بالأسطر C المختلفة الأحدث استعمالًا. وتُصيب القراءة تمامًا حين يكون سطرها بينها أي حين قُرئ أقل من C سطرًا مختلفًا منذ آخر استعمال له. بعبارة أخرى تُصيب القراءة حين تكون مسافة إعادة استعمالها أقل من C.

يتحقق الكود أدناه من الادعاء. يحاكي ذاكرة LRU لسعات من 1 إلى 4 ويحسب أيضًا معدل الإصابة من المسافات وحدها دون أي ذاكرة مخبئية. يتطابق العمودان. تُحسب المسافات مرة واحدة ثم تعطي معدل الإصابة لكل حجم.

def lru_hit_rate(lines, capacity):    cache = []    hits = 0    for line in lines:        if line in cache:            hits += 1            cache.remove(line)        elif len(cache) >= capacity:            cache.pop(0)        cache.append(line)    return hits / len(lines)def hit_rate_from_distances(distances, capacity):    hits = sum(1 for d in distances if d is not None and d < capacity)    return hits / len(distances)lines = [1, 2, 3, 1, 2, 3, 4, 1, 2, 3]d = reuse_distances(lines)for capacity in (1, 2, 3, 4):    print(capacity, "lines:", round(lru_hit_rate(lines, capacity), 3), round(hit_rate_from_distances(d, capacity), 3))1

1 lines: 0.0 0.0
2 lines: 0.0 0.0
3 lines: 0.3 0.3
4 lines: 0.6 0.6

1. 1الأرقام نفسها في العمودين: المسافات وحدها تتنبأ بمعدل الإصابة لكل حجم ذاكرة مخبئية.

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

def sweep_lines(n_lines, passes):    return list(range(n_lines)) * passeslines = sweep_lines(48, 3)for capacity in (16, 32, 47, 48):    print(capacity, "lines:", round(lru_hit_rate(lines, capacity), 3))

16 lines: 0.0
32 lines: 0.0
47 lines: 0.0
48 lines: 0.667

المتوسط المتحرك المحسوب بالطريقة البطيئة يقرأ آخر 20 قيمة كل يوم: أي يعيد قراءة 19 من القيم العشرين التي قرأها بالأمس. هذا برنامج ذو محلية زمنية كبيرة. يبني الكود العناوين المقروءة لأول 600 إغلاق ويحوّلها إلى أسطر ويقيس المسافات ومعدل الإصابة لأربعة أحجام ومجموعة عمل 20 قراءة متتالية.

def rolling_mean_trace(n, window, elem_bytes):    trace = []    for end in range(window - 1, n):        for position in range(end - window + 1, end + 1):            trace.append(position * elem_bytes)    return tracedef working_set(lines, window):    return max(len(set(lines[i:i + window])) for i in range(len(lines) - window + 1))lines = [address // 64 for address in rolling_mean_trace(600, 20, 8)]d = reuse_distances(lines)print(len(lines), "reads from", len(set(lines)), "lines")for capacity in (1, 2, 4, 8):    print(capacity, "lines:", round(hit_rate_from_distances(d, capacity), 3))print("working set of 20 reads:", working_set(lines, 20), "lines")

11620 reads from 75 lines
1 lines: 0.831
2 lines: 0.831
4 lines: 0.994
8 lines: 0.994
working set of 20 reads: 4 lines

يكفي سطر واحد لـ83% من القراءات لأن القيمة التالية في المصفوفة موجودة في السطر الذي قُرئ للتو. وأربعة أسطر تبلغ 99.4%. لا تحتاج الأسطر الخمسة والسبعون لمجموعة البيانات كلها إلى الاتساع: مجموعة عمل 20 قراءة 4 أسطر فقط فتكفي ذاكرة مخبئية صغيرة جدًا. هذا هو الفرق بين حجم البيانات وحجم مجموعة العمل.

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

• الدالة · السؤالتعتمد على
• reuse_distances(lines)بعد كم تُعاد قراءة كل سطر؟قائمة بترتيب آخر استعمال
• lru_hit_rate(lines, capacity)كم تصيب ذاكرة LRU محاكاة؟أسطر بترتيب LRU
• hit_rate_from_distances(distances, capacity)معدل الإصابة نفسه دون ذاكرة مخبئية؟reuse_distances
• working_set(lines, window)كم سطرًا يمسّه مقطع من القراءات؟نافذة منزلقة
• capacity_for(lines, target)إلى أي حد يمكن أن تصغر الذاكرة المخبئية؟reuse_distanceshit_rate_from_distances
• rolling_mean_trace(n, window, elem_bytes)ما العناوين التي يقرؤها متوسط متحرك بطيء؟حساب بسيط
• study(bars)ما مدى محلية متوسط متحرك على إغلاقات SPY؟rolling_mean_tracecapacity_for

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