تحسين البحث على نطاق واسع: كيفية معالجة رسم بياني يضم 10 مليارات حالة

منذ شهرين ، أخيرًا ، كان عليّ أن أعترف أنني لم أكن أذكياءً بما فيه الكفاية لتصفح بعض مستويات لغز Snakebird . كانت الطريقة الوحيدة لاستعادة بعض الثقة بالنفس هي كتابة محلل. لذلك يمكنني أن أدعي أن إنشاء برنامج لحل اللغز هو نفسه تقريبا مثل حلها بنفسي. يتوفر رمز برنامج C ++ الناتج على Github . يتم تطبيق الجزء الرئيسي من التعليمات البرمجية الواردة في المقالة في search.h و compress.h . في هذا المنشور ، سأتحدث بشكل أساسي عن تحسين عملية البحث الأولى التي تتطلب 50-100 جيجابايت من الذاكرة لتناسب 4 غيغابايت.

في وقت لاحق سأكتب منشورًا آخر ، والذي سيصف تفاصيل اللعبة. في هذا المنشور ، عليك أن تعرف أنني لم أجد أي بدائل جيدة للقوة الغاشمة ، لأنه لم تنجح أي من الحيل المعتادة. تحتوي اللعبة على العديد من الحالات ، لأن هناك الكثير من الكائنات المتحركة أو المدفوعة ، وشكل بعضها مهم ، والذي يمكن أن يتغير بمرور الوقت. لم يكن هناك إرشادي محافظ مناسب لخوارزميات مثل A * لتضييق مساحة البحث. كان الرسم البياني للبحث موجَّهًا ومحددًا ضمنيًا ؛ لذلك ، كان من المستحيل البحث في وقت واحد في الاتجاهين الأمامي والخلفي. الخطوة الوحيدة يمكن أن تغير الحالة بعدة طرق لا علاقة لها ، لذلك لا شيء يمكن أن يكون مفيدًا مثل التجزئة Zobrist .

أظهرت التقديرات التقريبية أنه في أكبر لغز ، بعد القضاء على جميع المواقف المتماثلة ، سيكون هناك حوالي 10 مليارات ولاية. حتى بعد تعبئة أوصاف الحالة بأقصى كثافة ، كان حجم الحالة 8-10 بايت. مع 100 غيغابايت من الذاكرة ، ستكون المهمة تافهة ، ولكن ليس لجهازي المنزلي مع 16 غيغابايت من الذاكرة. ونظرًا لأن Chrome يحتاج إلى 12 غيغابايت منها ، فإن مخزون الذاكرة الحقيقي الخاص بي أقرب إلى 4 غيغابايت. يجب حفظ كل شيء سيتجاوز هذا المستوى على القرص (القرص الصلب القديم والصدئ).

كيف تتناسب مع 100 غيغابايت من البيانات في 4 غيغابايت من ذاكرة الوصول العشوائي؟ إما أ) يجب ضغط الدول 1/20 من حجمها الأصلي أو الأمثل بالفعل ، أو ب) يجب أن تكون الخوارزمية قادرة على حفظ الحالات بشكل فعال من وإلى القرص ، أو ج) مجموعة من الطريقتين السابقتين ، أو د) أحتاج إلى شراء المزيد ذاكرة الوصول العشوائي أو استئجار آلة افتراضية قوية لعدة أيام. لم أفكر في الخيار D ، لأنه ممل جدًا. تم استبعاد الخيارين A و B بعد إثبات المفهوم باستخدام gzip: تم ضغط جزء من وصف الحالة يبلغ 50 ميجابايت إلى 35 ميجابايت فقط. هذا هو حوالي 7 بايت لكل ولاية ، وذاكرة بلدي حوالي 0.4 بايت لكل ولاية. وهذا هو ، بقي الخيار B ، على الرغم من أن البحث الأول اتسع بشكل غير مناسب للتخزين على محركات الأقراص الثانوية.

محتوى

