مصفوفة هياكل مقابل هيكل مصفوفات

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

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

يُستنتج عنوان القيمة من صفها وعمودها. في AoS رقم القيمة هو الصف × عدد الأعمدة + العمود. وفي SoA هو العمود × عدد الصفوف + الصف. اضرب في 8 بايت للنوع float64. يطبع الكود أدناه عناوين إغلاقات الأيام الأربعة الأولى في جدول من 100 يوم و5 أعمدة.

def address(layout, row, col, n_rows, n_cols, elem_bytes=8):    if layout == "aos":        return (row * n_cols + col) * elem_bytes1    return (col * n_rows + row) * elem_bytesclose = 3print("aos:", [address("aos", row, close, 100, 5) for row in range(4)])print("soa:", [address("soa", row, close, 100, 5) for row in range(4)])

aos: [24, 64, 104, 144]
soa: [2400, 2408, 2416, 2424]

1. 1في AoS يبعد الصف التالي n_cols قيمة فيتباعد إغلاقان متتاليان 5 قيم (40 بايت).

في AoS تتباعد إغلاقات الأيام المتتالية 40 بايت. وفي SoA تتباعد 8 بايت أي واحد بعد الآخر مباشرة وهذه هي بالضبط القراءة بالترتيب في أول موضوع من هذه المهارة.

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

def scan_column(layout, col, n_rows, n_cols):    return [address(layout, row, col, n_rows, n_cols) for row in range(n_rows)]for layout in ("aos", "soa"):    misses = count_misses(scan_column(layout, 3, 1000, 5))    print(layout, "misses:", misses, "- useful share:", round(1000 * 8 / (misses * 64), 3))

aos misses: 625 - useful share: 0.2
soa misses: 125 - useful share: 1.0

يخفق مسح SoA 125 مرة لكل 1000 قيمة أي إخفاق واحد لكل ثماني قيم ولا شيء مهدور. ويخفق مسح AoS 625 مرة أي خمسة أضعاف و20% فقط من البايتات المحمّلة إغلاقات. أما الـ80% الباقية فهي افتتاحات وأعلى وأدنى وأحجام لا ينظر إليها المتوسط أبدًا وتطرد أسطرًا مفيدة من الذاكرة المخبئية.

تطرح برامج تيكات كثيرة سؤالًا مختلفًا: لهذا التيك أعطني السعر والحجم والجانب معًا. وهذا يقرأ كل قيم الصف. في AoS الصف كله كتلة من 40 بايت تقع في سطر أو سطرين. وفي SoA القيم الخمس في خمس مصفوفات مختلفة فيفتح كل صف خمسة أسطر. يقرأ الكود صفًّا من كل سبعة ويعدّ الإخفاقات.

def scan_rows(layout, rows, n_rows, n_cols):    return [address(layout, row, col, n_rows, n_cols) for row in rows for col in range(n_cols)]rows = list(range(0, 1000, 7))for layout in ("aos", "soa"):    print(layout, "misses:", count_misses(scan_rows(layout, rows, 1000, 5)))

aos misses: 214
soa misses: 625

الآن يفوز AoS بعامل ثلاثة: 214 إخفاقًا مقابل 625. التخطيط الذي كان أسوأ بخمسة أضعاف لمسح العمود صار أفضل بثلاثة أضعاف لقراءة الصفوف. لا يوجد تخطيط هو الأفضل: لكل منهما طريقة قراءة هو الأفضل لها.

يقوم برنامج حقيقي بنوعي القراءة معًا، فيعتمد الاختيار على المزيج. لكل تخطيط اجمع إخفاقات حمل العمل: مسوح الأعمدة × إخفاقات العمود + قراءات الصفوف × إخفاقات الصفوف. يفوز التخطيط ذو المجموع الأصغر ويذهب التعادل إلى AoS. يجرّب الكود أدناه أربعة مزائج على الجدول نفسه.

def compare(n_rows, n_cols, col, rows):    out = {}    for layout in ("aos", "soa"):        out[layout] = {            "column": count_misses(scan_column(layout, col, n_rows, n_cols)),            "rows": count_misses(scan_rows(layout, rows, n_rows, n_cols)),        }    return outdef best_layout(n_column_scans, n_row_reads, n_rows, n_cols, col, rows):    counts = compare(n_rows, n_cols, col, rows)    totals = {layout: n_column_scans * counts[layout]["column"] + n_row_reads * counts[layout]["rows"] for layout in counts}    return "soa" if totals["soa"] < totals["aos"] else "aos"rows = list(range(0, 1000, 7))for scans, reads in ((1, 4), (1, 2), (1, 1), (4, 1)):    print(scans, "column scans per", reads, "row reads:", best_layout(scans, reads, 1000, 5, 3, rows))

1 column scans per 4 row reads: aos
1 column scans per 2 row reads: aos
1 column scans per 1 row reads: soa
4 column scans per 1 row reads: soa

يتبع المختبر الدرس: التخطيطان ونوعا القراءة والمقارنة واختيار التخطيط لحمل عمل والحصة المفيدة والدراسة على جدول SPY الحقيقي.

• الدالة · السؤالتعتمد على
• address(layout, row, col, n_rows, n_cols)أين توجد هذه القيمة؟حساب بسيط
• scan_column(layout, col, n_rows, n_cols)ما العناوين التي يقرؤها مسح عمود؟address
• scan_rows(layout, rows, n_rows, n_cols)ما العناوين التي تمسّها قراءة صفوف؟address
• compare(n_rows, n_cols, col, rows)كم إخفاقًا تكلّف كل قراءة في كل تخطيط؟scan_columnscan_rows
• best_layout(...)أي تخطيط يناسب هذا الحمل؟compare
• useful_fraction(layout, col, n_rows, n_cols)كم مما يُحمَّل يُستعمل؟scan_column
• study(bars)أي تخطيط يناسب جدول SPY؟comparebest_layout

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