هذا منشور طويل إلى حد ما ، لذلك إليك نظرة عامة مختصرة على الأقسام التالية:

• بحث اتساع - أول عرض اتساع - ما هي صيغة البحث المتسعة (BFS) المعتادة ، ولماذا لا يناسب تخزين أجزاء من حالة على قرص؟
• BFS مع الفرز والاندماج - تغيير في الخوارزمية للتخلص الفعال للدفعة من البيانات المكررة.
• ضغط - تقليل مقدار الذاكرة المستخدمة من قبل مئات المرات بسبب مزيج من الضغط القياسي والوطني.
• أوه ، أوه ، لقد خدعت! - في الأقسام الأولى ، التزمت الصمت حيال شيء ما: لا يكفي أن نعرف فقط مكان الحل ، لكن علينا أن نفهم بالضبط كيفية تحقيقه. في هذا القسم ، نقوم بتحديث الخوارزمية الأساسية بحيث تنقل بيانات كافية لإعادة إنشاء الحل من الحالة الأخيرة.
• فرز + دمج مع إخراج متعددة - تخزين المزيد من الحالات ينفي تماما فوائد الضغط. يجب تغيير خوارزمية الفرز + الدمج بحيث تخزن مجموعتين من بيانات الإخراج: واحدة ، مضغوطة جيدًا ، يتم استخدامها أثناء البحث ، والآخر يستخدم فقط لإعادة إنشاء الحل بعد العثور على الأول.
• تبادل - تبادل على لينكس هو أسوأ بكثير مما كنت اعتقد.
• ضغط الحالات الجديدة قبل الدمج - حتى الآن ، عملت تحسينات الذاكرة فقط مع الكثير من الحالات التي تمت زيارتها. لكن اتضح أن قائمة الحالات الجديدة التي تم إنشاؤها أكبر بكثير مما تعتقد. يعرض هذا القسم مخططًا لوصف أكثر كفاءة للحالات الجديدة.
• توفير مساحة على الحالات الرئيسية - استكشف المفاضلات بين استخدام وحدة المعالجة المركزية / الذاكرة لإعادة إنشاء الحل في النهاية.
• ما لم ينجح أو لا ينجح - بدت بعض الأفكار واعدة ، لكن كنتيجة لذلك توجب التراجع عنها ، بينما بدا لي البعض الآخر ، الذي كان من المفترض أن يكونوا عاملين في مجال البحوث ، غير مناسب في هذه الحالة.

البحث على نطاق واسع "عن طريق الكتب المدرسية"

كيف يبدو البحث المتسع أولاً ولماذا لا يجب استخدام قرص فيه؟ قبل هذا المشروع الصغير ، نظرت فقط في خيارات صياغة "من الكتب المدرسية" ، على سبيل المثال ، مثل:

def bfs(graph, start, end): visited = {start} todo = [start] while todo: node = todo.pop_first() if node == end: return True for kid in adjacent(node): if kid not in visited: visited.add(kid) todo.push_back(kid) return False 

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

لماذا يستخدم جدول التجزئة مشكلة؟ لأن جداول التجزئة تميل إلى إنشاء نمط وصول ذاكرة عشوائي تمامًا. إذا لم يفعلوا ، فهذه وظيفة تجزئة سيئة ، ومن المرجح أن يكون لجدول التجزئة أداء ضعيف بسبب التصادمات. يمكن أن يتسبب نمط الوصول العشوائي هذا في حدوث مشكلات في الأداء ، حتى لو كانت البيانات مناسبة في الذاكرة: من المحتمل أن يؤدي الوصول إلى جدول تجزئة كبير إلى حدوث أخطاء في ذاكرة التخزين المؤقت ومخازن ترجمة مؤقتة (TLBs). ولكن ماذا لو كان جزء كبير من البيانات موجودًا على القرص وليس في الذاكرة؟ ستكون النتائج كارثية: شيء من 10 مللي ثانية لكل عملية بحث.

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

BFS مع الفرز والاندماج

إذا أردنا دمج عمليات الوصول إلى البيانات في الحزم قدر الإمكان ، فما هو الحد الأقصى التقريبي الممكن تحقيقه؟ نظرًا لأن البرنامج لا يعرف العقد التي سيتم معالجتها في طبقة من العمق N + 1 حتى تتم معالجة الطبقة N تمامًا ، يبدو من الواضح أنه من الضروري إلغاء تكرار الحالات مرة واحدة على الأقل لكل عمق.

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

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

 def bfs(graph, start, end): visited = Stream() todo = Stream() visited.add(start) todo.add(start) while True: new = [] for node in todo: if node == end: return True for kid in adjacent(node): new.push_back(kid) new_stream = Stream() for node in new.sorted().uniq(): new_stream.add(node) todo, visited = merge_sorted_streams(new_stream, visited) return False # Merges sorted streams new and visited. Return a sorted stream of # elements that were just present in new, and another sorted # stream containing the elements that were present in either or # both of new and visited. def merge_sorted_streams(new, visited): out_todo, out_visited = Stream(), Stream() while visited or new: if visited and new: if visited.peek() == new.peek(): out_visited.add(visited.pop()) new.pop() elif visited.peek() < new.peek(): out_visited.add(visited.pop()) elif visited.peek() > new.peek(): out_todo.add(new.peek()) out_visited.add(new.pop()) elif visited: out_visited.add(visited.pop()) elif new: out_todo.add(new.peek()) out_visited.add(new.pop()) return out_todo, out_visited 

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

كيف سيبدو الأداء النظري من خلال توزيع مبسط للبيانات على 100 مستوى عمق ، ولكل منها 100 مليون حالة؟ سيتم قراءة الحالة المتوسطة وكتابة 50 مرة. هذا يعطي 10 بايت / حالة * 5 مليارات حالة * 50 = 2.5 تيرابايت. من المفترض أن محرك الأقراص الثابتة يمكنه القراءة والكتابة بسرعة متوسطة تبلغ 100 ميجابايت / ثانية ، أي أن معدل الإدخال / الإخراج سيستغرق في المتوسط ​​(2 * 2.5 تيرابايت) / (100 ميجابايت / ثانية) = ~ 50 كيلو / ثانية = ~ 13 ساعة . هذا أمران أقل من النتيجة السابقة (أربعة أشهر)!

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

ضغط

في المقدمة ، قلت إنه في التجارب الأولية ، لا يبدو ضغط الحالة واعداً ، وكانت نسبة الضغط 30٪ فقط. ولكن بعد إجراء تغييرات على الخوارزمية ، أصبحت الولايات مبسطة. يجب أن تكون أسهل بكثير للضغط.

لاختبار هذه النظرية ، استخدمت zstd مع لغز بلغ 14.6 مليون حالة ، كان حجم كل ولاية 8 بايت. بعد الفرز ، تم ضغطها في المتوسط ​​إلى 1.4 بايت لكل ولاية. يبدو وكأنه خطوة خطيرة إلى الأمام. لا يكفي تشغيل البرنامج بالكامل في الذاكرة ، ولكنه يمكن أن يقلل من وقت إدخال / إخراج القرص لبضع ساعات فقط.

هل من الممكن تحسين نتيجة خوارزمية الضغط للأغراض العامة الحديثة بطريقة ما إذا كنا نعرف شيئًا عن بنية البيانات؟ يمكنك أن تكون متأكدا تقريبا من ذلك. مثال جيد على ذلك هو تنسيق PNG. من الناحية النظرية ، يعد الضغط مجرد تمرير قياسي لفراغ. ولكن بدلاً من ضغط البيانات الأولية ، يتم تحويل الصورة أولاً باستخدام عوامل تصفية PNG . يعد عامل تصفية PNG أساسًا صيغة للتنبؤ بقيمة بايت من البيانات الأولية استنادًا إلى قيمة نفس البايت في السطر السابق و / أو نفس البايت في البيكسل السابق. على سبيل المثال ، يحول المرشح "up" كل بايت عن طريق طرح قيم السطر السابق منه عند الضغط ، وتنفيذ العملية المعاكسة عند التفريغ. بالنظر إلى أنواع الصور التي يتم استخدام PNG لها ، ستتكون النتيجة دائمًا تقريبًا من أصفار أو أرقام قريبة من الصفر. يمكن لفراغ ضغط هذه البيانات أفضل بكثير من البيانات الخام.

هل يمكن تطبيق هذا المبدأ على سجلات حالة BFS؟ يبدو أن هذا ينبغي أن يكون ممكنا. كما هو الحال مع PNG ، لدينا حجم خط ثابت ، ويمكننا أن نتوقع أن تكون الخطوط المجاورة متشابهة جدًا. أدت العينات الأولى مع مرشح الطرح / الإضافة ، متبوعًا بـ zstd ، إلى تحسن في نسبة الضغط بنسبة 40٪ أخرى: 0.87 بايت لكل ولاية. عمليات التصفية تافهة ، لذلك ، من وجهة نظر استهلاك وحدة المعالجة المركزية ، فهي "مجانية" من الناحية العملية.

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

افترض أن لدينا صفوف متجاورة R1 = [1 ، 2 ، 3 ، 4] و R2 = [1 ، 2 ، 6 ، 4]. عند إخراج R2 ، نقوم بمقارنة كل بايت بنفس بايتة السطر السابق ، وسيشير 0 إلى تطابق ، وسيشير 1 إلى عدم تطابق: diff = [0 ، 0 ، 1 ، 0]. ثم نقوم بتمرير هذه الصورة النقطية ، المشفرة باسم VarInt ، متبوعة فقط بالبايتات التي لا تتطابق مع السطر السابق. في هذا المثال ، نحصل على وحدتي بايت 0b00000100 6. في حد ذاته ، يقوم عامل التصفية هذا بضغط البيانات المرجعية إلى 2.2 بايت / الحالة. ولكن من خلال دمج عامل تصفية + zstd ، قمنا بتقليل حجم البيانات إلى 0.42 بايت / الحالة. أو بعبارة أخرى ، يصل هذا إلى 3.36 بت لكل ولاية ، وهو ما يزيد قليلاً عن مؤشراتنا المحسوبة التقريبية اللازمة لضمان أن جميع البيانات تتوافق مع ذاكرة الوصول العشوائي.

في الممارسة العملية ، تتحسن نسب الضغط لأن المجموعات المصنفة تصبح أكثر كثافة. عندما يصل البحث إلى النقطة التي تبدأ فيها الذاكرة في التسبب في مشاكل ، يمكن أن تصبح معدلات الضغط أفضل بكثير. المشكلة الأكبر هي أنه في النهاية نحصل على 4.6 مليار زيارة. بعد الفرز ، تشغل هذه الحالات 405 ميغابايت ويتم ضغطها وفقًا للمخطط الموضح أعلاه. هذا يعطينا 0.7 بت لكل ولاية . في النهاية ، يستغرق الضغط وإلغاء الضغط حوالي 25٪ من وقت وحدة المعالجة المركزية للبرنامج ، ولكن هذا حل وسط ممتاز لتقليل استهلاك الذاكرة بمقدار مائة مرة.

يبدو المرشح أعلاه مكلفًا بعض الشيء بسبب رأس VarInt على كل سطر. يبدو أنه من السهل الترقية على حساب تكاليف وحدة المعالجة المركزية المنخفضة أو زيادة طفيفة في التعقيد. جربت العديد من الخيارات المختلفة ، أو نقل البيانات بالترتيب حسب الأعمدة ، أو كتابة أقنعة بت في كتل أكبر ، إلخ. أسفرت هذه الخيارات وحدها عن نسب ضغط أعلى بكثير ، لكنها لم تنجح أيضًا عندما تم ضغط إخراج الفلتر بواسطة zstd. ولم يكن نوعًا من الخطأ zstd ، فقد تبين أن النتائج مع gzip و bzip2 كانت متشابهة. ليس لدي أي نظريات بارعة بشكل خاص حول سبب تحول هذا النوع من الترميز إلى ضغط أفضل بكثير من الخيارات الأخرى.

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

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

أوه ، أوه ، لقد خدعت!

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

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

 def bfs(graph, start, end): visited = {start: None} todo = [start] while todo: node = todo.pop_first() if node == end: return trace_solution(node, visited) for kid in adjacent(node): if kid not in visited: visited[kid] = node todo.push_back(kid) return None def trace_solution(state, visited): if state is None: return [] return trace_solution(start, visited[state]) + [state] 

لسوء الحظ ، سيؤدي هذا إلى تدمير جميع فوائد الضغط المكتسبة في القسم السابق ؛ أنها تستند إلى افتراض أن الخطوط المجاورة متشابهة جدًا. عندما ننظر إلى الدول نفسها ، هذا صحيح. لكن لا يوجد سبب للاعتقاد بأن هذا سيكون صحيحًا بالنسبة لحالات الوالدين ؛ في الواقع ، فهي بيانات عشوائية. ثانياً ، يجب على حل الفرز + الدمج قراءة وكتابة جميع الحالات التي يتم عرضها في كل تكرار. لحفظ ارتباط الحالة / الحالة الرئيسية ، يتعين علينا قراءة القرص والكتابة عليه في كل تكرار لكل هذه البيانات المضغوطة بشكل سيء.

فرز + دمج مع الإخراج متعددة

في النهاية ، عند العودة إلى الحل ، سيحتاج البرنامج فقط إلى حزم من الحالات / الحالات الرئيسية ، وبالتالي ، يمكننا تخزين بنيتين للبيانات على التوازي. ستستمر الزيارة لتكون مجموعة الدول التي تمت زيارتها ، كما تمت إعادة حسابه مسبقًا أثناء الدمج. الآباء هم على الأقل قائمة مرتبة من أزواج الدولة / الأصل التي لم يتم الكتابة فوقها. بعد كل عملية دمج ، تتم إضافة الزوج "الحالة + الحالة الأصل" إلى الآباء.

 def bfs(graph, start, end): parents = Stream() visited = Stream() todo = Stream() parents.add((start, None)) visited.add(start) todo.add(start) while True: new = [] for node in todo: if node == end: return trace_solution(node, parents) for kid in adjacent(node): new.push_back(kid) new_stream = Stream() for node in new.sorted().uniq(): new_stream.add(node) todo, visited = merge_sorted_streams(new_stream, visited, parents) return None # Merges sorted streams new and visited. New contains pairs of # key + value (just the keys are compared), visited contains just # keys. # # Returns a sorted stream of keys that were just present in new, # another sorted stream containing the keys that were present in either or # both of new and visited. Also adds the keys + values to the parents # stream for keys that were only present in new. def merge_sorted_streams(new, visited, parents): out_todo, out_visited = Stream(), Stream() while visited or new: if visited and new: visited_head = visited.peek() new_head = new.peek()[0] if visited_head == new_head: out_visited.add(visited.pop()) new.pop() elif visited_head < new_head: out_visited.add(visited.pop()) elif visited_head > new_head: out_todo.add(new_head) out_visited.add(new_head) out_parents.add(new.pop()) elif visited: out_visited.add(visited.pop()) elif new: out_todo.add(new.peek()[0]) out_visited.add(new.peek()[0]) out_parents.add(new.pop()) return out_todo, out_visited 

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

مبادلة

يتم تجاهل تفاصيل أخرى في الكود الزائف: لا يوجد كود صريح للقرص I / O ، ولكن فقط واجهة Stream. يمكن أن يكون التدفق دفقًا للملفات أو صفيفًا داخل الذاكرة ، لكننا تجاهلنا تفاصيل التنفيذ هذه. بدلاً من ذلك ، يقوم الرمز الزائف بإنشاء نمط وصول للذاكرة يتيح الاستخدام الأمثل للقرص. في عالم مثالي ، سيكون هذا كافيًا ، ويمكن تناول الباقي بواسطة نظام الذاكرة الظاهرية لنظام التشغيل الظاهري.

ولكن هذا لا يحدث ، على الأقل على لينكس. في مرحلة ما (قبل أن يتم ضغط مجموعة البيانات العاملة على أحجام الذاكرة) ، حصلت على البرنامج لتشغيله في حوالي 11 ساعة ، وتم حفظ البيانات بشكل رئيسي على القرص. بعد ذلك ، جعلت البرنامج يستخدم صفحات مجهولة بدلاً من تخزينها في الملفات ، وحدد ملف تبديل بحجم كافٍ على نفس محرك الأقراص. ومع ذلك ، بعد ثلاثة أيام ، ذهب البرنامج فقط ربع الطريق ، ومع ذلك ، مع مرور الوقت ، أصبح أبطأ. وفقًا لتقديراتي المتفائلة ، كان من المفترض أن تنهي المهمة في غضون 20 يومًا.

سأوضح - كان نفس الرمز ونمط الوصول نفسه تمامًا . الشيء الوحيد الذي تغير هو أن الذاكرة لم يتم حفظها كملف قرص صريح ، ولكن كمقايضة. لا توجد حاجة إلى أي دليل تقريبًا على أن المبادلة تدمر أداء Linux تمامًا ، في حين أن الملف العادي I / O لا يقوم بذلك. لقد افترضت دائمًا أن هذا يرجع إلى حقيقة أن البرامج تميل إلى اعتبار ذاكرة الوصول العشوائي ذاكرة وصول عشوائي. ولكن هذا ليس هو الحال.

اتضح أن صفحات حفظ الملفات والصفحات مجهولة الهوية يتم التعامل معها بشكل مختلف عن طريق النظام الفرعي للجهاز الظاهري. يتم تخزينها في ذاكرة التخزين المؤقت LRU منفصلة مع سياسات انتهاء الصلاحية مختلفة. بالإضافة إلى ذلك ، يبدو أن لديهم خصائص قراءة / قراءة مختلفة.

الآن أعلم: لن يعمل التبادل على Linux على الأرجح بشكل جيد حتى في ظل الظروف المثالية. إذا كان من المحتمل إلغاء تحميل أجزاء من مساحة العنوان لبعض الوقت على القرص ، فمن الأفضل حفظها يدويًا في الملفات بدلاً من الوثوق في المبادلة. لقد أنجزت ذلك من خلال تطبيق فئة الناقلات الخاصة بي ، والتي لا تعمل في البداية إلا في الذاكرة ، وبعد تجاوز حد معين للحجم ، يتم التبديل إلى ملف mmap في ملف منفصل مؤقت.

ضغط الحالات الجديدة قبل الدمج

في نموذج أداء مبسط ، افترضنا أن 100 مليون حالة جديدة ستحدث في كل عمق. اتضح أن هذا ليس بعيدًا عن الواقع (في اللغز الأكثر تعقيدًا ، بحد أقصى أكثر من 150 مليون حالة جديدة فريدة على طبقة واحدة من العمق). لكن هذا لا يجب قياسه. مجموعة العمل قبل الدمج مرتبطة ليس فقط بالحالات الفريدة ، ولكن أيضًا بجميع الحالات المستخلصة من هذا التكرار. يصل هذا الرقم إلى 880 مليون حالة إنتاج لكل طبقة عمق. يجب معالجة هذه الحالات البالغ عددها 880 مليون حالة بنمط وصول عشوائي للفرز ، ب) لا يمكن ضغطها بشكل فعال بسبب عدم وجود فرز ، ج) يجب تخزينها مع الحالة الأصلية. تبلغ مجموعة العمل هذه حوالي 16 جيجابايت.

الحل الواضح: استخدام نوع من الفرز الخارجي. ما عليك سوى كتابة جميع الحالات على القرص ، وإجراء الفرز الخارجي ، وإلغاء البيانات المكررة ، ثم دمج كالمعتاد. في البداية استخدمت هذا الحل ، وعلى الرغم من أنه تم التخلص من المشكلة A على الأكثر ، إلا أنني لم أتمكن من التعامل مع B و C.

في النهاية ، اتبعت مقاربة بديلة: جمعت الحالات في صفيف في الذاكرة. إذا أصبحت المصفوفة كبيرة جدًا (على سبيل المثال ، أكثر من 100 مليون عنصر) ، فسيتم فرزها وتكرارها وضغطها. هذا يعطينا مجموعة من عمليات فرز الحالة ، ولا توجد تكرارات داخل كل شوط ، لكنها ممكنة بين أشواط. في الأساس ، يظل رمز دمج الحالات الجديدة والزيارات كما هو ؛ لا يزال يعتمد على مرور تدريجي عبر الجداول. الاختلاف الوحيد هو أنه بدلاً من مجرد المرور عبر دفقين ، هناك دفق منفصل لكلٍ من عمليات فرز الحالات الجديدة.

بطبيعة الحال ، فإن معدلات ضغط هذه 100 مليون حالة ليست جيدة مثل ضغط مجموعة جميع الحالات التي تمت زيارتها. ولكن حتى مع وجود مثل هذه المؤشرات ، فإنه يقلل بشكل كبير من حجم مجموعة العمل ومتطلبات القرص I / O. تحتاج إلى مزيد من موارد وحدة المعالجة المركزية لمعالجة قائمة انتظار سلاسل الرسائل ذات الأولوية ، لكنها لا تزال حل وسط كبير.

توفير مساحة على الولايات الأم

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

نحتاج إلى توصيل الحالة S 'في العمق D + 1 بالحالة الأصلية S الخاصة بها في العمق D. إذا كان بإمكاننا التكرار على جميع الحالات الوالدية المحتملة S' ، فيمكننا التحقق مما إذا كان أي منها يظهر على العمق D في المجموعة التي تمت زيارتها . (لقد أنشأنا بالفعل الكثير من الزيارات ، والتي تم تجميعها حسب العمق كمنتج ثانوي مناسب لاشتقاق حزم حالة الدولة / الوالدين أثناء الدمج). لسوء الحظ ، لن يعمل هذا النهج لهذه المهمة ؛ من الصعب للغاية بالنسبة لنا إنشاء جميع الحالات الممكنة لـ S لمجموعة معينة. ومع ذلك ، بالنسبة إلى العديد من مهام البحث الأخرى ، قد يعمل هذا الحل.

إذا استطعنا فقط توليد انتقالات بين الدول إلى الأمام ، ولكن ليس إلى الخلف ، فلماذا لا نفعل هذا فقط؟ دعنا نذهب بشكل متكرر إلى جميع الولايات في العمق D ونرى نوع حالات الإنتاج التي يحصلون عليها. إذا كانت حالة ما في الإخراج تعطي S '، فوجدنا S. مناسب. المشكلة في هذه الخطة هي أنها تزيد من إجمالي استهلاك وحدة المعالجة المركزية للبرنامج بنسبة 50 ٪. (ليس بنسبة 100 ٪ ، لأنه في المتوسط ​​سنجد S من خلال النظر إلى نصف الحالات على عمق D).

لذلك ، لا أحب واحدة من الحالات المقيدة ، ولكن هنا ، على الأقل ، حل وسط بين وحدة المعالجة المركزية / الذاكرة ممكن. هل هناك حل أكثر قبولا في مكان ما بين؟ في النهاية ، قررت عدم تخزين الزوج (S '، S) ، ولكن الزوج (S' ، H (S)) ، حيث H عبارة عن دالة تجزئة 8 بت. للعثور على S لـ S معين ، نمر مرة أخرى بشكل متكرر بجميع الولايات في العمق D. ولكن قبل القيام بأي شيء آخر ، نحسب نفس التجزئة. إذا كان الناتج لا يتطابق مع H (S) ، فهذه ليست الحالة التي نبحث عنها ، ويمكننا ببساطة تخطيها. يعني هذا التحسين أنه يلزم إجراء عمليات إعادة حساب مكلفة لحالات 1/256 فقط ، مما يمثل زيادة طفيفة في تحميل وحدة المعالجة المركزية ، وفي الوقت نفسه يقلل من مقدار الذاكرة لتخزين الحالات الأصل من 8-10 بايت إلى 1 بايت.

ما لم ينجح أو لا يعمل

في الأقسام السابقة ، نظرنا في تسلسل التحسينات عالية المستوى التي نجحت. جربت أشياء أخرى لم تنجح ، أو وجدت في الأدب ، لكنني قررت في هذه الحالة بالذات أنها لن تعمل. هنا قائمة جزئية.

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

لقد تم إجراء القليل من الأبحاث بالفعل حول إجراء عملية بحث أولية من حيث الحجم عن الرسوم البيانية المحددة ضمنيًا في وحدة التخزين الثانوية ، يمكنك البدء في استكشاف هذا الموضوعمن هذه المادة 2008 . كما قد تعتقد ، فإن فكرة إجراء إلغاء البيانات المكررة مع الفرز + الدمج في وحدة التخزين الثانوية ليست جديدة. ما يثير الدهشة هو أنه افتتح فقط في عام 1993. متأخر جدا! هناك بعض الاقتراحات اللاحقة للبحث المتسع في وحدة التخزين الثانوية التي لا تتطلب خطوة الفرز.

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

ويستند بديل خطير آخر على جداول التجزئة المؤقتة. يتم تخزين الحالات التي تمت زيارتها دون فرز في ملف. نقوم بحفظ الناتج الناتج من العمق D إلى جدول التجزئة. ثم انتقل بشكل متكرر إلى الولايات التي تمت زيارتها وابحث عنها في جدول التجزئة. إذا تم العثور على العنصر في جدول التجزئة ، فاحذفه. بعد اجتياز الملف بأكمله بشكل تكراري ، سيبقى فيه فقط العناصر غير المكررة. ثم يتم إضافتهم إلى الملف واستخدامهم لتهيئة قائمة المهام للتكرار التالي. إذا كانت كمية المخرجات كبيرة لدرجة أن جدول التجزئة لا يتلاءم مع الذاكرة ، فيمكن تقسيم كل من جدولي الملفات والملفات إلى أجزاء باستخدام نفس المعايير (على سبيل المثال ، البتات العليا للحالة) وكل جزء معالج بشكل منفصل.

على الرغم من وجود معاييرإظهار أن النهج القائم على التجزئة هو حوالي 30 ٪ أسرع من الفرز + الدمج ، ولكن يبدو أنهم لا يأخذون في الاعتبار الضغط. لم أكن أرى كيف يمكن لرفض فوائد الضغط أن يبرر نفسه ، لذلك لم أجرب مثل هذه الأساليب.

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

استنتاج

بهذا أختتم حسابي لما تعلمته من مشروع قابل للتطبيق بشكل عام على مهام البحث الأخرى بالقوة الغاشمة. يسمح الجمع بين هذه الحيل بتقليل حجم حلول أكثر الألغاز تعقيدًا من اللعبة من 50-100 غيغابايت إلى 500 ميجابايت وزيادة التكاليف بسلاسة إذا تجاوزت المهمة الذاكرة المتوفرة وتمت كتابتها إلى القرص. بالإضافة إلى ذلك ، حل بلدي أسرع بنسبة 50٪ من إلغاء البيانات المكررة الساذجة للحالات استنادًا إلى جداول التجزئة ، حتى بالنسبة للألغاز التي تناسب الذاكرة.

Snakebird اللعبة يمكن شراؤها من البخار ، وجوجل اللعب و المتجر . أوصي به لأي شخص مهتم بالألغاز المعقدة للغاية ولكن الصادقة.